From: David Abrahams (david.abrahams_at_[hidden])
Date: 2002-01-11 11:36:23
I'd like to do something very much like transitive_closure. What I want to
do is build an index which tells me, for every (edge,vertex) pair, whether
the vertex is reachable through the edge without looping. Put another way,
can I reach the destination from the edge's target vertex without visiting
the edge's source vertex? Or another way, does a spanning tree exist which
includes the edge and the destination vertex?
It seems like the transitive_closure algorithm does all the right work, but
I can't see how to make it give me the answer I want.
One thought: I could map the graph G onto a G' which adds a self-edge for
every vertex, then map that to G'' with a vertex corresponding to every edge
in G'. Then I can do transitive_closure on G'' and ask whether the self-edge
in G' corresponding to a given vertex in G is reachable from any of the
other edges. The problem with this is that the criterion for determining
whether I've looped is wrong: I want a stronger condition than not passing
through a vertex of G'' (i.e. edge of G) twice: I want to rule out paths
which pass through the any immediate predecessors of a node which has been
visited already. This seems excessively complicated, though.
David Abrahams, C++ library designer for hire
C++ Booster (http://www.boost.org)
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk