
Boost Users : 
Subject: Re: [Boostusers] Graph Isomorphism
From: Evan Driscoll (driscoll_at_[hidden])
Date: 20110623 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
Boostusers list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net