Boost logo

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


Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at