Re: [Boost-users] Graph Isomorphism

Subject: Re: [Boost-users] Graph Isomorphism
From: Evan Driscoll (driscoll_at_[hidden])
Date: 2011-06-23 14:08:10

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.

But this works to illustrate my point:

          A                              B
  (q0) ---------> ((q1))       (p0) ------------> ((p1))
   |                /\           |                  /\
   | B               |           | A                |
   |                 | B         |                  | A
   V                 |           V                  |
  (q2)             (q3)         (p2)               (p4)
   /\                            /\
   |                             |
   | A                           | B
   |                             |
  (q4)                          (p3)

q0, p0 both have no incoming and one A and one B outgoing
q1, p1 both have one A and one B incoming and no outgoing
q2, p2 both have one A and one B incoming and no outgoing
q3, p3 both have one B outgoing and no incoming
q4, p4 both have one A outgoing and no incoming

Evan