1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
|
# Copyright 2001 by Tarjei Mikkelsen. All rights reserved.
# This code is part of the Biopython distribution and governed by its
# license. Please see the LICENSE file that should have been included
# as part of this package.
# get set abstraction for graph representation
from Bio.Pathway.Rep.HashSet import *
class MultiGraph:
"""A directed multigraph abstraction with labeled edges."""
def __init__(self, nodes = []):
"""Initializes a new MultiGraph object."""
self.__adjacency_list = {} # maps parent -> set of (child, label) pairs
for n in nodes:
self.__adjacency_list[n] = HashSet()
self.__label_map = {} # maps label -> set of (parent, child) pairs
def __eq__(self, g):
"""Returns true if g is equal to this graph."""
return isinstance(g, MultiGraph) and \
(self.__adjacency_list == g.__adjacency_list) and \
(self.__label_map == g.__label_map)
def __ne__(self, g):
"""Returns true if g is not equal to this graph."""
return not self.__eq__(g)
def __repr__(self):
"""Returns an unique string representation of this graph."""
s = "<MultiGraph: "
keys = self.__adjacency_list.keys()
keys.sort()
for key in keys:
values = self.__adjacency_list[key].list()
values.sort()
s = s + "(" + repr(key) + ": " + ",".join(map(repr, values)) + ")"
return s + ">"
def __str__(self):
"""Returns a concise string description of this graph."""
nodenum = len(self.__adjacency_list.keys())
edgenum = reduce(lambda x,y: x+y,
map(len, self.__adjacency_list.values()))
labelnum = len(self.__label_map.keys())
return "<MultiGraph: " + \
str(nodenum) + " node(s), " + \
str(edgenum) + " edge(s), " + \
str(labelnum) + " unique label(s)>"
def add_node(self, node):
"""Adds a node to this graph."""
if not self.__adjacency_list.has_key(node):
self.__adjacency_list[node] = HashSet()
def add_edge(self, source, to, label = None):
"""Adds an edge to this graph."""
if not self.__adjacency_list.has_key(source):
raise ValueError, "Unknown <from> node: " + str(source)
if not self.__adjacency_list.has_key(to):
raise ValueError, "Unknown <to> node: " + str(to)
edge = (to, label)
self.__adjacency_list[source].add(edge)
if not self.__label_map.has_key(label):
self.__label_map[label] = HashSet()
self.__label_map[label].add((source,to))
def child_edges(self, parent):
"""Returns a list of (child, label) pairs for parent."""
if not self.__adjacency_list.has_key(parent):
raise ValueError, "Unknown <parent> node: " + str(parent)
return self.__adjacency_list[parent].list()
def children(self, parent):
"""Returns a list of unique children for parent."""
s = HashSet([x[0] for x in self.child_edges(parent)])
return s.list()
def edges(self, label):
"""Returns a list of all the edges with this label."""
if not self.__label_map.has_key(label):
raise ValueError, "Unknown label: " + str(label)
return self.__label_map[label].list()
def labels(self):
"""Returns a list of all the edge labels in this graph."""
return self.__label_map.keys()
def nodes(self):
"""Returns a list of the nodes in this graph."""
return self.__adjacency_list.keys()
def parent_edges(self, child):
"""Returns a list of (parent, label) pairs for child."""
if not self.__adjacency_list.has_key(child):
raise ValueError, "Unknown <child> node: " + str(child)
parents = []
for parent in self.__adjacency_list.keys():
children = self.__adjacency_list[parent]
for x in children.list():
if x[0] is child:
parents.append((parent, x[1]))
return parents
def parents(self, child):
"""Returns a list of unique parents for child."""
s = HashSet([x[0] for x in self.parent_edges(child)])
return s.list()
def remove_node(self, node):
"""Removes node and all edges connected to it."""
if not self.__adjacency_list.has_key(node):
raise ValueError, "Unknown node: " + str(node)
# remove node (and all out-edges) from adjacency list
del self.__adjacency_list[node]
# remove all in-edges from adjacency list
for n in self.__adjacency_list.keys():
self.__adjacency_list[n] = HashSet(filter(lambda x,node=node: x[0] is not node,
self.__adjacency_list[n].list()))
# remove all refering pairs in label map
for label in self.__label_map.keys():
lm = HashSet(filter(lambda x,node=node: \
(x[0] is not node) and (x[1] is not node),
self.__label_map[label].list()))
# remove the entry completely if the label is now unused
if lm.empty():
del self.__label_map[label]
else:
self.__label_map[label] = lm
def remove_edge(self, parent, child, label):
"""Removes edge. -- NOT IMPLEMENTED"""
# hm , this is a multigraph - how should this be implemented?
raise NotImplementedError, "remove_edge is not yet implemented"
# auxilliary graph functions
def df_search(graph, root = None):
"""Depth first search of g.
Returns a list of all nodes that can be reached from the root node
in depth-first order.
If root is not given, the search will be rooted at an arbitrary node.
"""
seen = {}
search = []
if len(g.nodes()) < 1:
return search
if root is None:
root = (g.nodes())[0]
seen[root] = 1
search.append(root)
current = g.children(root)
while len(current) > 0:
node = current[0]
current = current[1:]
if not seen.has_key(node):
search.append(node)
seen[node] = 1
current = g.children(node) + current
return search
def bf_search(graph, root = None):
"""Breadth first search of g.
Returns a list of all nodes that can be reached from the root node
in breadth-first order.
If root is not given, the search will be rooted at an arbitrary node.
"""
seen = {}
search = []
if len(g.nodes()) < 1:
return search
if root is None:
root = (g.nodes())[0]
seen[root] = 1
search.append(root)
current = g.children(root)
while len(current) > 0:
node = current[0]
current = current[1:]
if not seen.has_key(node):
search.append(node)
seen[node] = 1
current.extend(g.children(node))
return search
|
