Modular Decomposition#

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

class sage.graphs.graph_decompositions.modular_decomposition.Node(node_type)#

Bases: object

Node class stores information about the node type, node split and index of the node in the parent tree.

Node type can be PRIME, SERIES, PARALLEL, NORMAL or FOREST. Node split can be NO_SPLIT, LEFT_SPLIT, RIGHT_SPLIT or BOTH_SPLIT. A node is split in the refinement phase and the split used is propagated to the ancestors.

node_type – is of type NodeType and specifies the type of node
node_split – is of type NodeSplit and specifies the type of splits which have occurred in the node and its descendants
index_in_root – specifies the index of the node in the forest obtained after promotion phase
comp_num – specifies the number given to nodes in a (co)component before refinement
is_separated – specifies whether a split has occurred with the node as the root

has_left_split()#

Check whether self has LEFT_SPLIT.

EXAMPLES:

sage: from sage.graphs.graph_decompositions.modular_decomposition import *
sage: node = Node(NodeType.PRIME)
sage: node.set_node_split(NodeSplit.LEFT_SPLIT)
sage: node.has_left_split()
True
sage: node = Node(NodeType.PRIME)
sage: node.set_node_split(NodeSplit.BOTH_SPLIT)
sage: node.has_left_split()
True

has_right_split()#

Check whether self has RIGHT_SPLIT.

EXAMPLES:

sage: from sage.graphs.graph_decompositions.modular_decomposition import *
sage: node = Node(NodeType.PRIME)
sage: node.set_node_split(NodeSplit.RIGHT_SPLIT)
sage: node.has_right_split()
True
sage: node = Node(NodeType.PRIME)
sage: node.set_node_split(NodeSplit.BOTH_SPLIT)
sage: node.has_right_split()
True

set_node_split(node_split)#

Add node_split to the node split of self.

LEFT_SPLIT and RIGHT_SPLIT can exist together in self as BOTH_SPLIT.

INPUT:

node_split – node_split to be added to self

EXAMPLES:

sage: from sage.graphs.graph_decompositions.modular_decomposition import *
sage: node = Node(NodeType.PRIME)
sage: node.set_node_split(NodeSplit.LEFT_SPLIT)
sage: node.node_split == NodeSplit.LEFT_SPLIT
True
sage: node.set_node_split(NodeSplit.RIGHT_SPLIT)
sage: node.node_split == NodeSplit.BOTH_SPLIT
True
sage: node = Node(NodeType.PRIME)
sage: node.set_node_split(NodeSplit.BOTH_SPLIT)
sage: node.node_split == NodeSplit.BOTH_SPLIT
True

class sage.graphs.graph_decompositions.modular_decomposition.NodeSplit(value)#

Bases: Enum

Enumeration class used to specify the split that has occurred at the node or at any of its descendants.

NodeSplit is defined for every node in modular decomposition tree and is required during the refinement and promotion phase of modular decomposition tree computation. Various node splits defined are

LEFT_SPLIT – indicates a left split has occurred
RIGHT_SPLIT – indicates a right split has occurred
BOTH_SPLIT – indicates both left and right split have occurred
NO_SPLIT – indicates no split has occurred

BOTH_SPLIT = 3#

LEFT_SPLIT = 1#

NO_SPLIT = 0#

RIGHT_SPLIT = 2#

class sage.graphs.graph_decompositions.modular_decomposition.NodeType(value)#

Bases: Enum

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
FOREST – indicates a forest containing trees
NORMAL – indicates the node is normal containing a vertex

FOREST = -1#

NORMAL = 3#

PARALLEL = 2#

PRIME = 0#

SERIES = 1#

class sage.graphs.graph_decompositions.modular_decomposition.VertexPosition(value)#

Bases: Enum

Enumeration class used to define position of a vertex w.r.t source in modular decomposition.

For computing modular decomposition of connected graphs a source vertex is chosen. The position of vertex is w.r.t this source vertex. The various positions defined are

LEFT_OF_SOURCE – indicates vertex is to left of source and is a neighbour of source vertex
RIGHT_OF_SOURCE – indicates vertex is to right of source and is connected to but not a neighbour of source vertex
SOURCE – indicates vertex is source vertex

LEFT_OF_SOURCE = -1#

RIGHT_OF_SOURCE = 1#

SOURCE = 0#

sage.graphs.graph_decompositions.modular_decomposition.children_node_type(module, node_type)#

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(modular_decomposition(g))
SERIES
 PARALLEL
  0
  5
 PARALLEL
  1
  4
 PARALLEL
  2
  3
sage: children_node_type(tree_root, NodeType.SERIES)
False
sage: children_node_type(tree_root, NodeType.PARALLEL)
True

sage.graphs.graph_decompositions.modular_decomposition.create_normal_node(vertex)#

Return a normal node with no children

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 create_normal_node
sage: node = create_normal_node(2)
sage: node
NORMAL [2]

sage.graphs.graph_decompositions.modular_decomposition.create_parallel_node()#

Return a parallel node with no children

OUTPUT:

A node object with node_type set as NodeType.PARALLEL

EXAMPLES:

sage: from sage.graphs.graph_decompositions.modular_decomposition import create_parallel_node
sage: node = create_parallel_node()
sage: node
PARALLEL []

sage.graphs.graph_decompositions.modular_decomposition.create_prime_node()#

Return a prime node with no children

OUTPUT:

A node object with node_type set as NodeType.PRIME

EXAMPLES:

sage: from sage.graphs.graph_decompositions.modular_decomposition import create_prime_node
sage: node = create_prime_node()
sage: node
PRIME []

sage.graphs.graph_decompositions.modular_decomposition.create_series_node()#

Return a series node with no children

OUTPUT:

A node object with node_type set as NodeType.SERIES

EXAMPLES:

sage: from sage.graphs.graph_decompositions.modular_decomposition import create_series_node
sage: node = create_series_node()
sage: node
SERIES []

sage.graphs.graph_decompositions.modular_decomposition.either_connected_or_not_connected(v, vertices_in_module, graph)#

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
  0
  5
 PARALLEL
  1
  4
 PARALLEL
  2
  3
sage: either_connected_or_not_connected(2, [1, 4], g)
True
sage: either_connected_or_not_connected(2, [3, 4], g)
False

sage.graphs.graph_decompositions.modular_decomposition.equivalent_trees(root1, root2)#

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

sage.graphs.graph_decompositions.modular_decomposition.form_module(index, other_index, tree_root, graph)#

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

sage.graphs.graph_decompositions.modular_decomposition.gamma_classes(graph)#

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})]

sage.graphs.graph_decompositions.modular_decomposition.get_module_type(graph)#

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

sage.graphs.graph_decompositions.modular_decomposition.get_vertices(component_root)#

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.FOREST)
sage: forest.children = [create_normal_node(2),
....:                    create_normal_node(3), create_normal_node(1)]
sage: series_node = Node(NodeType.SERIES)
sage: series_node.children = [create_normal_node(4),
....:                         create_normal_node(5)]
sage: parallel_node = Node(NodeType.PARALLEL)
sage: parallel_node.children = [create_normal_node(6),
....:                           create_normal_node(7)]
sage: forest.children.insert(1, series_node)
sage: forest.children.insert(3, parallel_node)
sage: get_vertices(forest)
[2, 4, 5, 3, 6, 7, 1]

sage.graphs.graph_decompositions.modular_decomposition.habib_maurer_algorithm(graph, g_classes=None)#

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.

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
 1
 5
 7
 8
 11
 0
 2
 6
 3
 9
 4
 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

Tetrahedral Graph is Series:

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

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

Graph from the Wikipedia article Modular_decomposition:

sage: d2 = {1:[2,3,4], 2:[1,4,5,6,7], 3:[1,4,5,6,7], 4:[1,2,3,5,6,7],
....:       5:[2,3,4,6,7], 6:[2,3,4,5,8,9,10,11],
....:       7:[2,3,4,5,8,9,10,11], 8:[6,7,9,10,11], 9:[6,7,8,10,11],
....:       10:[6,7,8,9], 11:[6,7,8,9]}
sage: g = Graph(d2)
sage: 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

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

sage.graphs.graph_decompositions.modular_decomposition.md_tree_to_graph(root)#

Create a graph having the given MD tree.

For the prime nodes we use that every path of length 4 or more is prime.

TODO: accept a function that generates prime graphs as a parameter and use that in the prime nodes.

EXAMPLES:

sage: from sage.graphs.graph_decompositions.modular_decomposition import *
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.graphs.graph_decompositions.modular_decomposition.modular_decomposition(graph, g_classes=None)#

Compute the modular decomposition by the algorithm of Habib and Maurer

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
 1
 5
 7
 8
 11
 0
 2
 6
 3
 9
 4
 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

Tetrahedral Graph is Series:

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

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

Graph from the Wikipedia article Modular_decomposition:

sage: d2 = {1:[2,3,4], 2:[1,4,5,6,7], 3:[1,4,5,6,7], 4:[1,2,3,5,6,7],
....:       5:[2,3,4,6,7], 6:[2,3,4,5,8,9,10,11],
....:       7:[2,3,4,5,8,9,10,11], 8:[6,7,9,10,11], 9:[6,7,8,10,11],
....:       10:[6,7,8,9], 11:[6,7,8,9]}
sage: g = Graph(d2)
sage: 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

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

sage.graphs.graph_decompositions.modular_decomposition.nested_tuple_to_tree(nest)#

Turn a tuple representing the modular decomposition into a tree.

INPUT:

nest – a nested tuple of the form returned by tree_to_nested_tuple()

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

sage.graphs.graph_decompositions.modular_decomposition.permute_decomposition(*args, **kwargs)#

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)

sage.graphs.graph_decompositions.modular_decomposition.print_md_tree(root)#

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(modular_decomposition(graphs.IcosahedralGraph()))
PRIME
 1
 5
 7
 8
 11
 0
 2
 6
 3
 9
 4
 10

sage.graphs.graph_decompositions.modular_decomposition.random_md_tree(max_depth, max_fan_out, leaf_probability)#

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

sage.graphs.graph_decompositions.modular_decomposition.recreate_decomposition(*args, **kwargs)#

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)

sage.graphs.graph_decompositions.modular_decomposition.relabel_tree(root, perm)#

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

sage.graphs.graph_decompositions.modular_decomposition.test_gamma_modules(*args, **kwargs)#

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)

sage.graphs.graph_decompositions.modular_decomposition.test_maximal_modules(tree_root, graph)#

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

sage.graphs.graph_decompositions.modular_decomposition.test_modular_decomposition(tree_root, graph)#

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

sage.graphs.graph_decompositions.modular_decomposition.test_module(module, graph)#

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

sage.graphs.graph_decompositions.modular_decomposition.tree_to_nested_tuple(root)#

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, [0, 5]), (PARALLEL, [1, 4]), (PARALLEL, [2, 3])])