Modular Decomposition

This module implements the function for computing the modular decomposition of undirected graphs.

AUTHORS:

  • Lokesh Jain (2017): first implementation of the linear time algorithm of D. Corneil, M. Habib, C. Paul and M. Tedder [TCHP2008]

  • David Einstein (2018): added the algorithm of M. Habib and M. Maurer [HM1979]

  • Cyril Bouvier (2024): second implementation of the linear time algorithm of D. Corneil, M. Habib, C. Paul and M. Tedder [TCHP2008]

class sage.graphs.graph_decompositions.modular_decomposition.Node(node_type)[source]

Bases: object

Node class stores information about the node type.

Node type can be PRIME, SERIES, PARALLEL, NORMAL or EMPTY.

  • node_type – is of type NodeType and specifies the type of node

classmethod create_leaf(v)[source]

Return Node object that is a leaf corresponding to the vertex v.

INPUT:

  • vertex – vertex number

OUTPUT: a node object representing the vertex with node_type set as NodeType.NORMAL

EXAMPLES:

sage: from sage.graphs.graph_decompositions.modular_decomposition import Node
sage: node = Node.create_leaf(2)
sage: node
NORMAL [2]

>>> from sage.all import *
>>> from sage.graphs.graph_decompositions.modular_decomposition import Node
>>> node = Node.create_leaf(Integer(2))
>>> node
NORMAL [2]
is_empty()[source]

Check whether self is an empty node.

EXAMPLES:

sage: from sage.graphs.graph_decompositions.modular_decomposition import *
sage: Node(NodeType.EMPTY).is_empty()
True
sage: Node.create_leaf(1).is_empty()
False

>>> from sage.all import *
>>> from sage.graphs.graph_decompositions.modular_decomposition import *
>>> Node(NodeType.EMPTY).is_empty()
True
>>> Node.create_leaf(Integer(1)).is_empty()
False
is_leaf()[source]

Check whether self is a leaf.

EXAMPLES:

sage: from sage.graphs.graph_decompositions.modular_decomposition import *
sage: n = Node(NodeType.PRIME)
sage: n.children.append(Node.create_leaf(1))
sage: n.children.append(Node.create_leaf(2))
sage: n.is_leaf()
False
sage: all(c.is_leaf() for c in n.children)
True

>>> from sage.all import *
>>> from sage.graphs.graph_decompositions.modular_decomposition import *
>>> n = Node(NodeType.PRIME)
>>> n.children.append(Node.create_leaf(Integer(1)))
>>> n.children.append(Node.create_leaf(Integer(2)))
>>> n.is_leaf()
False
>>> all(c.is_leaf() for c in n.children)
True
is_prime()[source]

Check whether self is a prime node.

EXAMPLES:

sage: from sage.graphs.graph_decompositions.modular_decomposition import *
sage: n = Node(NodeType.PRIME)
sage: n.children.append(Node.create_leaf(1))
sage: n.children.append(Node.create_leaf(2))
sage: n.is_prime()
True
sage: (n.children[0].is_prime(), n.children[1].is_prime())
(False, False)

>>> from sage.all import *
>>> from sage.graphs.graph_decompositions.modular_decomposition import *
>>> n = Node(NodeType.PRIME)
>>> n.children.append(Node.create_leaf(Integer(1)))
>>> n.children.append(Node.create_leaf(Integer(2)))
>>> n.is_prime()
True
>>> (n.children[Integer(0)].is_prime(), n.children[Integer(1)].is_prime())
(False, False)
is_series()[source]

Check whether self is a series node.

EXAMPLES:

sage: from sage.graphs.graph_decompositions.modular_decomposition import *
sage: n = Node(NodeType.SERIES)
sage: n.children.append(Node.create_leaf(1))
sage: n.children.append(Node.create_leaf(2))
sage: n.is_series()
True
sage: (n.children[0].is_series(), n.children[1].is_series())
(False, False)

>>> from sage.all import *
>>> from sage.graphs.graph_decompositions.modular_decomposition import *
>>> n = Node(NodeType.SERIES)
>>> n.children.append(Node.create_leaf(Integer(1)))
>>> n.children.append(Node.create_leaf(Integer(2)))
>>> n.is_series()
True
>>> (n.children[Integer(0)].is_series(), n.children[Integer(1)].is_series())
(False, False)
class sage.graphs.graph_decompositions.modular_decomposition.NodeType(value, names=<not given>, *values, module=None, qualname=None, type=None, start=1, boundary=None)[source]

Bases: IntEnum

NodeType is an enumeration class used to define the various types of nodes in modular decomposition tree.

The various node types defined are

  • PARALLEL – indicates the node is a parallel module

  • SERIES – indicates the node is a series module

  • PRIME – indicates the node is a prime module

  • EMPTY – indicates a empty tree

  • NORMAL – indicates the node is normal containing a vertex

EMPTY = -1[source]
NORMAL = 3[source]
PARALLEL = 2[source]
PRIME = 0[source]
SERIES = 1[source]
sage.graphs.graph_decompositions.modular_decomposition.check_algos_are_equivalent(trials, graph_gen, verbose=False)[source]

Verify that both algorithms compute the same tree (up to equivalence) for random graphs.

INPUT:

  • trials – integer; the number of tests the function will run.

  • graph_gen – function; a function that can be called without argument and returns a random graph.

  • verbose – boolean (defaul: False); enable printing debug information.

OUTPUT: None. Raises an AssertionError on failure.

EXAMPLES:

sage: from sage.graphs.graph_decompositions.modular_decomposition import *
sage: check_algos_are_equivalent(3, lambda : graphs.RandomGNP(10, 0.1))
sage: check_algos_are_equivalent(3, lambda : graphs.RandomGNP(10, 0.5))
sage: check_algos_are_equivalent(3, lambda : graphs.RandomGNP(10, 0.9))

>>> from sage.all import *
>>> from sage.graphs.graph_decompositions.modular_decomposition import *
>>> check_algos_are_equivalent(Integer(3), lambda : graphs.RandomGNP(Integer(10), RealNumber('0.1')))
>>> check_algos_are_equivalent(Integer(3), lambda : graphs.RandomGNP(Integer(10), RealNumber('0.5')))
>>> check_algos_are_equivalent(Integer(3), lambda : graphs.RandomGNP(Integer(10), RealNumber('0.9')))
sage.graphs.graph_decompositions.modular_decomposition.children_node_type(module, node_type)[source]

Check whether the node type of the children of module is node_type.

INPUT:

  • module – module which is tested

  • node_type – input node_type

EXAMPLES:

sage: from sage.graphs.graph_decompositions.modular_decomposition import *
sage: g = graphs.OctahedralGraph()
sage: tree_root = modular_decomposition(g)
sage: print_md_tree(tree_root)
SERIES
 PARALLEL
  2
  3
 PARALLEL
  1
  4
 PARALLEL
  0
  5
sage: children_node_type(tree_root, NodeType.SERIES)
False
sage: children_node_type(tree_root, NodeType.PARALLEL)
True

>>> from sage.all import *
>>> from sage.graphs.graph_decompositions.modular_decomposition import *
>>> g = graphs.OctahedralGraph()
>>> tree_root = modular_decomposition(g)
>>> print_md_tree(tree_root)
SERIES
 PARALLEL
  2
  3
 PARALLEL
  1
  4
 PARALLEL
  0
  5
>>> children_node_type(tree_root, NodeType.SERIES)
False
>>> children_node_type(tree_root, NodeType.PARALLEL)
True
sage.graphs.graph_decompositions.modular_decomposition.corneil_habib_paul_tedder_algorithm(G)[source]

Compute the modular decomposition by the algorithm of Corneil, Habib, Paul and Tedder.

INPUT:

  • G – the graph for which modular decomposition tree needs to be computed

OUTPUT: an object of type Node representing the modular decomposition tree of the graph G

This function computes the modular decomposition of the given graph by the algorithm of Corneil, Habib, Paul and Tedder [TCHP2008]. It is a recursive, linear-time algorithm that first computes the slice decomposition of the graph (via the extended lexBFS algorithm) and then computes the modular decomposition by calling itself recursively on the slices of the previously computed slice decomposition.

This functions is based on the last version of the paper [TCHP2008]. Previous versions of the paper and previous implementations were found to contains errors, see [AP2024].

See also

This function should not be used directly, it should be called via the modular_decomposition method of Graph with the parameter algorithm='corneil_habib_paul_tedder'.

This functions assumes that graph is a object of the class Graph and is a simple graph.

sage.graphs.graph_decompositions.modular_decomposition.either_connected_or_not_connected(v, vertices_in_module, graph)[source]

Check whether v is connected or disconnected to all vertices in the module.

INPUT:

  • v – vertex tested

  • vertices_in_module – list containing vertices in the module

  • graph – graph to which the vertices belong

EXAMPLES:

sage: from sage.graphs.graph_decompositions.modular_decomposition import *
sage: g = graphs.OctahedralGraph()
sage: print_md_tree(modular_decomposition(g))
SERIES
 PARALLEL
  2
  3
 PARALLEL
  1
  4
 PARALLEL
  0
  5
sage: either_connected_or_not_connected(2, [1, 4], g)
True
sage: either_connected_or_not_connected(2, [3, 4], g)
False

>>> from sage.all import *
>>> from sage.graphs.graph_decompositions.modular_decomposition import *
>>> g = graphs.OctahedralGraph()
>>> print_md_tree(modular_decomposition(g))
SERIES
 PARALLEL
  2
  3
 PARALLEL
  1
  4
 PARALLEL
  0
  5
>>> either_connected_or_not_connected(Integer(2), [Integer(1), Integer(4)], g)
True
>>> either_connected_or_not_connected(Integer(2), [Integer(3), Integer(4)], g)
False
sage.graphs.graph_decompositions.modular_decomposition.equivalent_trees(root1, root2)[source]

Check that two modular decomposition trees are the same.

Verify that the structure of the trees is the same. Two leaves are equivalent if they represent the same vertex, two internal nodes are equivalent if they have the same nodes type and the same number of children and there is a matching between the children such that each pair of children is a pair of equivalent subtrees.

EXAMPLES:

sage: from sage.graphs.graph_decompositions.modular_decomposition import *
sage: t1 = nested_tuple_to_tree((NodeType.SERIES, 1, 2,
....:             (NodeType.PARALLEL, 3, 4)))
sage: t2 = nested_tuple_to_tree((NodeType.SERIES,
....:             (NodeType.PARALLEL, 4, 3), 2, 1))
sage: equivalent_trees(t1, t2)
True

>>> from sage.all import *
>>> from sage.graphs.graph_decompositions.modular_decomposition import *
>>> t1 = nested_tuple_to_tree((NodeType.SERIES, Integer(1), Integer(2),
...             (NodeType.PARALLEL, Integer(3), Integer(4))))
>>> t2 = nested_tuple_to_tree((NodeType.SERIES,
...             (NodeType.PARALLEL, Integer(4), Integer(3)), Integer(2), Integer(1)))
>>> equivalent_trees(t1, t2)
True
sage.graphs.graph_decompositions.modular_decomposition.form_module(index, other_index, tree_root, graph)[source]

Forms a module out of the modules in the module pair.

Let \(M_1\) and \(M_2\) be the input modules. Let \(V\) be the set of vertices in these modules. Suppose \(x\) is a neighbor of subset of the vertices in \(V\) but not all the vertices and \(x\) does not belong to \(V\). Then the set of modules also include the module which contains \(x\). This process is repeated until a module is formed and the formed module if subset of \(V\) is returned.

INPUT:

  • index – first module in the module pair

  • other_index – second module in the module pair

  • tree_root – modular decomposition tree which contains the modules in the module pair

  • graph – graph whose modular decomposition tree is created

OUTPUT:

[module_formed, vertices] where module_formed is True if module is formed else False and vertices is a list of vertices included in the formed module

EXAMPLES:

sage: from sage.graphs.graph_decompositions.modular_decomposition import *
sage: g = graphs.HexahedralGraph()
sage: tree_root = modular_decomposition(g)
sage: form_module(0, 2, tree_root, g)
[False, {0, 1, 2, 3, 4, 5, 6, 7}]

>>> from sage.all import *
>>> from sage.graphs.graph_decompositions.modular_decomposition import *
>>> g = graphs.HexahedralGraph()
>>> tree_root = modular_decomposition(g)
>>> form_module(Integer(0), Integer(2), tree_root, g)
[False, {0, 1, 2, 3, 4, 5, 6, 7}]
sage.graphs.graph_decompositions.modular_decomposition.gamma_classes(graph)[source]

Partition the edges of the graph into Gamma classes.

Two distinct edges are Gamma related if they share a vertex but are not part of a triangle. A Gamma class of edges is a collection of edges such that any edge in the class can be reached from any other by a chain of Gamma related edges (that are also in the class).

The two important properties of the Gamma class

  • The vertex set corresponding to a Gamma class is a module

  • If the graph is not fragile (neither it or its complement is disconnected) then there is exactly one class that visits all the vertices of the graph, and this class consists of just the edges that connect the maximal strong modules of that graph.

EXAMPLES:

The gamma_classes of the octahedral graph are the three 4-cycles corresponding to the slices through the center of the octahedron:

sage: from sage.graphs.graph_decompositions.modular_decomposition import gamma_classes
sage: g = graphs.OctahedralGraph()
sage: sorted(gamma_classes(g), key=str)
[frozenset({0, 1, 4, 5}), frozenset({0, 2, 3, 5}), frozenset({1, 2, 3, 4})]

>>> from sage.all import *
>>> from sage.graphs.graph_decompositions.modular_decomposition import gamma_classes
>>> g = graphs.OctahedralGraph()
>>> sorted(gamma_classes(g), key=str)
[frozenset({0, 1, 4, 5}), frozenset({0, 2, 3, 5}), frozenset({1, 2, 3, 4})]
sage.graphs.graph_decompositions.modular_decomposition.get_module_type(graph)[source]

Return the module type of the root of the modular decomposition tree of graph.

INPUT:

  • graph – input sage graph

OUTPUT:

PRIME if graph is PRIME, PARALLEL if graph is PARALLEL and SERIES if graph is of type SERIES

EXAMPLES:

sage: from sage.graphs.graph_decompositions.modular_decomposition import get_module_type
sage: g = graphs.HexahedralGraph()
sage: get_module_type(g)
PRIME

>>> from sage.all import *
>>> from sage.graphs.graph_decompositions.modular_decomposition import get_module_type
>>> g = graphs.HexahedralGraph()
>>> get_module_type(g)
PRIME
sage.graphs.graph_decompositions.modular_decomposition.get_vertices(component_root)[source]

Compute the list of vertices in the (co)component.

INPUT:

  • component_root – root of the (co)component whose vertices need to be returned as a list

OUTPUT:

list of vertices in the (co)component

EXAMPLES:

sage: from sage.graphs.graph_decompositions.modular_decomposition import *
sage: forest = Node(NodeType.PRIME)
sage: forest.children = [Node.create_leaf(2), Node.create_leaf(0),
....:                    Node.create_leaf(3), Node.create_leaf(1)]
sage: series_node = Node(NodeType.SERIES)
sage: series_node.children = [Node.create_leaf(4),
....:                         Node.create_leaf(5)]
sage: parallel_node = Node(NodeType.PARALLEL)
sage: parallel_node.children = [Node.create_leaf(6),
....:                           Node.create_leaf(7)]
sage: forest.children.insert(1, series_node)
sage: forest.children.insert(3, parallel_node)
sage: get_vertices(forest)
[2, 4, 5, 0, 6, 7, 3, 1]

>>> from sage.all import *
>>> from sage.graphs.graph_decompositions.modular_decomposition import *
>>> forest = Node(NodeType.PRIME)
>>> forest.children = [Node.create_leaf(Integer(2)), Node.create_leaf(Integer(0)),
...                    Node.create_leaf(Integer(3)), Node.create_leaf(Integer(1))]
>>> series_node = Node(NodeType.SERIES)
>>> series_node.children = [Node.create_leaf(Integer(4)),
...                         Node.create_leaf(Integer(5))]
>>> parallel_node = Node(NodeType.PARALLEL)
>>> parallel_node.children = [Node.create_leaf(Integer(6)),
...                           Node.create_leaf(Integer(7))]
>>> forest.children.insert(Integer(1), series_node)
>>> forest.children.insert(Integer(3), parallel_node)
>>> get_vertices(forest)
[2, 4, 5, 0, 6, 7, 3, 1]
sage.graphs.graph_decompositions.modular_decomposition.habib_maurer_algorithm(graph, g_classes=None)[source]

Compute the modular decomposition by the algorithm of Habib and Maurer.

Compute the modular decomposition of the given graph by the algorithm of Habib and Maurer [HM1979] . If the graph is disconnected or its complement is disconnected return a tree with a PARALLEL or SERIES node at the root and children being the modular decomposition of the subgraphs induced by the components. Otherwise, the root is PRIME and the modules are identified by having identical neighborhoods in the gamma class that spans the vertices of the subgraph (exactly one is guaranteed to exist). The gamma classes only need to be computed once, as the algorithm computes the the classes for the current root and each of the submodules. See also [BM1983] for an equivalent algorithm described in greater detail.

This function should not be used directly, it should be called via the modular_decomposition method of Graph with the parameter algorithm='habib_maurer'.

This functions assumes that graph is a object of the class Graph, is a simple graph and has at least 1 vertex.

INPUT:

  • graph – the graph for which modular decomposition tree needs to be computed

  • g_classes – dictionary (default: None); a dictionary whose values are the gamma classes of the graph, and whose keys are a frozenset of the vertices corresponding to the class. Used internally.

OUTPUT: the modular decomposition tree of the graph

EXAMPLES:

The Icosahedral graph is Prime:

sage: from sage.graphs.graph_decompositions.modular_decomposition import *
sage: print_md_tree(habib_maurer_algorithm(graphs.IcosahedralGraph()))
PRIME
 3
 4
 7
 9
 11
 1
 5
 8
 0
 2
 6
 10

>>> from sage.all import *
>>> from sage.graphs.graph_decompositions.modular_decomposition import *
>>> print_md_tree(habib_maurer_algorithm(graphs.IcosahedralGraph()))
PRIME
 3
 4
 7
 9
 11
 1
 5
 8
 0
 2
 6
 10

The Octahedral graph is not Prime:

sage: print_md_tree(habib_maurer_algorithm(graphs.OctahedralGraph()))
SERIES
 PARALLEL
  0
  5
 PARALLEL
  1
  4
 PARALLEL
  2
  3

>>> from sage.all import *
>>> print_md_tree(habib_maurer_algorithm(graphs.OctahedralGraph()))
SERIES
 PARALLEL
  0
  5
 PARALLEL
  1
  4
 PARALLEL
  2
  3

Tetrahedral Graph is Series:

sage: print_md_tree(habib_maurer_algorithm(graphs.TetrahedralGraph()))
SERIES
 0
 1
 2
 3

>>> from sage.all import *
>>> print_md_tree(habib_maurer_algorithm(graphs.TetrahedralGraph()))
SERIES
 0
 1
 2
 3

Modular Decomposition tree containing both parallel and series modules:

sage: d = {2:[4,3,5], 1:[4,3,5], 5:[3,2,1,4], 3:[1,2,5], 4:[1,2,5]}
sage: g = Graph(d)
sage: print_md_tree(habib_maurer_algorithm(g))
SERIES
 PARALLEL
  1
  2
 PARALLEL
  3
  4
 5

>>> from sage.all import *
>>> d = {Integer(2):[Integer(4),Integer(3),Integer(5)], Integer(1):[Integer(4),Integer(3),Integer(5)], Integer(5):[Integer(3),Integer(2),Integer(1),Integer(4)], Integer(3):[Integer(1),Integer(2),Integer(5)], Integer(4):[Integer(1),Integer(2),Integer(5)]}
>>> g = Graph(d)
>>> print_md_tree(habib_maurer_algorithm(g))
SERIES
 PARALLEL
  1
  2
 PARALLEL
  3
  4
 5

Graph from Marc Tedder implementation of modular decomposition:

sage: d = {1:[5,4,3,24,6,7,8,9,2,10,11,12,13,14,16,17], 2:[1],
....:       3:[24,9,1], 4:[5,24,9,1], 5:[4,24,9,1], 6:[7,8,9,1],
....:       7:[6,8,9,1], 8:[6,7,9,1], 9:[6,7,8,5,4,3,1], 10:[1],
....:       11:[12,1], 12:[11,1], 13:[14,16,17,1], 14:[13,17,1],
....:       16:[13,17,1], 17:[13,14,16,18,1], 18:[17], 24:[5,4,3,1]}
sage: g = Graph(d)
sage: test_modular_decomposition(habib_maurer_algorithm(g), g)
True

>>> from sage.all import *
>>> d = {Integer(1):[Integer(5),Integer(4),Integer(3),Integer(24),Integer(6),Integer(7),Integer(8),Integer(9),Integer(2),Integer(10),Integer(11),Integer(12),Integer(13),Integer(14),Integer(16),Integer(17)], Integer(2):[Integer(1)],
...       Integer(3):[Integer(24),Integer(9),Integer(1)], Integer(4):[Integer(5),Integer(24),Integer(9),Integer(1)], Integer(5):[Integer(4),Integer(24),Integer(9),Integer(1)], Integer(6):[Integer(7),Integer(8),Integer(9),Integer(1)],
...       Integer(7):[Integer(6),Integer(8),Integer(9),Integer(1)], Integer(8):[Integer(6),Integer(7),Integer(9),Integer(1)], Integer(9):[Integer(6),Integer(7),Integer(8),Integer(5),Integer(4),Integer(3),Integer(1)], Integer(10):[Integer(1)],
...       Integer(11):[Integer(12),Integer(1)], Integer(12):[Integer(11),Integer(1)], Integer(13):[Integer(14),Integer(16),Integer(17),Integer(1)], Integer(14):[Integer(13),Integer(17),Integer(1)],
...       Integer(16):[Integer(13),Integer(17),Integer(1)], Integer(17):[Integer(13),Integer(14),Integer(16),Integer(18),Integer(1)], Integer(18):[Integer(17)], Integer(24):[Integer(5),Integer(4),Integer(3),Integer(1)]}
>>> g = Graph(d)
>>> test_modular_decomposition(habib_maurer_algorithm(g), g)
True

Tetrahedral Graph is Series:

sage: print_md_tree(habib_maurer_algorithm(graphs.TetrahedralGraph()))
SERIES
 0
 1
 2
 3

>>> from sage.all import *
>>> print_md_tree(habib_maurer_algorithm(graphs.TetrahedralGraph()))
SERIES
 0
 1
 2
 3

Modular Decomposition tree containing both parallel and series modules:

sage: d = {2:[4,3,5], 1:[4,3,5], 5:[3,2,1,4], 3:[1,2,5], 4:[1,2,5]}
sage: g = Graph(d)
sage: print_md_tree(habib_maurer_algorithm(g))
SERIES
 PARALLEL
  1
  2
 PARALLEL
  3
  4
 5

>>> from sage.all import *
>>> d = {Integer(2):[Integer(4),Integer(3),Integer(5)], Integer(1):[Integer(4),Integer(3),Integer(5)], Integer(5):[Integer(3),Integer(2),Integer(1),Integer(4)], Integer(3):[Integer(1),Integer(2),Integer(5)], Integer(4):[Integer(1),Integer(2),Integer(5)]}
>>> g = Graph(d)
>>> print_md_tree(habib_maurer_algorithm(g))
SERIES
 PARALLEL
  1
  2
 PARALLEL
  3
  4
 5
sage.graphs.graph_decompositions.modular_decomposition.md_tree_to_graph(root, prime_node_generator=None)[source]

Create a graph having the given MD tree.

For the prime nodes, the parameter prime_node_generator is called with the number of vertices as the only argument. If it is None, the path graph is used (it is prime when the length is 4 or more).

EXAMPLES:

sage: from sage.graphs.graph_decompositions.modular_decomposition import *
sage: from sage.graphs.graph_generators import graphs
sage: tup1 = (NodeType.PRIME, 1, (NodeType.SERIES, 2, 3),
....:        (NodeType.PARALLEL, 4, 5), 6)
sage: tree1 = nested_tuple_to_tree(tup1)
sage: g1 = md_tree_to_graph(tree1)
sage: g2 = Graph({1: [2, 3], 2: [1, 3, 4, 5], 3: [1, 2, 4, 5],
....:             4: [2, 3, 6], 5: [2, 3, 6], 6: [4, 5]})
sage: g1.is_isomorphic(g2)
True

sage: G = md_tree_to_graph(Node(NodeType.EMPTY))
sage: G.is_isomorphic(Graph())
True

sage: tree = Node(NodeType.SERIES)
sage: tree.children.extend(Node.create_leaf(i) for i in range(5))
sage: G = md_tree_to_graph(tree)
sage: G.is_isomorphic(graphs.CompleteGraph(5))
True

sage: tree = Node(NodeType.PRIME)
sage: tree.children.extend(Node.create_leaf(i) for i in range(5))
sage: png = lambda n: (graphs.PathGraph if n == 4 else graphs.CycleGraph)(n)
sage: G = md_tree_to_graph(tree, prime_node_generator=png)
sage: G.is_isomorphic(graphs.CycleGraph(5))
True

>>> from sage.all import *
>>> from sage.graphs.graph_decompositions.modular_decomposition import *
>>> from sage.graphs.graph_generators import graphs
>>> tup1 = (NodeType.PRIME, Integer(1), (NodeType.SERIES, Integer(2), Integer(3)),
...        (NodeType.PARALLEL, Integer(4), Integer(5)), Integer(6))
>>> tree1 = nested_tuple_to_tree(tup1)
>>> g1 = md_tree_to_graph(tree1)
>>> g2 = Graph({Integer(1): [Integer(2), Integer(3)], Integer(2): [Integer(1), Integer(3), Integer(4), Integer(5)], Integer(3): [Integer(1), Integer(2), Integer(4), Integer(5)],
...             Integer(4): [Integer(2), Integer(3), Integer(6)], Integer(5): [Integer(2), Integer(3), Integer(6)], Integer(6): [Integer(4), Integer(5)]})
>>> g1.is_isomorphic(g2)
True

>>> G = md_tree_to_graph(Node(NodeType.EMPTY))
>>> G.is_isomorphic(Graph())
True

>>> tree = Node(NodeType.SERIES)
>>> tree.children.extend(Node.create_leaf(i) for i in range(Integer(5)))
>>> G = md_tree_to_graph(tree)
>>> G.is_isomorphic(graphs.CompleteGraph(Integer(5)))
True

>>> tree = Node(NodeType.PRIME)
>>> tree.children.extend(Node.create_leaf(i) for i in range(Integer(5)))
>>> png = lambda n: (graphs.PathGraph if n == Integer(4) else graphs.CycleGraph)(n)
>>> G = md_tree_to_graph(tree, prime_node_generator=png)
>>> G.is_isomorphic(graphs.CycleGraph(Integer(5)))
True
sage.graphs.graph_decompositions.modular_decomposition.modular_decomposition(G, algorithm=None)[source]

Return the modular decomposition of the current graph.

This function should not be used directly, it should be called via the modular_decomposition method of Graph.

INPUT:

  • G – graph whose modular decomposition tree is to be computed

  • algorithm – string (default: None); the algorithm to use among:

    • None or 'corneil_habib_paul_tedder' – will use the Corneil-Habib-Paul-Tedder algorithm from [TCHP2008], its complexity is linear in the number of vertices and edges.

    • 'habib_maurer' – will use the Habib-Maurer algorithm from [HM1979], its complexity is cubic in the number of vertices.

OUTPUT: The modular decomposition tree, as an object of type Node.

sage.graphs.graph_decompositions.modular_decomposition.nested_tuple_to_tree(nest)[source]

Turn a tuple representing the modular decomposition into a tree.

INPUT:

OUTPUT: the root node of a modular decomposition tree

EXAMPLES:

sage: from sage.graphs.graph_decompositions.modular_decomposition import *
sage: tree = (NodeType.SERIES, 1, 2, (NodeType.PARALLEL, 3, 4))
sage: print_md_tree(nested_tuple_to_tree(tree))
SERIES
 1
 2
 PARALLEL
  3
  4

>>> from sage.all import *
>>> from sage.graphs.graph_decompositions.modular_decomposition import *
>>> tree = (NodeType.SERIES, Integer(1), Integer(2), (NodeType.PARALLEL, Integer(3), Integer(4)))
>>> print_md_tree(nested_tuple_to_tree(tree))
SERIES
 1
 2
 PARALLEL
  3
  4
sage.graphs.graph_decompositions.modular_decomposition.permute_decomposition(trials, algorithm, vertices, prob, verbose=False)[source]

Check that a graph and its permuted relabeling have the same modular decomposition.

We generate a trials random graphs and then generate an isomorphic graph by relabeling the original graph. We then verify

EXAMPLES:

sage: from sage.graphs.graph_decompositions.modular_decomposition import *
sage: permute_decomposition(30, habib_maurer_algorithm, 10, 0.5)

>>> from sage.all import *
>>> from sage.graphs.graph_decompositions.modular_decomposition import *
>>> permute_decomposition(Integer(30), habib_maurer_algorithm, Integer(10), RealNumber('0.5'))
sage.graphs.graph_decompositions.modular_decomposition.print_md_tree(root)[source]

Print the modular decomposition tree.

INPUT:

  • root – root of the modular decomposition tree

EXAMPLES:

sage: from sage.graphs.graph_decompositions.modular_decomposition import *
sage: print_md_tree(habib_maurer_algorithm(graphs.IcosahedralGraph()))
PRIME
 3
 4
 7
 9
 11
 1
 5
 8
 0
 2
 6
 10

>>> from sage.all import *
>>> from sage.graphs.graph_decompositions.modular_decomposition import *
>>> print_md_tree(habib_maurer_algorithm(graphs.IcosahedralGraph()))
PRIME
 3
 4
 7
 9
 11
 1
 5
 8
 0
 2
 6
 10
sage.graphs.graph_decompositions.modular_decomposition.random_md_tree(max_depth, max_fan_out, leaf_probability)[source]

Create a random MD tree.

INPUT:

  • max_depth – the maximum depth of the tree

  • max_fan_out – the maximum number of children a node can have (must be >=4 as a prime node must have at least 4 vertices)

  • leaf_probability – the probability that a subtree is a leaf

EXAMPLES:

sage: from sage.graphs.graph_decompositions.modular_decomposition import *
sage: set_random_seed(0)
sage: tree_to_nested_tuple(random_md_tree(2, 5, 0.5))
(PRIME, [0, 1, (PRIME, [2, 3, 4, 5, 6]), 7, (PARALLEL, [8, 9, 10])])

>>> from sage.all import *
>>> from sage.graphs.graph_decompositions.modular_decomposition import *
>>> set_random_seed(Integer(0))
>>> tree_to_nested_tuple(random_md_tree(Integer(2), Integer(5), RealNumber('0.5')))
(PRIME, [0, 1, (PRIME, [2, 3, 4, 5, 6]), 7, (PARALLEL, [8, 9, 10])])
sage.graphs.graph_decompositions.modular_decomposition.recreate_decomposition(trials, algorithm, max_depth, max_fan_out, leaf_probability, verbose=False)[source]

Verify that we can recreate a random MD tree.

We create a random MD tree, then create a graph having that decomposition, then find a modular decomposition for that graph, and verify that the two modular decomposition trees are equivalent.

EXAMPLES:

sage: from sage.graphs.graph_decompositions.modular_decomposition import *
sage: recreate_decomposition(3, habib_maurer_algorithm, 4, 6, 0.5,
....:                         verbose=False)

>>> from sage.all import *
>>> from sage.graphs.graph_decompositions.modular_decomposition import *
>>> recreate_decomposition(Integer(3), habib_maurer_algorithm, Integer(4), Integer(6), RealNumber('0.5'),
...                         verbose=False)
sage.graphs.graph_decompositions.modular_decomposition.relabel_tree(root, perm)[source]

Relabel the leaves of a tree according to a dictionary.

INPUT:

  • root – the root of the tree

  • perm – a function, dictionary, list, permutation, or None representing the relabeling. See relabel() for description of the permutation input.

EXAMPLES:

sage: from sage.graphs.graph_decompositions.modular_decomposition import *
sage: tuple_tree = (NodeType.SERIES, 1, 2, (NodeType.PARALLEL, 3, 4))
sage: tree = nested_tuple_to_tree(tuple_tree)
sage: print_md_tree(relabel_tree(tree, (4,3,2,1)))
SERIES
 4
 3
 PARALLEL
  2
  1

>>> from sage.all import *
>>> from sage.graphs.graph_decompositions.modular_decomposition import *
>>> tuple_tree = (NodeType.SERIES, Integer(1), Integer(2), (NodeType.PARALLEL, Integer(3), Integer(4)))
>>> tree = nested_tuple_to_tree(tuple_tree)
>>> print_md_tree(relabel_tree(tree, (Integer(4),Integer(3),Integer(2),Integer(1))))
SERIES
 4
 3
 PARALLEL
  2
  1
sage.graphs.graph_decompositions.modular_decomposition.test_gamma_modules(trials, vertices, prob, verbose=False)[source]

Verify that the vertices of each gamma class of a random graph are modules of that graph.

INPUT:

  • trials – the number of trials to run

  • vertices – the size of the graph to use

  • prob – the probability that any given edge is in the graph See RandomGNP() for more details

  • verbose – print information on each trial

EXAMPLES:

sage: from sage.graphs.graph_decompositions.modular_decomposition import *
sage: test_gamma_modules(3, 7, 0.5)

>>> from sage.all import *
>>> from sage.graphs.graph_decompositions.modular_decomposition import *
>>> test_gamma_modules(Integer(3), Integer(7), RealNumber('0.5'))
sage.graphs.graph_decompositions.modular_decomposition.test_maximal_modules(tree_root, graph)[source]

Test the maximal nature of modules in a modular decomposition tree.

Suppose the module \(M = [M_1, M_2, \cdots, n]\) is the input modular decomposition tree. Algorithm forms pairs like \((M_1, M_2), (M_1, M_3), \cdots, (M_1, M_n)\); \((M_2, M_3), (M_2, M_4), \cdots, (M_2, M_n)\); \(\cdots\) and so on and tries to form a module using the pair. If the module formed has same type as \(M\) and is of type SERIES or PARALLEL then the formed module is not considered maximal. Otherwise it is considered maximal and \(M\) is not a modular decomposition tree.

INPUT:

  • tree_root – modular decomposition tree whose modules are tested for maximal nature

  • graph – graph whose modular decomposition tree is tested

OUTPUT:

True if all modules at first level in the modular decomposition tree are maximal in nature

EXAMPLES:

sage: from sage.graphs.graph_decompositions.modular_decomposition import *
sage: g = graphs.HexahedralGraph()
sage: test_maximal_modules(modular_decomposition(g), g)
True

>>> from sage.all import *
>>> from sage.graphs.graph_decompositions.modular_decomposition import *
>>> g = graphs.HexahedralGraph()
>>> test_maximal_modules(modular_decomposition(g), g)
True
sage.graphs.graph_decompositions.modular_decomposition.test_modular_decomposition(tree_root, graph)[source]

Test the input modular decomposition tree using recursion.

INPUT:

  • tree_root – root of the modular decomposition tree to be tested

  • graph – graph whose modular decomposition tree needs to be tested

OUTPUT: True if input tree is a modular decomposition else False

EXAMPLES:

sage: from sage.graphs.graph_decompositions.modular_decomposition import *
sage: g = graphs.HexahedralGraph()
sage: test_modular_decomposition(modular_decomposition(g), g)
True

>>> from sage.all import *
>>> from sage.graphs.graph_decompositions.modular_decomposition import *
>>> g = graphs.HexahedralGraph()
>>> test_modular_decomposition(modular_decomposition(g), g)
True
sage.graphs.graph_decompositions.modular_decomposition.test_module(module, graph)[source]

Test whether input module is actually a module.

INPUT:

  • module – module which needs to be tested

  • graph – input sage graph which contains the module

OUTPUT: True if input module is a module by definition else False

EXAMPLES:

sage: from sage.graphs.graph_decompositions.modular_decomposition import *
sage: g = graphs.HexahedralGraph()
sage: tree_root = modular_decomposition(g)
sage: test_module(tree_root, g)
True
sage: test_module(tree_root.children[0], g)
True

>>> from sage.all import *
>>> from sage.graphs.graph_decompositions.modular_decomposition import *
>>> g = graphs.HexahedralGraph()
>>> tree_root = modular_decomposition(g)
>>> test_module(tree_root, g)
True
>>> test_module(tree_root.children[Integer(0)], g)
True
sage.graphs.graph_decompositions.modular_decomposition.tree_to_nested_tuple(root)[source]

Convert a modular decomposition tree to a nested tuple.

INPUT:

  • root – the root of the modular decomposition tree

OUTPUT:

A tuple whose first element is the type of the root of the tree and whose subsequent nodes are either vertex labels in the case of leaves or tuples representing the child subtrees.

EXAMPLES:

sage: from sage.graphs.graph_decompositions.modular_decomposition import *
sage: g = graphs.OctahedralGraph()
sage: tree_to_nested_tuple(modular_decomposition(g))
(SERIES, [(PARALLEL, [2, 3]), (PARALLEL, [1, 4]), (PARALLEL, [0, 5])])

>>> from sage.all import *
>>> from sage.graphs.graph_decompositions.modular_decomposition import *
>>> g = graphs.OctahedralGraph()
>>> tree_to_nested_tuple(modular_decomposition(g))
(SERIES, [(PARALLEL, [2, 3]), (PARALLEL, [1, 4]), (PARALLEL, [0, 5])])