# Modular decomposition¶

Modular decomposition

sage.graphs.modular_decomposition.modular_decomposition.modular_decomposition(g)

Returns a modular decomposition of the given graph.

INPUT:

• g – a graph

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

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: 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.

#### Previous topic

Products of graphs

#### Next topic

Convexity properties of graphs