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__