Opened 10 years ago

Closed 10 years ago

#10495 closed defect (duplicate)

is_isomorphic returns False for isomorphic multigraphs

Reported by: fwellen Owned by: jason, ncohen, rlm
Priority: major Milestone: sage-duplicate/invalid/wontfix
Component: graph theory Keywords: multigraph
Cc: Merged in:
Authors: Mike Hansen Reviewers: Nathann Cohen
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description

The method 'Graph.is_isomorphic' returns False for isomorphic graphs with multiple edges. 

sage: g = Graph( loops=True, multiedges=True )
sage: h = Graph( loops=True, multiedges=True )
sage: g.add_edges([(0,0,1)])
sage: h.add_edges([(1,1,1)])
sage: g.is_isomorphic(h)
False

Attachments (2)

trac_10495.patch​ (1.9 KB) - added by mhansen 10 years ago.
trac_10495.2.patch​ (1.4 KB) - added by ncohen 10 years ago.

Download all attachments as: .zip

Change History (12)

comment:1 Changed 10 years ago by fwellen

  • Summary changed from is_isomorphic returns FALSE for isomorphic multigraphs to is_isomorphic returns False for isomorphic multigraphs

Changed 10 years ago by mhansen

comment:2 Changed 10 years ago by mhansen

  • Authors set to Mike Hansen
  • Status changed from new to needs_review

comment:3 Changed 10 years ago by ncohen

  • Reviewers set to Nathann Cohen
  • Status changed from needs_review to positive_review

I was a bit worried this fixing would change the result of other doctests, but it passed a -testall -long (short of unrelated errors).... Positive review, and thank you for your patch ! :-)

Nathann

comment:4 Changed 10 years ago by jdemeyer

  • Milestone changed from sage-4.6.1 to sage-4.6.2

comment:5 Changed 10 years ago by jdemeyer

  • Status changed from positive_review to needs_work

Needs to be rebased to sage-4.6.2.alpha0, I get the following patch output:: 

patching file sage/graphs/base/c_graph.pyx
Hunk #1 FAILED at 1749.
Hunk #2 FAILED at 1762.
2 out of 2 hunks FAILED -- saving rejects to file sage/graphs/base/c_graph.pyx.rej
patching file sage/graphs/generic_graph.py
Hunk #1 succeeded at 14627 (offset 572 lines).

comment:6 Changed 10 years ago by ncohen

  • Status changed from needs_work to needs_review

I rebased the patch and fixed the first failure, though oddly the changes brought by the second one are already present in apha0... :-)

Mike, could you check this new patch ?

Nathann

Changed 10 years ago by ncohen

comment:7 Changed 10 years ago by ncohen

ping ? :-)

comment:8 Changed 10 years ago by ncohen

This does not happen anymore with a 4.7.rc0 and #10549 applied .... So as it is several months old, can it be closed ? :-)

Nathann

comment:9 Changed 10 years ago by jdemeyer

  • Milestone changed from sage-4.7 to sage-duplicate/invalid/wontfix
  • Status changed from needs_review to positive_review

Duplicate of #10549.

comment:10 Changed 10 years ago by jdemeyer

  • Resolution set to duplicate
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.