CODEWITHSUNDEEP
javascriptalgorithmgraph
deblocker
deblocker

Reputation: 7705

How to implement the search for all paths inside a directed graph in JavaScript?

I would like to find all distinct paths without cycles in following graph:

Directed Unweighted graph

From this graph, i composed the adjacency list, starting from node 0 and going to the right (in the picture above):

var rightAdjacent = [[1,7],[2],[3,9],[4],[5],[6,10],[8],[2],[5],[11],[12]];

As i am a noob in graphs, i started from a canonical algorithm for BFS, which seems to me the cheapest way to get what i need:

...    
var paths = []  
queue.push(0); // Starting node
parents[0] = null;

while (queue.length > 0) {
    u = queue.splice(0, 1)[0];
    for (i = 0, l= rightAdjacent.length; i < l; i++) { // Explore edge(u, v).
        v = rightAdjacent[u][i];
        if (rightAdjacent[v]) {
            if(rightAdjacent[v].status === 'unexplored') {
                rightAdjacent[v].status = 'exploring'; // Node u has been discovered
                queue.push(v);
                parents[v] = u;
            }
        } else {
            paths.push(collectPath(parents));
        }
    }
    rightAdjacent[u].status = 'explored'; 
}

... but in my first attempt i was able to collect only the list of the connected components, after which and until now, only garbage.

I have also composed the left-adjacency list, not knowing if this could be useful to speed up the search or to back-trace the discovered path. Any clue about this?

For the graph in the picture, i'm expecting following result (please correct me if i'am wrong):

[0,1,2,3,4,5,6],
[0,1,2,9,5,6],
[0,1,2,9,5,10,11,12],
[0,7,8,2,3,4,5,6],
[0,7,8,2,9,5,10,11,12]

where each single path has the nodes ordered from the starting node, through the first encountered, until the last.

Starting from an adjacency list, and without using recursion, wouldn't it be this the simplest way to collect all this paths, (the ordered parent nodes of all the parent paths) in my example, starting from node 0 and ending at nodes 6 and 12?

What is wrong in this piece of code?

Upvotes: 2

Views: 2253

Answers (1)

juvian
juvian

Reputation: 16068

Your rightAdjacent is missing the neighbours of node 6, which should be an empty array. An easy solution to implement is to do bfs but deep copy the visited and current path when you add a node to your path. When you have no neightbours, you can output/save the current path

		var rightAdjacent = [[1,7],[2],[3,9],[4],[5],[6,10],[],[8],[2],[5],[11],[12]];

    var queue = [{visited:{0:true},path:[0]}] // start with node 0

    function bfs(){
       while(queue.length){
           obj = queue.pop() // get last added path
           node = obj.path[obj.path.length-1] // get last visited node from that path
           visited = obj.visited
           if(node >= rightAdjacent.length || rightAdjacent[node].length == 0){ // we reached a leaf node
               console.log(obj.path)
           }else{
             for(var i=0;i<rightAdjacent[node].length;i++){ // we need to add the neighbours not visited
                 if(!visited[rightAdjacent[node][i]]){
                     visited[rightAdjacent[node][i]] = true
                     arr = obj.path.slice(0);
                    arr.push(rightAdjacent[node][i]); queue.push({visited:JSON.parse(JSON.stringify(visited)),path:arr}) // deep copy of both
                 }
             }
           }
       }	
    }

    bfs()

Upvotes: 2

Related Questions