Opened 7 years ago

Closed 6 years ago

#13114 closed defect (fixed)

Bug in is_isomorphic for multigraphs !

Reported by: ncohen Owned by: jason, ncohen, rlm
Priority: major Milestone: sage-5.3
Component: graph theory Keywords:
Cc: rlm, dcoudert Merged in: sage-5.3.beta2
Authors: Nathann Cohen Reviewers: David Coudert
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by 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

Attachments (1)

trac_13114.patch (4.7 KB) - added by ncohen 7 years ago.

Download all attachments as: .zip

Change History (6)

comment:1 Changed 7 years ago by ncohen

  • Cc dcoudert added
  • Description modified (diff)
  • Status changed from new to needs_review
  • Summary changed from Bug in is_isomorphic with unlabelled multiple edges ! to Bug in is_isomorphic for multigraphs !

Changed 7 years ago by ncohen

comment:2 Changed 6 years ago by jdemeyer

Please fill in your real name as Author.

comment:3 Changed 6 years ago by dcoudert

  • Authors set to Nathann Cohen

Nathann is far away so I fill it for him.

comment:4 Changed 6 years ago by dcoudert

  • Reviewers set to David Coudert
  • Status changed from needs_review to positive_review

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 !

comment:5 Changed 6 years ago by jdemeyer

  • Merged in set to sage-5.3.beta2
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.