Hi Robert!
Thank you, very nice! However, playing around with this, also in the setting of
crystals,
I came across the following bug:
sage: D = digraphs.RandomDirectedGNP(10, .2)
sage: E = digraphs.RandomDirectedGNP(10, .2)
sage: D.is_isomorphic(E, certify=True, edge_labels=True)
(False, None)
sage: D.is_isomorphic(D, certify=True, edge_labels=True)
---------------------------------------------------------------------------
KeyError Traceback (most recent call last)
/Users/anne/<ipython console> in <module>()
/Applications/sage/local/lib/python2.6/site-packages/sage/graphs/generic_graph.pyc
in is_isomorphic(self, other, certify, verbosity, edge_labels)
14125 isom_trans = {}
14126 for v in isom:
> 14127 isom_trans[self_vertices[v]] = G2_to[isom[v]]
14128 return True, isom_trans
14129
KeyError: 0
sage: B1 = CrystalOfTableaux(['A',2],shape=[1])
sage: B2 = CrystalOfTableaux(['A',2],shape=[2])
sage: T = TensorProductOfCrystals(B1,B2,
generators=[[B1.module_generators[0],B2.module_generators[0]]])
sage: TT = TensorProductOfCrystals(B2,B1,
generators=[[B2.module_generators[0],B1.module_generators[0]]])
sage: T.digraph().is_isomorphic(TT.digraph())
True
sage: T.digraph().is_isomorphic(TT.digraph(), edge_labels = True)
True
sage: T.digraph().is_isomorphic(TT.digraph(), certify = True, edge_labels =
True)
---------------------------------------------------------------------------
KeyError Traceback (most recent call last)
/Applications/sage-4.6/devel/sage-combinat/sage/categories/<ipython console> in
<module>()
/Applications/sage/local/lib/python2.6/site-packages/sage/graphs/generic_graph.pyc
in is_isomorphic(self, other, certify, verbosity, edge_labels)
14125 isom_trans = {}
14126 for v in isom:
> 14127 isom_trans[self_vertices[v]] = G2_to[isom[v]]
14128 return True, isom_trans
14129
KeyError: 0
sage: T.digraph().is_isomorphic(TT.digraph(), certify = True)
---------------------------------------------------------------------------
KeyError Traceback (most recent call last)
/Applications/sage-4.6/devel/sage-combinat/sage/categories/<ipython console> in
<module>()
/Applications/sage/local/lib/python2.6/site-packages/sage/graphs/generic_graph.pyc
in is_isomorphic(self, other, certify, verbosity, edge_labels)
14125 isom_trans = {}
14126 for v in isom:
> 14127 isom_trans[self_vertices[v]] = G2_to[isom[v]]
14128 return True, isom_trans
14129
KeyError: 0
Do you know what the problem might be?
I think for the moment I won't need colored vertices, just colored edges.
Best,
Anne
On 12/17/10 3:55 AM, Robert Miller wrote:
Anne,
The digraphs in sage also have isomorphism/automorphism groups
implemented. The pointer William gave you is for undirected graphs,
but if you go up a level you see much more generality...
sage: D = digraphs.RandomDirectedGNP(10, .2)
sage: E = digraphs.RandomDirectedGNP(10, .2)
sage: D.is_isomorphic(E, certify=True, edge_labels=True)
(False, None)
This will allow you to detect isomorphism with colored edges, and if
you want isomorphism with colored vertices, you need to do:
sage: D.canonical_label(partition=[range(10)], certify=True)
(Digraph on 10 vertices, {0: 0, 1: 8, 2: 1, 3: 5, 4: 9, 5: 3, 6: 6, 7:
2, 8: 4, 9: 7})
sage: E.canonical_label(partition=[range(10)], certify=True)
(Digraph on 10 vertices, {0: 9, 1: 4, 2: 3, 3: 8, 4: 7, 5: 6, 6: 0, 7:
2, 8: 5, 9: 1})
The partition specifies the vertex colors (ordering of the blocks
matters!) and certify gives you the explicit map from the digraph to
its canonical label. Isomorphism only holds if the returned digraphs
are equal. (Inputting a partition to is_isomorphic isn't implemented,
but wouldn't be too hard to do -- if people are really interested, I
can implement a patch.)
--
You received this message because you are subscribed to the Google Groups
"sage-combinat-devel" group.
To post to this group, send email to sage-combinat-de...@googlegroups.com.
To unsubscribe from this group, send email to
sage-combinat-devel+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/sage-combinat-devel?hl=en.
