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

Source Code for Module Bio.Pathway.Rep.MultiGraph

  1  # Copyright 2001 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 MultiGraph:
10 """A directed multigraph abstraction with labeled edges.""" 11
12 - def __init__(self, nodes = []):
13 """Initializes a new MultiGraph object.""" 14 self.__adjacency_list = {} # maps parent -> set of (child, label) pairs 15 for n in nodes: 16 self.__adjacency_list[n] = HashSet() 17 self.__label_map = {} # maps label -> set of (parent, child) pairs
18
19 - def __eq__(self, g):
20 """Returns true if g is equal to this graph.""" 21 return isinstance(g, MultiGraph) and \ 22 (self.__adjacency_list == g.__adjacency_list) and \ 23 (self.__label_map == g.__label_map)
24
25 - def __ne__(self, g):
26 """Returns true if g is not equal to this graph.""" 27 return not self.__eq__(g)
28
29 - def __repr__(self):
30 """Returns an unique string representation of this graph.""" 31 s = "<MultiGraph: " 32 keys = self.__adjacency_list.keys() 33 keys.sort() 34 for key in keys: 35 values = self.__adjacency_list[key].list() 36 values.sort() 37 s = s + "(" + repr(key) + ": " + ",".join(map(repr, values)) + ")" 38 return s + ">"
39
40 - def __str__(self):
41 """Returns a concise string description of this graph.""" 42 nodenum = len(self.__adjacency_list.keys()) 43 edgenum = reduce(lambda x,y: x+y, 44 map(len, self.__adjacency_list.values())) 45 labelnum = len(self.__label_map.keys()) 46 return "<MultiGraph: " + \ 47 str(nodenum) + " node(s), " + \ 48 str(edgenum) + " edge(s), " + \ 49 str(labelnum) + " unique label(s)>"
50
51 - def add_node(self, node):
52 """Adds a node to this graph.""" 53 if node not in self.__adjacency_list: 54 self.__adjacency_list[node] = HashSet()
55
56 - def add_edge(self, source, to, label = None):
57 """Adds an edge to this graph.""" 58 if source not in self.__adjacency_list: 59 raise ValueError("Unknown <from> node: " + str(source)) 60 if to not in self.__adjacency_list: 61 raise ValueError("Unknown <to> node: " + str(to)) 62 edge = (to, label) 63 self.__adjacency_list[source].add(edge) 64 if label not in self.__label_map: 65 self.__label_map[label] = HashSet() 66 self.__label_map[label].add((source,to))
67
68 - def child_edges(self, parent):
69 """Returns a list of (child, label) pairs for parent.""" 70 if parent not in self.__adjacency_list: 71 raise ValueError("Unknown <parent> node: " + str(parent)) 72 return self.__adjacency_list[parent].list()
73
74 - def children(self, parent):
75 """Returns a list of unique children for parent.""" 76 s = HashSet([x[0] for x in self.child_edges(parent)]) 77 return s.list()
78
79 - def edges(self, label):
80 """Returns a list of all the edges with this label.""" 81 if label not in self.__label_map: 82 raise ValueError("Unknown label: " + str(label)) 83 return self.__label_map[label].list()
84
85 - def labels(self):
86 """Returns a list of all the edge labels in this graph.""" 87 return self.__label_map.keys()
88
89 - def nodes(self):
90 """Returns a list of the nodes in this graph.""" 91 return self.__adjacency_list.keys()
92
93 - def parent_edges(self, child):
94 """Returns a list of (parent, label) pairs for child.""" 95 if child not in self.__adjacency_list: 96 raise ValueError("Unknown <child> node: " + str(child)) 97 parents = [] 98 for parent in self.__adjacency_list.keys(): 99 children = self.__adjacency_list[parent] 100 for x in children.list(): 101 if x[0] is child: 102 parents.append((parent, x[1])) 103 return parents
104
105 - def parents(self, child):
106 """Returns a list of unique parents for child.""" 107 s = HashSet([x[0] for x in self.parent_edges(child)]) 108 return s.list()
109
110 - def remove_node(self, node):
111 """Removes node and all edges connected to it.""" 112 if node not in self.__adjacency_list: 113 raise ValueError("Unknown node: " + str(node)) 114 # remove node (and all out-edges) from adjacency list 115 del self.__adjacency_list[node] 116 # remove all in-edges from adjacency list 117 for n in self.__adjacency_list.keys(): 118 self.__adjacency_list[n] = HashSet(filter(lambda x,node=node: x[0] is not node, 119 self.__adjacency_list[n].list())) 120 # remove all refering pairs in label map 121 for label in self.__label_map.keys(): 122 lm = HashSet(filter(lambda x,node=node: \ 123 (x[0] is not node) and (x[1] is not node), 124 self.__label_map[label].list())) 125 # remove the entry completely if the label is now unused 126 if lm.empty(): 127 del self.__label_map[label] 128 else: 129 self.__label_map[label] = lm
130
131 - def remove_edge(self, parent, child, label):
132 """Removes edge. -- NOT IMPLEMENTED""" 133 # hm , this is a multigraph - how should this be implemented? 134 raise NotImplementedError("remove_edge is not yet implemented")
135 136 # auxilliary graph functions 137
138 -def df_search(graph, root = None):
139 """Depth first search of g. 140 141 Returns a list of all nodes that can be reached from the root node 142 in depth-first order. 143 144 If root is not given, the search will be rooted at an arbitrary node. 145 """ 146 seen = {} 147 search = [] 148 if len(graph.nodes()) < 1: 149 return search 150 if root is None: 151 root = (graph.nodes())[0] 152 seen[root] = 1 153 search.append(root) 154 current = graph.children(root) 155 while len(current) > 0: 156 node = current[0] 157 current = current[1:] 158 if node not in seen: 159 search.append(node) 160 seen[node] = 1 161 current = graph.children(node) + current 162 return search
163
164 -def bf_search(graph, root = None):
165 """Breadth first search of g. 166 167 Returns a list of all nodes that can be reached from the root node 168 in breadth-first order. 169 170 If root is not given, the search will be rooted at an arbitrary node. 171 """ 172 seen = {} 173 search = [] 174 if len(graph.nodes()) < 1: 175 return search 176 if root is None: 177 root = (graph.nodes())[0] 178 seen[root] = 1 179 search.append(root) 180 current = graph.children(root) 181 while len(current) > 0: 182 node = current[0] 183 current = current[1:] 184 if node not in seen: 185 search.append(node) 186 seen[node] = 1 187 current.extend(graph.children(node)) 188 return search
189