On Thu, 23 Jun 2011, Evan Driscoll wrote:
On 06/23/2011 12:52 PM, Evan Driscoll wrote:
I'm still struggling with the edge label restrictions as well. The only way I can think of to incorporate them is to make sure that the set of labels from corresponding nodes is the same: but that's insufficient:
A B (q0) ---------> ((q1)) (p0) ------------> ((p1)) | | | B | A | | V V (q2) (p2)
These automata are not isomorphic; they don't even have the same language. But if you can only look at each vertex and the edges that are incident on it, it looks like it is.
Actually I lied; you can tell in that case, since q1 <--> p1 by the isomorphism, but the edges incident on q1 is just A and those incident on p1 is just B.
They are isomorphic as graphs, so your original claim was right I think. It looks like edge labels would be difficult to add to the current isomorphism algorithm, though. You could probably get some of the way there by changing the std::vector on line 154 of isomorphism.hpp (in SVN HEAD) to an std::map and passing in a map for invariant1 that returns the sorted list of outgoing edge labels from each vertex. You will probably also need some code to compare the edge labels between two vertices that the algorithm claims should match. That will not handle the more complicated example you put efficiently, though. You would also want to make the DFS order the outgoing edges of each vertex by their labels; there may be other things you need to do as well. I think for now you would be better off rewriting the algorithm, possibly based on the existing one. Contributing it back to BGL would be appreciated if you end up going that way. -- Jeremiah Willcock