Re: [Boost-users] Graph problem -- solvable using the Boost graph library ?

From: Aaron Windsor (aaron.windsor_at_[hidden])
Date: 2005-12-17 10:37:58

On 12/16/05, matthieu.ferrant_at_[hidden] <matthieu.ferrant_at_[hidden]> 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.  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