from graphs import *
class Tree:
"""
Fields: tree (Graph), root (Vertex)
Requires: edge from a parent to a child has a label with
the ID of the parent; in an non-empty tree, the
root is the ID of a vrtex in the tree
"""
## Tree() produces a Tree object.
## __init__: -> Tree
def __init__(self):
self.tree = Graph()
self.root = None
## repr(self) produces a string with all nodes, with
## each node listed with its weight, colour,
## and children.
## __repr__: Tree -> Str
## Requires: self is not empty
def __repr__(self):
string_rep = ""
to_process = [self.tree_root()]
while to_process != []:
next = to_process.pop(0)
current_line = repr(next)
children = self.children(next)
current_line = current_line + " has children " + \
repr(children) + "\n"
string_rep = string_rep + current_line
for child in children:
to_process.append(child)
return string_rep
## self.tree_root() produces the ID of the root of self or
## None if there is no root (the tree is empty).
## tree_root: Tree -> (anyof Str None)
def tree_root(self):
return self.root
## self.node_weight(u) produces the weight of the node with ID u.
## node_weight: Tree Str -> Int
## Requires: u is the ID of a node in self
def node_weight(self, u):
return self.tree.vertex_weight(u)
## self.node_colour(u) produces the colour of the node with ID u.
## node_colour: Tree Str -> Str
## Requires: u is the ID of a node in self
def node_colour(self, u):
return self.tree.vertex_colour(u)
## self.edge_weight(u) produces the weight of the edge between
## the node with ID u and its parent.
## edge_weight: Tree Str -> Int
## Requires: u is the ID of a node in self
## u is not the root
def edge_weight(self, u):
v = self.parent(u)
return self.tree.edge_weight(u, v)
## self.edge_colour(u) produces the colour of the edge between
## the node with ID u and its parent.
## edge_colour: Tree Str -> Str
## Requires: u is the ID of a edge in self
## u is not the root
def edge_colour(self, u):
v = self.parent(u)
return self.tree.edge_colour(u, v)
## self.is_leaf(u) produces True if u is a leaf in self and False
## otherwise.
## is_leaf: Tree Str -> Bool
## Requires: u is the ID of a node in self
def is_leaf(self, u):
return self.children(u) == []
## self.children(u) produces a list of the IDs of the children of u.
## children: Tree Str -> (listof Str)
## Requires: u is the ID of a node in self
def children(self, u):
candidates = self.tree.neighbours(u)
children = []
for candidate in candidates:
if self.tree.edge_label(u, candidate) == u:
children.append(candidate)
return children
## self.parent(u) produces the ID of the parent of u if any, and
## None if u is the root.
## parent: Tree Str -> (anyof Str None)
## Requires: u is the ID of a node in self
def parent(self, u):
candidates = self.tree.neighbours(u)
for candidate in candidates:
if self.tree.edge_label(u, candidate) != u:
return candidate
return None
## self == other produces True if self and other have nodes with
## the same IDs and children and the same roots.
## __eq__: Tree Tree -> Bool
def __eq__(self, other):
return self.tree_root() == other.tree_root() and self.tree == other.tree
## self.add_root(u) creates a node with ID u as the root of self.
## add_root: Tree Str Int Str -> None
## Requires: self is empty
def add_root(self, u, weight = 0, colour = "white"):
self.tree.add_vertex(u, "none", weight, colour)
self.root = u
## self.add_leaf(u, v) creates a new node with ID v as the child
## of the node with ID u.
## add_leaf: Tree Str Str -> None
## Requires: u is the ID of a node in self
## v is not the ID of a node in self
def add_leaf(self, u, v):
self.tree.add_vertex(v)
self.tree.add_edge(u, v, u, 0, "white")
## self.set_node_weight(u, new) updates the weight of the node
## with ID u to new.
## Effects: Mutates self by updating the weight of node u
## set_node_weight: Tree Str Int -> None
## Requires: u is the ID of a node in self
def set_node_weight(self, u, new):
self.tree.set_vertex_weight(u, new)
## self.set_node_colour(u, new) updates the colour of the node
## with ID u to new.
## Effects: Mutates self by updating the weight of node u
## set_node_colour: Tree Str Str -> None
## Requires: u is the ID of a node in self
def set_node_colour(self, u, new):
self.tree.set_vertex_colour(u, new)
## self.set_edge_weight(u, new) updates the weight of the edge
## between the node with ID u and its parent to new.
## Effects: Mutates self by updating the weight of the edge
## set_edge_weight: Tree Str Int -> None
## Requires: u is the ID of a node in self
## u is not the root
def set_edge_weight(self, u, new):
v = self.parent(u)
self.tree.set_edge_weight(u, v, new)
## self.set_edge_colour(u, new) updates the colour of the edge
## between the node with ID u and its parent to new.
## Effects: Mutates self by updating the colour of the edge
## set_edge_colour: Tree Str Str -> None
## Requires: u is the ID of a node in self
## u is not the root
def set_edge_colour(self, u, new):
v = self.parent(u)
self.tree.set_edge_colour(u, v, new)
## make_simple_tree(fname) opens the file fname, reads in the lines with the
## information given below, and produces a Tree:
## - number of nodes (one line)
## - ID of a node, number of children, IDs of children (one line
## per node, even if there are no children, with the total
## number of values on a line being the number of children plus
## two)
## make_simple_tree: Str -> Tree
def make_simple_tree(fname):
data_file = open(fname,"r")
data_list = data_file.readlines()
data_file.close()
new_tree = Tree()
# Extracts the number of nodes from the first line of the file.
num_v = int(data_list[0].strip().split()[0])
# For the line containing information about the root of the tree,
# extract data for fields from the list formed by stripping the
# line of blank spaces and dividing the input string into a
# list of items.
root_data = data_list[1].strip().split()
root_id = root_data[0]
# Form root of tree
new_tree.add_root(root_id)
# Add children of root
num_children = int(root_data[1])
for child in range(num_children):
child_id = root_data[child + 2]
new_tree.add_leaf(root_id, child_id)
# For each line containing node information extract data for fields
# from the list formed by stripping the line of blank spaces and
# dividing the input string into a list of items.
for line in data_list[2:num_v+1]:
data = line.strip().split()
id = data[0]
num_children = int(data[1])
for child in range(num_children):
child_id = data[child + 2]
new_tree.add_leaf(id, child_id)
return new_tree
## make_tree(fname) opens the file fname, reads in the lines with the
## information given below, and produces a Tree:
## - number of nodes (one line)
## - ID, weight, colour, and number of children of a node;
## followed by IDs of children (one line per node, even if there
## are no children, with the total number of values on a line being
## the number of children plus four)
## make_tree: Str -> Tree
def make_tree(fname):
data_file = open(fname,"r")
data_list = data_file.readlines()
data_file.close()
new_tree = Tree()
# Extracts the number of nodes from the first line of the file.
num_v = int(data_list[0].strip().split()[0])
# For the line containing information about the root of the tree,
# extract data for fields from the list formed by stripping the
# line of blank spaces and dividing the input string into a
# list of items.
root_data = data_list[1].strip().split()
root_id = root_data[0]
root_weight = int(root_data[1])
root_colour = root_data[2]
# Form root of tree
new_tree.add_root(root_id, root_weight, root_colour)
# Add children of root
num_children = int(root_data[3])
for child in range(num_children):
child_id = root_data[child + 4]
new_tree.add_leaf(root_id, child_id)
# For each line containing node information extract data for fields
# from the list formed by stripping the line of blank spaces and
# dividing the input string into a list of items.
for line in data_list[2:num_v+1]:
data = line.strip().split()
id = data[0]
weight = int(data[1])
colour = data[2]
# Update node with weight and colour
new_tree.set_node_weight(id, weight)
new_tree.set_node_colour(id, colour)
num_children = int(data[3])
for child in range(num_children):
child_id = data[child + 4]
new_tree.add_leaf(id, child_id)
return new_tree
## make_full_tree(fname) opens the file fname, reads in the lines with the
## information given below, and produces a Tree:
## - number of nodes (one line)
## - ID, weight, colour,
## weight of edge to parent, colour of edge to parent,
## (dummy edge values for root) and number of children of a node;
## followed by IDs of children (one line per node, even if there
## are no children, with the total number of values on a line being
## the number of children plus six)
## make_full_tree: Str -> Tree
def make_full_tree(fname):
data_file = open(fname,"r")
data_list = data_file.readlines()
data_file.close()
new_tree = Tree()
# Extracts the number of nodes from the first line of the file.
num_v = int(data_list[0].strip().split()[0])
# For the line containing information about the root of the tree,
# extract data for fields from the list formed by stripping the
# line of blank spaces and dividing the input string into a
# list of items.
root_data = data_list[1].strip().split()
root_id = root_data[0]
root_weight = int(root_data[1])
root_colour = root_data[2]
# Form root of tree
new_tree.add_root(root_id, root_weight, root_colour)
# Add children of root
num_children = int(root_data[5])
for child in range(num_children):
child_id = root_data[child + 6]
new_tree.add_leaf(root_id, child_id)
# For each line containing node information extract data for fields
# from the list formed by stripping the line of blank spaces and
# dividing the input string into a list of items.
for line in data_list[2:num_v+1]:
data = line.strip().split()
id = data[0]
weight = int(data[1])
colour = data[2]
edge_weight = int(data[3])
edge_colour = data[4]
# Update node with label, weight, and colour
new_tree.set_node_weight(id, weight)
new_tree.set_node_colour(id, colour)
new_tree.set_edge_weight(id, edge_weight)
new_tree.set_edge_colour(id, edge_colour)
num_children = int(data[5])
for child in range(num_children):
child_id = data[child + 6]
new_tree.add_leaf(id, child_id)
return new_tree