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

Subject: Re: [Boost-users] [BGL] Completely Perplexed Noob to BGL: Reachability Question
From: Roshan Rammohan (roshan.r_at_[hidden])
Date: 2009-03-26 15:22:32

Steven, Michael,

Thanks for your help. Using Steven's throw catch solution.

Yes. I have already ordered the BGL manual.

So I see how an extra parameters can be passed in through custom
constructors of the visitor. but the BGL manual should help.

Thanks again.

-Rr

On Thu, Mar 26, 2009 at 12:43 PM, Michael Olea <oleaj_at_[hidden]> 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_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>