Mercurial > repos > davidmurphy > codonlogo

comparison corebio/seq_io/_nexus/Nodes.py @ 0:c55bdc2fb9fa

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Uploaded
author davidmurphy
date Thu, 27 Oct 2011 12:09:09 -0400
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:c55bdc2fb9fa
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