What is the effect of "edge_labels=True" on is_isomorphic?
Nikos Apostolakis
After reading the doc string of "is_isomorphic" I thought that for two
edge-labelled graphs g,h, g.is_isomorphic(h, edge_labels=True) would be
true exactly when there is a label preserving isomorphism between the two
graphs. However:
sage: foo.edges()
[(0, 1, 2), (0, 2, 1), (2, 3, 3)]
sage: bar.edges()
[(0, 1, 1), (0, 2, 2), (2, 3, 3)]
sage: bar.is_isomorphic(foo, edge_labels = True)
True
So what is the effect of "edge_labels = True"? Or is this a bug? Is
there a way in sage to check whether two edge-labelled trees are
isomorphic?
TIA,
Nikos
Nathan Carter
>
> sage: foo.edges()
> [(0, 1, 2), (0, 2, 1), (2, 3, 3)]
> sage: bar.edges()
> [(0, 1, 1), (0, 2, 2), (2, 3, 3)]
> sage: bar.is_isomorphic(foo, edge_labels = True)
> True
I think there is a label-preserving isomorphism here, isn't there?
0->0 1->2 2->1 3->3
Nathan
Nikos Apostolakis
No, this is not an isomorphism. The output of foo.edges() gives the
edges as triples, the first two slots are the vertices the edge is
incident to and the third slot is the label of the edge. So,foo looks
like this: ( I hope the formating is preserved)
2 1 3
1 ----- 0 ----- 2 ----- 3
OTOH bar looks like this:
1 2 3
1 ----- 0 ----- 2 ----- 3
Clearly there is no isomorphism sending vertex 1 to vertex 2.
Actually there is only one non-trivial automorphism of this
graph 0 <--> 2 , 1 <--> 3. sage knows this:
sage: foo.automorphism_group()
Permutation Group with generators [(1,3)(2,4)]
BTW, shouldn't the generator of the automorphism group be presented
as "(0,2)(1,3)"?
Best,
Nikos
Robert Miller
> as "(0,2)(1,3)"?
GAP's permutation groups don't allow you to permute on the letter 0.
See the translation option of automorphism_group on that... This has
been a pain in the butt since day 1. Your "0" is probably the "4".
> >> sage: foo.edges()
> >> [(0, 1, 2), (0, 2, 1), (2, 3, 3)]
> >> sage: bar.edges()
> >> [(0, 1, 1), (0, 2, 2), (2, 3, 3)]
> >> sage: bar.is_isomorphic(foo, edge_labels = True)
> >> True
return True if and only if there is a label-preserving isomorphism, as
it does in your example in Sage 3.2.2:
----------------------------------------------------------------------
| Sage Version 3.2.2, Release Date: 2008-12-18 |
| Type notebook() for the GUI, and license() for information. |
----------------------------------------------------------------------
sage: foo = Graph()
sage: bar = Graph()
sage: foo.add_edges([(0,1,2),(0,2,1),(2,3,3)])
sage: bar.add_edges([(0,1,1),(0,2,2),(2,3,3)])
[(0, 1, 2), (0, 2, 1), (2, 3, 3)]
sage: bar.edges()
[(0, 1, 1), (0, 2, 2), (2, 3, 3)]
sage: bar.is_isomorphic(foo, edge_labels=True)
> 2 1 3
> 1 ----- 0 ----- 2 ----- 3
>
> OTOH bar looks like this:
>
> 1 2 3
> 1 ----- 0 ----- 2 ----- 3
sage: foo.plot(edge_labels=True)
Nikos Apostolakis
>> BTW, shouldn't the generator of the automorphism group be presented
>> as "(0,2)(1,3)"?
>
> Good luck ever convincing the right systems that this should happen:
> GAP's permutation groups don't allow you to permute on the letter 0.
> See the translation option of automorphism_group on that... This has
> been a pain in the butt since day 1. Your "0" is probably the "4".
>
>> >> sage: foo.edges()
>> >> [(0, 1, 2), (0, 2, 1), (2, 3, 3)]
>> >> sage: bar.edges()
>> >> [(0, 1, 1), (0, 2, 2), (2, 3, 3)]
>> >> sage: bar.is_isomorphic(foo, edge_labels = True)
>> >> True
>
> Which version of Sage are you using?
I tried this in a Sage 3.1.1 and in Sage 3.1.2
> The edge_labels option should return True if and only if there is a
> label-preserving isomorphism, as it does in your example in Sage
> 3.2.2:
>
> ----------------------------------------------------------------------
> | Sage Version 3.2.2, Release Date: 2008-12-18 |
> | Type notebook() for the GUI, and license() for information. |
> ----------------------------------------------------------------------
> sage: foo = Graph()
> sage: bar = Graph()
> sage: foo.add_edges([(0,1,2),(0,2,1),(2,3,3)])
> sage: bar.add_edges([(0,1,1),(0,2,2),(2,3,3)])
> sage: foo.edges()
> [(0, 1, 2), (0, 2, 1), (2, 3, 3)]
> sage: bar.edges()
> [(0, 1, 1), (0, 2, 2), (2, 3, 3)]
> sage: bar.is_isomorphic(foo, edge_labels=True)
> False
Great! I'll upgrade and hopefully everything will be fine. Thanks.
>> 2 1 3
>> 1 ----- 0 ----- 2 ----- 3
>>
>> OTOH bar looks like this:
>>
>> 1 2 3
>> 1 ----- 0 ----- 2 ----- 3
>
> You probably know, but you can do:
>
> sage: foo.plot(edge_labels=True)
>
Yeah, I know that but I kinda like ascii art :).
Thanks,
Nikos
Nikos Apostolakis
> Robert Miller <rlmil...@gmail.com> writes:
[...]
>> The edge_labels option should return True if and only if there is a
>> label-preserving isomorphism, as it does in your example in Sage
>> 3.2.2:
[...]
>
> Great! I'll upgrade and hopefully everything will be fine. Thanks.
>
I updated to 2.3.3 and is_isomorphic now works as expected. Thanks.
I still have some problems, with how sage treats graphs. For example:
sage: foo = Graph()
sage: foo.add_edges([(0, 1, 1), (0, 2, 2)])
sage: bar = Graph()
sage: bar.add_edges([(0, 1, 2), (0, 2, 1)])
sage: boo = [foo, bar]
sage: boo.remove(bar);
At this point, I would expect boo to have only one element namely foo.
However:
sage: boo[0].edges()
sage: [(0, 1, 2), (0, 2, 1)]
So it seems that instead of foo, bar was remoned. It appears that
the remove method thinks that foo and bar are the same, so when
asked to remove bar it removes foo, which it considers to be the
first appearance of bar! This is rather confusing.
Thanks,
Nikos
Robert Miller
sage: foo = Graph()
sage: foo.add_edges([(0, 1, 1), (0, 2, 2)])
sage: bar = Graph()
sage: bar.add_edges([(0, 1, 2), (0, 2, 1)])
True
sage: foo.weighted(True)
sage: foo == bar
True
sage: bar.weighted(True)
sage: foo == bar
False
If one graph isn't considered weighted, but the other is, Sage can
still return True. I've fixed this in ticket #5003.