Opened 10 years ago

Closed 10 years ago

# Bug in is_isomorphic for multigraphs !

Reported by: Owned by: ncohen jason, ncohen, rlm major sage-5.3 graph theory rlm, dcoudert sage-5.3.beta2 Nathann Cohen David Coudert N/A

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

### comment:1 Changed 10 years ago by ncohen

• 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 !

### comment:3 Changed 10 years ago by dcoudert

• Authors set to Nathann Cohen

Nathann is far away so I fill it for him.

### comment:4 Changed 10 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):
....:
sage: I = Graph()
sage: I.allow_multiple_edges(True)
sage: for u,v in G.edges(labels=None):
....:
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.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 10 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.