# Boost Users :

Subject: Re: [Boost-users] Graph Isomorphism
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2011-06-23 22:01:41

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