Opened 8 months ago

Closed 8 months ago

#33902 closed defect (duplicate)

bug in 'tedder' modular decomposition

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

Status badges

Description (last modified by dimpase)

in #26496 a simple implementation of modular decomposition was added, but no explicit example showing that 'tedder' is buggy. (PS - but see #25872) An example is now posted on sage-devel:

https://groups.google.com/d/msgid/sage-devel/4df9a528-ca41-4f71-9c7e-3543047b9c05n%40googlegroups.com

sage:     d = {
....:         1  :  [2, 3, 4],
....:         2  :  [1, 3, 4],
....:         3  :  [1, 2, 4],
....:         4  :  [1, 2, 3, 5],
....:         5  :  [10, 4, 6, 7, 8, 9],
....:         6  :  [5, 7],
....:         7  :  [5, 6, 8, 9],
....:         8  :  [5, 7, 9],
....:         9  :  [10, 5, 7, 8],
....:         10  :  [5, 9]
....:     }
....:     g = Graph(d)
sage: g.modular_decomposition(algorithm='tedder') # --- wrong ?!
(PRIME, [5, (SERIES, [9, (PARALLEL, [10, 7, 8, 6])]), 4, (SERIES, [3, 2, 1])])
sage: g.modular_decomposition(algorithm='habib')
(PRIME, [5, 4, (SERIES, [1, 2, 3]), (PRIME, [9, 7, 6, 8, 10])])

Change History (5)

comment:1 Changed 8 months ago by dimpase

Description: modified (diff)

comment:2 Changed 8 months ago by dcoudert

Since we remove algorithm 'tedder' in #25872, we can move this ticket to wontfix.

comment:3 Changed 8 months ago by dimpase

Milestone: sage-9.7sage-duplicate/invalid/wontfix
Status: newneeds_review

will be fixed in #25872

comment:4 Changed 8 months ago by dimpase

Reviewers: Dima Pasechnik
Status: needs_reviewpositive_review

comment:5 Changed 8 months ago by chapoton

Resolution: duplicate
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.