Modular decomposition bug

[jm58660]

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.

CC: @lokeshj1703 @dimpase @dcoudert @deinst

Component: graph theory

Author: Dima Pasechnik

Branch: f610e5a

Reviewer: David Coudert, Matthias Koeppe

Issue created by migration from https://trac.sagemath.org/ticket/25872

[dcoudert]

comment:1

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

[jm58660]

comment:2

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.

[dcoudert]

comment:3

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])])

[lokeshj1703]

Branch: u/jlokesh/modular_decomposition_bug

[lokeshj1703]

Commit: b71307d

[lokeshj1703]

comment:5

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:

b71307d

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

[dcoudert]

comment:6

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])])

[jm58660]

comment:7

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")

[sagetrac-git]

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

672a110

trac #25872: Added tests in graph.py#modular_decomposition

[sagetrac-git]

Changed commit from b71307d to 672a110

[lokeshj1703]

comment:9

Replying to @jm58660:

Still doesn't work.

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

[deinst]

comment:10

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(n³) 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.

[dcoudert]

comment:11

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.

[deinst]

comment:12

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

[dimpase]

comment:13

see also #33902

How about removing 'tedder' completely?

[dcoudert]

comment:14

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

[dimpase]

comment:15

OK, I'll try doing this.

[dcoudert]

comment:16

We can at least start with a deprecation warning.

[dimpase]

Changed branch from u/jlokesh/modular_decomposition_bug to u/dimpase/graphs/remove_tedder_modular_decomposition

[dimpase]

Changed commit from 672a110 to c7e8063

[dimpase]

Author: Dima Pasechnik

[dimpase]

New commits:

c7e8063

remove buggy 'tedder' modular decomposition

[dcoudert]

comment:23

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

[mkoeppe]

comment:25

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

This breaks existing code

[dcoudert]

comment:26

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 ?

[mkoeppe]

comment:27

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

[dimpase]

comment:28

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.

[mkoeppe]

comment:29

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.
 

[sagetrac-git]

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

f610e5a

retained 'algorithm=' with deprecation

[sagetrac-git]

Changed commit from 22f15f5 to f610e5a

[mkoeppe]

Changed reviewer from David Coudert to David Coudert, Matthias Koeppe

[mkoeppe]

comment:32

LGTM, thanks.

[vbraun]

Changed branch from u/dimpase/graphs/remove_tedder_modular_decomposition to f610e5a

[dimpase]

Changed commit from f610e5a to none