On 6/22/07, gast128 <gast128@hotmail.com> 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