1
2
3
4
5
6
7 from Bio.Pathway.Rep.HashSet import *
8
10 """A directed multigraph abstraction with labeled edges."""
11
13 """Initializes a new MultiGraph object."""
14 self.__adjacency_list = {}
15 for n in nodes:
16 self.__adjacency_list[n] = HashSet()
17 self.__label_map = {}
18
20 """Returns true if g is equal to this graph."""
21 return isinstance(g, MultiGraph) and \
22 (self.__adjacency_list == g.__adjacency_list) and \
23 (self.__label_map == g.__label_map)
24
26 """Returns true if g is not equal to this graph."""
27 return not self.__eq__(g)
28
30 """Returns an unique string representation of this graph."""
31 s = "<MultiGraph: "
32 keys = self.__adjacency_list.keys()
33 keys.sort()
34 for key in keys:
35 values = self.__adjacency_list[key].list()
36 values.sort()
37 s = s + "(" + repr(key) + ": " + ",".join(map(repr, values)) + ")"
38 return s + ">"
39
41 """Returns a concise string description of this graph."""
42 nodenum = len(self.__adjacency_list.keys())
43 edgenum = reduce(lambda x,y: x+y,
44 map(len, self.__adjacency_list.values()))
45 labelnum = len(self.__label_map.keys())
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:
54 self.__adjacency_list[node] = HashSet()
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)
63 self.__adjacency_list[source].add(edge)
64 if label not in self.__label_map:
65 self.__label_map[label] = HashSet()
66 self.__label_map[label].add((source,to))
67
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))
72 return self.__adjacency_list[parent].list()
73
75 """Returns a list of unique children for parent."""
76 s = HashSet([x[0] for x in self.child_edges(parent)])
77 return s.list()
78
80 """Returns a list of all the edges with this label."""
81 if label not in self.__label_map:
82 raise ValueError("Unknown label: " + str(label))
83 return self.__label_map[label].list()
84
86 """Returns a list of all the edge labels in this graph."""
87 return self.__label_map.keys()
88
90 """Returns a list of the nodes in this graph."""
91 return self.__adjacency_list.keys()
92
94 """Returns a list of (parent, label) pairs for child."""
95 if child not in self.__adjacency_list:
96 raise ValueError("Unknown <child> node: " + str(child))
97 parents = []
98 for parent in self.__adjacency_list.keys():
99 children = self.__adjacency_list[parent]
100 for x in children.list():
101 if x[0] is child:
102 parents.append((parent, x[1]))
103 return parents
104
106 """Returns a list of unique parents for child."""
107 s = HashSet([x[0] for x in self.parent_edges(child)])
108 return s.list()
109
111 """Removes node and all edges connected to it."""
112 if node not in self.__adjacency_list:
113 raise ValueError("Unknown node: " + str(node))
114
115 del self.__adjacency_list[node]
116
117 for n in self.__adjacency_list.keys():
118 self.__adjacency_list[n] = HashSet(filter(lambda x,node=node: x[0] is not node,
119 self.__adjacency_list[n].list()))
120
121 for label in self.__label_map.keys():
122 lm = HashSet(filter(lambda x,node=node: \
123 (x[0] is not node) and (x[1] is not node),
124 self.__label_map[label].list()))
125
126 if lm.empty():
127 del self.__label_map[label]
128 else:
129 self.__label_map[label] = lm
130
132 """Removes edge. -- NOT IMPLEMENTED"""
133
134 raise NotImplementedError("remove_edge is not yet implemented")
135
136
137
139 """Depth first search of g.
140
141 Returns a list of all nodes that can be reached from the root node
142 in depth-first order.
143
144 If root is not given, the search will be rooted at an arbitrary node.
145 """
146 seen = {}
147 search = []
148 if len(g.nodes()) < 1:
149 return search
150 if root is None:
151 root = (g.nodes())[0]
152 seen[root] = 1
153 search.append(root)
154 current = g.children(root)
155 while len(current) > 0:
156 node = current[0]
157 current = current[1:]
158 if node not in seen:
159 search.append(node)
160 seen[node] = 1
161 current = g.children(node) + current
162 return search
163
165 """Breadth first search of g.
166
167 Returns a list of all nodes that can be reached from the root node
168 in breadth-first order.
169
170 If root is not given, the search will be rooted at an arbitrary node.
171 """
172 seen = {}
173 search = []
174 if len(g.nodes()) < 1:
175 return search
176 if root is None:
177 root = (g.nodes())[0]
178 seen[root] = 1
179 search.append(root)
180 current = g.children(root)
181 while len(current) > 0:
182 node = current[0]
183 current = current[1:]
184 if node not in seen:
185 search.append(node)
186 seen[node] = 1
187 current.extend(g.children(node))
188 return search
189