Opened 4 years ago

Closed 6 months ago

Last modified 6 months ago

#25872 closed defect (fixed)

Modular decomposition bug

Reported by: Jori Mäntysalo Owned by:
Priority: major Milestone: sage-9.7
Component: graph theory Keywords:
Cc: Lokesh Jain, Dima Pasechnik, David Coudert, David Einstein Merged in:
Authors: Dima Pasechnik Reviewers: David Coudert, Matthias Koeppe
Report Upstream: N/A Work issues:
Branch: f610e5a (Commits, GitHub, GitLab) Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by Dima Pasechnik)

sage: G1 = Graph('FwA]w')
sage: G2 = Graph('F@Nfg')
sage: G1.modular_decomposition(algorithm='tedder')
(PRIME, [6, 2, 1, 5, 0, (PARALLEL, [3, 4])])
sage: G2.modular_decomposition(algorithm='tedder')
(PRIME, [6, 5, 0, 2, 3, 1, 4])
sage: G1.is_isomorphic(G2)
True

#24898 was not enough.

This ticket removes 'tedder' implementation, as buggy unfixable abandonware (see #33902 for another example of a bug); the algorithm= option is made into a no-op, to be removed after the deprecation period, as we only have one implementation now.

Change History (34)

comment:1 Changed 4 years ago by David Coudert

That's certainly not an easy issue to fix. I have not clue what's going on :(

comment:2 Changed 4 years ago by Jori Mäntysalo

I don't know if this helps, but I was cross-checking #25763 and it seems that the bug is not visible with

P._hasse_diagram.transitive_closure().to_undirected().is_prime()

where P is any poset. In the internal digraph we have consecutive integers as vertices and 0, 1, ..., n-1 is a topological sort of the digraph.

comment:3 Changed 4 years ago by David Coudert

I tried other labelings of the graph and its working correctly when the first vertex of G.vertex_iterator() is not involved in the parallel node.

sage: G3 = Graph('F|NE?')
sage: G3.modular_decomposition()
(PRIME, [2, (PARALLEL, [5, 6]), 1, 3, 0, 4])

With 'G2', the construction starts from vertex 0 that should be in a parallel node (PARALLEL, [0, 1]). If I add a twin to vertex 4, the new parallel node is detected.

sage: G2.add_edges([(2,7), (3,7)])
sage: G2.modular_decomposition()
(PRIME, [6, 5, 0, 2, 3, 1, (PARALLEL, [4, 7])])

comment:4 Changed 4 years ago by Lokesh Jain

Branch: u/jlokesh/modular_decomposition_bug

comment:5 in reply to:  4 Changed 4 years ago by Lokesh Jain

Commit: b71307dc19b118c8e53aa2ac3ed5880db01b9a9a

I have pushed the changes which were required to fix the bug. The change required was to remove the is_separated field from Node class in modular_decomposition.py. It removes the optimization which was causing the bug.


New commits:

b71307dtrac #25872: Remove is_separated instance variable from Node class in modular_decomposition.py

comment:6 Changed 4 years ago by David Coudert

Thank you Lokesh.

You must add the following tests to the TESTS block of method modular_decomposition to show that the issue is fixed.

Ticket :trac:`25872` is fixed::

    sage: G1 = Graph('FwA]w')
    sage: G2 = Graph('F@Nfg')
    sage: G1.is_isomorphic(G2)
    True
    sage: G1.modular_decomposition()
    (PRIME, [6, 2, 1, 5, 0, (PARALLEL, [3, 4])])
    sage: G2.modular_decomposition()
    (PRIME, [6, 5, (PARALLEL, [0, 1]), 2, 3, 4])
    sage: G2.add_edges([(2,7), (3,7)])
    sage: G2.modular_decomposition()
    (PRIME, [6, 5, (PARALLEL, [0, 1]), 2, 3, (PARALLEL, [4, 7])])

comment:7 Changed 4 years ago by Jori Mäntysalo

Still doesn't work.

sage: a = Graph('PdDoIHG?o@OeC?_BsWCSsI?c')
sage: b = a.canonical_label()
sage: a.is_prime(), b.is_prime()
(True, False)

Found by

set_random_seed(0)
for i in xrange(10^3):
    G1 = graphs.RandomGNP(17, 0.3)
    G2 = G1.canonical_label()
    if G1.is_prime() != G2.is_prime():
        print(i)
        G1.show()
        break
else:
    print("OK")
Last edited 4 years ago by Jori Mäntysalo (previous) (diff)

comment:8 Changed 4 years ago by git

Commit: b71307dc19b118c8e53aa2ac3ed5880db01b9a9a672a1103fbc56f550a664485487a2acbc24b438a

Branch pushed to git repo; I updated commit sha1. New commits:

672a110trac #25872: Added tests in graph.py#modular_decomposition

comment:9 in reply to:  7 Changed 4 years ago by Lokesh Jain

Replying to jmantysalo:

Still doesn't work.

Thanks for posting the example. Let me take a look.

comment:10 Changed 4 years ago by David Einstein

Cc: David Einstein added

A few questions.

Would it be of use to add an algorithm parameter to modular_decomposition and is_prime? I have code for the O(n3) algorithm of [Habib and Maurer 1979] that is probably slower than the current code, but seems to work. Should I attempt to integrate it, and if so should I do it in this ticket or start a new one?

Should we move modular_decomposition.py into the src/sage/graphs/graph_decompositions directory?

In the testing section of modular_decomposition.py the function children_node_type is used to flag an error if all of the children of a SERIES or PARALLEL node are of the same type as their parent. I think that this is too loose and an error should be noted if any of the children have the same type as their parents, otherwise the condition that nodes in the tree represent maximal modules is violated.

comment:11 Changed 4 years ago by David Coudert

This is a very good idea to add another algorithm and the parameter algorithm if it helps checking the validity of both algorithms. A slow algorithm is OK in such case. However, it should be done in a separate ticket.

It is possible to move the file to src/sage/graphs/graph_decompositions while working on the new ticket.

comment:12 Changed 4 years ago by David Einstein

I added trac #26496. The code there should be functional if you add algorithm='habib' to each call to modular_decomposition or is_prime.

comment:13 Changed 6 months ago by Dima Pasechnik

Description: modified (diff)
Milestone: sage-8.4sage-9.7

see also #33902

How about removing 'tedder' completely?

comment:14 Changed 6 months ago by David Coudert

I can only agree with that. The code is buggy and I don't know how to fix that.

comment:15 Changed 6 months ago by Dima Pasechnik

OK, I'll try doing this.

comment:16 Changed 6 months ago by David Coudert

We can at least start with a deprecation warning.

comment:17 Changed 6 months ago by Dima Pasechnik

Authors: Dima Pasechnik
Branch: u/jlokesh/modular_decomposition_bugu/dimpase/graphs/remove_tedder_modular_decomposition
Commit: 672a1103fbc56f550a664485487a2acbc24b438ac7e8063960107be1133b9a718203b8c5fe054159
Status: newneeds_review

New commits:

c7e8063remove buggy 'tedder' modular decomposition

comment:18 Changed 6 months ago by Dima Pasechnik

As it's buggy, no need for deprecation, IMHO

comment:19 Changed 6 months ago by David Coudert

This looks good, but In graph.py, we should add the ticket number to the note explaining that we removed a buggy algorithm

comment:20 Changed 6 months ago by git

Commit: c7e8063960107be1133b9a718203b8c5fe05415922f15f5d1a2935afebdabb130797e6370be464fd

Branch pushed to git repo; I updated commit sha1. New commits:

22f15f5mention trac ticket number

comment:21 in reply to:  19 Changed 6 months ago by Dima Pasechnik

Replying to dcoudert:

This looks good, but In graph.py, we should add the ticket number to the note explaining that we removed a buggy algorithm

done

comment:22 Changed 6 months ago by David Coudert

Reviewers: David Coudert
Status: needs_reviewpositive_review

Thank you Dima.

LGTM.

comment:23 Changed 6 months ago by David Coudert

We should certainly update the ticket description to reflect the removal.

comment:24 Changed 6 months ago by Dima Pasechnik

Description: modified (diff)

comment:25 Changed 6 months ago by Matthias Köppe

Status: positive_reviewneeds_work

the algorithm= option is removed, as we only have one implementation now.

This breaks existing code

comment:26 Changed 6 months ago by David Coudert

So what should we do ? deprecate this option before removing tedder in a year ? remove tedder now and let this parameter even if unused with a deprecation ? something else ?

comment:27 Changed 6 months ago by Matthias Köppe

Just make it so that passing algorithm='habib' does not become an error

comment:28 Changed 6 months ago by Dima Pasechnik

algorithm='tedder' should be an error now.

The problem is, however, not limited to this, as there is also a modular_decomposition(foo) function, which was equivalent to foo.modular_decomposition(algorithm='tedder'). In the present branch modular_decomposition(foo) became equivalent to the (old) foo.modular_decomposition(algorithm='habib'), because, what else?

I think it's too much fuss to fiddle around with deprecations here.

Last edited 6 months ago by Dima Pasechnik (previous) (diff)

comment:29 Changed 6 months ago by Matthias Köppe

Just don't make these breaking API changes:

--- a/src/sage/graphs/graph.py
+++ b/src/sage/graphs/graph.py
@@ -7574,7 +7574,7 @@ class Graph(GenericGraph):
             return list(core.values())
 
     @doc_index("Leftovers")
-    def modular_decomposition(self, algorithm='habib', style='tuple'):
+    def modular_decomposition(self, style='tuple'):
         r"""
         Return the modular decomposition of the current graph.
 
@@ -8035,23 +8014,13 @@ class Graph(GenericGraph):
         return self.planar_dual().is_circumscribable(solver=solver, verbose=verbose)
 
     @doc_index("Graph properties")
-    def is_prime(self, algorithm='habib'):
+    def is_prime(self):
         r"""
         Test whether the current graph is prime.
 

comment:30 Changed 6 months ago by git

Commit: 22f15f5d1a2935afebdabb130797e6370be464fdf610e5a8648308b5f3d87b4ea803a63ee72f08cf

Branch pushed to git repo; I updated commit sha1. New commits:

f610e5aretained 'algorithm=' with deprecation

comment:31 Changed 6 months ago by Dima Pasechnik

Status: needs_workneeds_review

comment:32 Changed 6 months ago by Matthias Köppe

Reviewers: David CoudertDavid Coudert, Matthias Koeppe
Status: needs_reviewpositive_review

LGTM, thanks.

comment:33 Changed 6 months ago by Volker Braun

Branch: u/dimpase/graphs/remove_tedder_modular_decompositionf610e5a8648308b5f3d87b4ea803a63ee72f08cf
Resolution: fixed
Status: positive_reviewclosed

comment:34 Changed 6 months ago by Dima Pasechnik

Commit: f610e5a8648308b5f3d87b4ea803a63ee72f08cf
Description: modified (diff)
Note: See TracTickets for help on using tickets.