graph isomorphism checking with labeled (or colored) vertices

[Jason Grout]

Hi all,

Is there an easy way to ask if two graphs are isomorphic, respecting
some coloring or labeling of the vertices? I see the is_isomorphic
function lets you respect edge labels, so I guess I could attach a new
vertex to, say, all "blue" vertices, and label each of the edges to this
new vertex as "blue", then ask for edge-preserving isomorphism checking.
But it would be nice if there was a way to do this without modifying
the graph, etc.

Thanks,

Jason

[David Joyner]

On Fri, Jan 6, 2012 at 9:43 AM, Jason Grout <jason...@creativetrax.com> wrote:
> Hi all,
>
> Is there an easy way to ask if two graphs are isomorphic, respecting some
> coloring or labeling of the vertices?  I see the is_isomorphic function lets

I don't know if this is easy or not but here is an idea:
First, suppose you have 2 colors, red and blue. Compute the automorphism gp of
the graph, then look at the stabilizer of the red vertices. Done.
Next, if you have more colors, you compute the stablizer of each
individual color, then take the intersection of all the stabilizers you get.

> you respect edge labels, so I guess I could attach a new vertex to, say, all
> "blue" vertices, and label each of the edges to this new vertex as "blue",
> then ask for edge-preserving isomorphism checking.  But it would be nice if
> there was a way to do this without modifying the graph, etc.
>
> Thanks,
>
> Jason
>

> --
> To post to this group, send an email to sage-...@googlegroups.com
> To unsubscribe from this group, send an email to
> sage-devel+...@googlegroups.com
> For more options, visit this group at
> http://groups.google.com/group/sage-devel
> URL: http://www.sagemath.org

[Nathann Cohen]

And if you accept to sligthly change the graph, you can add a universal vertex v to it. If u is of color red, color edge uv with red, and the same for all vertices. Do this in both graph and all will be fine :-)

Nathann

[Tom Boothby]

Jason,

I've been working with nonisomorphic colorings recently. I use the following:

def canonical_coloring_label(G,c):
"""
Given a coloring dictionary,

{color1 : [u1, u2, ...], color2 : [v1, v2, ... ], ... }

return a string which uniquely identifies the isomorphism
class of the coloring.

"""
H = G.copy()
for i in c:
H.add_edges([(i,j) for j in c[i]])
P = [G.vertices(), c.keys()]
return H.canonical_label(partition=P).graph6_string()

I agree, it'd be nice to not have to do this. I've been talking with
Robert Miller to use the new canonical augmentation code to generate
nonisomorphic colorings.

With colorings, embeddings, and matchings, I wonder: should we create
classes to represent these objects instead of passing around naked
data structures? Then, it would make a lot of sense to have things
like coloring1.is_isomorphic(coloring2).

[Volker Braun]

I had this problem a few weeks ago. Sage is already set up to check isomorphism of edge-labeled graphs, but I needed vertex-labeled graphs. It turns out that Robert Miller also implemented vertex-labeled isomorphism testing but it is not exposed in the is_isomorphic() method. But if you are willing to dig into the internals then you can actually check vertex-labeled isomorphisms, too.

Here is how it works (slightly edited version of an email that I sent to Robert to clarify): Testing isomorphism for vertex-labeled graphs is implemented in 

sage/groups/perm_gps/partn_ref/refinement_graphs.pyx

but not exposed by the is_isomorphic() method. Specifically, there is

def isomorphic(G1, G2, partn, ordering2, dig, use_indicator_function, sparse=False):

You have to specify the vertex labels by partitioning the vertices; the partn is a partition of range(n) for the vertices of G1. The ordering2 list is how the vertices of G2 are mapped to range(n) in the partition partn. Note that it is not unique, at least not as long as the partition is not the discrete partition. It is ok to just use any numbering of the vertices of G2.

[Dima Pasechnik]

Attach a loop to every vertex and colour these loops appropriately (a loop is an edge – otherwise it's a bug, IMHO).

This gives you an edge colouring.

[Dima Pasechnik]

On Friday, 6 January 2012 22:57:24 UTC+8, David Joyner wrote:

On Fri, Jan 6, 2012 at 9:43 AM, Jason Grout <jason...@creativetrax.com> wrote:
> Hi all,
>
> Is there an easy way to ask if two graphs are isomorphic, respecting some
> coloring or labeling of the vertices?  I see the is_isomorphic function lets

I don't know if this is easy or not but here is an idea:
First, suppose you have 2 colors, red and blue. Compute the automorphism gp of
the graph, then look at the stabilizer of the red vertices. Done.

this might be horribly inefficient.

 

Next, if you have more colors, you compute the stablizer of each
individual color, then take the intersection of all the stabilizers you get.

and this is even worse...

[Jason Grout]

On 1/6/12 11:35 PM, Dima Pasechnik wrote:
> Attach a loop to every vertex and colour these loops appropriately (a

> loop is an edge � otherwise it's a bug, IMHO).

> This gives you an edge colouring.

Ah, right, I forgot about loops. Thanks to everyone with workarounds.
If we end up doing this project, I'll probably look at adding a switch
for vertex labels.

Thanks,

Jason