Re: [Boost-users] grapg problem: getting all vertices between source and sink

From: Aaron Windsor (aaron.windsor_at_[hidden])
Date: 2007-06-26 07:40:57

On 6/22/07, gast128 <gast128_at_[hidden]> wrote:
> 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

I'm assuming you mean simple paths? (a simple path doesn't allow
repeated vertices). There's a simple path between vertices s and t
that passes through x exactly when the following three conditions
hold: (1) there's a path from s to x AND (2) there's a path from x to
t AND (3) if you remove any single vertex from the graph besides x,
there's still either a path from s to x or a path from x to t.

You can use the BGL's depth-first or breadth-first search to determine
if there's a path between two vertices, and you can use the BGL's
filtered_graph to remove one vertex at a time from the graph and test
for reachability. If you have a graph with n vertices, you can do the
test on the entire graph in time O(n^3).

Regards,
Aaron