#!/usr/bin/python # Copyright (c) 2005 by Mark T. Holder, Florida State University. (see end of file) ''' Tree class ''' from nexus.primitives import * from nexus.parser import * import random from splits import * import cStringIO from sets import Set from node import * from PIPRes.wrap.idl import getNO_SCORE from PIPRes.util.io import cipresGetLogger _LOG = cipresGetLogger('pipres.tree') #johanNylander = True def createMappingFuncs(origInds): '''Creates a pair of mapping functions. The first maps an each element in an iterable collection of non-negative (origInds) to its index if the collection were sorted. The second reverses the mapping. Useful for condensing a sparse array to a minimal length list, but being able to recover the original labels. @@@NEED to revisit this - was not working in the cipres_types.mapLeaves context (but I'm not sure I was invoking it correctly).@@@ ''' toOrig = list(origInds) toOrig.sort() #@@@ THIS seems unecessary, because the function only seems to be working when the origInds is sorted (fortuntately we are only calling it in this context right now). toCompressed = {} for n, o in enumerate(toOrig): assert(o >= 0) toCompressed[o] = n return toCompressed.__getitem__, toOrig.__getitem__ def numberedLeafTree(newick = None, **kwargs): kwargs['taxaNamingStyle'] = TaxaNamingEnum.numbersOnly treeFactory = kwargs.get('treeFactory', Tree) return treeFactory(newick, **kwargs) class Tree(object): def standardizeOrientation(self): '''If the tree is unrooted, the attachment point will be moved so that the lowest tip number is the lChild of self.root. Branch rotations will be performed so that the clade with the lowest numbered descendant will be leftmost for each nodes list of children.''' if not self.rooted: ind = self.getMinTaxonIndex() if ind < 0: return self.attachAtLeafByIndex(ind) for n in iterPreorder(self.root): n.standardizeChildOrder() def iterPreorder(self): if not self.root: return iter([]) return iterPreorder(self.root) def iterEdges(self): if (not self.root) or (not self.root.lChild): return iter([]) return iterEdges(self.root) def randomRefine(self, maxOutDegree = 2, rng = None): """Randomly refines the tree, setting new edges to length 0.0 returns a list of new Nodes created.""" newNds = [] if self.root is None: return newNds if rng is None: rng = random.Random() nds = self.iterPreorder() if not self.rooted: r = nds.next() newNds.append(r.randomRefine(maxOutDegree + 1, rng=rng)) for n in nds: newNds.append(n.randomRefine(maxOutDegree, rng=rng)) return newNds def validateLabelAsNumber(self, labelToken, alreadyRead, isLeaf): labStr = str(labelToken) if labStr == ':': if isLeaf: raise BadTreeDefError(labelToken, 'label required before : for leaves' % labelToken) return -1L if not isLeaf: raise BadTreeDefError(labelToken, 'internal node labels are disallowed') if not labStr.isdigit(): raise BadTreeDefError(labelToken, 'non-numeric label (%s) found' %labStr) labelAsNumber = long(labStr) if labelAsNumber < 1: raise BadTreeDefError(labelToken, 'Expecting integer labels starting at 1 (found %d)' % labelAsNumber) if labStr in alreadyRead: raise BadTreeDefError(labelToken, 'the label %s was repeated' % labelToken) alreadyRead.append(labStr) if self.taxaManager is not None: self.taxaManager.addTaxa([labStr]) return labelAsNumber - 1 def validateNodeName(self, labelToken, alreadyRead, isLeaf): '''Verifies that labels are not repeated by checking the alreadyRead list. If isLeaf is True a taxon index will be returned.''' labStr = str(labelToken) if labStr == ':': if isLeaf: raise BadTreeDefError(labelToken, 'label required before : for leaves' % labelToken) return -1L lu = labStr.upper() for l in alreadyRead: if l.upper() == lu: raise BadTreeDefError(labelToken, 'the label %s was repeated' % labelToken) if isLeaf: alreadyRead.append(labStr) if self.taxaManager is not None: try: i = self.taxaManager.translateTaxLabel(labelToken) return i except NexusUnknownTaxonError, x: if self.taxaManager.taxaAreFinal(): raise self.taxaManager.addTaxa([labStr]) return self.taxaManager.translateTaxLabel(labelToken) if self.__dict__.has_key('taxLabels'): for i, l in enumerate(self.taxLabels): if l == lu: return i if isLeaf: return len(alreadyRead) - 1L return 0L def temp_deepcopy__(self, memo = {}): from copy import copy, deepcopy other = self.__class__(rooted = copy(self.rooted), name = copy(self.name), taxaManager = deepcopy(self.taxaManager)) if self.root: other.root = deepcopy(self.root) return other def __str__(self): return self.getNewick() def _reprKeywordArgs(self): return '' def __repr__(self): s = '%s(%s)' % (self.__class__.__name__, self._reprKeywordArgs()) _LOG.debug(s) return s def __init__(self, newick = None, **kwargs ): '''In kwargs, uses taxaManager if present, if not used taxaNamingStyle and taxLabels. Other defaults in kwargs: rooted = False, name = '', breakAtSemicolon = True, ignoreCmdComments = False, collapseDegreeTwo = True, _nodeClass = NodeWithSplit ''' self.hasEdgeLengths = False # will be set as tree is read, but needs to exist self.name = kwargs.get('name', '') self.rooted = kwargs.get('rooted', False) self.taxaManager = getTaxaManagerFromDictArgs(kwargs) self.ignoreEdgeLengths = kwargs.get('ignoreEdgeLengths', False) self._nodeClass = kwargs.get('_nodeClass', NodeWithSplit) self.idl_score = kwargs.get('score') if newick is not None: self.read(newick, kwargs.get('breakAtSemicolon', True), kwargs.get('ignoreCmdComments', False), kwargs.get('collapseDegreeTwo', True), taxaNamingStyle = kwargs.get('taxaNamingStyle', TaxaNamingEnum.acceptNumbers) ) else: self.root = None splitList = kwargs.get('splits', []) nTax = self.taxaManager.getNTax() or kwargs.get('nTaxa', 0) if len(splitList) > 0 and nTax < 1: raise ValueError, 'Must specify "nTaxa" argument when constructing tree from "splits"' if nTax: self.buildFromSplits(splitList, nTax) # cast if the class is simply Tree (we don't use isinstance in case we implement a richer hierarchy - we are only adding information to the class here, # we don't want to overrule derived classes if they are present). if self.__class__ == Tree: if self._nodeClass == NodeWithSplit: self.__class__ = TreeWithSplits elif self._nodeClass == SimpleNode: self.__class__ = SimpleTree def __eq__(self, other): '''returns True if the topologies match (branch lengths are ignored) returns (symdiff == 0).''' if not other: return False if not isinstance(other, Tree): raise NotImplementedError, 'Tree __eq__ expects 2 Trees' if not self.root: return not other.root return self.symmetric_difference(other) == 0 def __ne__(self, other): return not self == other def attachAtLeafByIndex(self, ind): '''Makes the leaf with index 'ind' the leftChild of the root, by rerooting the tree.''' nd = self.findLeafByIndex(ind) if not nd: raise ValueError, 'Leaf not found' assert(nd.par) self.attachAtNode(nd.par) nd.makeSelfLeftmostChild() return nd def attachAtNode(self, nd): '''Assumes that nd is a part of this tree''' if nd == self.root: return nd._makeSelfRoot(True, True) self.root = nd def getName(self): return self.name def setName(self, name): self.name = name def clearTree(self): self.root = None def read(self, newick, breakAtSemicolon = True, ignoreCmdComments = False, collapseDegreeTwo = True, taxaNamingStyle = TaxaNamingEnum.acceptNumbers): return self.readTokenStream(iterNexusTokenizeStr(newick), breakAtSemicolon, ignoreCmdComments, collapseDegreeTwo,taxaNamingStyle) def readTokenStream(self, toks, breakAtSemicolon = True, ignoreCmdComments = False, collapseDegreeTwo = True, taxaNamingStyle = TaxaNamingEnum.validLabels): ''' reads string until ;''' labelValidator = taxaNamingStyle == TaxaNamingEnum.numbersOnly and Tree.validateLabelAsNumber or Tree.validateNodeName self.clearTree() root = self._nodeClass() t = toks.next() currNd = root readLabels = [] if str(t) != '(': raise BadTreeDefError(t, 'Expecting (') if not ignoreCmdComments: cmdComments = t.getSpecialComments() rootedSpecified = len(filter(lambda x: x.upper() == '&R', cmdComments)) > 0 unrootedSpecified = len(filter(lambda x: x.upper() == '&U', cmdComments)) > 0 if rootedSpecified or unrootedSpecified: if unrootedSpecified and rootedSpecified: raise BadTreeDefError(t, 'both rooted and unrooted tree specifications ([&R] and [&U])') self.rooted = rootedSpecified degTwo = [] readyForChild = True self.hasEdgeLengths = True #if johanNylander: # internalNodeIndex = 0 #added for johan's diva tree helper # this is a postorder indexing of internal nodes) while True: tStr = str(t) if tStr == ')': readyForChild = False if not currNd.lChild: try: if currNd.split == 0: raise BadTreeDefError(t, 'empty subtree found') except AttributeError: try: if currNd._index == -1L: raise AttributeError except AttributeError: raise BadTreeDefError(t, 'empty subtree found') self.hasEdgeLengths &= (currNd.edgeLength is not None) currNd = currNd.par if currNd is None: raise BadTreeDefError(t, 'Unbalanced ).') #if johanNylander: # try: # getattr(currNd, 'internalNodeIndex') # except: # currNd.internalNodeIndex = internalNodeIndex #added for johan's diva tree helper # internalNodeIndex += 1 #added for johan's diva tree helper if currNd.hasOneChild(): msg = 'Internal with only one child found' if collapseDegreeTwo: NexusParsing.statusMessage(msg) degTwo.append(currNd) else: raise BadTreeDefError(t, msg) currNd._refreshOwnSplit() if not breakAtSemicolon and currNd.par is None: break else: if tStr == '(': if not readyForChild: raise BadTreeDefError(t, 'Expecting , before the defintion of more subtrees') currNd = currNd._createChild() elif tStr == ',': self.hasEdgeLengths &= (currNd.edgeLength is not None) currNd = currNd.createSib() readyForChild = True elif breakAtSemicolon and tStr == ';': break else: readyForChild = False try: ind = labelValidator(self, t, readLabels, currNd.lChild is None) t = currNd._readInfo(t, ind, toks) except StopIteration: raise BadTreeDefError(t, 'Unexpected EOF') continue try: t = toks.next() except StopIteration: break if currNd.par is not None: self.root = None raise BadTreeDefError(t, 'Unbalanced (.') for d in degTwo: assert(d.lChild) d.lChild.addToEdgeLength(d.edgeLength) d.collapseEdge() self.root = root if self.rooted == False: # self.rooted might be None self.deroot() def buildFromSplits(self, splitList, nTaxa): assert(nTaxa >= 1) mask = makeSimpleMask(nTaxa) self.clearTree() self.root = self._nodeClass() root = self.root root._createChildren(nTaxa) for i, c in enumerate(root.children): c.index = i root._refreshOwnSplit() m = self.taxonMask for s in splitList: root.addCompatibleSplit(s, m) def deroot(self): self.rooted = False if self.root.numChildren == 2: rootL = self.root.lChild rootR = rootL.rSib if rootL.isInternal(): rootR.addToEdgeLength(rootL.edgeLength) rootL.collapseEdge() elif rootR.isInternal(): rootL.addToEdgeLength(rootR.edgeLength) rootR.collapseEdge() def _toRooted(self, withPolytomy = True, newRootsLChild = None): self.rooted = True if (newRootsLChild is None) and not withPolytomy: newLChild = newRootsLChild or (self.root and self.root.lChild) if not newLChild: assert(self.root is None) return p = newLChild.par if p: self.attachAtNode(p.numChildren == 1 and p or newLChild._createDegreeTwoParent()) else: self.attachAtNode(newLChild) def getTaxManager(self): return self.taxaManager def getNewick(self, edgeLenCode = TreeDisplay.withEdgeLengthsIfPresent, useTaxaNumbers=False, newTaxLabels=None, internalTaxonLabels=False): if not self.root: return '' c = cStringIO.StringIO() if not self.hasEdgeLengths: if edgeLenCode == TreeDisplay.demandEdgeLengths: raise ValueError, 'Edge lengths requested, but tree does not have edge lengths' edgeLenCode = TreeDisplay.noEdgeLengths if newTaxLabels: t = newTaxLabels else: t =(not useTaxaNumbers) and self.getTaxManager() or None self.root.writeNewick(c, t, edgeLenCode, internalTaxonLabels) return c.getvalue() def nexusStr(self): pref = (self.rooted is not None) and (self.rooted and '[&R]' or '[&U]') or '' return '%s%s' % (pref, self.__str__()) def writeDOT(self, out): n = str(self.name) or 'unnamed' gType = self.rooted and 'digraph' or 'graph' edgeSymbol = self.rooted and '->' or '--' out.write('%s %s {\n' % (gType, n)) out.write('\tnode [shape=plaintext height=.2]\n') self.root.writeDOTSubTree(out, self.taxaManager, edgeSymbol) out.write('\n|}\n') def getLeafSet(self): if not hasattr(self, 'leafSet'): self.refreshLeafSet() return self.leafSet def _demandSameTaxonMask(self, other): '''Raises ValueError if self, and other have different taxonMask.''' if self.taxonMask != other.taxonMask: d = self.taxonMask ^ other.taxonMask s = str([i for i in iterSplitIndices(self.taxonMask&d, -1, True)]) o = str([i for i in iterSplitIndices(other.taxonMask&d, -1, True)]) raise ValueError, 'trees with different leaf sets (unmatched bits: self has %s, and other has %s)' % (s, o) def _getSplitsSetsOriented(self, other, forceUnrooted = False): if self.rooted: orientArg = forceUnrooted and -1 or 0 else: orientArg = -1 if (self.rooted and not (other.rooted or forceUnrooted)) or (not self.rooted and other.rooted and not forceUnrooted): raise ValueError, 'trees differ in rooting status (and forceUnrooted = False)' return Set(self.getSplits(False, orientArg, forceUnrooted)), Set(other.getSplits(False, orientArg, forceUnrooted)) def symmetric_difference(self, other, forceUnrooted = False): ''' returns unweighted RF distance. horrendous algorithm.''' self._demandSameTaxonMask(other) #@ should compare taxa meanings not just masks selfOriented, otherOriented = self._getSplitsSetsOriented(other, forceUnrooted) sdSplits = selfOriented.symmetric_difference(otherOriented) return len(sdSplits) def isRefinementOf(self, other, forceUnrooted = False): self._demandSameTaxonMask(other) #@ should compare taxa meanings not just masks selfOriented, otherOriented = self._getSplitsSetsOriented(other, forceUnrooted) return otherOriented.issubset(selfOriented) def makeBinary(self): '''Adds nodes (with 0 length edges) to make the tree have outdegree 2 (for rooted trees) or degree 3 for unrooted.''' r = self.root if r is None: return childrenOfRoot = [c for c in r.children if c.isInternal()] for c in childrenOfRoot: for n in iterPostorder(c, Node.isInternal): n._enforceMaxNChildren(2, 2, 0.0) rootMaxN = self.rooted and 2 or 3 r._enforceMaxNChildren(rootMaxN, 2, 0.0) #def combinable(self, other): # ''' returns True if there are no splits in self that conflict with other''' # _demandSameTaxonMask(self, other) #@ should compare taxa meanings not just masks # selfOriented, otherOriented = self._getSplitsSetsOriented(other, forceUnrooted) # code here def show(self, fileName = 'testDot.dot'): if not showTreeInGraphViz(self, fileName): print self def comb(nLeaves, toLeft = True, taxaManager = None, rooted = False, edgeLength = None): if taxaManager is None: t = Tree(None, rooted=rooted, name='', taxaNamingStyle=TaxaNamingEnum.numbersOnly) if nLeaves > 0: t.taxaManager.addTaxa([str(nLeaves)]) else: t = Tree(None, rooted=rooted, name='', taxaManager=taxaManager) if nLeaves > 0: t.root = t._nodeClass() if nLeaves == 1: t.root.setIndex(0) return t.hasEdgeLengths = edgeLength is not None nRootChildren = min(nLeaves, rooted and 2 or 3) for i in range(nRootChildren): nd = t.root._createChild() nd.edgeLength = edgeLength nd.setIndex(toLeft and nLeaves - nRootChildren + i or i) nd = t.root for i in range(nRootChildren, nLeaves): nd = toLeft and nd.lChild or nd.rChild u, v = nd._createChild(), nd._createChild() u.edgeLength, v.edgeLength = edgeLength, edgeLength if toLeft: u.setIndex(0) v.setIndex(nLeaves - i) else: u.setIndex(i-1) v.setIndex(i) while nd: nd._refreshOwnSplit() nd = nd.par return t def _countEdges(self): '''returns number of edges in the tree and a list that can be used as an arg to _findEdgeN to speed up the lookup.''' cacheNum = 1 cache = [] for n, e in enumerate(iterEdges(self.root)): if n + 1 == cacheNum: cache.append(e) cacheNum <<= 1 return n + 1, cache def _findEdgeN(self, toReturn, cache = None): '''Returns the Edge with index n. n should be in the range [0,numEdges)''' cache = None #NOT using the optimized cache YET!!! for n, e in enumerate(iterEdges(self.root)): if n == toReturn: return e raise IndexError, 'Index %d is out of range (%d edges found)' % (toReturn, n + 1) def randEdge(self, rng): assert(self.root and self.root.lChild) n, cache = self._countEdges() assert(n > 0) rInd = rng.randint(0, n - 1) return self._findEdgeN(rInd, cache) def randTopology(nLeaves, taxaManager = None, edgeLength = None, rng = None): '''Returns a random, unrooted tree from the equiprobable distribution of all topologies''' t = Tree(None, rooted = False, name = '', taxaManager = taxaManager) rng = rng or random.Random() if nLeaves < 1: return t t.root = t._nodeClass() if nLeaves == 1: t.root.setIndex(0) return t for i in range(min(3, nLeaves)): nd = t.root._createChild() nd.edgeLength = edgeLength nd.setIndex(i) if nLeaves < 4: return t t.hasEdgeLengths = edgeLength is not None nd = t.root for i in range(3, nLeaves): toAdd = t._nodeClass() toAdd.setIndex(i) toAdd.edgeLength = edgeLength edge = t.randEdge(rng) newInternal = edge._bisect(toAdd) newInternal.edgeLength return t def pruneTo(self, indices, oneBased=False): '''Removes all taxa EXCEPT those whose self.index attributes are in 'indices' argument.''' offset = oneBased and 1 or 0 allTips = [i for i in iterTips(self.root)] for i in allTips: if not (i.index + offset) in indices: # print 'pruned leaf ', i.index + offset i.pruneSelf() # root might have a degree that is too low, because the node functions cannot remove the root # node (because the Tree contains a reference to the tree self.fixRootNode() self.root.refreshSplits() def iterTips(self): return iterTips(self.root) def fixRootNode(self): '''Removes the root if it has degree < 2 for rooted trees or < 3 for unrooted trees. Makes the leftmost non-tip child of the root the new root. Will return a two node tree if there is only 1 tip, and a 3-node tree if there are only 2 tips (a leaf will never be the tip).''' rootDegree = self.root.degree while rootDegree < 3: rootLChild = self.root.lChild if rootDegree == 1: if rootLChild.isLeaf(): return self.root.lChild = None # in case we have external references to the old root we'll make it an island rootLChild.par = None self.root = rootLChild rootDegree = self.root.degree rootLChild = self.root.lChild if rootDegree == 2 and not self.rooted: # we'll keep the left to right ordering of nodes the same as we reroot here if rootLChild.isLeaf(): newRootNode = rootLChild.rSib if newRootNode.isLeaf(): return newRootDaughter = rootLChild newRootDaughter.rSib = newRootNode.lChild newRootNode.lChild = newRootDaughter else: newRootNode = rootLChild newRootDaughter = rootLChild.rSib newRootNode.rChild.rSib = newRootDaughter newRootDaughter.par = newRootNode newRootDaughter.addToEdgeLength(newRootNode.edgeLength) newRootNode.edgeLength = None newRootNode.rSib = None newRootNode.par = None self.root.lChild = None # in case we have external references to the old root we'll make it an island self.root = newRootNode else: return rootDegree = self.root.degree def getNTaxa(self): if not self.root: return 0 return countBits(self.taxonMask) def getMinTaxonIndex(self): if not self.root: return -1 return getFirstBitAsIndex(self.taxonMask) def getMaxTaxonIndex(self): if not self.root: return -1 return getLastBitAsIndex(self.taxonMask) def mapLeaves(self, func): '''Changes the numbers assigned to leaves. Does NOT change self.taxaManager "func" should be callable and take any index [0, nTaxa) and return a non-negative number.''' for tip in self.iterTips(): tip.setIndex(func(tip.getIndex())) self.root.refreshSplits() # changing leaves invalidates the leaf set member if hasattr(self, 'leafSet'): del self.leafSet def getEdgeLengthSum(self): s = 0.0 if self.root is None: return s for e in iterEdges(self.root): s += e.end.edgeLength return s def getM_Newick(self): return '%s;' % self.getNewick(edgeLenCode = TreeDisplay.withEdgeLengthsIfPresent, useTaxaNumbers = True) def setM_Score(self, sco): self.idl_score = sco def getM_Score(self): if self.idl_score is None: self.idl_score = getNO_SCORE() return self.idl_score m_score = property(getM_Score, setM_Score) m_newick = property(getM_Newick) edgeLengthSum = property(getEdgeLengthSum) comb = staticmethod(comb) randTopology = staticmethod(randTopology) newick = property(getNewick) nTaxa = property(getNTaxa) class TreeWithSplits(Tree): def __init__(self, newick = None, **kwargs): kwargs['_nodeClass'] = NodeWithSplit super(TreeWithSplits, self).__init__(newick, **kwargs) '''Tree made up to of NodeWithSplit objects''' def findLeafByIndex(self, i): if i < 0L: raise ValueError, 'index cannot be negative' s = 1L << i return self.root and self.root.getALeafInSplit(s) or None def calcPathLengthMatrix(self): '''Returns a list of lists that represents the triangle + lower diagonal of an nLeaves x nLeaves matrix of tip-to-tip path lengths.''' nLeaves = self.nTaxa taxMask = self.taxonMask matrix = [] fullInds = splitToList(taxMask, taxMask, oneBased = False, ordinationInMask = True) for i in range(1, nLeaves + 1): matrix.append([0.0] * i) for edge in iterEdges(self.root): e = edge.end eLen = e.edgeLength upperInds = splitToList(e.split, taxMask, oneBased = False, ordinationInMask = True) lowerInds = copy.copy(fullInds) for u in upperInds: lowerInds.remove(u) for u in upperInds: for l in lowerInds: matrix[max(l, u)][min(l, u)] += eLen return matrix def getSplits(self, includeTrivials = True, orient = None, forceUnrooted = False): ''' pass orient = -1 to orient on the first bit of the tree's taxonMask''' if not (self.root and self.root.lChild): return [] if orient: tm = self.taxonMask firstBit = getFirstBitOnly(orient > 0 and orient or tm) if not firstBit & tm: ValueError, 'orienting split on non-existent taxon' return [orientSplit(i, tm, firstBit) for i in self.getSplits(includeTrivials, False, forceUnrooted)] if forceUnrooted and self.root.numChildren < 3 : func = not includeTrivials and Node.isInternal or bool a = [nd.split for nd in iterPreorder(self.root.lChild, func)] for c in iterChildren(self.root.lChild.rSib): a.extend([nd.split for nd in iterPreorder(c, func)]) return a if includeTrivials: return [nd.split for nd in iterPreorder(self.root)] return [nd.split for nd in iterPreorder(self.root, Node.isInternal)][1:] # remove the root split which is trivial def getTaxonMask(self): '''returns a long with 1 bits on for every taxon (or 0L if the tree is empty).''' return self.root and self.root.split or 0L def hasClade(self, nodeObj): return self.hasSplit(nodeObj.split) def hasSplit(self, split): tm = self.taxonMask masked = tm & split if not masked or (masked != split): return False if isTrivialSplit(masked, tm): return True if masked == tm: return True assert(self.root.lChild) return self.root.lChild._treeContainsSplitNonTrivial(masked, tm) def getNodeBySplit(self, split): tm = self.taxonMask masked = tm & split if not masked or (masked != split): return None if isTrivialSplit(masked, tm): if masked == getFirstBitOnly(m): return self.getALeafInSplit(masked) return self.getALeafInSplit(invertSplit(masked, mask)) if masked == tm: return self.root return self.root._treeFindSplitNonTrivial(masked, tm) def refreshLeafSet(self): self.leafSet = self.root and [i for i in iterSplitIndices(self.root.split, -1, True)] or [] def __hash__(self): if not self.root: return 0 h = long(0x8AAAAAAAL) for n in iterPreorder(self.root): h = h ^ hash(n.split) return h taxonMask = property(getTaxonMask) class SimpleTree(Tree): '''Tree made up to of SimpleNode objects''' def __init__(self, newick = None, **kwargs): kwargs['_nodeClass'] = SimpleNode super(SimpleTree, self).__init__(newick, **kwargs) def findLeafByIndex(self, ind): for i in self.iterTip(): if i.index == ind: return i return None def calcPathLengthMatrix(self): raise NotImplementedError, 'SimpleTree does not implement this method (yet)' def getSplits(self, includeTrivials = True, orient = None, forceUnrooted = False): raise NotImplementedError, 'SimpleTree does not implement this method (yet)' def getTaxonMask(self): raise NotImplementedError, 'SimpleTree does not implement this method (yet)' def hasClade(self, nodeObj): raise NotImplementedError, 'SimpleTree does not implement this method (yet)' def hasSplit(self, split): raise NotImplementedError, 'SimpleTree does not implement this method (yet)' def refreshLeafSet(self): raise NotImplementedError, 'SimpleTree does not implement this method (yet)' def __hash__(self): raise NotImplementedError, 'SimpleTree does not implement this method (yet)' taxonMask = property(getTaxonMask) def showTreeInGraphViz(tre, fileName): import os defGraphVizPath = '/Applications/Graphviz.app/' if not os.path.exists(defGraphVizPath): return False f = open(fileName, 'w') tre.writeDOT(f) f.close() os.system('open -a ' + defGraphVizPath + ' ' + fileName) return True # This file is part of the PIPRes library # # The PIPRes library is free software; you can redistribute it # and/or modify it under the terms of the GNU Lesser General # Public License as published by the Free Software Foundation; # either version 2.1 of the License, or (at your option) any later # version. # # This library is distributed in the hope that it will be useful, # but WITHOUT ANY WARRANTY; without even the implied warranty of # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the # GNU Lesser General Public License for more details. # # You should have received a copy of the GNU Lesser General Public # License along with this library; if not, write to the Free # Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, # MA 02111-1307, USA