## The Design of Software (CLOSED)A public forum for discussing the design of software, from the user interface to the code architecture. Now closed. |
||

The "Design of Software" discussion group has been merged with the main
Joel on Software discussion group.
The archives will remain online indefinitely. |
I don't care about the shortest anything. I would like to find all the paths in a directed graph that has cycles. I don't care how slow it is either as the graph is small.
I can't find any simple enough for me explanation of how to do this. Any ideas?
son of parnas Sunday, November 13, 2005
The answer is...
Infinity. If you're looking for ALL paths in a cyclic graph consisting of two nodes, A and B, where A goes to B, and B goes to A, then ABA is a path, ABABA is a path, ABABABA is a path, ABABABABABABABABABABABABA is a path, etc. Typically, you do establish some boundary conditions, for example, you can only visit each node once, or you cannot take the same path twice. This is an entire branch of computer science, but if you really want to just start reading algorithms, I suggest you research Dijkstra's Algorithm, Floyd's Algorithm and Warshall's Algorthim. Those three (in that order) are generally the introductory formulas for transversing a graph.
Anonymous Coward Sunday, November 13, 2005
> Dijkstra's Algorithm, Floyd's Algorithm and Warshall's Algorthim
They don't give you all paths.
son of parnas Sunday, November 13, 2005
Assuming you want each path to visit each node once and that there are n nodes, the number of paths is n!. In the traditional "Travelling Saleman Problem", you could discount duplicate circuits (A -> B -> C -> D is the same as B -> C -> D -> A) which would leave you with (n-1)!. Finally, you can eliminate forward and reverse paths (A -> B -> C -> D is the same as D -> C -> B -> A) for a total of (n-1)!/2 paths. For non-trivial values of n, the number of paths is very large.
The problem of finding the shortest path is a well researched field (simulated annealing is one well known method, but Gunter Dueck's "Threshold Accepting Algorithm" and "Great Deluge Algorithm" are both deterministic and fast). I haven't seen anyone trying to find all the routes, but I would tend to treat this as a sorting problem. Assume there are 4 nodes; A, B, C & D. First find all the paths that start with A, then all the paths that start with B and so on. When looking for the second node, cycle through all the nodes (in order) except the one at the beginning of the path. When looking for the third node, cycle through the remaining nodes (in order) except for the first and second nodes. Continue for as many cycles as necessary. When you use all the nodes, you have a completed path. Then remove the last node, and exchange it with the previous one. Here's the resulting sequence using the example nodes: A -> B -> C -> D A -> B -> D -> C A -> C -> B -> D A -> C -> D -> B A -> D -> B -> C A -> D -> C -> B B -> A -> C -> D B -> A -> D -> C B -> C -> A -> D B -> C -> D -> A B -> D -> A -> C B -> D -> C -> A ... Since you are interested in every path, the total number of paths (from the formula above) is 4! or 24. It looks correct as there seem to be six paths for each starting letter. This algorithm strikes me as being very solvable using a recursive function that continuously passes itself the remaining list of nodes. While this would be memory intensive for large values of n, it also eliminates the complexity of searching and resorting the list for each element. It also strikes me that you could treat this like Gray's code (allowing only one change at a time), which might speed up the recursion. If you're interested, I could code this up in Java or Python pretty easily as an example, but I have a few questions that might affect the design: 1) What is the maximum value of n you expect? 2) What is your input method and type? 3) What is your output method and type? 4) What is your language preference?
> Finally, you can eliminate forward and reverse paths (A -> B -> C -> D is the same as D -> C -> B -> A) for a total of (n-1)!/2 paths.
If it is a directed graph then it is the direction that tells you what is possible? > For non-trivial values of n, the number of paths is very large. Doesn't it depend on the density of the graph and the degree of interconnection? A sparse graph wouldn't have that many paths.
son of parnas Sunday, November 13, 2005
>> Dijkstra's Algorithm, Floyd's Algorithm and Warshall's Algorthim
> They don't give you all paths. That's because these three algorithms apply some limits. In Dijkstra's, you cannot complete the same cycle twice. That's why I capitalized the word ALL as a point of emphasis. It's like asking "how many chemical reactions are there?" as opposed to "how many chemical reactions are there taking place in this exact beaker containing exactly two liters of water?" You need to define the scenario exactly. Keep in mind that when you code this, you'll need to be precise for the computer's benefit anyway. >> Finally, you can eliminate forward and reverse paths (A -> B -> C -> D is the same as D -> C -> B -> A) for a total of (n-1)!/2 paths. > If it is a directed graph then it is the direction that tells you what is possible? Yes. Keep in mind that paths can be bidirectional - you can go forwards AND backwards. For example, airlines in the United States adopt a hub model of travel - you can fly to Chicago, then to Gary, then back to Chicago, then to Detroit, then back to Chicago, then onwards to Lansing. It's very rare to be able to get flights from Chicago to Gary to Detroit to Lansing in that order. >> For non-trivial values of n, the number of paths is very large. > Doesn't it depend on the density of the graph and the degree of interconnection? A sparse graph wouldn't have that many paths. Yes. It depends on the number of nodes, and the numbers of connections between those nodes aka paths. However, you define both the number of nodes and the number of paths. Once you have, you can use Steve's formula, but Steve assumes you will only visit each node once, and you will only travel each path once.
Anonymous Coward Monday, November 14, 2005
I think the original problem is being misunderstood. The OP is not asking about complete graphs (which Steve points out is just a combinatorial issue), nor cardinally infinite-graphs (well that's not too practical), nor necessarily regular graphs, heck, the vertices don't necessarily to have only one arc conncecting them.
I think a simple algorithm is to unfold the directed graph into tree as if it were one of those polygonal toys (http://www.zometool.com/ ) being unattached: 1. Take S, the set of vertices of the graph where each vertix has at least one incoming and one outgoing arc. 2. For each vertex in S, A, construct a tree. Label its root A and for each outgoing arc on the graph from A to its neighbor vertex X (which is a member of S, by the way), put in a branch on the tree with a node labeled X and edge (A,X). Continue in this way: whenever a vertex on the graph is reached, take each outgoing arc from that vertex which doesn't have a corresponding edge on the tree, make it into a branch of the tree, label it and take the endpoint of that arc/edge as a new vertex. When there are no more unlabeled outgoing arcs, the tree is done. (This is not a spanning tree as those span the vertices of a graph. Here we're interested in mapping all the arcs, or at least those arcs reachable from A.) 3. Scan the tree and look for nodes labled A (besides the root). Each of these paths from the root node A to the child node A corresponds to a cycle on the original graph which contain the vertex A. That's it. There will be repetitions of the ABCD and CDBA form by I imagine those will be easy to clean up. I believe, by the way, the technique to make a tree in step 2 is called a Tremaux algorithm.
Slava, I think that makes sense.
The way I think of your step 2 is for every cell in adjacency matrix that is set, follow all paths until you run out of vertexes or one until one of them is already in your path. For every cell with more that one path out, pop that on the stack, and follow them when your other paths run out.
son of parnas Monday, November 14, 2005
Yeah in general there'll be infinitely many paths in a cyclic graph.
Define precisely what you mean by 'path'. If you mean a Hamiltonian Path (one that visits each vertex at most once), then this http://mathworld.wolfram.com/HamiltonianPath.html has a reference for a fast algorithm you might wanna try looking up.
Walk through the graph as if it was a acyclic graph.
But I see two ways to avoid the infinite recursion: 1) paint the nodes as you reach them. Then travel all unpainted children. 2) send a scout two-ahead and if the scout ever points at the current node, you have a cycle and can not recurse further?
new nick, new rep Wednesday, November 16, 2005 |

Powered by FogBugz