Source code for p4.node
import p4.func
from p4.var import var
import sys
import p4.pf as pf
class NodeBranchPart(object):
def __init__(self):
self.rMatrixNum = -1
self.gdasrvNum = -1
#self.bigP = None
class NodeBranch(object):
def __init__(self):
self.len = 0.1
# self.textDrawSymbol = '-' # See var.modelSymbols for some
# alternative symbols
self.rawSplitKey = None # Odd or even
self.splitKey = None # Only even
#self.name = None
# self.uName = None # under-name
# self.color = None # US spelling.
# self.support = None # A float, so that it can preserve all its significant
# digits, yet can be formatted flexibly for output.
# self.biRootCount = None # For cons trees, where the input trees are
# bi-Rooted, ie have bifurcating roots. This
# is the number of compatible input trees that
# were rooted on this branch.
self.parts = [] # NodeBranchPart() objects
self.lenChanged = False
class NodePart(object):
def __init__(self):
#self.pats = None
#self.nPats = 0
self.compNum = -1
#self.cl = None
#self.cl2 = None
[docs]
class Node(object):
"""A Node is a vertex in a Tree. All but the root have a branch.
A Node has pointers to its parent, leftChild, and sibling, any of which may be None.
"""
# def __del__(self, freeNode=pf.p4_freeNode, dp_freeNode=pf.dp_freeNode,
# mysys=sys):
def __del__(self, freeNode=pf.p4_freeNode, mysys=sys):
# def __del__(self, freeNode=pf.p4_freeNode, dp_freeNode=pf.dp_freeNode):
# def __del__(self, freeNode=pf.p4_freeNode):
# if self.nodeNum == 0:
#mysys.stdout.write('Node.__del__() deleting node %i\n' % self.nodeNum)
# mysys.stdout.flush()
# Generally, cNodes are deleted before the cTree is freed. freeNode
# requires the cTree!
if self.cNode:
mysys.stdout.write('Node.__del__() node %i (%s) has a cNode (%s). How?!?\n' % (
self.nodeNum, self, self.cNode))
if self.doDataPart:
dp_freeNode(self.cNode)
else:
freeNode(self.cNode)
self.cNode = None
def __init__(self):
self.name = None
self.nodeNum = -1
self.parent = None
self.leftChild = None
self.sibling = None
self.isLeaf = 0
self.cNode = None # Pointer to a c-struct
# Zero-based seq numbering of course, so -1 means no sequence.
self.seqNum = -1
self.br = NodeBranch()
# self.rootCount = None # For cons trees, where the input trees do not
# have bifurcating roots. This is the number of
# compatible input trees that were rooted on this node.
self.parts = [] # NodePart objects
self.doDataPart = 0
self.flag = 0
[docs]
def wipe(self):
"""Set the pointers parent, leftChild, and sibling to None"""
self.parent = None
self.leftChild = None
self.sibling = None
[docs]
def rightmostChild(self):
"""Find and return the rightmostChild of self.
If self has no children, return None.
"""
n = self.leftChild
if not n:
return None
while n.sibling:
n = n.sibling
return n
[docs]
def leftSibling(self):
"""Find and return the sibling on the left.
A node has a pointer to its sibling, but that is the sibling
on the right. It is a bit awkward to find the sibling on the
left, as you need to go via the parent and the leftChild of
the parent.
If there is no parent, return None. If there is no
leftSibling, return None.
"""
if not self.parent:
# print 'leftSibling(%i). No parent. returning None.' %
# self.nodeNum
return None
lsib = self.parent.leftChild
if lsib == self:
# print 'leftSibling(%i). self is self.parent.leftChild.
# returning None.' % self.nodeNum
return None
while lsib:
if lsib.sibling == self:
# print 'leftSibling(%i): returning node %i' % (self.nodeNum,
# lsib.nodeNum)
return lsib
lsib = lsib.sibling
# These next 3 were suggestions from Rick Ree. Thanks, Rick!
# Then I added a couple more. Note that all of these use
# recursion, and so could bump into the recursion limit, and might
# fail on large trees. However, I tried iterPreOrder() on a
# random tree of 10,000 taxa, and it was fine.
# You can temporarily set a different recursion limit with the sys module.
# oldlimit = sys.getrecursionlimit()
# sys.setrecursionlimit(newLimit)
# See also Tree.iterNodesNoRoot()
[docs]
def iterChildren(self):
n = self.leftChild
while n:
yield n
n = n.sibling
[docs]
def iterPostOrder(self):
for c in self.iterChildren():
for n in c.iterPostOrder():
yield n
yield self
[docs]
def iterPreOrder(self):
yield self
for c in self.iterChildren():
for n in c.iterPreOrder():
yield n
[docs]
def iterLeaves(self):
for n in self.iterPreOrder():
if n.isLeaf:
yield n
[docs]
def iterInternals(self):
for n in self.iterPreOrder():
if not n.isLeaf:
yield n
[docs]
def iterDown(self, showDown=False):
"""Iterates over all the nodes below self (including self)
Starts by returning self. And then iterates over all nodes below self.
It does so by a combination of Node.iterPreOrder() and
Node.iterDown() (ie recursively). Now sometimes we want to
know if the nodes that are returned come from iterDown()
(strictly) or not (ie from iterPreOrder()). If that bit of
info is needed, then you can turn on the arg ``showDown``.
(The following is probably bad Python practice!) When that is done, whenever
iterDown() is called the first node that is returned will have
the attribute ``down`` set to True. But after it is returned,
that ``down`` attribute is zapped (to try to keep the bloat
down ...). So you need to test ``if hasattr(yourNode,
'down'):`` before you actually use it.
"""
if showDown:
self.down = True
yield self
if showDown:
del(self.down)
if self.parent:
for c in self.parent.iterChildren():
if c == self:
for n in c.parent.iterDown(showDown):
yield n
else:
for n in c.iterPreOrder():
yield n
# ###############################
[docs]
def getNChildren(self):
"""Returns the number of children that the node has."""
if not self.leftChild:
return 0
c = self.leftChild
counter = 0
while c:
c = c.sibling
counter += 1
return counter
[docs]
def isAncestorOf(self, otherNode):
"""Asks whether self is an an ancestor of otherNode."""
n = otherNode
while 1:
n = n.parent
if not n:
return False
elif n == self:
return True
[docs]
def _ladderize(self, biggerGroupsOnBottom):
"""This is only used by Tree.ladderize()."""
# print '====Node %i' % self.nodeNum
if not self.leftChild:
pass
else:
nLeaves = []
children = []
ch = self.leftChild
while ch:
nL = len([n2 for n2 in ch.iterLeaves()])
nLeaves.append(nL)
ch.nLeaves = nL
children.append(ch)
ch = ch.sibling
# print ' nLeaves = %s' % nLeaves
allOnes = True
for ch in children:
if ch.nLeaves > 1:
allOnes = False
break
if not allOnes:
children = p4.func.sortListOfObjectsOnAttribute(
children, 'nLeaves')
if not biggerGroupsOnBottom:
children.reverse()
# print '\n Children\n ------------'
# for ch in children:
# print ' node=%i, nLeaves=%i' % (ch.nodeNum, ch.nLeaves)
self.leftChild = children[0]
theLeftChild = self.leftChild
theLeftChild.sibling = None
for ch in children[1:]:
theLeftChild.sibling = ch
theLeftChild = ch
theLeftChild.sibling = None
for ch in children:
del(ch.nLeaves)
for ch in self.iterChildren():
ch._ladderize(biggerGroupsOnBottom)