Boost logo

Boost Users :

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


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)
> 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<> {
    reachable_visitor(const Vertex& v) : vertex(v) {}
    void discover_vertex(const Vertex& v, const Graph&) const {
        if(v == vertex) throw found_vertex();
    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

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