allpy: b92cad794578 allpy/graph.py

allpy

view allpy/graph.py @ 481:b92cad794578

allpy/structure: remove Sequence.pdb_residues, add Monomer.pdb_residue Information from aequence.pdb_residues[monomer] is now available in monomer.pdb_residue

author	boris (netbook) <bnagaev@gmail.com>
date	Fri, 18 Feb 2011 18:48:37 +0300
parents	e4c4151b9dc3
children	1f387f24c7c6

line source

1 from datetime import datetime, timedelta

2 from copy import copy

4 class TimeoutError(Exception):

5 pass

9 class Graph(object):

10 """ Undirected weighted graph

12 Data:

13 vertices -- set of elements

14 edges -- {edge: weight}.

15 edge is frozenset([e1, e2])

16 weight is float in (0, 1] or 1 (if all edges are equal)

18 >>> g = Graph(set([1,2,3]), {frozenset([1,2]): 1})

19 >>> g.fast_cliques()

20 Fast algorithm started

21 [frozenset([1, 2]), frozenset([3])]

22 >>> g = Graph(set([1,2,3]), {frozenset([1,2]): 1, frozenset([1,1]): 1})

23 >>> g.fast_cliques()

24 Fast algorithm started

25 [frozenset([1, 2]), frozenset([3])]

26 >>> g = Graph(set([1,2,3,4]), {frozenset([1,2]): 0.98,

27 ... frozenset([1,3]): 0.98, frozenset([2,3]): 0.1,

28 ... frozenset([1,1]): 1})

29 >>> g.fast_cliques()

30 Fast algorithm started

31 [frozenset([1, 2, 3]), frozenset([4])]

32 >>> g.fast_cliques(minsize=2)

33 Fast algorithm started

34 [frozenset([1, 2, 3])]

35 >>> g.bron_kerbosh()

36 Bron and Kerbosh algorithm started

37 [frozenset([1, 2, 3]), frozenset([4])]

38 >>> g.cliques()

39 Bron and Kerbosh algorithm started

40 [frozenset([1, 2, 3]), frozenset([4])]

41 >>> g.cliques(minsize=2)

42 Bron and Kerbosh algorithm started

43 [frozenset([1, 2, 3])]

44 >>> g.vertices

45 set([1, 2, 3, 4])

46 """

48 def __init__(self, vertices=None, edges=None):

49 if not vertices:

50 vertices = set()

51 if not edges:

52 edges = dict()

53 self.vertices = vertices

54 self.edges = edges

55 for edge, weight in copy(self.edges.items()):

56 if len(edge) != 2 or not edge.issubset(self.vertices):

57 self.edges.pop(edge)

59 @staticmethod

60 def edge(k1, k2):

61 """ Construct object, representing edge of graph """

62 return frozenset([k1, k2])

64 def bounded(self, k1, k2):

65 """ if these two vertices of the graph are bounded with edge """

66 return k1 is k2 or Graph.edge(k1, k2) in self.edges

68 def count_one(self, vertex):

69 """ Returns number of connections of this vertex """

70 return len([vertex1 for vertex1 in self.vertices

71 if self.bounded(vertex, vertex1)]) - 1

73 def weight_one(self, vertex):

74 """ Returns sum of weights of all connections of this vertex """

75 return sum([self.edges.get(Graph.edge(vertex, vertex1), 0)

76 for vertex1 in self.vertices if vertex is not vertex1])

78 def count_all(self):

79 """ Returns {vertex: number of connections of this vertex} """

80 c = dict([(vertex, 0) for vertex in self.vertices])

81 for edge in self.edges:

82 if edge.issubset(self.vertices):

83 for vertex in edge:

84 c[vertex] += 1

85 return c

87 def drop_vertex(self, vertex):

88 """ Remove vertex and all involved edges """

89 for vertex1 in self.vertices:

90 self.edges.pop(Graph.edge(vertex, vertex1), None)

91 self.vertices.discard(vertex)

93 def add_vertex(self, vertex, parent_graph):

94 """ Add vertex and corresponding edges from parent_graph

96 Added edges should be contained in self graph

97 (takes care of hanging edges)

98 """

99 self.vertices.add(vertex)

100 for vertex1 in self.vertices:

101 edge = Graph.edge(vertex, vertex1)

102 if edge in parent_graph.edges:

103 self.edges[edge] = parent_graph.edges[edge]

104

105 def drop_vertices(self, vertices):

106 """ Run drop_vertex for each of given vertices """

107 for vertex in vertices:

108 self.drop_vertex(vertex)

109

110 def bron_kerbosh(self, timeout=-1, minsize=1):

111 """ Bron and Kerboch algorithm implementation

112

113 returns list of cliques

114 clique is frozenset

115 if timeout=-1, it means infinity

116 if timeout has happened, raises TimeoutError

117 """

118 print 'Bron and Kerbosh algorithm started'

119 cliques = []

120

121 class ExtendCall(object):

122 def __init__(call, candidates, used, compsub):

123 call.candidates = candidates

124 call.used = used

125 call.compsub = compsub

126

127 def best_vertex(call):

128 """ return vertex with max count (and weight) """

129 g = Graph(call.candidates, self.edges)

130 c = g.count_all()

131 max_count = max(c.values())

132 best_vertices = [vertex for (vertex, count) in c.items()

133 if count == max_count]

134 if len(best_vertices) == 1:

135 return best_vertices[0]

136 weights = dict([(g.weight_one(v), v) for v in best_vertices])

137 max_weight = max(weights.keys())

138 return weights[max_weight]

139

140 def get_v_from_candidates(call):

141 """ return some v from candidates """

142 return iter(call.candidates).next()

143

144 def used_candidates(call):

145 """ if v from used connected with all from candidates """

146 for u in call.used:

147 for c in call.candidates:

148 if not self.bounded(u, c):

149 break

150 else:

151 return True

152 return False

153

154 def __call__(call):

155 """ process call and return list of recursive calls """

156 while call.candidates and not call.used_candidates():

157 v = call.get_v_from_candidates()

158 call.compsub.add(v)

159 new_candidates = set([i for i in call.candidates

160 if self.bounded(i, v) and i is not v])

161 new_used = set([i for i in call.used

162 if self.bounded(i, v) and i is not v])

163 if (not new_candidates) and (not new_used):

164 if len(call.compsub) >= minsize:

165 cliques.append(copy(frozenset(call.compsub)))

166 else:

167 yield ExtendCall(new_candidates,

168 new_used, copy(call.compsub))

169 call.compsub.remove(v)

170 call.candidates.remove(v)

171 call.used.add(v)

172

173 stop_time = datetime.now() + timedelta(0, timeout)

174 stack = [ExtendCall(copy(set(self.vertices)), set(), set())()]

175 while stack:

176 if timeout != -1 and datetime.now() > stop_time:

177 raise TimeoutError()

178 top = stack[-1]

179 try:

180 call = top.next()

181 stack.append(call())

182 except StopIteration:

183 stack.pop()

184

185 cliques.sort(key=lambda clique: len(clique), reverse=True)

186 return cliques

187

188 def drop_bad_vertices(self):

189 """ drop vertices untill self becomes a clique """

190 while True:

191 # drop vertices, while its is possible

192 if len(self.vertices) == 1:

193 break

194 c = self.count_all()

195 min_count = min(c.values())

196 bad_vertices = [vertex for (vertex, count) in c.items()

197 if count == min_count]

198 if len(bad_vertices) == len(self.vertices) and min_count != 0:

199 break

200 weights = dict([(vertex, self.weight_one(vertex)) for vertex

201 in bad_vertices])

202 min_weight = min(weights.values())

203 for vertex, weight in weights.items():

204 if weight == min_weight:

205 self.drop_vertex(vertex)

206 break

207

208 def expand_to_max_clique(self, parent_graph):

209 """ add vertices untill self becomes a nonextendible clique """

210 while True:

211 # add vertices, while its is possible

212 candidats = {}

213 for vertex in parent_graph.vertices:

214 c = len([i for i in self.vertices

215 if parent_graph.bounded(vertex, i)])

216 if c == len(parent_graph.vertices):

217 g = Graph(self.vertices, copy(self.edges))

218 g.add_vertex(vertex, parent_graph)

219 candidats[vertex] = g.weight_one(vertex)

220 if not candidats:

221 break

222 max_weight = max(candidats.values())

223 vertex = [vertex for (vertex, weight) in candidats.items()

224 if weight == max_weight][0]

225 self.add_vertex(vertex, parent_graph)

226

227 def fast_cliques(self, minsize=1):

228 """ returns list of cliques

229

230 clique is frozenset

231 """

232 print 'Fast algorithm started'

233 cliques = []

234 while True:

235 graph = Graph(copy(self.vertices), copy(self.edges))

236 for clique in cliques:

237 graph.drop_vertices(clique)

238 if not graph.vertices:

239 break

240 graph.drop_bad_vertices()

241 graph.expand_to_max_clique(self)

242 clique = copy(frozenset(graph.vertices))

243 if len(clique) >= minsize:

244 cliques.append(clique)

245 else:

246 break

247 return cliques

248

249

250 def cliques(self, timeout=-1, minsize=1):

251 """ returns length-sorted list of cliques

252

253 clique is frozenset

254

255 try to execute bron_kerbosh

256 if it raises TimeoutError, executes fast_cliques

257 """

258

259 try:

260 cliques = self.bron_kerbosh(timeout, minsize)

261 except TimeoutError:

262 cliques = self.fast_cliques(minsize)

263 return cliques

264

265 if __name__ == "__main__":

266 import doctest

267 doctest.testmod()

268