From: gast128 (gast128_at_[hidden])
Date: 2007-06-22 07:56:08
Dear all,
we have a simple problem: we want to know all vertices between a source and
sink vertex in adirected graph. So my thoughts were to see if a vertex is
reachable from both source and sink (by doing a breadth_first_search on the
graph from source and a breadth_first_search from the sink on the reverse
graph) and if reachable they lay in between.
However this counts too much vertices. Consider graph So -> Si -> C. C is
reachable from both So as reachable from Si using in edges. This is not good.
The breadth_first_search should not perform an out_edge discover from Si.
Do I have to implement my own breadth_first_search_with_stop or are there
alternatives?
Wkr,
me