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