Graph problem -- solvable using the Boost graph library ?
matthieu.ferrant@agfa.com wrote: Hi Matthieu, as a side remark, please don't use HTML emails,
I have a non-directed, acyclical graph with a series of end points. I need to compute the longest path between any two end points. Right now I do this computing the longest dijkstra shortest path (using the boost graph library) from each end point and picking the longest of these, but this is quite heavy. Is there a faster way to do this ?
http://boost.org/libs/graph/doc/johnson_all_pairs_shortest.html and http://boost.org/libs/graph/doc/floyd_warshall_shortest.html allows you to compute distances between all pairs of vertices and it will be a bit more efficient than repeative applications of Dijkstra. - Volodya
On 12/16/05, matthieu.ferrant@agfa.com
Hi,
I have a non-directed, acyclical graph with a series of end points. I need to compute the longest path between any two end points. Right now I do this computing the longest dijkstra shortest path (using the boost graph library) from each end point and picking the longest of these, but this is quite heavy. Is there a faster way to do this ?
There's no special algorithm in the BGL for this problem. Finding the longest path in a general graph is a difficult problem, but it happens to be easy for the special case of acyclic graphs. Since acyclic graphs have at most one path between any two vertices, you can use essentially any traversal that measures distances between vertices to find the longest path - as Volodya mentioned, the two all-pairs shortest path algorithms in the BGL can be used. You can also compute the longest path in an acyclic graph in linear time if you want to write a little code yourself. First, assume that the graph is connected - otherwise you could run the algorithm I'm about to describe on all of the connected components and take the maximum-length path you find in any component. If you imagine your tree rooted at some particular vertex v, then there are two cases: either the longest path passes through v, in which case the path starts at one of v's descendants d1, goes up to v through the unique path from d1 to v, then down to another one of v's descendants d2 on the unique path from v to d2. (All of this reasoning follows from the fact that in a tree, there is at most one path between any two vertices.) Otherwise, the longest path doesn't pass through v, and you can effectively remove v from the graph and recursively consider the trees rooted at all of v's children in the same way you just considered v. The easiest way of implementing this is probably a three step process: (1) compute the height of each node in the directed tree rooted by v (2) use the heights from (1) to compute the length of the longest path passing through each vertex, as described above. (3) use the longest path lengths from (2) to assemble the actual longest path. -Aaron
matthieu.ferrant@agfa.com wrote:
Hi,
I have a non-directed, acyclical graph with a series of end points. I need to compute the longest path between any two end points.
Do you need the longest path or the longest among the all pairs shortest paths ?
Right now I do this computing the longest dijkstra shortest path (using the boost graph library) from each end point and picking the longest of these, but this is quite heavy. Is there a faster way to do this ?
You can use all pairs shortest path algorithms (see other answer in this thread). If you really want the longest path, just transform the costs: use the opposite cost ( - c ) for each edge. Then search the shortest one and you will get the longest path in your original graph. Such a path is garanteed to exist as your graph is acyclical so there are no negative cycles in your graph. If you have a relatively small number of end points, just add an additional source to all the end points and an additional sink from all endpoints. Then use point to point shortest path such as Bellman-Ford from the added source to the added source. You need to find appropriate equal costs for all the added edges. If your longest path has positive cost, using 0 for the cost of the new edges should be correct: an all virtual path has cost 0 while the shortest one is negative ie. lower. HTH, -- Grégoire Dooms
participants (4)
-
Aaron Windsor -
Grégoire Dooms -
matthieu.ferrant＠agfa.com -
Vladimir Prus