How to enumerate paths through a graph?
November 17, 2010 12:46 AM Subscribe
What's the right way to find all unique paths through a directed graph (using PHP)?
What's the right way to do this? I'm starting with a .dot (graphviz) file that describes a simple directed graph. Like this:
digraph G {
1->2
2->0
2->7
2->3
5->1
5->6
5->21
0->11
0->12
7->9
7->10
}
...I want to write a program (in PHP) that parses the .dot file and lists all the unique paths through the graph, like this:
1, 2, 0, 11 1, 2, 7, 9 1, 2, 0, 12 ...etc.
What's the right way to do this? Depth-first search? Any help appreciated, and by "help" I mean "functioning PHP code" =]
What's the right way to do this? I'm starting with a .dot (graphviz) file that describes a simple directed graph. Like this:
digraph G {
1->2
2->0
2->7
2->3
5->1
5->6
5->21
0->11
0->12
7->9
7->10
}
...I want to write a program (in PHP) that parses the .dot file and lists all the unique paths through the graph, like this:
1, 2, 0, 11 1, 2, 7, 9 1, 2, 0, 12 ...etc.
What's the right way to do this? Depth-first search? Any help appreciated, and by "help" I mean "functioning PHP code" =]
Best answer: I think this should give you a good start.
posted by kmz at 2:03 AM on November 17, 2010
posted by kmz at 2:03 AM on November 17, 2010
By "path," do you mean a Hamiltonian path? That might be a good place to start googling. Good luck. I feel like even your lower bound will be sort of high.
The "dumb" approach is to recurse on every child, keeping a count and a list of seen nodes.
posted by yaymukund at 2:14 AM on November 17, 2010
The "dumb" approach is to recurse on every child, keeping a count and a list of seen nodes.
posted by yaymukund at 2:14 AM on November 17, 2010
Graph traversal has the two major options here. You've left one big open question though: how do you count loops in the graph? Technically, differing numbers of iterations through that loop result in different paths.
posted by pwnguin at 6:24 AM on November 17, 2010
posted by pwnguin at 6:24 AM on November 17, 2010
I recently worked on a similar problem in Ruby for cyclic graphs, unfortunately I am allergic to PHP and every time I code in it I break out in hives. So the best I can do is share some of my general lessons learned.
First, if your graph will have any cycles (loops) things get very complicated, since you have to follow every branch because it might loop back into the current path you're trying to trace. Things are greatly simplified for acyclic graphs (no loops), in that case you know that your path will never loop back behind you, and you can just iterate through every branch.
Second, one issue is that cyclic graphs can have paths that never end (you can iterate forever in a loop), is it important to know if you enter an infinite loop, or is it sufficient to document the path up until it re-enter's an existing path (i.e., a Hamilton path as yaymukund pointed out)?
Third, depth-first or breadth-first won't make a difference for acyclic graphs. However, again, things are more complicated with cyclic graphs, and also depends on what you mean by "path". For cyclic graphs, depth-first and breadth-first iterations for finding a Hamilton path will give you different path answers. What I mean by that is that if you have the directed graph below (edge direction points down):
.........1........... Note: This directed cyclic graph has two infinite loops
......../..\..........
.......2...3.........
....../.......\.......
.....4........5......
..../............\....
...3.............2... These are not new nodes, just loops back to node 3 and 2 respectively
A depth-first search gives you a Hamilton path of 1,2,4,3,5 (all nodes visited), while a breadth-first search gives you a Hamilton path of 1,2,3,4,5.
The bottom line is that it really matters whether or not your graph is cyclic or acyclic, and what you mean by "path" as others have indicated above. Once that is understood, then there are probably existing php design patterns out there to do what you want.
posted by forforf at 6:26 AM on November 17, 2010
First, if your graph will have any cycles (loops) things get very complicated, since you have to follow every branch because it might loop back into the current path you're trying to trace. Things are greatly simplified for acyclic graphs (no loops), in that case you know that your path will never loop back behind you, and you can just iterate through every branch.
Second, one issue is that cyclic graphs can have paths that never end (you can iterate forever in a loop), is it important to know if you enter an infinite loop, or is it sufficient to document the path up until it re-enter's an existing path (i.e., a Hamilton path as yaymukund pointed out)?
Third, depth-first or breadth-first won't make a difference for acyclic graphs. However, again, things are more complicated with cyclic graphs, and also depends on what you mean by "path". For cyclic graphs, depth-first and breadth-first iterations for finding a Hamilton path will give you different path answers. What I mean by that is that if you have the directed graph below (edge direction points down):
.........1........... Note: This directed cyclic graph has two infinite loops
......../..\..........
.......2...3.........
....../.......\.......
.....4........5......
..../............\....
...3.............2... These are not new nodes, just loops back to node 3 and 2 respectively
A depth-first search gives you a Hamilton path of 1,2,4,3,5 (all nodes visited), while a breadth-first search gives you a Hamilton path of 1,2,3,4,5.
The bottom line is that it really matters whether or not your graph is cyclic or acyclic, and what you mean by "path" as others have indicated above. Once that is understood, then there are probably existing php design patterns out there to do what you want.
posted by forforf at 6:26 AM on November 17, 2010
This thread is closed to new comments.
posted by hattifattener at 12:48 AM on November 17, 2010