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

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

class sage.graphs.graph_decompositions.modular_decomposition.NodeType

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

class sage.graphs.graph_decompositions.modular_decomposition.VertexPosition

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

sage.graphs.graph_decompositions.modular_decomposition.assembly(graph, root, vertex_status, vertex_dist)

Assemble the forest obtained after the promotion phase into a modular decomposition tree.

INPUT:

  • graph – graph whose MD tree is to be computed

  • root – Forest which would be assembled into a MD tree

  • vertex_status – Dictionary which stores the position of vertex with respect to the source

  • vertex_dist – Dictionary which stores the distance of vertex from source vertex

EXAMPLES:

sage: from sage.graphs.graph_decompositions.modular_decomposition import *
sage: g = Graph()
sage: g.add_vertices([1, 2, 3, 4, 5, 6, 7])
sage: g.add_edge(2, 3)
sage: g.add_edge(4, 3)
sage: g.add_edge(5, 3)
sage: g.add_edge(2, 6)
sage: g.add_edge(2, 7)
sage: g.add_edge(6, 1)
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: vertex_status = {2: VertexPosition.LEFT_OF_SOURCE,
....:                  3: VertexPosition.SOURCE,
....:                  1: VertexPosition.RIGHT_OF_SOURCE,
....:                  4: VertexPosition.LEFT_OF_SOURCE,
....:                  5: VertexPosition.LEFT_OF_SOURCE,
....:                  6: VertexPosition.RIGHT_OF_SOURCE,
....:                  7: VertexPosition.RIGHT_OF_SOURCE}
sage: vertex_dist = {2: 1, 4: 1, 5: 1, 3: 0, 6: 2, 7: 2, 1: 3}
sage: forest.children[0].comp_num = 1
sage: forest.children[1].comp_num = 1
sage: forest.children[1].children[0].comp_num = 1
sage: forest.children[1].children[1].comp_num = 1
sage: number_components(forest, vertex_status)
sage: assembly(g, forest, vertex_status, vertex_dist)
sage: forest.children
[PRIME [NORMAL [2], SERIES [NORMAL [4], NORMAL [5]], NORMAL [3],
        PARALLEL [NORMAL [6], NORMAL [7]], NORMAL [1]]]

sage: g.add_edge(4, 2)
sage: g.add_edge(5, 2)
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: number_cocomponents(forest, vertex_status)
sage: assembly(g, forest, vertex_status, vertex_dist)
sage: forest.children
[PRIME [NORMAL [2], SERIES [NORMAL [4], NORMAL [5], NORMAL [3]],
        PARALLEL [NORMAL [6], NORMAL [7]], NORMAL [1]]]
sage.graphs.graph_decompositions.modular_decomposition.check_parallel(graph, root, left, right, source_index, mu, vertex_dist, vertices_in_component)

Assemble the forest to create a parallel module.

INPUT:

  • root – forest which needs to be assembled

  • left – the leftmost fragment of the last module

  • right – the rightmost fragment of the last module

  • source_index – index of the tree containing the source vertex

  • mu – dictionary which maps the (co)components with their mu values

  • vertex_dist – dictionary which stores the distance of vertex from source vertex

  • vertices_in_component – dictionary which stores a list of various vertices in a (co)component

OUTPUT:

[module_formed, source_index] where module_formed is True if module is formed else False and source_index is the index of the new module which contains the source vertex

EXAMPLES:

sage: from sage.graphs.graph_decompositions.modular_decomposition import *
sage: g = Graph()
sage: g.add_vertices([1, 2, 3, 4, 5, 6, 7])
sage: g.add_edge(2, 3)
sage: g.add_edge(4, 3)
sage: g.add_edge(5, 3)
sage: g.add_edge(2, 6)
sage: g.add_edge(2, 7)
sage: g.add_edge(2, 1)
sage: g.add_edge(4, 1)
sage: forest = Node(NodeType.FOREST)
sage: forest.children = [create_normal_node(2),
....:                    create_normal_node(3)]
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), create_normal_node(1)]
sage: forest.children.insert(1, series_node)
sage: forest.children.append(parallel_node)
sage: vertex_status = {2: VertexPosition.LEFT_OF_SOURCE,
....:                  3: VertexPosition.SOURCE,
....:                  1: VertexPosition.RIGHT_OF_SOURCE,
....:                  4: VertexPosition.LEFT_OF_SOURCE,
....:                  5: VertexPosition.LEFT_OF_SOURCE,
....:                  6: VertexPosition.RIGHT_OF_SOURCE,
....:                  7: VertexPosition.RIGHT_OF_SOURCE}
sage: vertex_dist = {2: 1, 4: 1, 5: 1, 3: 0, 6: 2, 7: 2, 1: 2}
sage: source_index = 2
sage: vertices_in_component = {}
sage: mu = {}
sage: left = right = forest.children[2]
sage: for index, component in enumerate(forest.children):
....:     vertices_in_component[index] = get_vertices(component)
....:     component.index_in_root = index
sage: for index, component in enumerate(forest.children):
....:     if index < source_index:
....:         mu[index] = compute_mu_for_co_component(g, index,
....:                                           source_index, forest,
....:                                           vertices_in_component)
....:     elif index > source_index:
....:         mu[index] = compute_mu_for_component(g, index,
....:                                           source_index, forest,
....:                                           vertices_in_component)
sage: number_components(forest, vertex_status)
sage: check_parallel(g, forest, left, right,
....:              source_index, mu, vertex_dist,
....:              vertices_in_component)
[True, 2]
sage: forest.children
[NORMAL [2],
 SERIES [NORMAL [4], NORMAL [5]],
 PARALLEL [NORMAL [3], NORMAL [6], NORMAL [7], NORMAL [1]]]
sage.graphs.graph_decompositions.modular_decomposition.check_prime(graph, root, left, right, source_index, mu, vertex_dist, vertices_in_component)

Assemble the forest to create a prime module.

INPUT:

  • root – forest which needs to be assembled

  • left – the leftmost fragment of the last module

  • right – the rightmost fragment of the last module

  • source_index – index of the tree containing the source vertex

  • mu – dictionary which maps the (co)components with their mu values

  • vertex_dist – dictionary which stores the distance of vertex from source vertex

  • vertices_in_component – dictionary which stores a list of various vertices in a (co)component

OUTPUT:

[module_formed, source_index] where module_formed is True if module is formed else False and source_index is the index of the new module which contains the source vertex

EXAMPLES:

sage: from sage.graphs.graph_decompositions.modular_decomposition import *
sage: g = Graph()
sage: g.add_vertices([1, 2, 3, 4, 5, 6, 7])
sage: g.add_edge(2, 3)
sage: g.add_edge(4, 3)
sage: g.add_edge(5, 3)
sage: g.add_edge(2, 6)
sage: g.add_edge(2, 7)
sage: g.add_edge(6, 1)
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: vertex_status = {2: VertexPosition.LEFT_OF_SOURCE,
....:                  3: VertexPosition.SOURCE,
....:                  1: VertexPosition.RIGHT_OF_SOURCE,
....:                  4: VertexPosition.LEFT_OF_SOURCE,
....:                  5: VertexPosition.LEFT_OF_SOURCE,
....:                  6: VertexPosition.RIGHT_OF_SOURCE,
....:                  7: VertexPosition.RIGHT_OF_SOURCE}
sage: vertex_dist = {2: 1, 4: 1, 5: 1, 3: 0, 6: 2, 7: 2, 1: 3}
sage: source_index = 2
sage: vertices_in_component = {}
sage: mu = {}
sage: left = right = forest.children[2]
sage: for index, component in enumerate(forest.children):
....:     vertices_in_component[index] = get_vertices(component)
....:     component.index_in_root = index
sage: for index, component in enumerate(forest.children):
....:     if index < source_index:
....:         mu[index] = compute_mu_for_co_component(g, index,
....:                                           source_index, forest,
....:                                           vertices_in_component)
....:     elif index > source_index:
....:         mu[index] = compute_mu_for_component(g, index,
....:                                           source_index, forest,
....:                                           vertices_in_component)
sage: forest.children[0].comp_num = 1
sage: forest.children[1].comp_num = 1
sage: forest.children[1].children[0].comp_num = 1
sage: forest.children[1].children[1].comp_num = 1
sage: number_components(forest, vertex_status)
sage: check_prime(g, forest, left, right,
....:              source_index, mu, vertex_dist,
....:              vertices_in_component)
[True, 0]
sage: forest.children
[PRIME [NORMAL [2], SERIES [NORMAL [4], NORMAL [5]], NORMAL [3],
        PARALLEL [NORMAL [6], NORMAL [7]], NORMAL [1]]]
sage.graphs.graph_decompositions.modular_decomposition.check_series(root, left, right, source_index, mu)

Assemble the forest to create a series module.

INPUT:

  • root – forest which needs to be assembled

  • left – The leftmost fragment of the last module

  • right – The rightmost fragment of the last module

  • source_index – index of the tree containing the source vertex

  • mu – dictionary which maps the (co)components with their mu values

  • vertex_dist – dictionary which stores the distance of vertex from source vertex

  • vertices_in_component – dictionary which stores a list of various vertices in a (co)component

OUTPUT:

[module_formed, source_index] where module_formed is True if module is formed else False and source_index is the index of the new module which contains the source vertex

EXAMPLES:

sage: from sage.graphs.graph_decompositions.modular_decomposition import *
sage: g = Graph()
sage: g.add_vertices([1, 2, 3, 4, 5, 6, 7])
sage: g.add_edge(2, 3)
sage: g.add_edge(4, 3)
sage: g.add_edge(5, 3)
sage: g.add_edge(2, 6)
sage: g.add_edge(2, 7)
sage: g.add_edge(2, 1)
sage: g.add_edge(6, 1)
sage: g.add_edge(4, 2)
sage: g.add_edge(5, 2)
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: vertex_status = {2: VertexPosition.LEFT_OF_SOURCE,
....:                  3: VertexPosition.SOURCE,
....:                  1: VertexPosition.RIGHT_OF_SOURCE,
....:                  4: VertexPosition.LEFT_OF_SOURCE,
....:                  5: VertexPosition.LEFT_OF_SOURCE,
....:                  6: VertexPosition.RIGHT_OF_SOURCE,
....:                  7: VertexPosition.RIGHT_OF_SOURCE}
sage: vertex_dist = {2: 1, 4: 1, 5: 1, 3: 0, 6: 2, 7: 2, 1: 3}
sage: source_index = 2
sage: vertices_in_component = {}
sage: mu = {}
sage: left = right = forest.children[2]
sage: for index, component in enumerate(forest.children):
....:     vertices_in_component[index] = get_vertices(component)
....:     component.index_in_root = index
sage: for index, component in enumerate(forest.children):
....:     if index < source_index:
....:         mu[index] = compute_mu_for_co_component(g, index,
....:                                           source_index, forest,
....:                                           vertices_in_component)
....:     elif index > source_index:
....:         mu[index] = compute_mu_for_component(g, index,
....:                                           source_index, forest,
....:                                           vertices_in_component)
sage: number_cocomponents(forest, vertex_status)
sage: number_components(forest, vertex_status)
sage: check_series(forest, left, right,
....:              source_index, mu)
[True, 1]
sage: forest.children
[NORMAL [2],
 SERIES [NORMAL [4], NORMAL [5], NORMAL [3]],
 PARALLEL [NORMAL [6], NORMAL [7]],
 NORMAL [1]]
sage.graphs.graph_decompositions.modular_decomposition.children_node_type(module, node_type)

Check whether the node type of the childrens 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
        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
sage.graphs.graph_decompositions.modular_decomposition.clear_node_split_info(root)

Set the node_split of nodes to NO_SPLIT

INPUT:

  • root – the forest which needs to be cleared of split information

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: series_node.children[0].node_split = NodeSplit.LEFT_SPLIT
sage: series_node.node_split = NodeSplit.RIGHT_SPLIT
sage: forest.children.insert(1, series_node)
sage: clear_node_split_info(forest)
sage: series_node.node_split == NodeSplit.NO_SPLIT
True
sage: series_node.children[0].node_split == NodeSplit.NO_SPLIT
True
sage.graphs.graph_decompositions.modular_decomposition.compute_mu_for_co_component(graph, component_index, source_index, root, vertices_in_component)

Compute the mu value for co-component

INPUT:

  • graph – Graph whose MD tree needs to be computed

  • component_index – index of the co-component

  • source_index – index of the source in the forest

  • root – the forest which needs to be assembled into a MD tree

  • vertices_in_component – dictionary which maps index i to list of vertices in the tree at index i in the forest

OUTPUT:

The mu value (component in the forest) for the co-component

EXAMPLES:

sage: from sage.graphs.graph_decompositions.modular_decomposition import *
sage: g = Graph()
sage: g.add_vertices([1, 2, 3, 4, 5, 6, 7])
sage: g.add_edge(2, 3)
sage: g.add_edge(4, 3)
sage: g.add_edge(5, 3)
sage: g.add_edge(2, 6)
sage: g.add_edge(2, 7)
sage: g.add_edge(2, 1)
sage: g.add_edge(6, 1)
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: vertices_in_component = {}
sage: for index, component in enumerate(forest.children):
....:     vertices_in_component[index] = get_vertices(component)
sage: compute_mu_for_co_component(g, 0, 2, forest,
....:                             vertices_in_component)
NORMAL [1]
sage: compute_mu_for_co_component(g, 1, 2, forest,
....:                             vertices_in_component)
NORMAL [3]
sage.graphs.graph_decompositions.modular_decomposition.compute_mu_for_component(graph, component_index, source_index, root, vertices_in_component)

Compute the mu value for component

INPUT:

  • graph – Graph whose MD tree needs to be computed

  • component_index – index of the component

  • source_index – index of the source in the forest

  • root – the forest which needs to be assembled into a MD tree

  • vertices_in_component – dictionary which maps index i to list of vertices in the tree at the index i in the forest

OUTPUT:

The mu value (co-component in the forest) for the component

EXAMPLES:

sage: from sage.graphs.graph_decompositions.modular_decomposition import *
sage: g = Graph()
sage: g.add_vertices([1, 2, 3, 4, 5, 6, 7])
sage: g.add_edge(2, 3)
sage: g.add_edge(4, 3)
sage: g.add_edge(5, 3)
sage: g.add_edge(2, 6)
sage: g.add_edge(2, 7)
sage: g.add_edge(6, 1)
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: vertices_in_component = {}
sage: for index, component in enumerate(forest.children):
....:     vertices_in_component[index] = get_vertices(component)
sage: compute_mu_for_component(g, 3, 2, forest,
....:                          vertices_in_component)
SERIES [NORMAL [4], NORMAL [5]]
sage: compute_mu_for_component(g, 4, 2, forest,
....:                          vertices_in_component)
NORMAL [2]
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
        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
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_child_splits(root)

Add the node_split of children to the parent node

INPUT:

  • root – input modular decomposition tree

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: series_node.children[0].node_split = NodeSplit.LEFT_SPLIT
sage: series_node.node_split = NodeSplit.RIGHT_SPLIT
sage: forest.children.insert(1, series_node)
sage: get_child_splits(forest)
sage: series_node.node_split == NodeSplit.BOTH_SPLIT
True
sage: forest.node_split == NodeSplit.BOTH_SPLIT
True
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_vertex_in(node)

Return the first vertex encountered in the depth-first traversal of the tree rooted at node

INPUT:

  • tree – input modular decomposition tree

OUTPUT:

Return the first vertex encountered in recursion

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: forest.children.insert(1, series_node)
sage: get_vertex_in(forest)
2
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.has_left_cocomponent_fragment(root, cocomp_index)

Check whether cocomponent at cocomp_index has a cocomponent to its left with same comp_num.

INPUT:

  • root – the forest to which cocomponent belongs

  • cocomp_index – index at which cocomponent is present in root

OUTPUT:

True if cocomponent at cocomp_index has a cocomponent to its left with same comp_num, and False otherwise.

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: forest.children[0].comp_num = 1
sage: forest.children[1].comp_num = 1
sage: forest.children[1].children[0].comp_num = 1
sage: forest.children[1].children[1].comp_num = 1
sage: has_left_cocomponent_fragment(forest, 1)
True
sage: has_left_cocomponent_fragment(forest, 0)
False
sage.graphs.graph_decompositions.modular_decomposition.has_right_component_fragment(root, comp_index)

Check whether component at comp_index has a component to its right with same comp_num.

INPUT:

  • root – the forest to which component belongs

  • comp_index – index at which component is present in root

OUTPUT:

True if component at comp_index has a component to its right with same comp_num, and False otherwise.

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: forest.children[3].comp_num = 1
sage: forest.children[4].comp_num = 1
sage: has_right_component_fragment(forest, 3)
True
sage: has_right_component_fragment(forest, 4)
False
sage.graphs.graph_decompositions.modular_decomposition.has_right_layer_neighbor(graph, root, comp_index, vertex_dist, vertices_in_component)

Check whether component at comp_index has a connected component to its right with vertices at different level from the source vertex.

INPUT:

  • root – the forest to which component belongs

  • comp_index – index at which component is present in root

  • vertex_dist – dictionary which stores the distance of vertex from source vertex

  • vertices_in_component – dictionary which stores a list of various vertices in a (co)component

OUTPUT:

True if component at comp_index has a right layer neighbor, and False otherwise.

EXAMPLES:

sage: from sage.graphs.graph_decompositions.modular_decomposition import *
sage: g = Graph()
sage: g.add_vertices([1, 2, 3, 4, 5, 6, 7])
sage: g.add_edge(2, 3)
sage: g.add_edge(4, 3)
sage: g.add_edge(5, 3)
sage: g.add_edge(2, 6)
sage: g.add_edge(2, 7)
sage: g.add_edge(2, 1)
sage: g.add_edge(6, 1)
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: vertex_dist = {2: 1, 4: 1, 5: 1, 3: 0, 6: 2, 7: 2, 1: 3}
sage: vertices_in_component = {}
sage: for index, component in enumerate(forest.children):
....:     vertices_in_component[index] = get_vertices(component)
....:     component.index_in_root = index
sage: has_right_layer_neighbor(g, forest, 3, vertex_dist,
....:                          vertices_in_component)
True
sage.graphs.graph_decompositions.modular_decomposition.is_component_connected(graph, index1, index2, vertices_in_component)

Check whether the two specified (co)components are connected.

INPUT:

  • graph – Graph whose MD tree needs to be computed

  • index1 – index of the first (co)component

  • index2 – index of the second (co)component

  • vertices_in_component – dictionary which maps index i to list of vertices in the tree at the index i in the forest

OUTPUT:

True if the (co)components are connected else False

EXAMPLES:

sage: from sage.graphs.graph_decompositions.modular_decomposition import *
sage: g = Graph()
sage: g.add_vertices([1, 2, 3, 4, 5, 6, 7])
sage: g.add_edge(2, 3)
sage: g.add_edge(4, 3)
sage: g.add_edge(5, 3)
sage: g.add_edge(2, 6)
sage: g.add_edge(2, 7)
sage: g.add_edge(6, 1)
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: vertices_in_component = {}
sage: for index, component in enumerate(forest.children):
....:     vertices_in_component[index] = get_vertices(component)
sage: is_component_connected(g, 0, 1, vertices_in_component)
False
sage: is_component_connected(g, 0, 3, vertices_in_component)
True
sage.graphs.graph_decompositions.modular_decomposition.maximal_subtrees_with_leaves_in_x(root, v, x, vertex_status, tree_left_of_source, level)

Refine the forest based on the active edges(x) of vertex v

INPUT:

  • root – the forest which needs to be assembled into a MD tree

  • v – the vertex used to refine

  • x – set of vertices connected to v and at different distance from source compared to v

  • vertex_status – dictionary mapping the vertex to the position w.r.t source

  • tree_left_of_source – flag indicating whether tree is

  • level – indicates the recursion level, 0 for root

OUTPUT:

[contained_in_x, split] where contained_in_x is True if all vertices in root are subset of x else False and split is the split which occurred at any node in root

EXAMPLES:

sage: from sage.graphs.graph_decompositions.modular_decomposition import *
sage: g = Graph()
sage: g.add_vertices([1, 2, 3, 4, 5, 6, 7])
sage: g.add_edge(2, 3)
sage: g.add_edge(4, 3)
sage: g.add_edge(5, 3)
sage: g.add_edge(2, 6)
sage: g.add_edge(2, 7)
sage: g.add_edge(2, 1)
sage: g.add_edge(6, 1)
sage: g.add_edge(4, 2)
sage: g.add_edge(5, 2)
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: vertex_status = {2: VertexPosition.LEFT_OF_SOURCE,
....:                  3: VertexPosition.SOURCE,
....:                  1: VertexPosition.RIGHT_OF_SOURCE,
....:                  4: VertexPosition.LEFT_OF_SOURCE,
....:                  5: VertexPosition.LEFT_OF_SOURCE,
....:                  6: VertexPosition.RIGHT_OF_SOURCE,
....:                  7: VertexPosition.RIGHT_OF_SOURCE}
sage: vertex_dist = {2: 1, 4: 1, 5: 1, 3: 0, 6: 2, 7: 2, 1: 3}
sage: x = {u for u in g.neighbor_iterator(2)
....:            if vertex_dist[u] != vertex_dist[2]}
sage: maximal_subtrees_with_leaves_in_x(forest, 2, x, vertex_status,
....:                                   False, 0)
sage: forest
FOREST [NORMAL [2], SERIES [NORMAL [4], NORMAL [5]], NORMAL [3],
        PARALLEL [NORMAL [6], NORMAL [7]], NORMAL [1]]
sage: x = {u for u in g.neighbor_iterator(1)
....:            if vertex_dist[u] != vertex_dist[1]}
sage: maximal_subtrees_with_leaves_in_x(forest, 1, x, vertex_status,
....:                                   False, 0)
sage: forest
FOREST [NORMAL [2], SERIES [NORMAL [4], NORMAL [5]], NORMAL [3],
        PARALLEL [PARALLEL [NORMAL [6]], PARALLEL [NORMAL [7]]],
        NORMAL [1]]
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)

Compute the modular decomposition tree of graph.

The tree structure is represented in form of nested lists. A tree node is an object of type Node. The Node object further contains a list of its children

INPUT:

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

OUTPUT:

A nested list representing the modular decomposition tree computed for the graph

EXAMPLES:

The Icosahedral graph is Prime:

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

The Octahedral graph is not Prime:

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

Tetrahedral Graph is Series:

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

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(modular_decomposition(g))
SERIES
      5
      PARALLEL
        3
        4
      PARALLEL
        1
        2
sage.graphs.graph_decompositions.modular_decomposition.nested_tuple_to_tree(nest)

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
sage.graphs.graph_decompositions.modular_decomposition.number_cocomponents(root, vertex_status)

Number the cocomponents to the left of SOURCE vertex in the forest input to the assembly phase

INPUT:

  • root – the forest which contains the cocomponents and components

  • vertex_status – dictionary which stores the position of vertex w.r.t SOURCE

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(2, parallel_node)
sage: vertex_status = {2: VertexPosition.LEFT_OF_SOURCE,
....:                  3: VertexPosition.SOURCE,
....:                  1: VertexPosition.RIGHT_OF_SOURCE,
....:                  4: VertexPosition.LEFT_OF_SOURCE,
....:                  5: VertexPosition.LEFT_OF_SOURCE,
....:                  6: VertexPosition.LEFT_OF_SOURCE,
....:                  7: VertexPosition.LEFT_OF_SOURCE}
sage: number_cocomponents(forest, vertex_status)
sage: forest.children[1].children[0].comp_num
1
sage: forest.children[1].children[1].comp_num
2
sage.graphs.graph_decompositions.modular_decomposition.number_components(root, vertex_status)

Number the components to the right of SOURCE vertex in the forest input to the assembly phase

INPUT:

  • root – the forest which contains the components and cocomponents

  • vertex_status – dictionary which stores the position of vertex w.r.t SOURCE

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.append(series_node)
sage: forest.children.append(parallel_node)
sage: vertex_status = {2: VertexPosition.LEFT_OF_SOURCE,
....:                  3: VertexPosition.SOURCE,
....:                  1: VertexPosition.RIGHT_OF_SOURCE,
....:                  4: VertexPosition.RIGHT_OF_SOURCE,
....:                  5: VertexPosition.RIGHT_OF_SOURCE,
....:                  6: VertexPosition.RIGHT_OF_SOURCE,
....:                  7: VertexPosition.RIGHT_OF_SOURCE}
sage: number_components(forest, vertex_status)
sage: forest.children[-1].children[0].comp_num
2
sage: forest.children[-1].children[1].comp_num
3
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
 5
 7
 11
 1
 8
 0
 9
 4
 10
 6
 2
 3
sage.graphs.graph_decompositions.modular_decomposition.promote_child(root)

Perform the promotion phase on the forest \(root\).

If marked parent has no children it is removed, if it has one child then it is replaced by its child

INPUT:

  • root – the forest which needs to be promoted

EXAMPLES:

sage: from sage.graphs.graph_decompositions.modular_decomposition import *
sage: g = Graph()
sage: g.add_vertices([1, 2, 3, 4, 5, 6, 7])
sage: g.add_edge(2, 3)
sage: g.add_edge(4, 3)
sage: g.add_edge(5, 3)
sage: g.add_edge(2, 6)
sage: g.add_edge(4, 7)
sage: g.add_edge(2, 1)
sage: g.add_edge(6, 1)
sage: g.add_edge(4, 2)
sage: g.add_edge(5, 2)
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: vertex_status = {2: VertexPosition.LEFT_OF_SOURCE,
....:                  3: VertexPosition.SOURCE,
....:                  1: VertexPosition.RIGHT_OF_SOURCE,
....:                  4: VertexPosition.LEFT_OF_SOURCE,
....:                  5: VertexPosition.LEFT_OF_SOURCE,
....:                  6: VertexPosition.RIGHT_OF_SOURCE,
....:                  7: VertexPosition.RIGHT_OF_SOURCE}
sage: vertex_dist = {2: 1, 4: 1, 5: 1, 3: 0, 6: 2, 7: 2, 1: 3}
sage: refine(g, forest, vertex_dist, vertex_status)
sage: promote_right(forest)
sage: promote_child(forest)
sage: forest
FOREST [NORMAL [2], SERIES [NORMAL [4], NORMAL [5]], NORMAL [3],
        NORMAL [7], NORMAL [6], NORMAL [1]]
sage.graphs.graph_decompositions.modular_decomposition.promote_left(root)

Perform the promotion phase on the forest root.

If child and parent both are marked by LEFT_SPLIT then child is removed and placed just before the parent

INPUT:

  • root – The forest which needs to be promoted

EXAMPLES:

sage: from sage.graphs.graph_decompositions.modular_decomposition import *
sage: g = Graph()
sage: g.add_vertices([1, 2, 3, 4, 5, 6, 7])
sage: g.add_edge(2, 3)
sage: g.add_edge(4, 3)
sage: g.add_edge(5, 3)
sage: g.add_edge(2, 6)
sage: g.add_edge(4, 7)
sage: g.add_edge(2, 1)
sage: g.add_edge(6, 1)
sage: g.add_edge(4, 2)
sage: g.add_edge(5, 2)
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: vertex_status = {2: VertexPosition.LEFT_OF_SOURCE,
....:                  3: VertexPosition.SOURCE,
....:                  1: VertexPosition.RIGHT_OF_SOURCE,
....:                  4: VertexPosition.LEFT_OF_SOURCE,
....:                  5: VertexPosition.LEFT_OF_SOURCE,
....:                  6: VertexPosition.RIGHT_OF_SOURCE,
....:                  7: VertexPosition.RIGHT_OF_SOURCE}
sage: vertex_dist = {2: 1, 4: 1, 5: 1, 3: 0, 6: 2, 7: 2, 1: 3}
sage: x = {u for u in g.neighbor_iterator(2)
....:            if vertex_dist[u] != vertex_dist[2]}
sage: maximal_subtrees_with_leaves_in_x(forest, 2, x, vertex_status,
....:                                   False, 0)
sage: promote_left(forest)
sage: forest
FOREST [NORMAL [2], SERIES [NORMAL [4], NORMAL [5]], NORMAL [3],
        PARALLEL [NORMAL [6]], PARALLEL [NORMAL [7]],
        PARALLEL [], NORMAL [1]]
sage.graphs.graph_decompositions.modular_decomposition.promote_right(root)

Perform the promotion phase on the forest root.

If child and parent both are marked by RIGHT_SPLIT then child is removed and placed just after the parent

INPUT:

  • root – the forest which needs to be promoted

EXAMPLES:

sage: from sage.graphs.graph_decompositions.modular_decomposition import *
sage: g = Graph()
sage: g.add_vertices([1, 2, 3, 4, 5, 6, 7])
sage: g.add_edge(2, 3)
sage: g.add_edge(4, 3)
sage: g.add_edge(5, 3)
sage: g.add_edge(2, 6)
sage: g.add_edge(4, 7)
sage: g.add_edge(2, 1)
sage: g.add_edge(6, 1)
sage: g.add_edge(4, 2)
sage: g.add_edge(5, 2)
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: vertex_status = {2: VertexPosition.LEFT_OF_SOURCE,
....:                  3: VertexPosition.SOURCE,
....:                  1: VertexPosition.RIGHT_OF_SOURCE,
....:                  4: VertexPosition.LEFT_OF_SOURCE,
....:                  5: VertexPosition.LEFT_OF_SOURCE,
....:                  6: VertexPosition.RIGHT_OF_SOURCE,
....:                  7: VertexPosition.RIGHT_OF_SOURCE}
sage: vertex_dist = {2: 1, 4: 1, 5: 1, 3: 0, 6: 2, 7: 2, 1: 3}
sage: refine(g, forest, vertex_dist, vertex_status)
sage: promote_right(forest)
sage: forest
FOREST [NORMAL [2], SERIES [SERIES [NORMAL [4]], SERIES [NORMAL [5]]],
        NORMAL [3], PARALLEL [], PARALLEL [NORMAL [7]],
        PARALLEL [NORMAL [6]], NORMAL [1]]
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.recursively_number_parts(part_root, part_num, by_type)

Recursively number the nodes in the (co)components(parts).

If the node_type of part_root is same as by_type then part_num is incremented for subtree at each child of part_root else part is numbered by part_num.

INPUT:

  • part_root – root of the part to be numbered

  • part_num – input number to be used as reference for numbering the (co)components

  • by_type – type which determines how numbering is done

OUTPUT:

The value incremented to part_num.

EXAMPLES:

sage: from sage.graphs.graph_decompositions.modular_decomposition import *
sage: series_node = Node(NodeType.SERIES)
sage: series_node.children = [create_normal_node(4),
....:                         create_normal_node(5)]
sage: recursively_number_parts(series_node, 1, NodeType.SERIES)
2
sage: series_node.comp_num
1
sage: series_node.children[0].comp_num
1
sage: series_node.children[1].comp_num
2
sage.graphs.graph_decompositions.modular_decomposition.refine(graph, root, vertex_dist, vertex_status)

Refine the forest based on the active edges

INPUT:

  • graph – graph whose MD tree needs to be computed

  • root – the forest which needs to be assembled into a MD tree

  • vertex_dist – dictionary mapping the vertex with distance from the source

  • vertex_status – dictionary mapping the vertex to the position w.r.t. source

EXAMPLES:

sage: from sage.graphs.graph_decompositions.modular_decomposition import *
sage: g = Graph()
sage: g.add_vertices([1, 2, 3, 4, 5, 6, 7])
sage: g.add_edge(2, 3)
sage: g.add_edge(4, 3)
sage: g.add_edge(5, 3)
sage: g.add_edge(2, 6)
sage: g.add_edge(2, 7)
sage: g.add_edge(2, 1)
sage: g.add_edge(6, 1)
sage: g.add_edge(4, 2)
sage: g.add_edge(5, 2)
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: vertex_status = {2: VertexPosition.LEFT_OF_SOURCE,
....:                  3: VertexPosition.SOURCE,
....:                  1: VertexPosition.RIGHT_OF_SOURCE,
....:                  4: VertexPosition.LEFT_OF_SOURCE,
....:                  5: VertexPosition.LEFT_OF_SOURCE,
....:                  6: VertexPosition.RIGHT_OF_SOURCE,
....:                  7: VertexPosition.RIGHT_OF_SOURCE}
sage: vertex_dist = {2: 1, 4: 1, 5: 1, 3: 0, 6: 2, 7: 2, 1: 3}
sage: refine(g, forest, vertex_dist, vertex_status)
sage: forest
FOREST [NORMAL [2], SERIES [NORMAL [4], NORMAL [5]], NORMAL [3],
       PARALLEL [PARALLEL [NORMAL [6]], PARALLEL [NORMAL [7]]],
       NORMAL [1]]
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, [2, 3]), (PARALLEL, [1, 4]), (PARALLEL, [0, 5])])
sage.graphs.graph_decompositions.modular_decomposition.update_comp_num(node)

Set the comp_num of node to the comp_num of its first child.

INPUT:

  • node – node whose comp_num needs to be updated

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