Opened 7 years ago
Closed 7 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 )
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)
Change History (6)
comment:1 Changed 7 years ago by
- 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
comment:2 Changed 7 years ago by
comment:4 Changed 7 years ago by
- 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 7 years ago by
- 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.
Please fill in your real name as Author.