[frames] | no frames]

# 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
4  # as part of this package.
5
6  # get set abstraction for graph representation
7
8  from functools import reduce
9
10
11 -class Graph(object):
12      """A directed graph abstraction with labeled edges."""
13
14 -    def __init__(self, nodes=()):
15          """Initializes a new Graph object."""
16          self._adjacency_list = {}    # maps parent -> set of child objects
17          for n in nodes:
19          self._label_map = {}         # maps label -> set of (parent, child) pairs
20          self._edge_map = {}          # maps (parent, child) pair -> label
21
22 -    def __eq__(self, g):
23          """Returns true if g is equal to this graph."""
24          return isinstance(g, Graph) and \
26                 (self._label_map == g._label_map) and \
27                 (self._edge_map == g._edge_map)
28
29 -    def __ne__(self, g):
30          """Returns true if g is not equal to this graph."""
31          return not self.__eq__(g)
32
33 -    def __repr__(self):
34          """Returns a unique string representation of this graph."""
35          s = "<Graph: "
37              values = sorted([(x, self._edge_map[(key, x)])
39              s += "(%r: %s)" % (key, ",".join(repr(v) for v in values))
40          return s + ">"
41
42 -    def __str__(self):
43          """Returns a concise string description of this graph."""
45          edgenum = reduce(lambda x, y: x + y,
46                           [len(v) for v in self._adjacency_list.values()])
47          labelnum = len(self._label_map)
48          return "<Graph: " + \
49                 str(nodenum) + " node(s), " + \
50                 str(edgenum) + " edge(s), " + \
51                 str(labelnum) + " unique label(s)>"
52
54          """Adds a node to this graph."""
55          if node not in self._adjacency_list:
57
58 -    def add_edge(self, source, to, label=None):
59          """Adds an edge to this graph."""
60          if source not in self._adjacency_list:
61              raise ValueError("Unknown <from> node: " + str(source))
62          if to not in self._adjacency_list:
63              raise ValueError("Unknown <to> node: " + str(to))
64          if (source, to) in self._edge_map:
65              raise ValueError(str(source) + " -> " + str(to) + " exists")
67          if label not in self._label_map:
68              self._label_map[label] = set()
70          self._edge_map[(source, to)] = label
71
72 -    def child_edges(self, parent):
73          """Returns a list of (child, label) pairs for parent."""
74          if parent not in self._adjacency_list:
75              raise ValueError("Unknown <parent> node: " + str(parent))
76          return [(x, self._edge_map[(parent, x)])
78
79 -    def children(self, parent):
80          """Returns a list of unique children for parent."""
82
83 -    def edges(self, label):
84          """Returns a list of all the edges with this label."""
85          if label not in self._label_map:
86              raise ValueError("Unknown label: " + str(label))
87          return self._label_map[label].list()
88
89 -    def labels(self):
90          """Returns a list of all the edge labels in this graph."""
91          return list(self._label_map.keys())
92
93 -    def nodes(self):
94          """Returns a list of the nodes in this graph."""
96
97 -    def parent_edges(self, child):
98          """Returns a list of (parent, label) pairs for child."""
99          if child not in self._adjacency_list:
100              raise ValueError("Unknown <child> node: " + str(child))
101          parents = []
102          for parent, children in self._adjacency_list.items():
103              for x in children:
104                  if x == child:
105                      parents.append((parent, self._edge_map[(parent, child)]))
106          return sorted(parents)
107
108 -    def parents(self, child):
109          """Returns a list of unique parents for child."""
110          return sorted(set(x[0] for x in self.parent_edges(child)))
111
112 -    def remove_node(self, node):
113          """Removes node and all edges connected to it."""
114          if node not in self._adjacency_list:
115              raise ValueError("Unknown node: " + str(node))
116          # remove node (and all out-edges) from adjacency list
118          # remove all in-edges from adjacency list
121                                            if x != node)
122          # remove all referring pairs in label map
123          for label in list(self._label_map.keys()):  # we're editing this!
124              lm = set(x for x in self._label_map[label]
125                       if (x[0] != node) and (x[1] != node))
126              # remove the entry completely if the label is now unused
127              if lm:
128                  self._label_map[label] = lm
129              else:
130                  del self._label_map[label]
131          # remove all referring entries in edge map
132          for edge in list(self._edge_map.keys()):  # we're editing this!
133              if edge[0] == node or edge[1] == node:
134                  del self._edge_map[edge]
135
136 -    def remove_edge(self, parent, child, label):
137          """Removes edge. -- NOT IMPLEMENTED"""
138          # hm , this is a multigraph - how should this be implemented?
139          raise NotImplementedError("remove_edge is not yet implemented")
140
<!--
expandto(location.href);
// -->

```

 Generated by Epydoc 3.0.1 on Mon Jul 10 15:17:04 2017 http://epydoc.sourceforge.net