Bug in is_isomorphic for multigraphs !

[nathanncohen]

In order to test for isomorphism of multigraphs, multiple edges are converted to labeled edges whose label encodes the multiplicity.
Yeah. But if, on the other side, we chose to ignore edge labels for isomorphism then the information of multiplicity vanishes !

The bug has been reported by Stavros Garoufalidis.

sage: g = Graph([(0, 0, 0), (0, 2, 0), (1, 1, 0), (1, 2, 0), (1, 2, 1), (2, 2, 0)])                                                                                                                                                                                  
sage: gg = Graph([(0, 0, 0), (0, 1, 0), (1, 1, 0), (1, 2, 0), (2, 2, 0), (2, 2, 1)])                                                                                                                                                                                 
sage: g.is_isomorphic(gg)
True

Nathann

CC: @rlmill @dcoudert

Component: graph theory

Author: Nathann Cohen

Reviewer: David Coudert

Merged: sage-5.3.beta2

Issue created by migration from https://trac.sagemath.org/ticket/13114

[jdemeyer]

comment:2

Attachment: trac_13114.patch.gz

Please fill in your real name as Author.

[dcoudert]

comment:3

Nathann is far away so I fill it for him.

[dcoudert]

Author: Nathann Cohen

[dcoudert]

comment:4

I did the following test, among others:

sage: g = Graph([(0, 0, 0), (0, 2, 0), (1, 1, 0), (1, 2, 0), (1, 2, 1), (2, 2, 0)])
sage: gg = Graph([(0, 0, 0), (0, 1, 0), (1, 1, 0), (1, 2, 0), (2, 2, 0), (2, 2, 1)])
sage: g.is_isomorphic(gg)
False
sage:
sage: G = graphs.RandomGNP(10,.2)
sage: H = Graph()
sage: H.allow_multiple_edges(True)
sage: for u,v in G.edges(labels=None):
    H.add_edge(u,v,{'l':1})
    H.add_edge(u,v,{'k':2})
....:     
sage: I = Graph()
sage: I.allow_multiple_edges(True)
sage: for u,v in G.edges(labels=None):
    I.add_edge(u,v,1)
    I.add_edge(u,v,2)
....:     
sage: I.is_isomorphic(G)
False
sage: I.is_isomorphic(H)
True
sage: I.is_isomorphic(H, edge_labels=True)
(False, False)
sage: I = H.copy()
sage: I.is_isomorphic(H, edge_labels=True)
True
sage: I.edges()
[(0, 1, {'k': 2}), (0, 1, {'l': 1}), (0, 8, {'k': 2}), (0, 8, {'l': 1}), (1, 4, {'k': 2}), (1, 4, {'l': 1}), (3, 9, {'k': 2}), (3, 9, {'l': 1}), (5, 6, {'k': 2}), (5, 6, {'l': 1}), (6, 8, {'k': 2}), (6, 8, {'l': 1}), (7, 8, {'k': 2}), (7, 8, {'l': 1}), (7, 9, {'k': 2}), (7, 9, {'l': 1})]
sage: I.delete_edge(0,1)
sage: I.edges()
[(0, 1, {'l': 1}), (0, 2, {'k': 2}), (0, 2, {'l': 1}), (0, 8, {'k': 2}), (0, 8, {'l': 1}), (0, 9, {'k': 2}), (0, 9, {'l': 1}), (1, 3, {'k': 2}), (1, 3, {'l': 1}), (1, 4, {'k': 2}), (1, 4, {'l': 1}), (2, 5, {'k': 2}), (2, 5, {'l': 1}), (2, 6, {'k': 2}), (2, 6, {'l': 1}), (2, 8, {'k': 2}), (2, 8, {'l': 1}), (5, 6, {'k': 2}), (5, 6, {'l': 1}), (6, 8, {'k': 2}), (6, 8, {'l': 1})]
sage: I.add_edge(0,1,{'x':2})
sage: I.is_isomorphic(H)
True
sage: I.is_isomorphic(H, edge_labels=True)
(False, False)

For me the patch is working correctly. Build OK, functionality OK, long tests OK, docbuild OK.
So I give positive review !

[dcoudert]

Reviewer: David Coudert

[jdemeyer]

Merged: sage-5.3.beta2