Modular decomposition
Returns a modular decomposition of the given graph.
INPUT:
OUTPUT:
A pair of two values (recursively encoding the decomposition) :
The type of the current module :
- "Parallel"
- "Prime"
- "Serie"
The list of submodules (as list of pairs (type, list), recursively...) or the vertex’s name if the module is a singleton.
Note
As this fuction could be used by efficient C routines, the vertices returned are not labels but identifiants from [0, ..., g.order()-1]
ALGORITHM:
This function uses a C implementation of a 2-step algorithm implemented by Fabien de Montgolfier [FMDecb] :
- Computation of a factorizing permutation [HabibViennot1999b].
- Computation of the tree itself [CapHabMont02b].
EXAMPLES:
The Bull Graph is prime:
sage: from sage.graphs.modular_decomposition.modular_decomposition import modular_decomposition
sage: modular_decomposition(graphs.BullGraph())
('Prime', [3, 4, 0, 1, 2])
The Petersen Graph too:
sage: modular_decomposition(graphs.PetersenGraph())
('Prime', [2, 6, 3, 9, 7, 8, 0, 1, 5, 4])
This a clique on 5 vertices with 2 pendant edges, though, has a more interesting decomposition
sage: g = graphs.CompleteGraph(5)
sage: g.add_edge(0,5)
sage: g.add_edge(0,6)
sage: modular_decomposition(g)
('Serie', [0, ('Parallel', [5, ('Serie', [1, 4, 3, 2]), 6])])
REFERENCES:
[FMDecb] | Fabien de Montgolfier http://www.liafa.jussieu.fr/~fm/algos/index.html |
[HabibViennot1999b] | Michel Habib, Christiphe Paul, Laurent Viennot Partition refinement techniques: An interesting algorithmic tool kit International Journal of Foundations of Computer Science vol. 10 n2 pp.147–170, 1999 |
[CapHabMont02b] | C. Capelle, M. Habib et F. de Montgolfier Graph decomposition and Factorising Permutations Discrete Mathematics and Theoretical Computer Sciences, vol 5 no. 1 , 2002. |