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

Subject: Re: [Boost-users] Completely Perplexed Noob to BGL: Reachability Question
From: Steven Watanabe (watanabesj_at_[hidden])
Date: 2009-03-26 12:12:34

AMDG

Roshan Rammohan wrote:
>  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.
>
>  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 saw a very closely related example here. (thanks to Steven Watanabe)
>  http://lists.boost.org/boost-users/2009/03/46396.php
>
>  That was helpful, but I'm still not able to adapt this to my need mainly
> because I find the syntax and concepts of generic programming extremely
> confusing.
>
>  I am not sure how I can pass an extra parameter into a BFSVisitor which the
> member function discover_vertex can use. Does discover_vertex have to have
> only a vertex_descriptor and a Graph?
>  I want to pass another constant vertex to it so I can return on equality.
>
>  I need to initiate a BFS from vertex B, (and not continue with new trees
> once the tree with B as root is finished) .
>  On discovering vertex A in this search I need to return true, false for all
> other cases.
>
>  Pretty simple, and I am hoping someone would write a code snippet for me
> that will solve the problem and also provide me with the baby step I need
> to  wrap my head around this Visitor concept.
>   

In this case, you probably need to write your own visitor.

struct found_vertex {};

template<class Graph, class Vertex>
struct reachable_visitor : boost::bfs_visitor<> {
public:
    reachable_visitor(const Vertex& v) : vertex(v) {}
    void discover_vertex(const Vertex& v, const Graph&) const {
        if(v == vertex) throw found_vertex();
    }
private:
    Vertex vertex;
};

template<class Graph, class Vertex>
bool reachable(const Graph& g, const Vertex& start, const Vertex& end) {
    try {
        boost::breadth_first_search(g, start, 
boost::visitor(reachable_visitor<Graph, Vertex>(end)));
    } catch(found_vertex&) {
        return true;
    }
    return false;
}

In Christ,
Steven Watanabe