/usr/share/pyshared/Bio/Nexus/Nodes.py is in python-biopython 1.58-1.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 | # Copyright 2005-2008 by Frank Kauff & Cymon J. Cox. All rights reserved.
# This code is part of the Biopython distribution and governed by its
# license. Please see the LICENSE file that should have been included
# as part of this package.
#
# Nodes.py
#
# Provides functionality of a linked list.
# Each node has one (or none) predecessor, and an arbitrary number of successors.
# Nodes can store arbitrary data in a NodeData class.
#
# Subclassed by Nexus.Trees to store phylogenetic trees.
#
# Bug reports to Frank Kauff (fkauff@biologie.uni-kl.de)
#
class ChainException(Exception):
pass
class NodeException(Exception):
pass
class Chain(object):
"""Stores a list of nodes that are linked together."""
def __init__(self):
"""Initiates a node chain: (self)."""
self.chain={}
self.id=-1
def _get_id(self):
"""Gets a new id for a node in the chain."""
self.id+=1
return self.id
def all_ids(self):
"""Return a list of all node ids."""
return self.chain.keys()
def add(self,node,prev=None):
"""Attaches node to another: (self, node, prev)."""
if prev is not None and prev not in self.chain:
raise ChainException('Unknown predecessor: '+str(prev))
else:
id=self._get_id()
node.set_id(id)
node.set_prev(prev)
if prev is not None:
self.chain[prev].add_succ(id)
self.chain[id]=node
return id
def collapse(self,id):
"""Deletes node from chain and relinks successors to predecessor: collapse(self, id)."""
if id not in self.chain:
raise ChainException('Unknown ID: '+str(id))
prev_id=self.chain[id].get_prev()
self.chain[prev_id].remove_succ(id)
succ_ids=self.chain[id].get_succ()
for i in succ_ids:
self.chain[i].set_prev(prev_id)
self.chain[prev_id].add_succ(succ_ids)
node=self.chain[id]
self.kill(id)
return node
def kill(self,id):
"""Kills a node from chain without caring to what it is connected: kill(self,id)."""
if id not in self.chain:
raise ChainException('Unknown ID: '+str(id))
else:
del self.chain[id]
def unlink(self,id):
"""Disconnects node from his predecessor: unlink(self,id)."""
if id not in self.chain:
raise ChainException('Unknown ID: '+str(id))
else:
prev_id=self.chain[id].prev
if prev_id is not None:
self.chain[prev_id].succ.pop(self.chain[prev_id].succ.index(id))
self.chain[id].prev=None
return prev_id
def link(self, parent,child):
"""Connects son to parent: link(self,son,parent)."""
if child not in self.chain:
raise ChainException('Unknown ID: '+str(child))
elif parent not in self.chain:
raise ChainException('Unknown ID: '+str(parent))
else:
self.unlink(child)
self.chain[parent].succ.append(child)
self.chain[child].set_prev(parent)
def is_parent_of(self,parent,grandchild):
"""Check if grandchild is a subnode of parent: is_parent_of(self,parent,grandchild)."""
if grandchild==parent or grandchild in self.chain[parent].get_succ():
return True
else:
for sn in self.chain[parent].get_succ():
if self.is_parent_of(sn,grandchild):
return True
else:
return False
def trace(self,start,finish):
"""Returns a list of all node_ids between two nodes (excluding start, including end): trace(start,end)."""
if start not in self.chain or finish not in self.chain:
raise NodeException('Unknown node.')
if not self.is_parent_of(start,finish) or start==finish:
return []
for sn in self.chain[start].get_succ():
if self.is_parent_of(sn,finish):
return [sn]+self.trace(sn,finish)
class Node(object):
"""A single node."""
def __init__(self,data=None):
"""Represents a node with one predecessor and multiple successors: (self, data=None)."""
self.id=None
self.data=data
self.prev=None
self.succ=[]
def set_id(self,id):
"""Sets the id of a node, if not set yet: (self,id)."""
if self.id is not None:
raise NodeException('Node id cannot be changed.')
self.id=id
def get_id(self):
"""Returns the node's id: (self)."""
return self.id
def get_succ(self):
"""Returns a list of the node's successors: (self)."""
return self.succ
def get_prev(self):
"""Returns the id of the node's predecessor: (self)."""
return self.prev
def add_succ(self,id):
"""Adds a node id to the node's successors: (self,id)."""
if isinstance(id,type([])):
self.succ.extend(id)
else:
self.succ.append(id)
def remove_succ(self,id):
"""Removes a node id from the node's successors: (self,id)."""
self.succ.remove(id)
def set_succ(self,new_succ):
"""Sets the node's successors: (self,new_succ)."""
if not isinstance(new_succ,type([])):
raise NodeException('Node successor must be of list type.')
self.succ=new_succ
def set_prev(self,id):
"""Sets the node's predecessor: (self,id)."""
self.prev=id
def get_data(self):
"""Returns a node's data: (self)."""
return self.data
def set_data(self,data):
"""Sets a node's data: (self,data)."""
self.data=data
|