Back to index

python-biopython  1.60
Nodes.py
Go to the documentation of this file.
00001 # Copyright 2005-2008 by Frank Kauff & Cymon J. Cox. All rights reserved.
00002 # This code is part of the Biopython distribution and governed by its
00003 # license. Please see the LICENSE file that should have been included
00004 # as part of this package.
00005 #
00006 # Nodes.py
00007 # 
00008 # Provides functionality of a linked list.
00009 # Each node has one (or none) predecessor, and an arbitrary number of successors.
00010 # Nodes can store arbitrary data in a NodeData class.
00011 #
00012 # Subclassed by Nexus.Trees to store phylogenetic trees.
00013 #
00014 # Bug reports to Frank Kauff (fkauff@biologie.uni-kl.de)
00015 #
00016 
00017 class ChainException(Exception):
00018     pass
00019 
00020 class NodeException(Exception):
00021     pass
00022 
00023 class Chain(object):
00024     """Stores a list of nodes that are linked together."""
00025     
00026     def __init__(self):
00027         """Initiates a node chain: (self)."""
00028         self.chain={}
00029         self.id=-1
00030 
00031     def _get_id(self):
00032         """Gets a new id for a node in the chain."""
00033         self.id+=1
00034         return self.id 
00035    
00036     def all_ids(self):
00037         """Return a list of all node ids."""
00038         return self.chain.keys()
00039 
00040     def add(self,node,prev=None):
00041         """Attaches node to another: (self, node, prev)."""
00042         if prev is not None and prev not in self.chain:
00043             raise ChainException('Unknown predecessor: '+str(prev))
00044         else:
00045             id=self._get_id()
00046             node.set_id(id)
00047             node.set_prev(prev)
00048             if prev is not None:
00049                 self.chain[prev].add_succ(id)
00050             self.chain[id]=node
00051         return id
00052 
00053     def collapse(self,id):
00054         """Deletes node from chain and relinks successors to predecessor: collapse(self, id)."""
00055         if id not in self.chain:
00056             raise ChainException('Unknown ID: '+str(id))
00057         prev_id=self.chain[id].get_prev()
00058         self.chain[prev_id].remove_succ(id)
00059         succ_ids=self.chain[id].get_succ()
00060         for i in succ_ids:
00061             self.chain[i].set_prev(prev_id)
00062         self.chain[prev_id].add_succ(succ_ids)
00063         node=self.chain[id]
00064         self.kill(id)
00065         return node
00066 
00067     def kill(self,id):
00068         """Kills a node from chain without caring to what it is connected: kill(self,id)."""
00069         if id not in self.chain:
00070             raise ChainException('Unknown ID: '+str(id))
00071         else:
00072             del self.chain[id]
00073 
00074     def unlink(self,id):
00075         """Disconnects node from his predecessor: unlink(self,id)."""
00076         if id not in self.chain:
00077             raise ChainException('Unknown ID: '+str(id))
00078         else:
00079             prev_id=self.chain[id].prev
00080             if prev_id is not None:
00081                 self.chain[prev_id].succ.pop(self.chain[prev_id].succ.index(id))
00082             self.chain[id].prev=None
00083             return prev_id
00084 
00085     def link(self, parent,child):
00086         """Connects son to parent: link(self,son,parent)."""
00087         if child not in self.chain:
00088             raise ChainException('Unknown ID: '+str(child))
00089         elif parent not in self.chain:
00090             raise ChainException('Unknown ID: '+str(parent))
00091         else:
00092             self.unlink(child)
00093             self.chain[parent].succ.append(child)
00094             self.chain[child].set_prev(parent)
00095 
00096     def is_parent_of(self,parent,grandchild):
00097         """Check if grandchild is a subnode of parent: is_parent_of(self,parent,grandchild)."""
00098         if grandchild==parent or grandchild in self.chain[parent].get_succ():
00099             return True
00100         else:
00101             for sn in self.chain[parent].get_succ():
00102                 if self.is_parent_of(sn,grandchild):
00103                     return True
00104             else:
00105                 return False
00106 
00107     def trace(self,start,finish):
00108         """Returns a list of all node_ids between two nodes (excluding start, including end): trace(start,end)."""
00109         if start not in self.chain or finish not in self.chain:
00110             raise NodeException('Unknown node.')
00111         if not self.is_parent_of(start,finish) or start==finish:
00112             return []
00113         for sn in self.chain[start].get_succ():
00114             if self.is_parent_of(sn,finish):
00115                 return [sn]+self.trace(sn,finish)
00116                 
00117 class Node(object):
00118     """A single node."""
00119 
00120     def __init__(self,data=None):
00121         """Represents a node with one predecessor and multiple successors: (self, data=None)."""
00122         self.id=None
00123         self.data=data
00124         self.prev=None
00125         self.succ=[]
00126 
00127     def set_id(self,id):
00128         """Sets the id of a node, if not set yet: (self,id)."""
00129         if self.id is not None:
00130             raise NodeException('Node id cannot be changed.')
00131         self.id=id
00132 
00133     def get_id(self):
00134         """Returns the node's id: (self)."""
00135         return self.id
00136 
00137     def get_succ(self):
00138         """Returns a list of the node's successors: (self)."""
00139         return self.succ
00140 
00141     def get_prev(self):
00142         """Returns the id of the node's predecessor: (self)."""
00143         return self.prev
00144 
00145     def add_succ(self,id):
00146         """Adds a node id to the node's successors: (self,id)."""
00147         if isinstance(id,type([])):
00148             self.succ.extend(id)
00149         else:
00150             self.succ.append(id)
00151 
00152     def remove_succ(self,id):
00153         """Removes a node id from the node's successors: (self,id)."""
00154         self.succ.remove(id)
00155 
00156     def set_succ(self,new_succ):
00157         """Sets the node's successors: (self,new_succ)."""
00158         if not isinstance(new_succ,type([])):
00159             raise NodeException('Node successor must be of list type.')
00160         self.succ=new_succ
00161 
00162     def set_prev(self,id):
00163         """Sets the node's predecessor: (self,id)."""
00164         self.prev=id
00165     
00166     def get_data(self):
00167         """Returns a node's data: (self)."""
00168         return self.data
00169 
00170     def set_data(self,data):
00171         """Sets a node's data: (self,data)."""
00172         self.data=data