Re: [boost] Re: Automata Library

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2001-06-01 08:49:08

On Fri, 1 Jun 2001, Vladimir Prus wrote:
ghost>
ghost> I am very sceptical about this idea. After all, automaton
ghost> should do one thing -- perform transition, and do it fast,
ghost> whereas traversing adjacent vertices may be slow or not
ghost> supported. This is quite different from graph. Unless I'm
ghost> shown an implementation doing both tasks equally well, I
ghost> won't belive such can be written.

Perhaps you don't understand what I'm suggesting. When I was browsing
through the ASTL source code, I saw a function named astl_copy_breadth()
which includes code that looks like this:

// Iterating on from1 outgoing transitions:
DFA1::Edges edges = dfa1.delta2(from1);
for(trans_it = edges.begin(), trans_end = edges.end();
    trans_it != trans_end; ++trans_it)
{
  to1 = (*trans_it).second;
  ...
}

To me this looks exactly like traversing a graph... so it would make sense
to use the graph interface we have all agreed on. That way when people are
reading the code, they can see a familiar interface instead of trying to
learn a new one. I'm guessing, but converting to the BGL interface might
look like this:

for (tie(trans_it, trans_end) = out_edges(from1, dfa1);
     trans_it != trans_end; ++trans_it)
{
  to1 = target(*trans_it, dfa1);
  ...
}

Who knows, maybe the astl_copy_breadth() could even be implemented by the
copy_graph() function in the BGL.

Cheers,
Jeremy

----------------------------------------------------------------------
 Jeremy Siek                        www: http://www.lsc.nd.edu/~jsiek/
 Ph.D. Candidate, IU B'ton          email: jsiek_at_[hidden]
 Summer Manager, AT&T Research      phone: [phone]
----------------------------------------------------------------------