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