error in the function modular_decomposition(g) from sage.graphs.graph_decompositions.modular_decomposition

[Anne-Aymone BOURGUIN]

Hello,

I am using the sage.graphs.graph_decompositions.modular_decomposition with two configurations :

* a Windows (64-bit) system, with sage 9.3 installed (Python 3.7.10)

* an Ubuntu (64-bit) system, with sage 9.5 installed (Python 3.8.10)
I was working with sage 9.0 on Ubuntu until I noticed differences between the modular decompositions that I got from my different computers.
At that time, I noticed that it was the 9.0 version which gave me wrong decompositions, so I installed the 9.5 version.

Now, I still have some errors :
I use the modular_decomposition function without optional parameters, so it's the "habib" algorithm that is used...

I'm joining my code to this message.
The example that I'm sending today is pretty easy to check by hand, and we can see that the modular decomposition is not what it should be.

In case the file is not opening, the example is just :
    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)

And modular_decomposition(g) gives me :

PRIME
 5
 SERIES
  9
  PARALLEL
   10
   7
   8
   6
 4
 SERIES
  3
  2
  1

(6 and 9 should not be neighbors, but they are in this modular decomposition)

Best regards,
Anne-Aymone Bourguin

[Anne-Aymone BOURGUIN]

I'm sorry, a little confusion on my part : I don't know which algorithm is used in this function (habib or tedder or ?...).

[Dima Pasechnik]

On Sage 9.6, I get

sage: g.modular_decomposition()
(PRIME, [5, 4, (SERIES, [1, 2, 3]), (PRIME, [9, 7, 6, 8, 10])])

sage: g.modular_decomposition(algorithm='tedder')
(PRIME, [5, (SERIES, [9, (PARALLEL, [10, 7, 8, 6])]), 4, (SERIES, [3, 2, 1])])

It appears that the 1st output is correct (that's the default,
'habib', algorithm), and
the 2nd (with 'tedder') is not.

'habib' was added in https://trac.sagemath.org/ticket/26496
- and this seems to be the 1st example we know where our 'tedder' is wrong.

I've opened https://trac.sagemath.org/ticket/33902 to deal with this.

Dima




>
> Best regards,
> Anne-Aymone Bourguin
>
> --
> You received this message because you are subscribed to the Google Groups "sage-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/4df9a528-ca41-4f71-9c7e-3543047b9c05n%40googlegroups.com.

[Dima Pasechnik]

PS. Somehow we know for years that 'tedder' is buggy, see
https://trac.sagemath.org/ticket/25872
but did not take an action. Sorry :-(