On Thu, Mar 26, 2009 at 12:43 PM, Michael Olea <oleaj@sbcglobal.net> wrote:

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

_______________________________________________
Boost-users mailing list
Boost-users@lists.boost.org
http://lists.boost.org/mailman/listinfo.cgi/boost-users