Graph problem -- solvable using the Boost graph library ?

[m***@agfa.com]

_______________________________________________
Boost-users mailing list
Boost-***@lists.boost.org
http://lists.boost.org/mailman/listinfo.cgi/boost-users

[Vladimir Prus]

***@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

[Aaron Windsor]

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

[Dmitry Bufistov]

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 ?

Hi,
Unfortunately I didn't test, but I'm pretty sure, that for acyclic
graphs Dijkstra's algorithm has linear complexity (you don't need color
map at all), and you don't need to find all connected components, so
your current approach is the best solution or very close to the best=)
--dima

[z***@globalnet.hr]

Post by Dmitry Bufistov

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 ?

Hi,
Unfortunately I didn't test, but I'm pretty sure, that for acyclic
graphs Dijkstra's algorithm has linear complexity (you don't need color

If the graph is acyclic -> it is a tree -> there is 1 and only 1 path
between any two vertices (consequently, it is both shortest and longest).
So you might as well perform breadth-first search from a starting vertex to
get all paths and distances to other vertices. BFS complexity is O(|A|) where
|A| is the number of edges in the graph.

If you need all-pairs paths, then you end up with O(|V|*|A|) with a
naive algorithm (|V| time executing BFS from different end points), where
|V| is the number of vertices.

You can actually do better. You don't need to perform BFS for all
vertices, but just for branching points (i.e. those whose degree is > 2).
The rest of the vertices are just linear paths of constant length which
can't affect path lengths between branch points (since you're dealing
with a tree).

Disclaimer: Its late at night and I haven't drawn any picture for
myself. This is straight out of my head. Please double-check this.

[z***@globalnet.hr]

Post by Dmitry Bufistov
Unfortunately I didn't test, but I'm pretty sure, that for acyclic
graphs Dijkstra's algorithm has linear complexity (you don't need color

I would disagree. Dijkstra algorithm doesn't care about cycles. Its
only prerequisite for correct operation is that all edge lengths are
positive. Roughly, it does the following:
0. assign label 0 to start vertex, and infinity to all other vertices
put U := V (V is the vertex set)
1. choose the vertex u from U such that u has minimum label and update
weights of vertices reachable from u. the label is actually the
distance to u from the starting vertex.
2. set U := U \ {u} and repeat until U is empty

Step 1 is repeated |V| times. With primitive data structure for vertex
labeling (such as array or linked list), the min operation takes O(|V|)
so the total running time is O(|V|^2). If Fibonacci heap is used for
computing the minimum, the running time can be reduced to O(|E|+|V|*log|V|).

But in no case can the Dijkstra algorithm run in linear time.

[Grégoire Dooms]

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