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   
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 list(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 87 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