Re: [Boost-users] Graph Isomorphism

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