Mercurial > repos > davidmurphy > codonlogo
comparison corebio/seq_io/_nexus/Nodes.py @ 4:4d47ab2b7bcc
Uploaded
author | davidmurphy |
---|---|
date | Fri, 13 Jan 2012 07:18:19 -0500 |
parents | c55bdc2fb9fa |
children |
comparison
equal
deleted
inserted
replaced
3:09d2dac9ef73 | 4:4d47ab2b7bcc |
---|---|
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 |