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
orFOREST
. Node split can beNO_SPLIT
,LEFT_SPLIT
,RIGHT_SPLIT
orBOTH_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 nodenode_split
– is of type NodeSplit and specifies the type of splits which have occurred in the node and its descendantsindex_in_root
– specifies the index of the node in the forest obtained after promotion phasecomp_num
– specifies the number given to nodes in a (co)component before refinementis_separated
– specifies whether a split has occurred with the node as the root
- has_left_split()#
Check whether
self
hasLEFT_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
hasRIGHT_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
andRIGHT_SPLIT
can exist together inself
asBOTH_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 areLEFT_SPLIT
– indicates a left split has occurredRIGHT_SPLIT
– indicates a right split has occurredBOTH_SPLIT
– indicates both left and right split have occurredNO_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 moduleSERIES
– indicates the node is a series modulePRIME
– indicates the node is a prime moduleFOREST
– indicates a forest containing treesNORMAL
– 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 vertexRIGHT_OF_SOURCE
– indicates vertex is to right of source and is connected to but not a neighbour of source vertexSOURCE
– 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
isnode_type
.INPUT:
module
– module which is testednode_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 testedvertices_in_module
– list containing vertices in the modulegraph
– 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 pairother_index
– second module in the module pairtree_root
– modular decomposition tree which contains the modules in the module pairgraph
– graph whose modular decomposition tree is created
OUTPUT:
[module_formed, vertices]
wheremodule_formed
isTrue
if module is formed elseFalse
andvertices
is a list of vertices included in the formed moduleEXAMPLES:
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 andSERIES
if graph is of type SERIESEXAMPLES:
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
orSERIES
node at the root and children being the modular decomposition of the subgraphs induced by the components. Otherwise, the root isPRIME
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 computedg_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
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
orSERIES
node at the root and children being the modular decomposition of the subgraphs induced by the components. Otherwise, the root isPRIME
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 computedg_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 bytree_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 verifyEXAMPLES:
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 treeperm
– a function, dictionary, list, permutation, orNone
representing the relabeling. Seerelabel()
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 runvertices
– the size of the graph to useprob
– the probability that any given edge is in the graph. SeeRandomGNP()
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
orPARALLEL
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 naturegraph
– graph whose modular decomposition tree is tested
OUTPUT:
True
if all modules at first level in the modular decomposition tree are maximal in natureEXAMPLES:
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 testedgraph
– graph whose modular decomposition tree needs to be tested
OUTPUT:
True
if input tree is a modular decomposition elseFalse
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 testedgraph
– input sage graph which contains the module
OUTPUT:
True
if input module is a module by definition elseFalse
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])])