Boost logo

Boost Users :

Subject: Re: [Boost-users] [BGL] Completely Perplexed Noob to BGL: Reachability Question
From: Michael Olea (oleaj_at_[hidden])
Date: 2009-03-26 14:43:18

On Mar 26, 2009, at 3:08 AM, Roshan Rammohan wrote:

> Hi all,
> Although I was attracted to BGL since I have to use a lot of graph
> algorithms for my work, and I have managed to read through as much
> online documentation as possible,
> generic programming is still very mysterious to me.

You might want to get a copy of "The Boost Graph Library: User Guide
and Reference Manual" if you do not have it already.

> All I need to do is compute reachability from vertex B to vertex A
> before I add the edge A->B to a graph (directed and acyclic) so
> that I can maintain its acyclic property.
> I do not want to add the edge, discover a cycle and then remove it.

I've attached an example below. It is essentially the same as the
solution Steven Watanabe posted earlier, except that rather than
throwing an exception in the event of finding that the target vertex
is reachable it sets a reference to a boolean flag. The point in both
cases is that the visitor passed to breadth_first_search is passed by
value, so the caller needs some way to get the result of what the
visitor found. One advantage of throwing an exception is that the
search halts as soon as it discovers that the target vertex is

Here's the output of a little test routine:

DAG before adding another acyclic edge:
A --> C
B --> D E
C --> B D
D --> E
E -->
Attempting to add directed cycle edge D -> A
Edge D -> A correctly refused
Attempting to add acyclic edge A -> D
Edge A -> D correctly accdepted
DAG after adding another acyclic edge:
A --> C D
B --> D E
C --> B D
D --> E
E -->

Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at