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   
  8  from functools import reduce 
  9   
 10   
 11  # TODO - Subclass graph? 
12 -class MultiGraph(object):
13 """A directed multigraph abstraction with labeled edges.""" 14
15 - def __init__(self, nodes=[]):
16 """Initializes a new MultiGraph object.""" 17 self._adjacency_list = {} # maps parent -> set of (child, label) pairs 18 for n in nodes: 19 self._adjacency_list[n] = set() 20 self._label_map = {} # maps label -> set of (parent, child) pairs
21
22 - def __eq__(self, g):
23 """Returns true if g is equal to this graph.""" 24 return isinstance(g, MultiGraph) and \ 25 (self._adjacency_list == g._adjacency_list) and \ 26 (self._label_map == g._label_map)
27
28 - def __ne__(self, g):
29 """Returns true if g is not equal to this graph.""" 30 return not self.__eq__(g)
31
32 - def __repr__(self):
33 """Returns a unique string representation of this graph.""" 34 s = "<MultiGraph: " 35 for key in sorted(self._adjacency_list): 36 values = sorted(self._adjacency_list[key]) 37 s += "(%r: %s)" % (key, ",".join(repr(v) for v in values)) 38 return s + ">"
39
40 - def __str__(self):
41 """Returns a concise string description of this graph.""" 42 nodenum = len(self._adjacency_list) 43 edgenum = reduce(lambda x, y: x+y, 44 [len(v) for v in self._adjacency_list.values()]) 45 labelnum = len(self._label_map) 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] = set()
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] = set() 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 sorted(self._adjacency_list[parent])
73
74 - def children(self, parent):
75 """Returns a list of unique children for parent.""" 76 return sorted(set(x[0] for x in self.child_edges(parent)))
77
78 - def edges(self, label):
79 """Returns a list of all the edges with this label.""" 80 if label not in self._label_map: 81 raise ValueError("Unknown label: " + str(label)) 82 return sorted(self._label_map[label])
83
84 - def labels(self):
85 """Returns a list of all the edge labels in this graph.""" 86 return list(self._label_map.keys())
87
88 - def nodes(self):
89 """Returns a list of the nodes in this graph.""" 90 return list(self._adjacency_list.keys())
91
92 - def parent_edges(self, child):
93 """Returns a list of (parent, label) pairs for child.""" 94 if child not in self._adjacency_list: 95 raise ValueError("Unknown <child> node: " + str(child)) 96 parents = [] 97 for parent, children in self._adjacency_list.items(): 98 for x in children: 99 if x[0] == child: 100 parents.append((parent, x[1])) 101 return sorted(parents)
102
103 - def parents(self, child):
104 """Returns a list of unique parents for child.""" 105 return sorted(set(x[0] for x in self.parent_edges(child)))
106
107 - def remove_node(self, node):
108 """Removes node and all edges connected to it.""" 109 if node not in self._adjacency_list: 110 raise ValueError("Unknown node: " + str(node)) 111 # remove node (and all out-edges) from adjacency list 112 del self._adjacency_list[node] 113 # remove all in-edges from adjacency list 114 for n in self._adjacency_list: 115 self._adjacency_list[n] = set(x for x in self._adjacency_list[n] 116 if x[0] != node) 117 # remove all refering pairs in label map 118 for label in list(self._label_map.keys()): # we're editing this! 119 lm = set(x for x in self._label_map[label] 120 if (x[0] != node) and (x[1] != node)) 121 # remove the entry completely if the label is now unused 122 if lm: 123 self._label_map[label] = lm 124 else: 125 del self._label_map[label]
126
127 - def remove_edge(self, parent, child, label):
128 """Removes edge. -- NOT IMPLEMENTED""" 129 # hm , this is a multigraph - how should this be implemented? 130 raise NotImplementedError("remove_edge is not yet implemented")
131 132 # auxilliary graph functions 133 134
135 -def df_search(graph, root=None):
136 """Depth first search of g. 137 138 Returns a list of all nodes that can be reached from the root node 139 in depth-first order. 140 141 If root is not given, the search will be rooted at an arbitrary node. 142 """ 143 seen = {} 144 search = [] 145 if len(graph.nodes()) < 1: 146 return search 147 if root is None: 148 root = (graph.nodes())[0] 149 seen[root] = 1 150 search.append(root) 151 current = graph.children(root) 152 while len(current) > 0: 153 node = current[0] 154 current = current[1:] 155 if node not in seen: 156 search.append(node) 157 seen[node] = 1 158 current = graph.children(node) + current 159 return search
160 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