Coverage for local/lib/python2.7/site-packages/sage/graphs/modular

FOREST [NORMAL [2], SERIES [SERIES [NORMAL [4]], SERIES [NORMAL [5]]], NORMAL [3], PARALLEL [], PARALLEL [NORMAL [7]], PARALLEL [NORMAL [6]], NORMAL [1]]

"""

q = deque()

# q has [parent, child] elements as parent needs to be modified

for child in root.children:

q.append([root, child])

while q:

parent, child = q.popleft()

if child.node_type == NodeType.NORMAL:

continue

# stores the elements to be removed from the child

to_remove = []

# stores the index of child in parent list

index = parent.children.index(child)

for grand_child in child.children:

# if tree and child both have RIGHT_SPLIT then tree from

# child is inserted just after child in the parent

if grand_child.has_right_split() and child.has_right_split():

parent.children.insert(index + 1, grand_child)

to_remove.append(grand_child)

q.append([parent, grand_child])

else:

q.append([child, grand_child])

for grand_child in to_remove:

child.children.remove(grand_child)

def 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.modular_decomposition import Node, NodeType, \

VertexPosition, create_normal_node, refine, promote_right, \

promote_child

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

"""

q = deque()

# q has [parent, child] elements as parent needs to be modified

for child in root.children:

q.append([root, child])

while q:

parent, child = q.popleft()

if child.node_type == NodeType.NORMAL:

continue

# if child node itself has only one child

if len(child.children) == 1 and (child.node_split != \

NodeSplit.NO_SPLIT or \

child.node_type == NodeType.FOREST):

# replace child node by its own child

grand_child = child.children[0]

index = parent.children.index(child)

parent.children.insert(index, grand_child)

parent.children.remove(child)

q.append([parent, grand_child])

# if child node has no children

elif ((not child.children) and child.node_split != NodeSplit.NO_SPLIT):

# remove the child node

parent.children.remove(child)

else:

for grand_child in child.children:

q.append([child, grand_child])

def 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.modular_decomposition import Node, NodeType, \

NodeSplit, create_normal_node, clear_node_split_info

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

"""

root.node_split = NodeSplit.NO_SPLIT

if root.node_type != NodeType.NORMAL:

for node in root.children:

clear_node_split_info(node)

def 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.modular_decomposition import Node, NodeType, \

VertexPosition, create_normal_node, refine

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

"""

x_used = []

# active edges of each vertex in the graph is used to refine the forest

for v in graph.vertices():

if v in vertex_status and vertex_status[v] == VertexPosition.SOURCE:

continue

# set of vertices connected through active edges to v

x = {u for u in graph.neighbor_iterator(v)

if vertex_dist[u] != vertex_dist[v]}

if x not in x_used:

x_used.append(x)

maximal_subtrees_with_leaves_in_x(root, v, x,

vertex_status, False, 0)

get_child_splits(root)

def 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.modular_decomposition import Node, NodeType, \

NodeSplit, create_normal_node, get_child_splits

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

"""

if root.node_type != NodeType.NORMAL:

for node in root.children:

get_child_splits(node)

root.set_node_split(node.node_split)

def 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.modular_decomposition import Node, NodeType, \

VertexPosition, create_normal_node, \

maximal_subtrees_with_leaves_in_x

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

"""

def update_node_info(node, node_type, node_split, comp_num, subtree_list):

"""

Set the various fields for a tree node and update its subtrees

- ``node`` -- node whose fields need to be updated

- ``node_type`` -- node_type to be set

- ``node_split`` -- node_split to be set

- ``comp_num`` -- comp_num to be set

- ``subtree_list`` -- list containing the subtrees

"""

node.node_type = node_type

node.node_split = node_split

node.comp_num = comp_num

node.children = subtree_list

return_split = NodeSplit.NO_SPLIT #initialize split to NO_SPLIT

# all trees in a forest are refined using x

if root.node_type == NodeType.FOREST:

# indicates whether tree is left of source, True if left of source

left_flag = True

for node in root.children:

if node.node_type == NodeType.NORMAL and \

node.children[0] in vertex_status and \

vertex_status[node.children[0]] == VertexPosition.SOURCE:

left_flag = False

subtree_result = maximal_subtrees_with_leaves_in_x(node, v, x,

vertex_status,

left_flag,

level)

if subtree_result:

# Mark the ancestors

root.set_node_split(subtree_result[1])

# handles the prime, series and parallel cases

elif root.node_type != NodeType.NORMAL:

flag = True # indicates the entire root is contained in x

split_flag = False # indicates a split is required

Ta = [] # contains subtrees with leaves in x

Tb = [] # contains subtrees with leaves not in x

for node in root.children:

# refines the children of root

subtree_result = maximal_subtrees_with_leaves_in_x(node, v, x,

vertex_status,

tree_left_of_source,

level + 1)

if subtree_result:

flag = flag and subtree_result[0]

# add the node split of children to root

root.set_node_split(subtree_result[1])

if subtree_result[0]:

Ta.append(node)

split_flag = True

else:

Tb.append(node)

if root.node_type == NodeType.PRIME:

# mark all the children of prime nodes

for node in root.children:

node.set_node_split(root.node_split)

if flag:

# return if all subtrees are in x, no split required

return [True, root.node_split]

elif split_flag: # split required`

split = NodeSplit.LEFT_SPLIT

# if v is right of source and tree is also right of source then

# RIGHT_SPLIT

if vertex_status[v] == VertexPosition.RIGHT_OF_SOURCE and \

not tree_left_of_source:

split = NodeSplit.RIGHT_SPLIT

# add the split to root node_split

root.set_node_split(split)

if root.node_type == NodeType.PRIME:

# mark all the children of prime nodes

for node in root.children:

node.set_node_split(split)

return [False, split]

if root.is_separated:

# if root has already been split then further split not

# required

return [flag, root.node_split]

node_type = root.node_type

root.is_separated = True

# root[1] would now contain Ta and Tb

root.children = []

# add two nodes for Ta and Tb

a = create_parallel_node()

update_node_info(a, node_type, root.node_split,

Ta[0].comp_num, Ta)

b = create_parallel_node()

update_node_info(b, node_type, root.node_split,

Tb[0].comp_num, Tb)

root.children.append(a)

root.children.append(b)

return_split = root.node_split

return [flag, return_split]

# root is a vertex and is contained in x

elif root.children[0] in x:

return [True, root.node_split]

# root is a vertex and is not contained in x

else:

return [False, root.node_split]

def 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.modular_decomposition import create_prime_node

sage: node = create_prime_node()

sage: node

PRIME []

"""

return Node(NodeType.PRIME)

def 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.modular_decomposition import create_parallel_node

sage: node = create_parallel_node()

sage: node

PARALLEL []

"""

return Node(NodeType.PARALLEL)

def 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.modular_decomposition import create_series_node

sage: node = create_series_node()

sage: node

SERIES []

"""

return Node(NodeType.SERIES)

def 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.modular_decomposition import create_normal_node

sage: node = create_normal_node(2)

sage: node

NORMAL [2]

"""

node = Node(NodeType.NORMAL)

node.children.append(vertex)

return node

def print_md_tree(root):

"""

Print the modular decomposition tree

INPUT:

- ``root`` -- root of the modular decomposition tree

EXAMPLES::

sage: from sage.graphs.modular_decomposition import \

modular_decomposition, test_modular_decomposition, print_md_tree

sage: print_md_tree(modular_decomposition(graphs.IcosahedralGraph()))

PRIME

"""

def recursive_print_md_tree(root, level):

"""

Print the modular decomposition tree at root

INPUT:

- ``root`` -- root of the modular decomposition tree

- ``level`` -- indicates the depth of root in the original modular

decomposition tree

"""

if root.node_type != NodeType.NORMAL:

print("{}{}".format(level,str(root.node_type)))

for tree in root.children:

recursive_print_md_tree(tree, level + " ")

else:

print("{}{}".format(level,str(root.children[0])))

recursive_print_md_tree(root, "")

#=============================================================================

# Below functions are implemented to test the modular decomposition tree

#=============================================================================

#Function implemented for testing

def test_modular_decomposition(tree_root, graph):

"""

This function tests 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.modular_decomposition import \

modular_decomposition, test_modular_decomposition

sage: g = graphs.HexahedralGraph()

sage: test_modular_decomposition(modular_decomposition(g), g)

True

"""

if tree_root.node_type != NodeType.NORMAL:

for module in tree_root.children:

if not test_module(module, graph):

# test whether modules pass the defining

# characteristics of modules

return False

if not test_modular_decomposition(module,

graph.subgraph(

get_vertices(module))):

# recursively test the modular decomposition subtrees

return False

if not test_maximal_modules(tree_root, graph):

# test whether the mdoules are maximal in nature

return False

return True

#Function implemented for testing

def test_maximal_modules(tree_root, graph):

"""

This function tests maximal nature of modules in a modular decomposition

tree.

Suppose the module M = [M1, M2, ..., Mn] is the input modular

decomposition tree. Algorithm forms pairs like (M1, M2), (M1, M3),

...(M1, Mn); (M2, M3), (M2, M4), ...(M2, Mn); ... 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 ddecomposition tree

are maximal in nature

EXAMPLES::

sage: from sage.graphs.modular_decomposition import \

modular_decomposition, test_maximal_modules

sage: g = graphs.HexahedralGraph()

sage: test_maximal_modules(modular_decomposition(g), g)

True

"""

if tree_root.node_type != NodeType.NORMAL:

for index, module in enumerate(tree_root.children):

for other_index in range(index + 1, len(tree_root.children)):

# compute the module formed using modules at index and

# other_index

module_formed = form_module(index, other_index,

tree_root, graph)

if module_formed[0]:

# Module formed and the parent of the formed module

# should not both be of type SERIES or PARALLEL

if ((get_module_type(graph.subgraph(module_formed[1])) ==

tree_root.node_type

) and

(tree_root.node_type == NodeType.PARALLEL or

tree_root.node_type == NodeType.SERIES

)):

continue

return False

return True

#Function implemented for testing

def get_module_type(graph):

"""

Return the module type of the root of modular decomposition tree for the

input 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.modular_decomposition import get_module_type

sage: g = graphs.HexahedralGraph()

sage: get_module_type(g)

PRIME

"""

if not graph.is_connected():

return NodeType.PARALLEL

elif graph.complement().is_connected():

return NodeType.PRIME

return NodeType.SERIES

#Function implemented for testing

def form_module(index, other_index, tree_root, graph):

"""

This function forms a module out of the modules in the module pair.

Let modules input be M1 and M2. 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.modular_decomposition import \

modular_decomposition, form_module

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

"""

vertices = set(get_vertices(tree_root.children[index]) +

get_vertices(tree_root.children[other_index]))

# stores all neighbors which are common for all vertices in V

common_neighbors = set()

# stores all neighbors of vertices in V which are outside V

all_neighbors = set()

while True:

# remove vertices from all_neighbors and common_neighbors

all_neighbors = all_neighbors - set(vertices)

common_neighbors = common_neighbors - set(vertices)

for v in vertices:

# stores the neighbors of v which are outside the set of vertices

neighbor_list = set(graph.neighbors(v))

neighbor_list = neighbor_list - vertices

# update all_neighbors and common_neighbors using the

# neighbor_list

all_neighbors = all_neighbors | neighbor_list

common_neighbors = common_neighbors & neighbor_list

if all_neighbors == common_neighbors: # indicates a module is formed

# module formed covers the entire graph

if len(vertices) == graph.order():

return [False, vertices]

return [True, vertices]

# add modules containing uncommon neighbors into the formed module

for v in (all_neighbors - common_neighbors):

for index in range(len(tree_root.children)):

if v in get_vertices(tree_root.children[index]):

vertices = vertices | \

set(get_vertices(tree_root.children[index]))

break

#Function implemented for testing

def 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.modular_decomposition import \

modular_decomposition, test_module

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

"""

# A single vertex is a module

if module.node_type == NodeType.NORMAL:

return True

#vertices contained in module

vertices_in_module = get_vertices(module)

#vertices outside module

vertices_outside = list(set(graph.vertices()) - set(vertices_in_module))

# Nested module with only one child

if module.node_type != NodeType.NORMAL and len(module.children) == 1:

return False

# If children of SERIES module are all SERIES modules

if module.node_type == NodeType.SERIES:

if children_node_type(module, NodeType.SERIES):

return False

# If children of PARALLEL module are all PARALLEL modules

if module.node_type == NodeType.PARALLEL:

if children_node_type(module, NodeType.PARALLEL):

return False

# check the module by definition. Vertices in a module should all either

# be connected or disconnected to any vertex outside module

for v in vertices_outside:

if not either_connected_or_not_connected(v, vertices_in_module,

graph):

return False

return True

#Function implemented for testing

def children_node_type(module, node_type):

"""

Test whether node_type of children of a node is same as input node_type

INPUT:

- ``module`` -- module which is tested

- ``node_type`` -- input node_type

OUTPUT:

``True`` if node_type of children of module is same as input node_type

else ``False``

EXAMPLES::

sage: from sage.graphs.modular_decomposition import \

modular_decomposition, print_md_tree, children_node_type, \

NodeType

sage: g = graphs.OctahedralGraph()

sage: tree_root = modular_decomposition(g)

sage: print_md_tree(modular_decomposition(g))

SERIES

PARALLEL

sage: children_node_type(tree_root, NodeType.SERIES)

False

sage: children_node_type(tree_root, NodeType.PARALLEL)

True

"""

for node in module.children:

if node.node_type != node_type:

return False

return True

#Function implemented for testing

def either_connected_or_not_connected(v, vertices_in_module, graph):

"""

Test 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

OUTPUT:

``True`` if v is either connected or disconnected to all the vertices in

the module else ``False``

EXAMPLES::

sage: from sage.graphs.modular_decomposition import \

print_md_tree, modular_decomposition, \

either_connected_or_not_connected

sage: g = graphs.OctahedralGraph()

sage: print_md_tree(modular_decomposition(g))

SERIES

PARALLEL

sage: either_connected_or_not_connected(2, [1, 4], g)

True

sage: either_connected_or_not_connected(2, [3, 4], g)

False

"""

# marks whether vertex v is connected to first vertex in the module

connected = graph.has_edge(vertices_in_module[0], v)

# if connected is True then all vertices in module should be connected to

# v else disconnected

for u in vertices_in_module:

if (graph.has_edge(u,v) != connected):

return False

return True

Coverage for local/lib/python2.7/site-packages/sage/graphs/modular_decomposition.py : 98%

538 statements 526 run 12 missing 0 excluded