tedder modular decomposition bug

[Will-Atherton]

Is there an existing issue for this?

• [X] I have searched the existing issues for a bug report that matches the one I want to file, without success.

Did you read the documentation and troubleshoot guide?

• [X] I have read the documentation and troubleshoot guide

Environment

- **OS**: Ubuntu 20.04.5
- **Sage Version**: 10.0.beta9

Steps To Reproduce

sage: from sage.graphs.graph_decompositions.modular_decomposition import * sage: d = {0:[1,2,3,4,6,7,8], 1:[3,4,5,6,7,8], 2:[3,5,6,7,8], 3:[4,6,7,8], 4:[5,8], 5:[6,7], 6:[8], 7:[8]} sage: g = Graph(d) sage: tedder_algorithm(g) # -- wrong SERIES [NORMAL [4], NORMAL [1], NORMAL [2], PARALLEL [NORMAL [6], NORMAL [7]], PARALLEL [NORMAL [5], SERIES [NORMAL [0], NORMAL [3], NORMAL [8]]]] sage: habib_maurer_algorithm(g) SERIES [PRIME [NORMAL [4], PARALLEL [NORMAL [6], NORMAL [7]], NORMAL [1], NORMAL [2]], PARALLEL [SERIES [NORMAL [0], NORMAL [3], NORMAL [8]], NORMAL [5]]]

Expected Behavior

Tedder algorithm meant to return same result (up to permutation of children of a node) as Habib Maurer Algorithm

Actual Behavior

Tedder algorithm doesn't group some of the nodes (Normal [4], Parallel [Normal [6], Normal [7]], [Normal [1], Normal [2]) under a Prime node

Additional Information

No response

[dimpase]

Tedder's code shows the same error. To run it, unzip the zip file somewhere, and run

javac *.java -d .
java modularDecomposition/ContainsMain ex.txt

with ex.txt the example above in the needed format: ex.txt

It outputs

(SERIES, numChildren=5(label=e, neighbours:a,b,d,f,j), (label=b, neighbours:a,d,e,f,g,i,j), (label=c, neighbours:a,d,f,g,i,j),
 (PARALLEL, numChildren=2(label=g, neighbours:a,b,c,d,f,j), (label=i, neighbours:a,b,c,d,f,j)), 
(PARALLEL, numChildren=2(label=f, neighbours:b,c,e,g,i), (SERIES, numChildren=3(label=j, neighbours:a,b,c,d,e,g,i), 
(label=a, neighbours:b,c,d,e,g,i,j), (label=d, neighbours:a,b,c,e,g,i,j))))

In case, here is the complement in the same format ex-compl.txt and

$ java modularDecomposition/ContainsMain ex-compl.txt 
(PARALLEL, numChildren=2(PRIME, numChildren=4(label=b, neighbours:c), (label=c, neighbours:b,e), 
(label=e, neighbours:c,g,i), (SERIES, numChildren=2(label=g, neighbours:e,i), (label=i, neighbours:e,g))), 
(SERIES, numChildren=2(label=f, neighbours:a,d,j), (PARALLEL, numChildren=3(label=j, neighbours:f), 
(label=a, neighbours:f), (label=d, neighbours:f))))

so the complement does have a PRIME node, whereas the original example does not (sic!)

[dimpase]

here is the plot of the complement of the example.