CODEWITHSUNDEEP
algorithmgraphdepth-first-searchbreadth-first-search
Citut
Citut

Reputation: 907

How to find all nodes distance k away from each other in directed graph (exploring every edge in a graph)?

0

I am working on a problem where I need to find all nodes at distance k from each other. So if k=3, then I need to find all nodes where they are connected by a path of distance 3. There are no self edges so if i has an edge pointing to s, s can't point back to i directly. I think I thought of two implementations here, both involving BFS. I noticed an edge case where BFS might not visit all edges because nodes might already be visited.

Do BFS at each node. Keep track of the "level" of each node in some array, where distance[0] is the root node, distance1 is all nodes adjacent to the root node, distance[2] are all nodes that are grandchildren of the root node and so on. Then to find all nodes at distance k we look at distance[i] and distance[i+k].

Do BFS once, using the same distance algorithm as above, but don't do BFS at each node. Reverse all of the edges and do BFS again to find any missed paths. This would have a much better time complexity than approach 1, but I am not sure if it would actually explore every edge and path (in my test cases it seemed to).

Is there a better approach to this? As an example in this graph with k = 2:

enter image description here

The paths would be 1 to 3, 1 to 5, 2 to 6, 2 to 5, 4 to 3, 1 to 4.

EDIT: The reversal of edges won't work, my current best bet is just do a BFS and then a DFS at each node until a depth of k is reached.

Upvotes: 0

Views: 1665

Answers (1)

grodzi
grodzi

Reputation: 5703

You may consider a basic adjacentry matrix M in which elements are not a 0 or 1 in order to indicate a connection but instead they hold the available paths of size k.

e.g for 2->5 you would store M(2,5) = {1,2} (because there exists a path of length 1 and of length 2 between node 2 and 5)

let a and b two elems of M

a * b is defined as:

ab_res = {} //a set without duplicates
for all size i in a
    for all size j in b
        s = i+j
        append(s) to ab_res
ab_res;

a + b is defined as:

ab_res = {}
for all size i in a
    append(i) to ab_res
for all size j in a
    append(j) to ab_res

This approach allows not to recompute paths of inferior size. It would work with cycles as well.

Below an unoptimized version to illustrate algorithm.

const pathk = 2;
let G = {
    1:[2],
    2:[3,4,5],
    4:[6],
    6:[3]
}
//init M
let M = Array(6).fill(0).map(x=>Array(6).fill(0).map(y=>new Set));
Object.keys(G).forEach(m=>{
    G[m].forEach(to=>{
        M[m-1][to-1] = new Set([1]);
    })
});


function add(sums){
    let arr = sums.flatMap(s=>[...s]);
    return new Set(arr);
}
function times(a,b){
    let s = new Set;
    [...a].forEach(i=>{
        [...b].forEach(j=>{
            s.add(i+j);
        })
    });
    return s;
}
function prod(a,b, pathk){
    //the GOOD OL ugly matrix product :)
    const n = a.length;
    let M = Array(6).fill(0).map(x=>Array(6).fill(0).map(y=>new Set));
    a.forEach((row,i)=>{
        for(let bcol = 0; bcol<n; ++bcol){

            let sum = [];
            for(let k = 0; k<n; ++k){
                sum.push( times(a[i][k], b[k][bcol]) );
            }
            M[i][bcol] = add(sum);
            if(M[i][bcol].has(pathk)){
                console.log('got it ', i+1, bcol+1);
            }
        }
    })
    return M;
}

//note that
//1. you can do exponentiation to fasten stuff
//2. you can discard elems in the set if they equal k (or more...)
//3. you may consider operating the product on an adjency list to save computation time & memory..
let Mi = M.map(r=>r.map(x=>new Set([...x])));//copy
for(let i = 1; i<=pathk; ++i){
    Mi = prod(Mi,M, pathk);
}

Upvotes: 1

Related Questions