   directed graph with loops, generate all paths
  I'm looking for an algorithm to generate a set of all unique paths between two nodes in a directed graph that can have loops, with uniqueness determined by whether there is a unique arc in the pathso for example in the graph:a : b,cb : dc : ed : b,e(left is node, right is the nodes you can move to, note the b,d loop)from a,e the generate paths would beabdeabdbdeace   
  here's an algorithm off the top of my head, anyone think of a more effecient way to do this?list open_pathslist closed_pathsopen_paths.push_back(path(start_node));while(!open_paths.empty()){    int num = open_paths.size();    while(num-->0)    {   path cpath = open_paths.pop_front();   for each connected node 'n'   {  path npath = cpath+n  if(n is end_node) closed_paths.push_back(npath)  else if(npath is unique) open_paths.push_back(npath)   }    }}which would in this case (new lines for passes of algorithm) would give:open: a  closed:open: ab, ac  closed: open: abdclosed: aceopen: abdb    closed: ace, abdeopen: abdbd   closed: ace, abdeopen:    closed: ace, abde, abdbdeany suggestions on a more effecient algorithm?[Edited by - luca-deltodesco on June 14, 2009 5:17:19 PM];  Off the top of my head -- whenever a branch is encountered, you recurse down all paths, keeping track of the current path as you go.  If you find the target node then you return the path, but if you reach a terminal node or a node you've already visited, then you return failure.EDIT:  Actually that won't allow loops, but it could be a good start.  I suppose I'm not very clear on your criteria for uniqueness either, but I'll keep thinking :)   ;Quote:Original post by ZipsterOff the top of my head -- whenever a branch is encountered, you recurse down all paths, keeping track of the current path as you go.  If you find the target node then you return the path, but if you reach a terminal node or a node you've already visited, then you return failure.That was my first thought, but that would discard the path abdbde in my exampleI've thought of a second algorithm which avoids the need to determine if a path is unique (something that in my current tired state is eluding me to how exactly is best to do that) as it only generates unique paths, but it requires storing a copy of the network with each path as it goes, so not sure if that's really any better.   ;Quote:Original post by ZipsterEDIT:  I suppose I'm not very clear on your criteria for uniqueness either, but I'll keep thinking :)Neither am i ^^, basicly the path is unique if it contains an arc, that another path doesn't have.so abdbde is unique from abde because it also contains the arc db;  here's another example of the result i'm looking for:paths:abd,acdabcd,acbdabcbd,acbcdIf it helps, the reason i'm looking for such a solution is to evaluate every possible flow through a program execution, where the nodes are representing blocks of compiled code between labels and branches.   ;  How about this... start with the original algorithm where you recurse down each path.  However, in addition to storing all the nodes you've visited, also store all the "decisions" you've made from that node.  If you reach a node, and you've already made all possible decisions, then you fail.So starting at node 'a', you branch off to nodes 'b' and 'c'.  The first branch records that you decided to go to node 'b' (i.e. "a : b"), and the second branch records that you went to node 'c' (i.e. "a : c").  At node 'b', you branch off to nodes 'c' and 'd'.  The first branch records "b : c", the second branch records "b : d".  The first branch reaches node 'c', and branches back off to nodes 'b' and 'd'.  Once you arrive back at node 'b', you see "b : c" and determine that you already visited node 'c' from node 'b', so this time you go to node 'd' and record "b : c,d".  A similar thing happens with the path that went from node 'a' to 'c'.The basic idea is that whenever you reach a node, you travel to all nodes you haven't already visited and record that decision per branch.  Every time a particular path reaches a node, it will be making one less recursive branch, until it reaches a node and finds it has no more branches left to take that it hasn't already taken.  If it seems like a lot of recursion and a lot of paths, that's because it is :)  At first I thought it was infinite and your solution set was "a(bd)+e", but then I realized exactly what it was you wanted.   ;  What you need is depth-first search. Make sure that you mark all the edges that you have already used along the way. This code is not very high quality, but I hope it displays the algorithm clearly:#include <iostream>#include <vector>#include <map>#include <set>#include <stack>std::map<char, std::vector<char> > edges;std::vector<char> path;void find_paths(char origin, char destination, std::set<std::pair<char, char> > &visited) {  path.push_back(origin);  if(origin==destination) {    // Path found!    for(std::vector<char>::const_iterator it=path.begin(),end=path.end(); it!=end; ++it) std::cout << *it;    std::cout << '\n';  }  std::vector<char> const &next_steps = edges[origin];  for(std::vector<char>::const_iterator it=next_steps.begin(),   end=next_steps.end(); it!=end; ++it) {    if(visited.insert(std::make_pair(origin, *it)).second) { find_paths(*it, destination, visited); visited.erase(std::make_pair(origin, *it));    }  }  path.pop_back();}int main() {  edges['a'].push_back('b');  edges['a'].push_back('c');  edges['b'].push_back('c');  edges['b'].push_back('d');  edges['c'].push_back('b');  edges['c'].push_back('d');    std::set<std::pair<char, char> > visited;  find_paths('a', 'd', visited);};  alvaro, if i'm understanding that algorithm correctly it will work for the second diagram, but not for situations like the first, in which case it would not produce the path containing the loop as in that loop it must travel the same arc twice to reach the destination, a path may travel the same arc more than once, as long as doing so allows it to travel an arc that was not yet travelled, so the path abdbde is allowed, even though it travels arc bd twice, because it also travels db which was not yet an arc travelled.Zipster, yours also seems to suffer this.----My condition of uniqueness still seems to hold for this more complicated example where the paths i need are these I believe.abceabcbceabdceabdcbceabcbdeabcbdce----An added constraint to the graph would be that a node can have as many arcs directed into it, but only 2 at most coming out of it.Zipster perhaps yours could be modified to say that if you reach a node where you've already made all the decisions, rather than failing, you branch off once more. I believe the added constraint i've realised above should mean that you can only become stuck on a node, when there is a single arc out of it, so the number of possible paths shouldn't explode...----Although this would be more suited to a different forum for this next part, i said i was using this to find all the flows through a program execution, the reason i'm doing that is in an optimisation step, wherein i want to see if a register is no longer being used; so to do that i need to know all the possible ways the program might flow from that point on, to see if it gets used again,[Edited by - luca-deltodesco on June 15, 2009 4:51:09 AM];  The algorithms we presented (which happen to be the same actually) work just fine, I think, if you make some adjustments to the initial graph.  For each input into a particular node, create a copy of that node that has all the same outputs as the original node, but only a single input.  For instance, your above graph (EDIT: looks like you changed it but bear with me!) would go from this:a : bb : cc : b,dd : c,ee :To this:a : bb : cb* : cc : b*,dc* : b*,ed : c*,ee :Nodes 'b' and 'c' get a copy, since they have more than one input.  'b' accepts the input from 'a', and 'b*' accepts the input from both 'c' and 'c*' (since each copy of node 'c' has the same outputs).  'c' accepts the input from both 'b' and 'b*' for the same reason, and 'c*' accepts the input from 'd'.  'd' accepts input from 'c' and 'c*', and 'e' accepts input from 'd'.  Once you use alvaro's algorithm to generate the paths, collapse the node copies into the originals, i.e. node 'b*' becomes a pseudonym for 'b', and 'c*' becomes a pseudonym for 'c'.  I haven't fully tested this out, but it seems to work alright on the test cases :)   