Bug in the final result of my instance

[Nasaku03]

Hello;

By executing your code on this instance :

14: 2,5
2: 14,3,5
3: 2,4,5
4: 3,5
5: 14,2,3,4,6
6: 5,7,8
7: 6,8,9,10,11,12,13
8: 6,7,9,10,11,12,13
9: 7,8
10: 7,8,11
11: 7,8,10,12
12: 7,8,11,13
13: 7,8,12

It is clear that to get a clear result, i replace the node '1' by the node '14' because you use the node '1' to represent the label "parallel".

I get this result: P(1(7,8),0(9,P(10,11,12,13)),6,3,14,4,2,5)

But what i was expected is this result: P(P(14,2,3,4),5,6,0(7,8),1(9,P(10,11,12,13)))

There is two issues:

1. The two labeled '0' and '1' are inversed (following your description)
2. The final result is wrong, the module P(14,2,3,4) is not detected

Best

[AnnaLindeberg]

Hi! How did you calculate the expected modular decomposition?

I would say that the first point is an error in the readme rather than the code - surely the label '1' on an internal vertex of the MDT should indicate that the corresponding strong module is a series module (and not parallell, as stated). That is, any two vertices $x$ and $y$ with a '1'-labeled lca are adjacent inte the underlying graph. For example, this is the case for 7 and 8 in your graph. I'll fix the readme!

The second point is more subtle: it is true that $\{14,2,3,4\}$ is a module, and it is prime (it induces a $P_4$ in the graph). But the root is also prime-labeled (as the full vertex set is a prime modules), the function reduceMD so to say "merges" these two prime vertices in the output. I'm honestly uncertain if this is correct or not (in other cases, eg a complete graph, this merging should be done for sure). If I recall correctly, the original paper is very vague about how an unreduced MDT should be transformed to a reduced MDT. When I find the time I'll consult the literature and see if I can find a fix! You're also more than welcome to see if you can find a solution and send a pull request.

Cheers!