Package Bio :: Package Nexus :: Module Nodes
[hide private]
[frames] | no frames]

Source Code for Module Bio.Nexus.Nodes

  1  # Copyright 2005-2008 by Frank Kauff & Cymon J. Cox. All rights reserved. 
  2  # This code is part of the Biopython distribution and governed by its 
  3  # license. Please see the LICENSE file that should have been included 
  4  # as part of this package. 
  5  # 
  6  # Nodes.py 
  7  #  
  8  # Provides functionality of a linked list. 
  9  # Each node has one (or none) predecessor, and an arbitrary number of successors. 
 10  # Nodes can store arbitrary data in a NodeData class. 
 11  # 
 12  # Subclassed by Nexus.Trees to store phylogenetic trees. 
 13  # 
 14  # Bug reports to Frank Kauff (fkauff@biologie.uni-kl.de) 
 15  # 
 16   
17 -class ChainException(Exception):
18 pass
19
20 -class NodeException(Exception):
21 pass
22
23 -class Chain(object):
24 """Stores a list of nodes that are linked together.""" 25
26 - def __init__(self):
27 """Initiates a node chain: (self).""" 28 self.chain={} 29 self.id=-1
30
31 - def _get_id(self):
32 """Gets a new id for a node in the chain.""" 33 self.id+=1 34 return self.id
35
36 - def all_ids(self):
37 """Return a list of all node ids.""" 38 return self.chain.keys()
39
40 - def add(self,node,prev=None):
41 """Attaches node to another: (self, node, prev).""" 42 if prev is not None and prev not in self.chain: 43 raise ChainException('Unknown predecessor: '+str(prev)) 44 else: 45 id=self._get_id() 46 node.set_id(id) 47 node.set_prev(prev) 48 if prev is not None: 49 self.chain[prev].add_succ(id) 50 self.chain[id]=node 51 return id
52
53 - def collapse(self,id):
54 """Deletes node from chain and relinks successors to predecessor: collapse(self, id).""" 55 if id not in self.chain: 56 raise ChainException('Unknown ID: '+str(id)) 57 prev_id=self.chain[id].get_prev() 58 self.chain[prev_id].remove_succ(id) 59 succ_ids=self.chain[id].get_succ() 60 for i in succ_ids: 61 self.chain[i].set_prev(prev_id) 62 self.chain[prev_id].add_succ(succ_ids) 63 node=self.chain[id] 64 self.kill(id) 65 return node
66
67 - def kill(self,id):
68 """Kills a node from chain without caring to what it is connected: kill(self,id).""" 69 if id not in self.chain: 70 raise ChainException('Unknown ID: '+str(id)) 71 else: 72 del self.chain[id]
73 84 95
96 - def is_parent_of(self,parent,grandchild):
97 """Check if grandchild is a subnode of parent: is_parent_of(self,parent,grandchild).""" 98 if grandchild==parent or grandchild in self.chain[parent].get_succ(): 99 return True 100 else: 101 for sn in self.chain[parent].get_succ(): 102 if self.is_parent_of(sn,grandchild): 103 return True 104 else: 105 return False
106
107 - def trace(self,start,finish):
108 """Returns a list of all node_ids between two nodes (excluding start, including end): trace(start,end).""" 109 if start not in self.chain or finish not in self.chain: 110 raise NodeException('Unknown node.') 111 if not self.is_parent_of(start,finish) or start==finish: 112 return [] 113 for sn in self.chain[start].get_succ(): 114 if self.is_parent_of(sn,finish): 115 return [sn]+self.trace(sn,finish)
116
117 -class Node(object):
118 """A single node.""" 119
120 - def __init__(self,data=None):
121 """Represents a node with one predecessor and multiple successors: (self, data=None).""" 122 self.id=None 123 self.data=data 124 self.prev=None 125 self.succ=[]
126
127 - def set_id(self,id):
128 """Sets the id of a node, if not set yet: (self,id).""" 129 if self.id is not None: 130 raise NodeException('Node id cannot be changed.') 131 self.id=id
132
133 - def get_id(self):
134 """Returns the node's id: (self).""" 135 return self.id
136
137 - def get_succ(self):
138 """Returns a list of the node's successors: (self).""" 139 return self.succ
140
141 - def get_prev(self):
142 """Returns the id of the node's predecessor: (self).""" 143 return self.prev
144
145 - def add_succ(self,id):
146 """Adds a node id to the node's successors: (self,id).""" 147 if isinstance(id,type([])): 148 self.succ.extend(id) 149 else: 150 self.succ.append(id)
151
152 - def remove_succ(self,id):
153 """Removes a node id from the node's successors: (self,id).""" 154 self.succ.remove(id)
155
156 - def set_succ(self,new_succ):
157 """Sets the node's successors: (self,new_succ).""" 158 if not isinstance(new_succ,type([])): 159 raise NodeException('Node successor must be of list type.') 160 self.succ=new_succ
161
162 - def set_prev(self,id):
163 """Sets the node's predecessor: (self,id).""" 164 self.prev=id
165
166 - def get_data(self):
167 """Returns a node's data: (self).""" 168 return self.data
169
170 - def set_data(self,data):
171 """Sets a node's data: (self,data).""" 172 self.data=data
173