Re: [boost] BGL

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2001-12-11 14:40:04

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