Source code for neurom.core.tree

# Copyright (c) 2015, Ecole Polytechnique Federale de Lausanne, Blue Brain Project
# All rights reserved.
#
# This file is part of NeuroM <https://github.com/BlueBrain/NeuroM>
#
# Redistribution and use in source and binary forms, with or without
# modification, are permitted provided that the following conditions are met:
#
#     1. Redistributions of source code must retain the above copyright
#        notice, this list of conditions and the following disclaimer.
#     2. Redistributions in binary form must reproduce the above copyright
#        notice, this list of conditions and the following disclaimer in the
#        documentation and/or other materials provided with the distribution.
#     3. Neither the name of the copyright holder nor the names of
#        its contributors may be used to endorse or promote products
#        derived from this software without specific prior written permission.
#
# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY
# DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
# (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
# LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
# ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
# (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
# SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

"""Generic tree class and iteration functions."""
from collections import deque


[docs]class Tree(object):
    """Simple recursive tree class."""
    def __init__(self):
        """Initialize a Tree object."""
        self.parent = None
        self.children = list()

[docs]    def add_child(self, tree):
        """Add a child to the list of this tree's children.

        This tree becomes the added tree's parent
        """
        tree.parent = self
        self.children.append(tree)
        return tree

[docs]    def is_forking_point(self):
        """Is tree a forking point?."""
        return len(self.children) > 1

[docs]    def is_bifurcation_point(self):
        """Is tree a bifurcation point?."""
        return len(self.children) == 2

[docs]    def is_leaf(self):
        """Is tree a leaf?."""
        return len(self.children) == 0

[docs]    def is_root(self):
        """Is tree the root node?."""
        return self.parent is None

[docs]    def ipreorder(self):
        """Depth-first pre-order iteration of tree nodes."""
        children = deque((self, ))
        while children:
            cur_node = children.pop()
            children.extend(reversed(cur_node.children))
            yield cur_node

[docs]    def ipostorder(self):
        """Depth-first post-order iteration of tree nodes."""
        children = [self, ]
        seen = set()
        while children:
            cur_node = children[-1]
            if cur_node not in seen:
                seen.add(cur_node)
                children.extend(reversed(cur_node.children))
            else:
                children.pop()
                yield cur_node

[docs]    def iupstream(self):
        """Iterate from a tree node to the root nodes."""
        t = self
        while t is not None:
            yield t
            t = t.parent

[docs]    def ileaf(self):
        """Iterator to all leaves of a tree."""
        return filter(Tree.is_leaf, self.ipreorder())

[docs]    def iforking_point(self, iter_mode=ipreorder):
        """Iterator to forking points. Returns a tree object.

        Arguments:
            tree: the tree over which to iterate
            iter_mode: iteration mode. Default: ipreorder.
        """
        return filter(Tree.is_forking_point, iter_mode(self))

[docs]    def ibifurcation_point(self, iter_mode=ipreorder):
        """Iterator to bifurcation points. Returns a tree object.

        Arguments:
            tree: the tree over which to iterate
            iter_mode: iteration mode. Default: ipreorder.
        """
        return filter(Tree.is_bifurcation_point, iter_mode(self))

    def __nonzero__(self):
        """Check non-zero."""
        return bool(self.children)

    __bool__ = __nonzero__