Re: [boost] BGL

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2001-12-11 15:24:44

One thing more. You may not want to hit the same vertex twice through
epsilon transitions, so one could add a color map to record which vertices
have been seen.

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

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