Bug in is_isomorphic for multigraphs !

[ncohen]

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

[jdemeyer]

Please fill in your real name as Author.

[dcoudert]

Nathann is far away so I fill it for him.

[dcoudert]

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 !