BGL: like transitive_closure, but not exactly

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.

Any ideas?

-Dave
===================================================
  David Abrahams, C++ library designer for hire
 resume: http://users.rcn.com/abrahams/resume.html

        C++ Booster (http://www.boost.org)
          email: david.abrahams_at_[hidden]
===================================================