0
|
1 # Copyright 2005 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@duke.edu)
|
|
15 #
|
|
16
|
|
17 class ChainException(Exception):
|
|
18 pass
|
|
19
|
|
20 class NodeException(Exception):
|
|
21 pass
|
|
22
|
|
23 class Chain:
|
|
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('Unknow 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
|
|
74 def unlink(self,id):
|
|
75 """Disconnects node from his predecessor: unlink(self,id)."""
|
|
76 if id not in self.chain:
|
|
77 raise ChainException('Unknown ID: '+str(id))
|
|
78 else:
|
|
79 prev_id=self.chain[id].prev
|
|
80 if prev_id is not None:
|
|
81 self.chain[prev_id].succ.pop(self.chain[prev_id].succ.index(id))
|
|
82 self.chain[id].prev=None
|
|
83 return prev_id
|
|
84
|
|
85 def link(self, parent,child):
|
|
86 """Connects son to parent: link(self,son,parent)."""
|
|
87 if child not in self.chain:
|
|
88 raise ChainException('Unknown ID: '+str(child))
|
|
89 elif parent not in self.chain:
|
|
90 raise ChainException('Unknown ID: '+str(parent))
|
|
91 else:
|
|
92 self.unlink(child)
|
|
93 self.chain[parent].succ.append(child)
|
|
94 self.chain[child].set_prev(parent)
|
|
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:
|
|
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
|