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; }

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

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 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

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