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 = sorted(self.__adjacency_list.keys())
33 for key in keys:
34 values = sorted(self.__adjacency_list[key].list())
35 s += "(" + repr(key) + ": " + ",".join(map(repr, values)) + ")"
36 return s + ">"
37
39 """Returns a concise string description of this graph."""
40 nodenum = len(self.__adjacency_list)
41 edgenum = reduce(lambda x,y: x+y,
42 map(len, self.__adjacency_list.values()))
43 labelnum = len(self.__label_map)
44 return "<MultiGraph: " + \
45 str(nodenum) + " node(s), " + \
46 str(edgenum) + " edge(s), " + \
47 str(labelnum) + " unique label(s)>"
48
50 """Adds a node to this graph."""
51 if node not in self.__adjacency_list:
52 self.__adjacency_list[node] = HashSet()
53
54 - def add_edge(self, source, to, label = None):
55 """Adds an edge to this graph."""
56 if source not in self.__adjacency_list:
57 raise ValueError("Unknown <from> node: " + str(source))
58 if to not in self.__adjacency_list:
59 raise ValueError("Unknown <to> node: " + str(to))
60 edge = (to, label)
61 self.__adjacency_list[source].add(edge)
62 if label not in self.__label_map:
63 self.__label_map[label] = HashSet()
64 self.__label_map[label].add((source,to))
65
67 """Returns a list of (child, label) pairs for parent."""
68 if parent not in self.__adjacency_list:
69 raise ValueError("Unknown <parent> node: " + str(parent))
70 return self.__adjacency_list[parent].list()
71
73 """Returns a list of unique children for parent."""
74 s = HashSet([x[0] for x in self.child_edges(parent)])
75 return s.list()
76
78 """Returns a list of all the edges with this label."""
79 if label not in self.__label_map:
80 raise ValueError("Unknown label: " + str(label))
81 return self.__label_map[label].list()
82
84 """Returns a list of all the edge labels in this graph."""
85 return self.__label_map.keys()
86
88 """Returns a list of the nodes in this graph."""
89 return self.__adjacency_list.keys()
90
92 """Returns a list of (parent, label) pairs for child."""
93 if child not in self.__adjacency_list:
94 raise ValueError("Unknown <child> node: " + str(child))
95 parents = []
96 for parent in self.__adjacency_list:
97 children = self.__adjacency_list[parent]
98 for x in children.list():
99 if x[0] is child:
100 parents.append((parent, x[1]))
101 return parents
102
104 """Returns a list of unique parents for child."""
105 s = HashSet([x[0] for x in self.parent_edges(child)])
106 return s.list()
107
109 """Removes node and all edges connected to it."""
110 if node not in self.__adjacency_list:
111 raise ValueError("Unknown node: " + str(node))
112
113 del self.__adjacency_list[node]
114
115 for n in self.__adjacency_list:
116 self.__adjacency_list[n] = HashSet(filter(lambda x,node=node: x[0] is not node,
117 self.__adjacency_list[n].list()))
118
119 for label in self.__label_map.keys():
120 lm = HashSet(filter(lambda x,node=node: \
121 (x[0] is not node) and (x[1] is not node),
122 self.__label_map[label].list()))
123
124 if lm.empty():
125 del self.__label_map[label]
126 else:
127 self.__label_map[label] = lm
128
130 """Removes edge. -- NOT IMPLEMENTED"""
131
132 raise NotImplementedError("remove_edge is not yet implemented")
133
134
135
137 """Depth first search of g.
138
139 Returns a list of all nodes that can be reached from the root node
140 in depth-first order.
141
142 If root is not given, the search will be rooted at an arbitrary node.
143 """
144 seen = {}
145 search = []
146 if len(graph.nodes()) < 1:
147 return search
148 if root is None:
149 root = (graph.nodes())[0]
150 seen[root] = 1
151 search.append(root)
152 current = graph.children(root)
153 while len(current) > 0:
154 node = current[0]
155 current = current[1:]
156 if node not in seen:
157 search.append(node)
158 seen[node] = 1
159 current = graph.children(node) + current
160 return search
161
163 """Breadth first search of g.
164
165 Returns a list of all nodes that can be reached from the root node
166 in breadth-first order.
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