#13114: Bug in is_isomorphic for multigraphs !
---------------------------------+------------------------------------------
Reporter: ncohen | Owner: jason, ncohen, rlm
Type: defect | Status: positive_review
Priority: major | Milestone: sage-5.3
Component: graph theory | Resolution:
Keywords: | Work issues:
Report Upstream: N/A | Reviewers: David Coudert
Authors: Nathann Cohen | Merged in:
Dependencies: | Stopgaps:
---------------------------------+------------------------------------------
Changes (by dcoudert):
* status: needs_review => positive_review
* reviewer: => David Coudert
Comment:
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 !
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13114#comment:4>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
