Completely Perplexed Noob to BGL: Reachability Question
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. 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. Thanks in advance. - Roshan Rammohan PhD Candidate, A.I. lab, Dept of C.S., Univ. of New Mexico, USA
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
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; }
Nice, but is throw-to-return-type-idiom really the best to be used here? Isn't there a "better" way to do this? regards Jens Weller -- Neu: GMX FreeDSL Komplettanschluss mit DSL 6.000 Flatrate + Telefonanschluss für nur 17,95 Euro/mtl.!* http://dsl.gmx.de/?ac=OM.AD.PD003K11308T4569a
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 -->
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@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
Is it still the case that boost statecharts require allocation and destruction of a state object when entering and exiting that state? I'm curious, as I'm comparing boost statecharts with Samek's. Heinzmann provided some commentary on the differences: http://www.state-machine.com/resources/Heinzmann04.pdf Samek's QHSM implementation does not require allocations for entering and exiting states (specifically, QHSM states are not object instances, rather they are represented simply as a pointer to a member function). Of course Heinzmann was also promoting his own personal implementation...which I don't think he ever finally published or made available for download.
Brent Arias wrote:
Is it still the case that boost statecharts require allocation and destruction of a state object when entering and exiting that state? I'm curious, as I'm comparing boost statecharts with Samek's. Heinzmann provided some commentary on the differences:
http://www.state-machine.com/resources/Heinzmann04.pdf
Samek's QHSM implementation does not require allocations for entering and exiting states (specifically, QHSM states are not object instances, rather they are represented simply as a pointer to a member function).
Of course Heinzmann was also promoting his own personal implementation...which I don't think he ever finally published or made available for download.
You might want to take a look at Christophe Henry's meta state machine (msm) library recently added to the review queue. It's based on the lightweight state transition table approach from the Template Meta Programming book by Gurtevoy and Abrahams. The review-ready version can be found: - in the Vault: http://www.boostpro.com/vault/index.php?direction=0&order=&directory=Msm& - or better (in case of bugfixes), in the sandbox: https://svn.boost.org/svn/boost/sandbox/msm/ . You will find there the Review version under /tags/version-1.20, the most current version at the same level under /boost (or /libs for the doc). Jeff
participants (6)
-
Brent Arias -
Jeff Flinn -
Jens Weller -
Michael Olea -
Roshan Rammohan -
Steven Watanabe