allpy: c755fb38896c allpy/graph.py

allpy

view allpy/graph.py @ 517:c755fb38896c

graph.py: optimization replace weight_one() to weight_all()

author	boris (kodomo) <bnagaev@gmail.com>
date	Thu, 24 Feb 2011 17:37:28 +0300
parents	1f387f24c7c6
children	449bd8ebeb30

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 weight_all(self):

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

70 w = dict([(vertex, 0) for vertex in self.vertices])

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

72 if edge.issubset(self.vertices):

73 for vertex in edge:

74 w[vertex] += weight

75 return w

77 def count_all(self):

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

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

80 for edge in self.edges:

81 if edge.issubset(self.vertices):

82 for vertex in edge:

83 c[vertex] += 1

84 return c

86 def drop_vertex(self, vertex):

87 """ Remove vertex and all involved edges """

88 for vertex1 in self.vertices:

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

90 self.vertices.discard(vertex)

92 def add_vertex(self, vertex, parent_graph):

93 """ Add vertex and corresponding edges from parent_graph

95 Added edges should be contained in self graph

96 (takes care of hanging edges)

97 """

98 self.vertices.add(vertex)

99 for vertex1 in self.vertices:

100 edge = Graph.edge(vertex, vertex1)

101 if edge in parent_graph.edges:

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

103

104 def drop_vertices(self, vertices):

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

106 for vertex in vertices:

107 self.drop_vertex(vertex)

108

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

110 """ Bron and Kerboch algorithm implementation

111

112 returns list of cliques

113 clique is frozenset

114 if timeout=-1, it means infinity

115 if timeout has happened, raises TimeoutError

116 """

117 if timeout == 0:

118 raise TimeoutError()

119 print 'Bron and Kerbosh algorithm started'

120 cliques = []

121

122 class ExtendCall(object):

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

124 call.candidates = candidates

125 call.used = used

126 call.compsub = compsub

127

128 def best_vertex(call):

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

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

131 c = g.count_all()

132 max_count = max(c.values())

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

134 if count == max_count])

135 if len(best_vertices) == 1:

136 return best_vertices.pop()

137 weights = g.weight_all()

138 _rev = dict([(v,k) for (k,v) in weights.items()

139 if k in best_vertex])

140 max_weight = max(_rev.keys())

141 return _rev[max_weight]

142

143 def get_v_from_candidates(call):

144 """ return some v from candidates """

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

146

147 def used_candidates(call):

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

149 for u in call.used:

150 for c in call.candidates:

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

152 break

153 else:

154 return True

155 return False

156

157 def __call__(call):

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

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

160 v = call.get_v_from_candidates()

161 call.compsub.add(v)

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

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

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

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

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

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

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

169 else:

170 yield ExtendCall(new_candidates,

171 new_used, copy(call.compsub))

172 call.compsub.remove(v)

173 call.candidates.remove(v)

174 call.used.add(v)

175

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

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

178 while stack:

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

180 raise TimeoutError()

181 top = stack[-1]

182 try:

183 call = top.next()

184 stack.append(call())

185 except StopIteration:

186 stack.pop()

187

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

189 return cliques

190

191 def drop_bad_vertices(self):

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

193 while True:

194 # drop vertices, while its is possible

195 if len(self.vertices) <= 1:

196 break

197 c = self.count_all()

198 min_count = min(c.values())

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

200 if count == min_count]

201 if min_count == 0:

202 self.drop_vertices(bad_vertices)

203 continue

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

205 break

206 weights = self.weight_all()

207 _rev = dict([(v,k) for (k,v) in weights.items()

208 if k in bad_vertices])

209 min_weight = min(_rev.keys())

210 self.drop_vertex(_rev[min_weight])

211

212 def expand_to_max_clique(self, parent_graph):

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

214 while True:

215 # add vertices, while its is possible

216 candidats = set()

217 for vertex in parent_graph.vertices:

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

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

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

221 candidats.add(vertex)

222 if not candidats:

223 break

224 weights = parent_graph.weight_all()

225 _rev = dict([(v,k) for (k,v) in weights.items()

226 if k in candidats])

227 max_weight = max(_rev.keys())

228 vertex = _rev[max_weight]

229 self.add_vertex(vertex, parent_graph)

230

231 def fast_cliques(self, minsize=1):

232 """ returns list of cliques

233

234 clique is frozenset

235 """

236 print 'Fast algorithm started'

237 cliques = []

238 while True:

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

240 for clique in cliques:

241 graph.drop_vertices(clique)

242 if not graph.vertices:

243 break

244 graph.drop_bad_vertices()

245 graph.expand_to_max_clique(self)

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

247 if len(clique) >= minsize:

248 cliques.append(clique)

249 else:

250 break

251 return cliques

252

253

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

255 """ returns length-sorted list of cliques

256

257 clique is frozenset

258

259 try to execute bron_kerbosh

260 if it raises TimeoutError, executes fast_cliques

261 """

262

263 try:

264 cliques = self.bron_kerbosh(timeout, minsize)

265 except TimeoutError:

266 cliques = self.fast_cliques(minsize)

267 return cliques

268

269 if __name__ == "__main__":

270 import doctest

271 doctest.testmod()

272