Re: [Boost-users] [BGL] Completely Perplexed Noob to BGL: Reachability Question

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  
reachable.

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 -->