Opened 3 years ago

Closed 3 years ago

#24898 closed defect (fixed)

wrong relabel handling in modular_decomposition of graphs

Reported by: tmonteil Owned by:
Priority: major Milestone: sage-8.2
Component: graph theory Keywords:
Cc: jlokesh, dimpase, dcoudert Merged in:
Authors: Dima Pasechnik Reviewers: Thierry Monteil
Report Upstream: N/A Work issues:
Branch: c3235d7 (Commits, GitHub, GitLab) Commit: c3235d74d226be93ec5e389b2ac6e77bf6dc71c1
Dependencies: Stopgaps:

Status badges

Description

As reported on this ask question:

sage: G=Graph({1:[2],2:[1]})
sage: G.modular_decomposition()
---------------------------------------------------------------------------
KeyError                                  Traceback (most recent call last)
<ipython-input-5-05fa7ad0eb50> in <module>()
----> 1 G.modular_decomposition()

/opt/sagemath/sage-source/local/lib/python2.7/site-packages/sage/graphs/graph.pyc in modular_decomposition(self)
   7185         relabel = lambda x : (x.node_type, [relabel(_) for _ in x.children]) if x.node_type != NodeType.NORMAL else id_label[x.children[0]]
   7186 
-> 7187         return relabel(D)
   7188 
   7189     @doc_index("Graph properties")

/opt/sagemath/sage-source/local/lib/python2.7/site-packages/sage/graphs/graph.pyc in <lambda>(x)
   7183         id_label = dict(enumerate(self.vertices()))
   7184 
-> 7185         relabel = lambda x : (x.node_type, [relabel(_) for _ in x.children]) if x.node_type != NodeType.NORMAL else id_label[x.children[0]]
   7186 
   7187         return relabel(D)

/opt/sagemath/sage-source/local/lib/python2.7/site-packages/sage/graphs/graph.pyc in <lambda>(x)
   7183         id_label = dict(enumerate(self.vertices()))
   7184 
-> 7185         relabel = lambda x : (x.node_type, [relabel(_) for _ in x.children]) if x.node_type != NodeType.NORMAL else id_label[x.children[0]]
   7186 
   7187         return relabel(D)

KeyError: 2

Change History (5)

comment:1 Changed 3 years ago by tmonteil

  • Cc jlokesh dimpase dcoudert added

comment:2 Changed 3 years ago by dimpase

  • Authors set to Dima Pasechnik

removing the leftover from the old implementation fixes the problem. patch coming.

comment:3 Changed 3 years ago by dimpase

  • Branch set to u/dimpase/moddecfix
  • Commit set to c3235d74d226be93ec5e389b2ac6e77bf6dc71c1
  • Status changed from new to needs_review

New commits:

c3235d7removing unneeded and harmful id_labels dict

comment:4 Changed 3 years ago by tmonteil

  • Reviewers set to Thierry Monteil
  • Status changed from needs_review to positive_review

Thanks for being reactive.

comment:5 Changed 3 years ago by vbraun

  • Branch changed from u/dimpase/moddecfix to c3235d74d226be93ec5e389b2ac6e77bf6dc71c1
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.