Module coinor.gimpy.tree

Tree class built on top of Graph class.

'''
Tree class built on top of Graph class.
'''
from __future__ import print_function
from __future__ import absolute_import
from builtins import str

from .graph import Graph, Node
from .global_constants import *
try:
    from src.blimpy import Stack, Queue
except ImportError:
    from coinor.blimpy import Stack, Queue
import operator
import sys

class Tree(Graph):
    '''
    Tree class. It inherits from Graph class. Provides DFS, BFS and traverse
    methods.
    '''
    def __init__(self, **attrs):
        '''
        API: __init__(self, **attrs)
        Description:
            Constructor. Sets attrbutes of class using argument.
        Input:
            attrs: Attributes in keyword arguments format.
        '''
        attrs['type'] = DIRECTED_GRAPH
        if 'layout' not in attrs:
            attrs['layout'] = 'dot'
        Graph.__init__(self, **attrs)
        self.root = None

    def get_children(self, n):
        '''
        API: get_children(self, n)
        Description:
            Returns list of children of node n.
        Pre:
            Node with name n should exist.
        Input:
            n: Node name.
        Return:
            Returns list of names of children nodes of n.
        '''
        return self.get_neighbors(n)

    def get_parent(self, n):
        '''
        API: get_parent(self, n)
        Description:
            Returns parent node name if n's parent exists, returns
            None otherwise.
        Pre:
            Node with name n should exist.
        Input:
            n: Node name.
        Return:
            Returns parent name of n if its parent exists, returns None
            otherwise.
        '''
        n = self.get_node(n)
        return n.get_attr('parent')

    def add_root(self, root, **attrs):
        '''
        API: add_root(self, root, **attrs)
        Description:
            Adds root node to the tree with name root and returns root Node
            instance.
        Input:
            root: Root node name.
            attrs: Root node attributes.
        Post:
            Changes self.root.
        Return:
            Returns root Node instance.
        '''
        attrs['level'] = 0
        self.root = self.add_node(root, **attrs)
        return self.root

    def add_child(self, n, parent, **attrs):
        '''
        API: add_child(self, n, parent, **attrs)
        Description:
            Adds child n to node parent and return Node n.
        Pre:
            Node with name parent should exist.
        Input:
            n: Child node name.
            parent: Parent node name.
            attrs: Attributes of node being added.
        Post:
            Updates Graph related graph data attributes.
        Return:
            Returns n Node instance.
        '''
        attrs['level'] = self.get_node(parent).get_attr('level') + 1
        attrs['parent'] = parent
        self.add_node(n, **attrs)
        self.add_edge(parent, n)
        return self.get_node(n)

    def dfs(self, root = None, display = None):
        '''
        API: dfs(self, root = None, display = None)
        Description:
            Searches tree starting from node named root using depth-first
            strategy if root argument is provided. Starts search from root node
            of the tree otherwise.
        Pre:
            Node indicated by root argument should exist.
        Input:
            root: Starting node name.
            display: Display argument.
        '''
        if root == None:
            root = self.root
        if display == None:
            display = self.attr['display']
        self.traverse(root, display, Stack())

    def bfs(self, root = None, display = None):
        '''
        API: bfs(self, root = None, display = None)
        Description:
            Searches tree starting from node named root using breadth-first
            strategy if root argument is provided. Starts search from root node
            of the tree otherwise.
        Pre:
            Node indicated by root argument should exist.
        Input:
            root: Starting node name.
            display: Display argument.
        '''
        if root == None:
            root = self.root
        if display == None:
            display = self.attr['display']
        self.traverse(root, display, Queue())

    def traverse(self, root = None, display = None, q = Stack()):
        '''
        API: traverse(self, root = None, display = None, q = Stack())
        Description:
            Traverses tree starting from node named root. Used strategy (BFS,
            DFS) is controlled by argument q. It is a DFS if q is Queue(), BFS
            if q is Stack(). Starts search from root argument if it is given.
            Starts from root node of the tree otherwise.
        Pre:
            Node indicated by root argument should exist.
        Input:
            root: Starting node name.
            display: Display argument.
            q: Queue data structure instance. It is either a Stack() or
            Queue().
        '''
        if root == None:
            root = self.root
        if display == None:
            display = self.attr['display']
        if isinstance(q, Queue):
            addToQ = q.enqueue
            removeFromQ = q.dequeue
        elif isinstance(q, Stack):
            addToQ = q.push
            removeFromQ = q.pop
        addToQ(root)
        while not q.isEmpty():
            current = removeFromQ()
            #print current
            if display:
                self.display(highlight = [current])
            for n in self.get_children(current):
                addToQ(n)


class BinaryTree(Tree):
    '''
    Binary tree class. Inherits Tree class. Provides methods for adding
    left/right childs and binary tree specific DFS and BFS methods.
    '''
    def __init__(self, **attrs):
        '''
        API: __init__(self, **attrs)
        Description:
            Class constructor.
        Input:
            attrs: Tree attributes in keyword arguments format. See Graph and
            Tree class for details.
        '''
        Tree.__init__(self, **attrs)

    def add_root(self, root, **attrs):
        '''
        API: add_root(self, root, **attrs)
        Description:
            Adds root node to the binary tree.
        Input:
            root: Name of the root node.
            attrs: Attributes of the root node.
        Post:
            Changes self.root attribute.
        '''
        Tree.add_root(self, root, **attrs)

    def add_right_child(self, n, parent, **attrs):
        '''
        API: add_right_child(self, n, parent, **attrs)
        Description:
            Adds right child n to node parent.
        Pre:
            Right child of parent should not exist.
        Input:
            n: Node name.
            parent: Parent node name.
            attrs: Attributes of node n.
        '''
        if self.get_right_child(parent) is not None:
            msg = "Right child already exists for node " + str(parent)
            raise Exception(msg)
        attrs['direction'] = 'R'
        self.set_node_attr(parent, 'Rchild', n)
        self.add_child(n, parent, **attrs)

    def add_left_child(self, n, parent, **attrs):
        '''
        API: add_left_child(self, n, parent, **attrs)
        Description:
            Adds left child n to node parent.
        Pre:
            Left child of parent should not exist.
        Input:
            n: Node name.
            parent: Parent node name.
            attrs: Attributes of node n.
        '''
        if self.get_left_child(parent) is not None:
            msg = "Right child already exists for node " + str(parent)
            raise Exception(msg)
        attrs['direction'] = 'L'
        self.set_node_attr(parent, 'Lchild', n)
        self.add_child(n, parent, **attrs)

    def get_right_child(self, n):
        '''
        API: get_right_child(self, n)
        Description:
            Returns right child of node n. n can be Node() instance or string
            (name of node).
        Pre:
            Node n should be present in the tree.
        Input:
            n: Node name or Node() instance.
        Return:
            Returns name of the right child of n.
        '''
        if isinstance(n, Node):
            return n.get_attr('Rchild')
        return self.get_node_attr(n, 'Rchild')

    def get_left_child(self, n):
        '''
        API: get_left_child(self, n)
        Description:
            Returns left child of node n. n can be Node() instance or string
            (name of node).
        Pre:
            Node n should be present in the tree.
        Input:
            n: Node name or Node() instance.
        Return:
            Returns name of the left child of n.
        '''
        if isinstance(n, Node):
            return n.get_attr('Lchild')
        return self.get_node_attr(n, 'Lchild')

    def del_node(self, n):
        '''
        API: del_node(self, n)
        Description:
            Removes node n from tree.
        Pre:
            Node n should be present in the tree.
        Input:
            n: Node name.
        '''
        parent = self.get_node_attr(n, 'parent')
        if self.get_node_attr(n, 'direction') == 'R':
            self.set_node_attr(parent, 'Rchild', None)
        else:
            self.set_node_attr(parent, 'Lchild', None)
        Graph.del_node(self, n)

    def print_nodes(self, order = 'in', priority = 'L', display = None,
                    root = None):
        '''
        API: print_nodes(self, order = 'in', priority = 'L', display = None,
                    root = None)
        Description:
            A recursive function that prints nodes to stdout starting from
            root.
        Input:
            order: Order of printing. Acceptable arguments are 'pre', 'in',
            'post'.
            priority: Priority of printing, acceptable arguments are 'L' and
            'R'.
            display: Display mode.
            root: Starting node.
        '''
        old_display = None
        if root == None:
            root = self.root.name
        if display == None:
            display = self.attr['display']
        else:
            old_display = self.attr['display']
            self.attr['display'] = display
        if priority == 'L':
            first_child = self.get_left_child
            second_child = self.get_right_child
        else:
            first_child = self.get_right_child
            second_child = self.get_left_child
        if order == 'pre':
            print(root)
        if first_child(root) is not None:
            if display:
                self.display(highlight = [root])
            self.print_nodes(order, priority, display, first_child(root))
        if order == 'in':
            print(root)
        if second_child(root) is not None:
            if display:
                self.display(highlight = [root])
            self.print_nodes(order, priority, display, second_child(root))
        if order == 'post':
            print(root)
        if display:
            self.display(highlight = [root])
        if old_display:
            self.attr['display'] = old_display

    def dfs(self, root = None, display = None, priority = 'L'):
        '''
        API: dfs(self, root=None, display=None, priority='L', order='in')
        Description:
            Searches tree starting from node named root using depth-first
            strategy if root argument is provided. Starts search from root node
            of the tree otherwise.
        Input:
            root: Starting node.
            display: Display mode.
            priority: Priority used when exploring children of the node.
            Acceptable arguments are 'L' and 'R'.
        '''
        if root == None:
            root = self.root
        self.traverse(root, display, Stack(), priority)

    def bfs(self, root = None, display = None, priority = 'L'):
        '''
        API: bfs(self, root=None, display=None, priority='L', order='in')
        Description:
            Searches tree starting from node named root using breadth-first
            strategy if root argument is provided. Starts search from root node
            of the tree otherwise.
        Input:
            root: Starting node.
            display: Display mode.
            priority: Priority used when exploring children of the node.
            Acceptable arguments are 'L' and 'R'.
        '''
        if root == None:
            root = self.root
        self.traverse(root, display, Queue(), priority)

    def traverse(self, root = None, display = None, q = Stack(),
                 priority = 'L'):
        '''
        API: traverse(self, root=None, display=None, q=Stack(), priority='L',
                      order='in')
        Description:
            Traverses tree starting from node named root if root argument is
            provided. Starts search from root node of the tree otherwise. Search
            strategy is determined by q data structure. It is DFS if q is
            Stack() and BFS if Queue().
        Input:
            root: Starting node.
            display: Display mode.
            q: Queue data structure, either Queue() or Stack().
            priority: Priority used when exploring children of the node.
            Acceptable arguments are 'L' and 'R'.
            order: Ineffective, will be removed.
        '''
        old_display = None
        if root == None:
            root = self.root
        if display == None:
            display = self.attr['display']
        else:
            old_display = self.attr['display']
            self.attr['display'] = display
        if isinstance(q, Queue):
            addToQ = q.enqueue
            removeFromQ = q.dequeue
        elif isinstance(q, Stack):
            addToQ = q.push
            removeFromQ = q.pop
        if priority == 'L':
            first_child = self.get_left_child
            second_child = self.get_right_child
        else:
            first_child = self.get_right_child
            second_child = self.get_left_child
        addToQ(root)
        while not q.isEmpty():
            current = removeFromQ()
            if display:
                self.display(highlight = [current])
            n = first_child(current)
            if n is not None:
                addToQ(n)
            n = second_child(current)
            if n is not None:
                addToQ(n)
        if old_display:
            self.attr['display'] = old_display

    def printexp(self, display = None, root = None):
        if root == None:
            root = self.root
        if display == None:
            display = self.attr['display']
        if self.get_left_child(root):
            if display:
                self.display(highlight = [root])
            print('(', end=' ')
            sys.stdout.flush()
            self.printexp(display, self.get_left_child(root))
        if isinstance(root, Node):
            if 'label' in root.attr:
                root_label = root.attr['label']
            else:
                root_label = root.name
        else:
            root_label = self.get_node_attr(root, 'label')
            if root_label == None:
                root_label = root
        print(root_label, end=' ')
        sys.stdout.flush()
        if display:
                self.display(highlight = [root])
        if self.get_right_child(root):
            self.printexp(display, self.get_right_child(root))
            print(')', end=' ')
            sys.stdout.flush()
            if display:
                self.display(highlight = [root])

    def postordereval(self, display = None, root = None):
        if root == None:
            root = self.root
        if display == None:
            display = self.attr['display']
        opers = {'+':operator.add, '-':operator.sub, '*':operator.mul,
                 '/':operator.truediv}
        res1 = None
        res2 = None
        if self.get_left_child(root):
            if display:
                self.display(highlight = [root])
            res1 = self.postordereval(display, self.get_left_child(root))
        if isinstance(root, Node):
            if 'label' in root.attr:
                root_label = root.attr['label']
            else:
                root_label = root.name
        else:
            root_label = self.get_node_attr(root, 'label')
            if root_label == None:
                root_label = root
        print(root_label, end=' ')
        sys.stdout.flush()
        if display:
                self.display(highlight = [root])
        if self.get_right_child(root):
            res2 = self.postordereval(display, self.get_right_child(root))
        if res1 and res2:
            result = opers[root_label](res1 , res2)
            print('=', result)
            sys.stdout.flush()
            if display:
                self.display(highlight = [root])
            print(result, end=' ')
            sys.stdout.flush()
            return result
        else:
            return int(root_label) 

if __name__ == '__main__':

    T = BinaryTree(display = 'matplotlib')
    T.add_root('*')
    T.add_left_child('+', '*')
    T.add_left_child('4', '+')
    T.add_right_child('5', '+')
    T.add_right_child('7', '*')
    T.printexp()
    print()
    T.postordereval()
    print()

Classes

class BinaryTree (**attrs)

Binary tree class. Inherits Tree class. Provides methods for adding left/right childs and binary tree specific DFS and BFS methods.

API: init(self, **attrs)

Description

Class constructor.

Input

attrs: Tree attributes in keyword arguments format. See Graph and Tree class for details.

Expand source code

class BinaryTree(Tree):
    '''
    Binary tree class. Inherits Tree class. Provides methods for adding
    left/right childs and binary tree specific DFS and BFS methods.
    '''
    def __init__(self, **attrs):
        '''
        API: __init__(self, **attrs)
        Description:
            Class constructor.
        Input:
            attrs: Tree attributes in keyword arguments format. See Graph and
            Tree class for details.
        '''
        Tree.__init__(self, **attrs)

    def add_root(self, root, **attrs):
        '''
        API: add_root(self, root, **attrs)
        Description:
            Adds root node to the binary tree.
        Input:
            root: Name of the root node.
            attrs: Attributes of the root node.
        Post:
            Changes self.root attribute.
        '''
        Tree.add_root(self, root, **attrs)

    def add_right_child(self, n, parent, **attrs):
        '''
        API: add_right_child(self, n, parent, **attrs)
        Description:
            Adds right child n to node parent.
        Pre:
            Right child of parent should not exist.
        Input:
            n: Node name.
            parent: Parent node name.
            attrs: Attributes of node n.
        '''
        if self.get_right_child(parent) is not None:
            msg = "Right child already exists for node " + str(parent)
            raise Exception(msg)
        attrs['direction'] = 'R'
        self.set_node_attr(parent, 'Rchild', n)
        self.add_child(n, parent, **attrs)

    def add_left_child(self, n, parent, **attrs):
        '''
        API: add_left_child(self, n, parent, **attrs)
        Description:
            Adds left child n to node parent.
        Pre:
            Left child of parent should not exist.
        Input:
            n: Node name.
            parent: Parent node name.
            attrs: Attributes of node n.
        '''
        if self.get_left_child(parent) is not None:
            msg = "Right child already exists for node " + str(parent)
            raise Exception(msg)
        attrs['direction'] = 'L'
        self.set_node_attr(parent, 'Lchild', n)
        self.add_child(n, parent, **attrs)

    def get_right_child(self, n):
        '''
        API: get_right_child(self, n)
        Description:
            Returns right child of node n. n can be Node() instance or string
            (name of node).
        Pre:
            Node n should be present in the tree.
        Input:
            n: Node name or Node() instance.
        Return:
            Returns name of the right child of n.
        '''
        if isinstance(n, Node):
            return n.get_attr('Rchild')
        return self.get_node_attr(n, 'Rchild')

    def get_left_child(self, n):
        '''
        API: get_left_child(self, n)
        Description:
            Returns left child of node n. n can be Node() instance or string
            (name of node).
        Pre:
            Node n should be present in the tree.
        Input:
            n: Node name or Node() instance.
        Return:
            Returns name of the left child of n.
        '''
        if isinstance(n, Node):
            return n.get_attr('Lchild')
        return self.get_node_attr(n, 'Lchild')

    def del_node(self, n):
        '''
        API: del_node(self, n)
        Description:
            Removes node n from tree.
        Pre:
            Node n should be present in the tree.
        Input:
            n: Node name.
        '''
        parent = self.get_node_attr(n, 'parent')
        if self.get_node_attr(n, 'direction') == 'R':
            self.set_node_attr(parent, 'Rchild', None)
        else:
            self.set_node_attr(parent, 'Lchild', None)
        Graph.del_node(self, n)

    def print_nodes(self, order = 'in', priority = 'L', display = None,
                    root = None):
        '''
        API: print_nodes(self, order = 'in', priority = 'L', display = None,
                    root = None)
        Description:
            A recursive function that prints nodes to stdout starting from
            root.
        Input:
            order: Order of printing. Acceptable arguments are 'pre', 'in',
            'post'.
            priority: Priority of printing, acceptable arguments are 'L' and
            'R'.
            display: Display mode.
            root: Starting node.
        '''
        old_display = None
        if root == None:
            root = self.root.name
        if display == None:
            display = self.attr['display']
        else:
            old_display = self.attr['display']
            self.attr['display'] = display
        if priority == 'L':
            first_child = self.get_left_child
            second_child = self.get_right_child
        else:
            first_child = self.get_right_child
            second_child = self.get_left_child
        if order == 'pre':
            print(root)
        if first_child(root) is not None:
            if display:
                self.display(highlight = [root])
            self.print_nodes(order, priority, display, first_child(root))
        if order == 'in':
            print(root)
        if second_child(root) is not None:
            if display:
                self.display(highlight = [root])
            self.print_nodes(order, priority, display, second_child(root))
        if order == 'post':
            print(root)
        if display:
            self.display(highlight = [root])
        if old_display:
            self.attr['display'] = old_display

    def dfs(self, root = None, display = None, priority = 'L'):
        '''
        API: dfs(self, root=None, display=None, priority='L', order='in')
        Description:
            Searches tree starting from node named root using depth-first
            strategy if root argument is provided. Starts search from root node
            of the tree otherwise.
        Input:
            root: Starting node.
            display: Display mode.
            priority: Priority used when exploring children of the node.
            Acceptable arguments are 'L' and 'R'.
        '''
        if root == None:
            root = self.root
        self.traverse(root, display, Stack(), priority)

    def bfs(self, root = None, display = None, priority = 'L'):
        '''
        API: bfs(self, root=None, display=None, priority='L', order='in')
        Description:
            Searches tree starting from node named root using breadth-first
            strategy if root argument is provided. Starts search from root node
            of the tree otherwise.
        Input:
            root: Starting node.
            display: Display mode.
            priority: Priority used when exploring children of the node.
            Acceptable arguments are 'L' and 'R'.
        '''
        if root == None:
            root = self.root
        self.traverse(root, display, Queue(), priority)

    def traverse(self, root = None, display = None, q = Stack(),
                 priority = 'L'):
        '''
        API: traverse(self, root=None, display=None, q=Stack(), priority='L',
                      order='in')
        Description:
            Traverses tree starting from node named root if root argument is
            provided. Starts search from root node of the tree otherwise. Search
            strategy is determined by q data structure. It is DFS if q is
            Stack() and BFS if Queue().
        Input:
            root: Starting node.
            display: Display mode.
            q: Queue data structure, either Queue() or Stack().
            priority: Priority used when exploring children of the node.
            Acceptable arguments are 'L' and 'R'.
            order: Ineffective, will be removed.
        '''
        old_display = None
        if root == None:
            root = self.root
        if display == None:
            display = self.attr['display']
        else:
            old_display = self.attr['display']
            self.attr['display'] = display
        if isinstance(q, Queue):
            addToQ = q.enqueue
            removeFromQ = q.dequeue
        elif isinstance(q, Stack):
            addToQ = q.push
            removeFromQ = q.pop
        if priority == 'L':
            first_child = self.get_left_child
            second_child = self.get_right_child
        else:
            first_child = self.get_right_child
            second_child = self.get_left_child
        addToQ(root)
        while not q.isEmpty():
            current = removeFromQ()
            if display:
                self.display(highlight = [current])
            n = first_child(current)
            if n is not None:
                addToQ(n)
            n = second_child(current)
            if n is not None:
                addToQ(n)
        if old_display:
            self.attr['display'] = old_display

    def printexp(self, display = None, root = None):
        if root == None:
            root = self.root
        if display == None:
            display = self.attr['display']
        if self.get_left_child(root):
            if display:
                self.display(highlight = [root])
            print('(', end=' ')
            sys.stdout.flush()
            self.printexp(display, self.get_left_child(root))
        if isinstance(root, Node):
            if 'label' in root.attr:
                root_label = root.attr['label']
            else:
                root_label = root.name
        else:
            root_label = self.get_node_attr(root, 'label')
            if root_label == None:
                root_label = root
        print(root_label, end=' ')
        sys.stdout.flush()
        if display:
                self.display(highlight = [root])
        if self.get_right_child(root):
            self.printexp(display, self.get_right_child(root))
            print(')', end=' ')
            sys.stdout.flush()
            if display:
                self.display(highlight = [root])

    def postordereval(self, display = None, root = None):
        if root == None:
            root = self.root
        if display == None:
            display = self.attr['display']
        opers = {'+':operator.add, '-':operator.sub, '*':operator.mul,
                 '/':operator.truediv}
        res1 = None
        res2 = None
        if self.get_left_child(root):
            if display:
                self.display(highlight = [root])
            res1 = self.postordereval(display, self.get_left_child(root))
        if isinstance(root, Node):
            if 'label' in root.attr:
                root_label = root.attr['label']
            else:
                root_label = root.name
        else:
            root_label = self.get_node_attr(root, 'label')
            if root_label == None:
                root_label = root
        print(root_label, end=' ')
        sys.stdout.flush()
        if display:
                self.display(highlight = [root])
        if self.get_right_child(root):
            res2 = self.postordereval(display, self.get_right_child(root))
        if res1 and res2:
            result = opers[root_label](res1 , res2)
            print('=', result)
            sys.stdout.flush()
            if display:
                self.display(highlight = [root])
            print(result, end=' ')
            sys.stdout.flush()
            return result
        else:
            return int(root_label) 

Ancestors

• Tree
• Graph

Subclasses

• coinor.grumpy.BBTree.BBTree

Methods

def add_left_child(self, n, parent, **attrs)

API: add_left_child(self, n, parent, **attrs)

Description

Adds left child n to node parent.

Pre

Left child of parent should not exist.

Input

n: Node name. parent: Parent node name. attrs: Attributes of node n.

Expand source code

def add_left_child(self, n, parent, **attrs):
    '''
    API: add_left_child(self, n, parent, **attrs)
    Description:
        Adds left child n to node parent.
    Pre:
        Left child of parent should not exist.
    Input:
        n: Node name.
        parent: Parent node name.
        attrs: Attributes of node n.
    '''
    if self.get_left_child(parent) is not None:
        msg = "Right child already exists for node " + str(parent)
        raise Exception(msg)
    attrs['direction'] = 'L'
    self.set_node_attr(parent, 'Lchild', n)
    self.add_child(n, parent, **attrs)

def add_right_child(self, n, parent, **attrs)

API: add_right_child(self, n, parent, **attrs)

Description

Adds right child n to node parent.

Pre

Right child of parent should not exist.

Input

n: Node name. parent: Parent node name. attrs: Attributes of node n.

Expand source code

def add_right_child(self, n, parent, **attrs):
    '''
    API: add_right_child(self, n, parent, **attrs)
    Description:
        Adds right child n to node parent.
    Pre:
        Right child of parent should not exist.
    Input:
        n: Node name.
        parent: Parent node name.
        attrs: Attributes of node n.
    '''
    if self.get_right_child(parent) is not None:
        msg = "Right child already exists for node " + str(parent)
        raise Exception(msg)
    attrs['direction'] = 'R'
    self.set_node_attr(parent, 'Rchild', n)
    self.add_child(n, parent, **attrs)

def add_root(self, root, **attrs)

API: add_root(self, root, **attrs)

Description

Adds root node to the binary tree.

Input

root: Name of the root node. attrs: Attributes of the root node.

Post

Changes self.root attribute.

Expand source code

def add_root(self, root, **attrs):
    '''
    API: add_root(self, root, **attrs)
    Description:
        Adds root node to the binary tree.
    Input:
        root: Name of the root node.
        attrs: Attributes of the root node.
    Post:
        Changes self.root attribute.
    '''
    Tree.add_root(self, root, **attrs)

def bfs(self, root=None, display=None, priority='L')

API: bfs(self, root=None, display=None, priority='L', order='in')

Description

Searches tree starting from node named root using breadth-first strategy if root argument is provided. Starts search from root node of the tree otherwise.

Input

root: Starting node. display: Display mode. priority: Priority used when exploring children of the node. Acceptable arguments are 'L' and 'R'.

Expand source code

def bfs(self, root = None, display = None, priority = 'L'):
    '''
    API: bfs(self, root=None, display=None, priority='L', order='in')
    Description:
        Searches tree starting from node named root using breadth-first
        strategy if root argument is provided. Starts search from root node
        of the tree otherwise.
    Input:
        root: Starting node.
        display: Display mode.
        priority: Priority used when exploring children of the node.
        Acceptable arguments are 'L' and 'R'.
    '''
    if root == None:
        root = self.root
    self.traverse(root, display, Queue(), priority)

def del_node(self, n)

API: del_node(self, n)

Description

Removes node n from tree.

Pre

Node n should be present in the tree.

Input

n: Node name.

Expand source code

def del_node(self, n):
    '''
    API: del_node(self, n)
    Description:
        Removes node n from tree.
    Pre:
        Node n should be present in the tree.
    Input:
        n: Node name.
    '''
    parent = self.get_node_attr(n, 'parent')
    if self.get_node_attr(n, 'direction') == 'R':
        self.set_node_attr(parent, 'Rchild', None)
    else:
        self.set_node_attr(parent, 'Lchild', None)
    Graph.del_node(self, n)

def dfs(self, root=None, display=None, priority='L')

API: dfs(self, root=None, display=None, priority='L', order='in')

Description

Searches tree starting from node named root using depth-first strategy if root argument is provided. Starts search from root node of the tree otherwise.

Input

root: Starting node. display: Display mode. priority: Priority used when exploring children of the node. Acceptable arguments are 'L' and 'R'.

Expand source code

def dfs(self, root = None, display = None, priority = 'L'):
    '''
    API: dfs(self, root=None, display=None, priority='L', order='in')
    Description:
        Searches tree starting from node named root using depth-first
        strategy if root argument is provided. Starts search from root node
        of the tree otherwise.
    Input:
        root: Starting node.
        display: Display mode.
        priority: Priority used when exploring children of the node.
        Acceptable arguments are 'L' and 'R'.
    '''
    if root == None:
        root = self.root
    self.traverse(root, display, Stack(), priority)

def get_left_child(self, n)

API: get_left_child(self, n)

Description

Returns left child of node n. n can be Node() instance or string (name of node).

Pre

Node n should be present in the tree.

Input

n: Node name or Node() instance.

Return

Returns name of the left child of n.

Expand source code

def get_left_child(self, n):
    '''
    API: get_left_child(self, n)
    Description:
        Returns left child of node n. n can be Node() instance or string
        (name of node).
    Pre:
        Node n should be present in the tree.
    Input:
        n: Node name or Node() instance.
    Return:
        Returns name of the left child of n.
    '''
    if isinstance(n, Node):
        return n.get_attr('Lchild')
    return self.get_node_attr(n, 'Lchild')

def get_right_child(self, n)

API: get_right_child(self, n)

Description

Returns right child of node n. n can be Node() instance or string (name of node).

Pre

Node n should be present in the tree.

Input

n: Node name or Node() instance.

Return

Returns name of the right child of n.

Expand source code

def get_right_child(self, n):
    '''
    API: get_right_child(self, n)
    Description:
        Returns right child of node n. n can be Node() instance or string
        (name of node).
    Pre:
        Node n should be present in the tree.
    Input:
        n: Node name or Node() instance.
    Return:
        Returns name of the right child of n.
    '''
    if isinstance(n, Node):
        return n.get_attr('Rchild')
    return self.get_node_attr(n, 'Rchild')

def postordereval(self, display=None, root=None)

Expand source code

def postordereval(self, display = None, root = None):
    if root == None:
        root = self.root
    if display == None:
        display = self.attr['display']
    opers = {'+':operator.add, '-':operator.sub, '*':operator.mul,
             '/':operator.truediv}
    res1 = None
    res2 = None
    if self.get_left_child(root):
        if display:
            self.display(highlight = [root])
        res1 = self.postordereval(display, self.get_left_child(root))
    if isinstance(root, Node):
        if 'label' in root.attr:
            root_label = root.attr['label']
        else:
            root_label = root.name
    else:
        root_label = self.get_node_attr(root, 'label')
        if root_label == None:
            root_label = root
    print(root_label, end=' ')
    sys.stdout.flush()
    if display:
            self.display(highlight = [root])
    if self.get_right_child(root):
        res2 = self.postordereval(display, self.get_right_child(root))
    if res1 and res2:
        result = opers[root_label](res1 , res2)
        print('=', result)
        sys.stdout.flush()
        if display:
            self.display(highlight = [root])
        print(result, end=' ')
        sys.stdout.flush()
        return result
    else:
        return int(root_label) 

def print_nodes(self, order='in', priority='L', display=None, root=None)

API: print_nodes(self, order = 'in', priority = 'L', display = None, root = None)

Description

A recursive function that prints nodes to stdout starting from root.

Input

order: Order of printing. Acceptable arguments are 'pre', 'in', 'post'. priority: Priority of printing, acceptable arguments are 'L' and 'R'. display: Display mode. root: Starting node.

Expand source code

def print_nodes(self, order = 'in', priority = 'L', display = None,
                root = None):
    '''
    API: print_nodes(self, order = 'in', priority = 'L', display = None,
                root = None)
    Description:
        A recursive function that prints nodes to stdout starting from
        root.
    Input:
        order: Order of printing. Acceptable arguments are 'pre', 'in',
        'post'.
        priority: Priority of printing, acceptable arguments are 'L' and
        'R'.
        display: Display mode.
        root: Starting node.
    '''
    old_display = None
    if root == None:
        root = self.root.name
    if display == None:
        display = self.attr['display']
    else:
        old_display = self.attr['display']
        self.attr['display'] = display
    if priority == 'L':
        first_child = self.get_left_child
        second_child = self.get_right_child
    else:
        first_child = self.get_right_child
        second_child = self.get_left_child
    if order == 'pre':
        print(root)
    if first_child(root) is not None:
        if display:
            self.display(highlight = [root])
        self.print_nodes(order, priority, display, first_child(root))
    if order == 'in':
        print(root)
    if second_child(root) is not None:
        if display:
            self.display(highlight = [root])
        self.print_nodes(order, priority, display, second_child(root))
    if order == 'post':
        print(root)
    if display:
        self.display(highlight = [root])
    if old_display:
        self.attr['display'] = old_display

def printexp(self, display=None, root=None)

Expand source code

def printexp(self, display = None, root = None):
    if root == None:
        root = self.root
    if display == None:
        display = self.attr['display']
    if self.get_left_child(root):
        if display:
            self.display(highlight = [root])
        print('(', end=' ')
        sys.stdout.flush()
        self.printexp(display, self.get_left_child(root))
    if isinstance(root, Node):
        if 'label' in root.attr:
            root_label = root.attr['label']
        else:
            root_label = root.name
    else:
        root_label = self.get_node_attr(root, 'label')
        if root_label == None:
            root_label = root
    print(root_label, end=' ')
    sys.stdout.flush()
    if display:
            self.display(highlight = [root])
    if self.get_right_child(root):
        self.printexp(display, self.get_right_child(root))
        print(')', end=' ')
        sys.stdout.flush()
        if display:
            self.display(highlight = [root])

def traverse(self, root=None, display=None, q=[], priority='L')

API: traverse(self, root=None, display=None, q=Stack(), priority='L', order='in')

Description

Traverses tree starting from node named root if root argument is provided. Starts search from root node of the tree otherwise. Search strategy is determined by q data structure. It is DFS if q is Stack() and BFS if Queue().

Input

root: Starting node. display: Display mode. q: Queue data structure, either Queue() or Stack(). priority: Priority used when exploring children of the node. Acceptable arguments are 'L' and 'R'. order: Ineffective, will be removed.

Expand source code

def traverse(self, root = None, display = None, q = Stack(),
             priority = 'L'):
    '''
    API: traverse(self, root=None, display=None, q=Stack(), priority='L',
                  order='in')
    Description:
        Traverses tree starting from node named root if root argument is
        provided. Starts search from root node of the tree otherwise. Search
        strategy is determined by q data structure. It is DFS if q is
        Stack() and BFS if Queue().
    Input:
        root: Starting node.
        display: Display mode.
        q: Queue data structure, either Queue() or Stack().
        priority: Priority used when exploring children of the node.
        Acceptable arguments are 'L' and 'R'.
        order: Ineffective, will be removed.
    '''
    old_display = None
    if root == None:
        root = self.root
    if display == None:
        display = self.attr['display']
    else:
        old_display = self.attr['display']
        self.attr['display'] = display
    if isinstance(q, Queue):
        addToQ = q.enqueue
        removeFromQ = q.dequeue
    elif isinstance(q, Stack):
        addToQ = q.push
        removeFromQ = q.pop
    if priority == 'L':
        first_child = self.get_left_child
        second_child = self.get_right_child
    else:
        first_child = self.get_right_child
        second_child = self.get_left_child
    addToQ(root)
    while not q.isEmpty():
        current = removeFromQ()
        if display:
            self.display(highlight = [current])
        n = first_child(current)
        if n is not None:
            addToQ(n)
        n = second_child(current)
        if n is not None:
            addToQ(n)
    if old_display:
        self.attr['display'] = old_display

Inherited members

• Tree:
  • add_child
  • add_edge
  • add_node
  • augment_cycle
  • check_edge
  • create
  • create_cluster
  • create_residual_graph
  • cycle_canceling
  • del_edge
  • display
  • edge_to_string
  • fifo_label_correcting
  • find_cycle_capacity
  • find_feasible_flow
  • floyd_warshall
  • floyd_warshall_get_cycle
  • floyd_warshall_get_path
  • get_children
  • get_degrees
  • get_diameter
  • get_edge_attr
  • get_edge_cost
  • get_edge_list
  • get_edge_num
  • get_in_degrees
  • get_in_neighbors
  • get_layout
  • get_negative_cycle
  • get_neighbors
  • get_node
  • get_node_attr
  • get_node_list
  • get_node_num
  • get_out_degrees
  • get_out_neighbors
  • get_parent
  • get_simplex_solution_graph
  • label_components
  • label_correcting_check_cycle
  • label_correcting_get_cycle
  • label_strong_component
  • max_flow
  • max_flow_preflowpush
  • min_cost_flow
  • minimum_spanning_tree_kruskal
  • minimum_spanning_tree_prim
  • network_simplex
  • page_rank
  • print_flow
  • process_edge_dijkstra
  • process_edge_flow
  • process_edge_prim
  • process_edge_search
  • process_node_search
  • random
  • relabel
  • search
  • set_display_mode
  • set_edge_attr
  • set_layout
  • set_node_attr
  • show_flow
  • simplex_augment_cycle
  • simplex_compute_potentials
  • simplex_connect
  • simplex_determine_leaving_arc
  • simplex_find_cycle
  • simplex_find_tree
  • simplex_identify_cycle
  • simplex_mark_entering_arc
  • simplex_mark_leaving_arc
  • simplex_mark_st_arcs
  • simplex_optimal
  • simplex_redraw
  • simplex_remove_arc
  • simplex_search
  • simplex_select_entering_arc
  • strong_connect
  • tarjan
  • to_string
  • write

class Tree (**attrs)

Tree class. It inherits from Graph class. Provides DFS, BFS and traverse methods.

API: init(self, **attrs)

Description

Constructor. Sets attrbutes of class using argument.

Input

attrs: Attributes in keyword arguments format.

Expand source code

class Tree(Graph):
    '''
    Tree class. It inherits from Graph class. Provides DFS, BFS and traverse
    methods.
    '''
    def __init__(self, **attrs):
        '''
        API: __init__(self, **attrs)
        Description:
            Constructor. Sets attrbutes of class using argument.
        Input:
            attrs: Attributes in keyword arguments format.
        '''
        attrs['type'] = DIRECTED_GRAPH
        if 'layout' not in attrs:
            attrs['layout'] = 'dot'
        Graph.__init__(self, **attrs)
        self.root = None

    def get_children(self, n):
        '''
        API: get_children(self, n)
        Description:
            Returns list of children of node n.
        Pre:
            Node with name n should exist.
        Input:
            n: Node name.
        Return:
            Returns list of names of children nodes of n.
        '''
        return self.get_neighbors(n)

    def get_parent(self, n):
        '''
        API: get_parent(self, n)
        Description:
            Returns parent node name if n's parent exists, returns
            None otherwise.
        Pre:
            Node with name n should exist.
        Input:
            n: Node name.
        Return:
            Returns parent name of n if its parent exists, returns None
            otherwise.
        '''
        n = self.get_node(n)
        return n.get_attr('parent')

    def add_root(self, root, **attrs):
        '''
        API: add_root(self, root, **attrs)
        Description:
            Adds root node to the tree with name root and returns root Node
            instance.
        Input:
            root: Root node name.
            attrs: Root node attributes.
        Post:
            Changes self.root.
        Return:
            Returns root Node instance.
        '''
        attrs['level'] = 0
        self.root = self.add_node(root, **attrs)
        return self.root

    def add_child(self, n, parent, **attrs):
        '''
        API: add_child(self, n, parent, **attrs)
        Description:
            Adds child n to node parent and return Node n.
        Pre:
            Node with name parent should exist.
        Input:
            n: Child node name.
            parent: Parent node name.
            attrs: Attributes of node being added.
        Post:
            Updates Graph related graph data attributes.
        Return:
            Returns n Node instance.
        '''
        attrs['level'] = self.get_node(parent).get_attr('level') + 1
        attrs['parent'] = parent
        self.add_node(n, **attrs)
        self.add_edge(parent, n)
        return self.get_node(n)

    def dfs(self, root = None, display = None):
        '''
        API: dfs(self, root = None, display = None)
        Description:
            Searches tree starting from node named root using depth-first
            strategy if root argument is provided. Starts search from root node
            of the tree otherwise.
        Pre:
            Node indicated by root argument should exist.
        Input:
            root: Starting node name.
            display: Display argument.
        '''
        if root == None:
            root = self.root
        if display == None:
            display = self.attr['display']
        self.traverse(root, display, Stack())

    def bfs(self, root = None, display = None):
        '''
        API: bfs(self, root = None, display = None)
        Description:
            Searches tree starting from node named root using breadth-first
            strategy if root argument is provided. Starts search from root node
            of the tree otherwise.
        Pre:
            Node indicated by root argument should exist.
        Input:
            root: Starting node name.
            display: Display argument.
        '''
        if root == None:
            root = self.root
        if display == None:
            display = self.attr['display']
        self.traverse(root, display, Queue())

    def traverse(self, root = None, display = None, q = Stack()):
        '''
        API: traverse(self, root = None, display = None, q = Stack())
        Description:
            Traverses tree starting from node named root. Used strategy (BFS,
            DFS) is controlled by argument q. It is a DFS if q is Queue(), BFS
            if q is Stack(). Starts search from root argument if it is given.
            Starts from root node of the tree otherwise.
        Pre:
            Node indicated by root argument should exist.
        Input:
            root: Starting node name.
            display: Display argument.
            q: Queue data structure instance. It is either a Stack() or
            Queue().
        '''
        if root == None:
            root = self.root
        if display == None:
            display = self.attr['display']
        if isinstance(q, Queue):
            addToQ = q.enqueue
            removeFromQ = q.dequeue
        elif isinstance(q, Stack):
            addToQ = q.push
            removeFromQ = q.pop
        addToQ(root)
        while not q.isEmpty():
            current = removeFromQ()
            #print current
            if display:
                self.display(highlight = [current])
            for n in self.get_children(current):
                addToQ(n)

Ancestors

• Graph

Subclasses

• BinaryTree

Methods

def add_child(self, n, parent, **attrs)

API: add_child(self, n, parent, **attrs)

Description

Adds child n to node parent and return Node n.

Pre

Node with name parent should exist.

Input

n: Child node name. parent: Parent node name. attrs: Attributes of node being added.

Post

Updates Graph related graph data attributes.

Return

Returns n Node instance.

Expand source code

def add_child(self, n, parent, **attrs):
    '''
    API: add_child(self, n, parent, **attrs)
    Description:
        Adds child n to node parent and return Node n.
    Pre:
        Node with name parent should exist.
    Input:
        n: Child node name.
        parent: Parent node name.
        attrs: Attributes of node being added.
    Post:
        Updates Graph related graph data attributes.
    Return:
        Returns n Node instance.
    '''
    attrs['level'] = self.get_node(parent).get_attr('level') + 1
    attrs['parent'] = parent
    self.add_node(n, **attrs)
    self.add_edge(parent, n)
    return self.get_node(n)

def add_root(self, root, **attrs)

API: add_root(self, root, **attrs)

Description

Adds root node to the tree with name root and returns root Node instance.

Input

root: Root node name. attrs: Root node attributes.

Post

Changes self.root.

Return

Returns root Node instance.

Expand source code

def add_root(self, root, **attrs):
    '''
    API: add_root(self, root, **attrs)
    Description:
        Adds root node to the tree with name root and returns root Node
        instance.
    Input:
        root: Root node name.
        attrs: Root node attributes.
    Post:
        Changes self.root.
    Return:
        Returns root Node instance.
    '''
    attrs['level'] = 0
    self.root = self.add_node(root, **attrs)
    return self.root

def bfs(self, root=None, display=None)

API: bfs(self, root = None, display = None)

Description

Searches tree starting from node named root using breadth-first strategy if root argument is provided. Starts search from root node of the tree otherwise.

Pre

Node indicated by root argument should exist.

Input

root: Starting node name. display: Display argument.

Expand source code

def bfs(self, root = None, display = None):
    '''
    API: bfs(self, root = None, display = None)
    Description:
        Searches tree starting from node named root using breadth-first
        strategy if root argument is provided. Starts search from root node
        of the tree otherwise.
    Pre:
        Node indicated by root argument should exist.
    Input:
        root: Starting node name.
        display: Display argument.
    '''
    if root == None:
        root = self.root
    if display == None:
        display = self.attr['display']
    self.traverse(root, display, Queue())

def dfs(self, root=None, display=None)

API: dfs(self, root = None, display = None)

Description

Searches tree starting from node named root using depth-first strategy if root argument is provided. Starts search from root node of the tree otherwise.

Pre

Node indicated by root argument should exist.

Input

root: Starting node name. display: Display argument.

Expand source code

def dfs(self, root = None, display = None):
    '''
    API: dfs(self, root = None, display = None)
    Description:
        Searches tree starting from node named root using depth-first
        strategy if root argument is provided. Starts search from root node
        of the tree otherwise.
    Pre:
        Node indicated by root argument should exist.
    Input:
        root: Starting node name.
        display: Display argument.
    '''
    if root == None:
        root = self.root
    if display == None:
        display = self.attr['display']
    self.traverse(root, display, Stack())

def get_children(self, n)

API: get_children(self, n)

Description

Returns list of children of node n.

Pre

Node with name n should exist.

Input

n: Node name.

Return

Returns list of names of children nodes of n.

Expand source code

def get_children(self, n):
    '''
    API: get_children(self, n)
    Description:
        Returns list of children of node n.
    Pre:
        Node with name n should exist.
    Input:
        n: Node name.
    Return:
        Returns list of names of children nodes of n.
    '''
    return self.get_neighbors(n)

def get_parent(self, n)

API: get_parent(self, n)

Description

Returns parent node name if n's parent exists, returns None otherwise.

Pre

Node with name n should exist.

Input

n: Node name.

Return

Returns parent name of n if its parent exists, returns None otherwise.

Expand source code

def get_parent(self, n):
    '''
    API: get_parent(self, n)
    Description:
        Returns parent node name if n's parent exists, returns
        None otherwise.
    Pre:
        Node with name n should exist.
    Input:
        n: Node name.
    Return:
        Returns parent name of n if its parent exists, returns None
        otherwise.
    '''
    n = self.get_node(n)
    return n.get_attr('parent')

def traverse(self, root=None, display=None, q=[])

API: traverse(self, root = None, display = None, q = Stack())

Description

Traverses tree starting from node named root. Used strategy (BFS, DFS) is controlled by argument q. It is a DFS if q is Queue(), BFS if q is Stack(). Starts search from root argument if it is given. Starts from root node of the tree otherwise.

Pre

Node indicated by root argument should exist.

Input

root: Starting node name. display: Display argument. q: Queue data structure instance. It is either a Stack() or Queue().

Expand source code

def traverse(self, root = None, display = None, q = Stack()):
    '''
    API: traverse(self, root = None, display = None, q = Stack())
    Description:
        Traverses tree starting from node named root. Used strategy (BFS,
        DFS) is controlled by argument q. It is a DFS if q is Queue(), BFS
        if q is Stack(). Starts search from root argument if it is given.
        Starts from root node of the tree otherwise.
    Pre:
        Node indicated by root argument should exist.
    Input:
        root: Starting node name.
        display: Display argument.
        q: Queue data structure instance. It is either a Stack() or
        Queue().
    '''
    if root == None:
        root = self.root
    if display == None:
        display = self.attr['display']
    if isinstance(q, Queue):
        addToQ = q.enqueue
        removeFromQ = q.dequeue
    elif isinstance(q, Stack):
        addToQ = q.push
        removeFromQ = q.pop
    addToQ(root)
    while not q.isEmpty():
        current = removeFromQ()
        #print current
        if display:
            self.display(highlight = [current])
        for n in self.get_children(current):
            addToQ(n)

Inherited members

• Graph:
  • add_edge
  • add_node
  • augment_cycle
  • check_edge
  • create
  • create_cluster
  • create_residual_graph
  • cycle_canceling
  • del_edge
  • del_node
  • display
  • edge_to_string
  • fifo_label_correcting
  • find_cycle_capacity
  • find_feasible_flow
  • floyd_warshall
  • floyd_warshall_get_cycle
  • floyd_warshall_get_path
  • get_degrees
  • get_diameter
  • get_edge_attr
  • get_edge_cost
  • get_edge_list
  • get_edge_num
  • get_in_degrees
  • get_in_neighbors
  • get_layout
  • get_negative_cycle
  • get_neighbors
  • get_node
  • get_node_attr
  • get_node_list
  • get_node_num
  • get_out_degrees
  • get_out_neighbors
  • get_simplex_solution_graph
  • label_components
  • label_correcting_check_cycle
  • label_correcting_get_cycle
  • label_strong_component
  • max_flow
  • max_flow_preflowpush
  • min_cost_flow
  • minimum_spanning_tree_kruskal
  • minimum_spanning_tree_prim
  • network_simplex
  • page_rank
  • print_flow
  • process_edge_dijkstra
  • process_edge_flow
  • process_edge_prim
  • process_edge_search
  • process_node_search
  • random
  • relabel
  • search
  • set_display_mode
  • set_edge_attr
  • set_layout
  • set_node_attr
  • show_flow
  • simplex_augment_cycle
  • simplex_compute_potentials
  • simplex_connect
  • simplex_determine_leaving_arc
  • simplex_find_cycle
  • simplex_find_tree
  • simplex_identify_cycle
  • simplex_mark_entering_arc
  • simplex_mark_leaving_arc
  • simplex_mark_st_arcs
  • simplex_optimal
  • simplex_redraw
  • simplex_remove_arc
  • simplex_search
  • simplex_select_entering_arc
  • strong_connect
  • tarjan
  • to_string
  • write