java - Building an All Paths Algorithm for a DAG -

java - Building an All Paths Algorithm for a DAG -

been trying build method gets conceivable unique paths through dag. went recursion because seemed easiest understand. ended this:

public class brutus { //the previous nodes visited public arraylist<node> resulthistory = new arraylist<node>(); //directed graph class, contains hashmap [adjacencies] // has keys nodes contains edges public adjacencylist paths; //a list of pathways between nodes represented list of nodes public arraylist<arraylist<node>> allpaths = new arraylist<arraylist<node>>(); public brutus(adjacencylist paths) { this.paths = paths; } public arraylist<arraylist<node>> findall() { int counter = 1; (node key : paths.adjacencies.keyset()) { system.out.println("[" + counter + "]: " + key.tostring()); stringtokenizer st = new stringtokenizer( paths.getadjacentstring(key), ","); while (st.hasmoretokens()) { string kid = st.nexttoken(); if (paths.getnodefromgraph(child) != null) { resulthistory = new arraylist<node>(); resulthistory.add(key); findpath(child, resulthistory); } } counter++; } homecoming allpaths; } public void findpath(string child, arraylist<node> resulthistory) { if (resulthistory.contains(paths.getnodefromgraph(child))) { return; } resulthistory.add(paths.getnodefromgraph(child)); if(!(inlist(resulthistory, allpaths))) { allpaths.add(resulthistory); } stringtokenizer st = new stringtokenizer( paths.getadjacentstring(paths.getnodefromgraph(child)), ","); while (st.hasmoretokens()) { kid = st.nexttoken(); if (paths.getnodefromgraph(child) != null) { findpath(child, resulthistory); } } } public boolean inlist(arraylist<node> resulthistory, arraylist<arraylist<node>> allpaths) { (int = 0; < allpaths.size();i++) { if (allpaths.get(i).equals(resulthistory)) { homecoming true; } } homecoming false; }

problem is, don't think works paths, since can't find paths within it. although dataset 900 nodes, unable find pattern! other questions on stack seem more specialized , such attempted build own algorithm!

can either suggest superior way perform this, or tell me i've done wrong? if algorithms correct, best way withdraw paths between 2 nodes?

edit: realize new paths don't created kid nodes of original, how create does?

here there implementation based on bfs algorithm. denote path sequence of vertices l = (v, v', v'', ...) , perform next 2 operations on it:

extend(l, v): puts vertex v @ end of list l; v = back(l): gets lastly vertex in list l. findpaths(g, v) { // first path is, simply, starting node. // should first vertex in topological order. pending_paths = {(v)}; while (pending_paths not empty) { l = pending_paths.remove_first(); // pop first pending path output(l); // output (or save in list returned, if prefer) v = back(l); // lastly vertex of path foreach(edge (v, v') in g) { // each border outgoing v'... // extend l v' , set list of paths examined. pending_paths.push_back(extend(l, v')); } } }

java algorithm directed-acyclic-graphs