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

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 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 bool reachable(const Graph& g, const Vertex& start, const Vertex& end) { try { boost::breadth_first_search(g, start, boost::visitor(reachable_visitor(end))); } catch(found_vertex&) { return true; } return false; } In Christ, Steven Watanabe