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