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

Question

I would like to find all distinct paths without cycles in following 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?

All the paths pass through nodes 2 and 5, so you have 3 parts, each with 2 distinct options: [0,1,2] or [0,7,8,2]; [2,3,4,5] or [2,9,5]; and [5,6] or [5,10,11,12]. So that gives you 2x2x2 = 8 options: [0,1,2,3,4,5,6], [0,1,2,3,4,5,10,11,12], [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,3,4,5,10,11,12], [0,7,8,2,9,5,6], [0,7,8,2,9,5,10,11,12] — m69's been on strike for years, Aug 05 '16 at 04:49
@m69 Yeah, good catch. Could this pre-calculated at the moment i compose the adjacency list, i.e: something like mul(adjacencyList.len >1)? — deblocker, Aug 05 '16 at 12:52
I don't have much experience with graphs. I'd try to find some sort of standard graph traversal algorithm that's optimised for all kinds of special cases, rather than try to roll my own. — m69's been on strike for years, Aug 06 '16 at 00:11
I need to find which path has the largest number of nodes, could you please help? — , Sep 19 '18 at 08:28
@EngrUmair: please look at the snippet in the accepted answer: everytime you reach a leaf node, you will have the list of nodes inside `obj.path`. Get all the paths, and loop over them to get the one with the max `length` (array). — deblocker, Sep 19 '18 at 08:35
@deblocker In my case I don't have only right and left I have forward path as well — , Sep 19 '18 at 08:59
you may find my nodes in this image https://imgur.com/a/Fg1ETzz — , Sep 19 '18 at 09:05
@EngrUmair: I believe You may need to post a new question... — deblocker, Sep 19 '18 at 10:06
@deblocker can you please answer this question? https://stackoverflow.com/questions/52411607/better-way-to-create-paths-in-javascript-for-maximum-captures — , Sep 19 '18 at 18:04

score 2 · Accepted Answer · answered Aug 04 '16 at 18:16

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()

As i have situations with a lot of "leaf" nodes, could you please explain the rule, i.e. why not to add an empty entry also for node 12? — deblocker, Aug 04 '16 at 18:33
Empty array for 12 should be added yeah, but in this case its covered by the >= length of rightAdjacent — juvian, Aug 04 '16 at 18:55
@deblocker here is a better way using dfs : https://jsfiddle.net/91gf32fa/2/ (uses less memory, no need to deep copy anything) — juvian, Aug 05 '16 at 17:01
I just changed the function to avoid the JSON part and to use plain arrays, i'm already very happy with this, THX anyway, Maybe this would help someone which loves recursion more than me. — deblocker, Aug 05 '16 at 17:20

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

1 Answers1

Linked