Re: [boost] BGL

From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2001-12-11 15:24:55

Another way to solve this problem is to create a set of all nodes
reachable from the starting node using only epsilon edges (as is done in
the conversion from a nondeterministic finite automaton to a deterministic
one).  This set can be created using a depth-first search whose visitor
writes each node visited into a vector, and which only follows edges that
have the epsilon property.  Then, iterate through each out edge of each
node in this vector.  This can be done with two for loops, without
requiring a function object for the body of the loop.  This algorithm also
has the feature that it only iterates through the out edges of each node
once, even if there are multiple epsilon-edge paths from the starting node
to it.

                                                        Jeremiah Willcock

On Tue, 11 Dec 2001, Jeremy Siek wrote:

> I see two approaches to solving this problem, one is an algorithmic
> solution, and the other is an iterator adaptor solution.
>
> The algorithmic solution is easy to implement, but the usage is more
> cumbersome since you have to put the body of your loop into a function
> object.
>
> // Algorithm approach
> template <typename Graph, typename Function, typename IsEpsilonMap>
> void for_all_eps_out_edges
>   (typename graph_traits<Graph>::vertex_descriptor v,
>    const Graph& g, Function f, IsEpsilonMap is_eps)
> {
>   for (tie(out, out_end) = out_edges(v, g); out != out_end; ++out)
>     if (get(is_eps, *out))
>       for_all_eps_out_edges(target(*out, g), g, is_eps);
>     else
>       f(*out);
> }
>
> The iterator adaptor solution is more difficult to implement, so I'll just
> outline the idea, but the user interface would be slick, pretty much
> transparent. You create an iterator adaptor that internally keeps a stack
> of out_edge_iterator pairs. When the current top iterator hits an epsilon
> out-edge, you look at the target and push its begin/end out-edge iterators
> on to the stack. When the current iterator reaches the end, then you pop
> from the stack. As I said, this would be pretty tricky (read time
> consuming) to implement. Also, this will probably be a bit slower than the
> algorithmic approach.
>
> Cheers,
> Jeremy
>
> On Tue, 11 Dec 2001, William Eidson wrote:
>
> > Newbie question on the bgl.
> >
> > I have been studying the library and see it as a very powerful tool.  My question is about implementing a concept know as an epsilon arc or a free transition edge.
> >
> > Conceptually, when iterating an out-edges collection from a vertex, there maybe edges with property type of epsilon.  Which causes it to jump imediately into the out edges of the conected vertex.
> >
> > Does anybody have any clues about how to proceed?
> >
> > Thanks in advance
> >
> > Bill Eidson
> >
>
> ----------------------------------------------------------------------
>  Jeremy Siek                          http://www.osl.iu.edu/~jsiek/
>  Ph.D. Student, Indiana Univ. B'ton   email: jsiek_at_[hidden]
>  C++ Booster (http://www.boost.org)   office phone: [phone]
> ----------------------------------------------------------------------
>
>
>
> Info: http://www.boost.org  Send unsubscribe requests to: <mailto:boost-unsubscribe_at_[hidden]>
>
> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
>
>
>