[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
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:
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 \
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: "
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."""
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
52          """Adds a node to this graph."""
53          if node not in self._adjacency_list:
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)
64          if label not in self._label_map:
65              self._label_map[label] = set()
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))
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."""
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
113          # remove all in-edges from adjacency list
116                                            if x[0] != node)
117          # remove all referring 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  # auxiliary 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
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
<!--
expandto(location.href);
// -->

```

 Generated by Epydoc 3.0.1 on Thu Aug 25 13:17:14 2016 http://epydoc.sourceforge.net