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