# Boost Users :

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