Package Bio :: Package Pathway :: Package Rep :: Module Graph
[hide private]
[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 
  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 -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: 18 self._adjacency_list[n] = set() 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 \ 25 (self._adjacency_list == g._adjacency_list) 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: " 36 for key in sorted(self._adjacency_list): 37 values = sorted([(x, self._edge_map[(key, x)]) 38 for x in self._adjacency_list[key].list()]) 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.""" 44 nodenum = len(self._adjacency_list) 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
53 - def add_node(self, node):
54 """Adds a node to this graph.""" 55 if node not in self._adjacency_list: 56 self._adjacency_list[node] = set()
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") 66 self._adjacency_list[source].add(to) 67 if label not in self._label_map: 68 self._label_map[label] = set() 69 self._label_map[label].add((source, to)) 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)]) 77 for x in sorted(self._adjacency_list[parent])]
78
79 - def children(self, parent):
80 """Returns a list of unique children for parent.""" 81 return sorted(self._adjacency_list[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.""" 95 return list(self._adjacency_list.keys())
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 117 del self._adjacency_list[node] 118 # remove all in-edges from adjacency list 119 for n in self._adjacency_list.keys(): 120 self._adjacency_list[n] = set(x for x in self._adjacency_list[n] 121 if x != node) 122 # remove all refering 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 refering 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