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   
 18 -class ChainException(Exception): 
 19      pass 
 20   
 21   
 22 -class NodeException(Exception): 
 23      pass 
 24   
 25   
 26 -class Chain(object): 
 27      """Stores a list of nodes that are linked together.""" 
 28   
 29 -    def __init__(self): 
 30          """Initiates a node chain.""" 
 31          self.chain={} 
 32          self.id=-1 
 33   
 34 -    def _get_id(self): 
 35          """Gets a new id for a node in the chain.""" 
 36          self.id+=1 
 37          return self.id 
 38   
 39 -    def all_ids(self): 
 40          """Return a list of all node ids.""" 
 41          return self.chain.keys() 
 42   
 43 -    def add(self,node,prev=None): 
 44          """Attaches node to another.""" 
 45          if prev is not None and prev not in self.chain: 
 46              raise ChainException('Unknown predecessor: '+str(prev)) 
 47          else: 
 48              id=self._get_id() 
 49              node.set_id(id) 
 50              node.set_prev(prev) 
 51              if prev is not None: 
 52                  self.chain[prev].add_succ(id) 
 53              self.chain[id]=node 
 54          return id 
 55   
 56 -    def collapse(self,id): 
 57          """Deletes node from chain and relinks successors to predecessor.""" 
 58          if id not in self.chain: 
 59              raise ChainException('Unknown ID: '+str(id)) 
 60          prev_id=self.chain[id].get_prev() 
 61          self.chain[prev_id].remove_succ(id) 
 62          succ_ids=self.chain[id].get_succ() 
 63          for i in succ_ids: 
 64              self.chain[i].set_prev(prev_id) 
 65          self.chain[prev_id].add_succ(succ_ids) 
 66          node=self.chain[id] 
 67          self.kill(id) 
 68          return node 
 69   
 70 -    def kill(self,id): 
 71          """Kills a node from chain without caring to what it is connected.""" 
 72          if id not in self.chain: 
 73              raise ChainException('Unknown ID: '+str(id)) 
 74          else: 
 75              del self.chain[id] 
 76   
 77 -    def unlink(self,id): 
 78          """Disconnects node from his predecessor.""" 
 79          if id not in self.chain: 
 80              raise ChainException('Unknown ID: '+str(id)) 
 81          else: 
 82              prev_id=self.chain[id].prev 
 83              if prev_id is not None: 
 84                  self.chain[prev_id].succ.pop(self.chain[prev_id].succ.index(id)) 
 85              self.chain[id].prev=None 
 86              return prev_id 
 87   
 88 -    def link(self, parent,child): 
 89          """Connects son to parent.""" 
 90          if child not in self.chain: 
 91              raise ChainException('Unknown ID: '+str(child)) 
 92          elif parent not in self.chain: 
 93              raise ChainException('Unknown ID: '+str(parent)) 
 94          else: 
 95              self.unlink(child) 
 96              self.chain[parent].succ.append(child) 
 97              self.chain[child].set_prev(parent) 
 98   
 99 -    def is_parent_of(self,parent,grandchild): 
100          """Check if grandchild is a subnode of parent.""" 
101          if grandchild==parent or grandchild in self.chain[parent].get_succ(): 
102              return True 
103          else: 
104              for sn in self.chain[parent].get_succ(): 
105                  if self.is_parent_of(sn,grandchild): 
106                      return True 
107              else: 
108                  return False 
109   
110 -    def trace(self,start,finish): 
111          """Returns a list of all node_ids between two nodes (excluding start, including end).""" 
112          if start not in self.chain or finish not in self.chain: 
113              raise NodeException('Unknown node.') 
114          if not self.is_parent_of(start,finish) or start==finish: 
115              return [] 
116          for sn in self.chain[start].get_succ(): 
117              if self.is_parent_of(sn,finish): 
118                  return [sn]+self.trace(sn,finish) 
119   
120   
121 -class Node(object): 
122      """A single node.""" 
123   
124 -    def __init__(self,data=None): 
125          """Represents a node with one predecessor and multiple successors.""" 
126          self.id=None 
127          self.data=data 
128          self.prev=None 
129          self.succ=[] 
130   
131 -    def set_id(self,id): 
132          """Sets the id of a node, if not set yet.""" 
133          if self.id is not None: 
134              raise NodeException('Node id cannot be changed.') 
135          self.id=id 
136   
137 -    def get_id(self): 
138          """Returns the node's id.""" 
139          return self.id 
140   
141 -    def get_succ(self): 
142          """Returns a list of the node's successors.""" 
143          return self.succ 
144   
145 -    def get_prev(self): 
146          """Returns the id of the node's predecessor.""" 
147          return self.prev 
148   
149 -    def add_succ(self,id): 
150          """Adds a node id to the node's successors.""" 
151          if isinstance(id,type([])): 
152              self.succ.extend(id) 
153          else: 
154              self.succ.append(id) 
155   
156 -    def remove_succ(self,id): 
157          """Removes a node id from the node's successors.""" 
158          self.succ.remove(id) 
159   
160 -    def set_succ(self,new_succ): 
161          """Sets the node's successors.""" 
162          if not isinstance(new_succ,type([])): 
163              raise NodeException('Node successor must be of list type.') 
164          self.succ=new_succ 
165   
166 -    def set_prev(self,id): 
167          """Sets the node's predecessor.""" 
168          self.prev=id 
169   
170 -    def get_data(self): 
171          """Returns a node's data.""" 
172          return self.data 
173   
174 -    def set_data(self,data): 
175          """Sets a node's data.""" 
176          self.data=data 
177