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   
  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] = set() 
 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] = set() 
 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] = set() 
 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 sorted(self._adjacency_list[parent])] 
 79   
 80 -    def children(self, parent): 
 81          """Returns a list of unique children for parent.""" 
 82          return sorted(self._adjacency_list[parent]) 
 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, children in self._adjacency_list.iteritems(): 
104              for x in children: 
105                  if x is child: 
106                      parents.append((parent, self._edge_map[(parent, child)])) 
107          return sorted(parents) 
108   
109 -    def parents(self, child): 
110          """Returns a list of unique parents for child.""" 
111          return sorted(set([x[0] for x in self.parent_edges(child)])) 
112   
113 -    def remove_node(self, node): 
114          """Removes node and all edges connected to it.""" 
115          if node not in self._adjacency_list: 
116              raise ValueError("Unknown node: " + str(node)) 
117          # remove node (and all out-edges) from adjacency list 
118          del self._adjacency_list[node] 
119          # remove all in-edges from adjacency list 
120          for n in self._adjacency_list.keys(): 
121              self._adjacency_list[n] = set(x for x in self._adjacency_list[n] 
122                                            if x is not node) 
123          # remove all refering pairs in label map 
124          for label in self._label_map.keys(): 
125              lm = set(x for x in self._label_map[label] 
126                       if (x[0] is not node) and (x[1] is not node)) 
127              # remove the entry completely if the label is now unused 
128              if lm: 
129                  self._label_map[label] = lm 
130              else: 
131                  del self._label_map[label] 
132          # remove all refering entries in edge map 
133          for edge in self._edge_map.keys(): 
134              if edge[0] is node or edge[1] is node: 
135                  del self._edge_map[edge] 
136   
137 -    def remove_edge(self, parent, child, label): 
138          """Removes edge. -- NOT IMPLEMENTED""" 
139          # hm , this is a multigraph - how should this be implemented? 
140          raise NotImplementedError("remove_edge is not yet implemented") 
141