Boost logo

Boost :

From: Vladimir Prus (ghost_at_[hidden])
Date: 2001-06-27 02:54:52

On Tuesday 26 June 2001 21:11, Jeremy Siek wrote:
> On Tue, 26 Jun 2001, Vladimir Prus wrote:
> ghost> 3. Algorithms.
> ghost> Should be more of them. E.g. I would like to see Hopcroft's
> minimization ghost> algorithm and isomorphism algorithm. Fortunately, new
> algorithm can be ghost> plugged as they are written, so this issue is not
> very important.
> BGL has an isomorphism algorithm. The algorithm used is not the best, but
> it is good for many situations. The best algorithm is the one used by the
> "nauty" implementation, and is quite complex. I've made a stab at
> converting this algorithm, but ran out of time.

I may be wrong, but I think that automata isomorphism can be implemented much
more efficiently than graph isomorphism. The fact that edges are maked with
transition symbols considerably decreases degree of freedom -- once
correspondence between two vertices is established (e.g. between initial
states) there's but one possible correspondence between successors.
Therefore, two "parallel" dfs are sufficient to find if automata are


Boost list run by bdawes at, gregod at, cpdaniel at, john at