Opened 10 years ago

Closed 10 years ago

#10812 closed defect (duplicate)

the certify=True option causes Graph.is_isomorphic to crash

Reported by: fwellen Owned by: somebody
Priority: major Milestone: sage-duplicate/invalid/wontfix
Component: graph theory Keywords: Graph isomorphism
Cc: Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description

Here are two isomorphic multi-graphs, that are recognized by is_isomorphic as being isomorphic and cause is_isomorphic to crash on certify=True. (Sage-4.6 from source on 64bit-Fedora)

sage: G = Graph(multiedges = True, loops = True)
sage: H = Graph(multiedges = True, loops = True)
sage: G.add_edges([(0,1,0),(1,0,1),(1,1,2),(0,0,3)])
sage: H.add_edges([(0,1,3),(1,0,2),(1,1,1),(0,0,0)])
sage: G.is_isomorphic(H, certify=True)
---------------------------------------------------------------------------                                                                                                                          
KeyError                                  Traceback (most recent call last)                                                                                                                          
                                                                                                                                                                                                     
/home/felix/sage-4.6/<ipython console> in <module>()                                                                                                                                                 
                                                                                                                                                                                                     
/home/felix/sage/local/lib/python2.6/site-packages/sage/graphs/generic_graph.pyc in is_isomorphic(self, other, certify, verbosity, edge_labels)                                                      
  14135             isom_trans = {}                                                                                                                                                                  
  14136             for v in isom:
> 14137                 isom_trans[self_vertices[v]] = G2_to[isom[v]]
  14138             return True, isom_trans
  14139 

KeyError: 0

Change History (3)

comment:1 Changed 10 years ago by ncohen

Even when #10516 is applied ?

Nathann

comment:2 Changed 10 years ago by rlm

Fixed by #10549.

comment:3 Changed 10 years ago by rlm

  • Milestone changed from sage-4.7 to sage-duplicate/invalid/wontfix
  • Resolution set to duplicate
  • Status changed from new to closed

Since there is no code here and the issue is fixed by #10549, which has been merged, I'm closing this ticket.

Note: See TracTickets for help on using tickets.