Package Bio :: Package Pathway :: Package Rep :: Module Graph
[hide private]
[frames] | no frames]

Source Code for Module Bio.Pathway.Rep.Graph

  1  # Copyright 2002 by Tarjei Mikkelsen.  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  # get set abstraction for graph representation 
  7  from Bio.Pathway.Rep.HashSet import * 
  8   
9 -class Graph(object):
10 """A directed graph abstraction with labeled edges.""" 11
12 - def __init__(self, nodes = []):
13 """Initializes a new Graph object.""" 14 self.__adjacency_list = {} # maps parent -> set of child objects 15 for n in nodes: 16 self.__adjacency_list[n] = HashSet() 17 self.__label_map = {} # maps label -> set of (parent, child) pairs 18 self.__edge_map = {} # maps (parent, child) pair -> label
19
20 - def __eq__(self, g):
21 """Returns true if g is equal to this graph.""" 22 return isinstance(g, Graph) and \ 23 (self.__adjacency_list == g.__adjacency_list) and \ 24 (self.__label_map == g.__label_map) and \ 25 (self.__edge_map == g.__edge_map)
26
27 - def __ne__(self, g):
28 """Returns true if g is not equal to this graph.""" 29 return not self.__eq__(g)
30
31 - def __repr__(self):
32 """Returns an unique string representation of this graph.""" 33 s = "<Graph: " 34 keys = self.__adjacency_list.keys() 35 keys.sort() 36 for key in keys: 37 values = [(x,self.__edge_map[(key,x)]) \ 38 for x in self.__adjacency_list[key].list()] 39 values.sort() 40 s = s + "(" + repr(key) + ": " + ",".join(map(repr, values)) + ")" 41 return s + ">"
42
43 - def __str__(self):
44 """Returns a concise string description of this graph.""" 45 nodenum = len(self.__adjacency_list.keys()) 46 edgenum = reduce(lambda x,y: x+y, 47 map(len, self.__adjacency_list.values())) 48 labelnum = len(self.__label_map.keys()) 49 return "<Graph: " + \ 50 str(nodenum) + " node(s), " + \ 51 str(edgenum) + " edge(s), " + \ 52 str(labelnum) + " unique label(s)>"
53
54 - def add_node(self, node):
55 """Adds a node to this graph.""" 56 if node not in self.__adjacency_list: 57 self.__adjacency_list[node] = HashSet()
58
59 - def add_edge(self, source, to, label = None):
60 """Adds an edge to this graph.""" 61 if source not in self.__adjacency_list: 62 raise ValueError("Unknown <from> node: " + str(source)) 63 if to not in self.__adjacency_list: 64 raise ValueError("Unknown <to> node: " + str(to)) 65 if (source,to) in self.__edge_map: 66 raise ValueError(str(source) + " -> " + str(to) + " exists") 67 self.__adjacency_list[source].add(to) 68 if label not in self.__label_map: 69 self.__label_map[label] = HashSet() 70 self.__label_map[label].add((source,to)) 71 self.__edge_map[(source,to)] = label
72
73 - def child_edges(self, parent):
74 """Returns a list of (child, label) pairs for parent.""" 75 if parent not in self.__adjacency_list: 76 raise ValueError("Unknown <parent> node: " + str(parent)) 77 return [(x, self.__edge_map[(parent,x)]) \ 78 for x in self.__adjacency_list[parent].list()]
79
80 - def children(self, parent):
81 """Returns a list of unique children for parent.""" 82 return self.__adjacency_list[parent].list()
83
84 - def edges(self, label):
85 """Returns a list of all the edges with this label.""" 86 if label not in self.__label_map: 87 raise ValueError("Unknown label: " + str(label)) 88 return self.__label_map[label].list()
89
90 - def labels(self):
91 """Returns a list of all the edge labels in this graph.""" 92 return self.__label_map.keys()
93
94 - def nodes(self):
95 """Returns a list of the nodes in this graph.""" 96 return self.__adjacency_list.keys()
97
98 - def parent_edges(self, child):
99 """Returns a list of (parent, label) pairs for child.""" 100 if child not in self.__adjacency_list: 101 raise ValueError("Unknown <child> node: " + str(child)) 102 parents = [] 103 for parent in self.__adjacency_list.keys(): 104 children = self.__adjacency_list[parent] 105 for x in children.list(): 106 if x is child: 107 parents.append((parent, self.__edge_map[(parent, child)])) 108 return parents
109
110 - def parents(self, child):
111 """Returns a list of unique parents for child.""" 112 s = HashSet([x[0] for x in self.parent_edges(child)]) 113 return s.list()
114
115 - def remove_node(self, node):
116 """Removes node and all edges connected to it.""" 117 if node not in self.__adjacency_list: 118 raise ValueError("Unknown node: " + str(node)) 119 # remove node (and all out-edges) from adjacency list 120 del self.__adjacency_list[node] 121 # remove all in-edges from adjacency list 122 for n in self.__adjacency_list.keys(): 123 self.__adjacency_list[n] = HashSet(filter(lambda x,node=node: x is not node, 124 self.__adjacency_list[n].list())) 125 # remove all refering pairs in label map 126 for label in self.__label_map.keys(): 127 lm = HashSet(filter(lambda x,node=node: \ 128 (x[0] is not node) and (x[1] is not node), 129 self.__label_map[label].list())) 130 # remove the entry completely if the label is now unused 131 if lm.empty(): 132 del self.__label_map[label] 133 else: 134 self.__label_map[label] = lm 135 # remove all refering entries in edge map 136 for edge in self.__edge_map.keys(): 137 if edge[0] is node or edge[1] is node: 138 del self.__edge_map[edge]
139
140 - def remove_edge(self, parent, child, label):
141 """Removes edge. -- NOT IMPLEMENTED""" 142 # hm , this is a multigraph - how should this be implemented? 143 raise NotImplementedError("remove_edge is not yet implemented")
144