allpy: fd7371f14c6d lib/graph.py

allpy

view lib/graph.py @ 117:fd7371f14c6d

lib::graph -- improvement of code and fix of bug in add_node function

author	boris <bnagaev@gmail.com>
date	Sat, 23 Oct 2010 20:59:22 +0400
parents	0ef1a722b738
children	dd9fa5a8dc5a

line source

1 # -*- coding: utf-8 -*-

3 from datetime import datetime

4 from copy import copy

6 class TimeoutError(Exception):

7 pass

11 class Graph(object):

12 """

13 Data:

14 nodes -- set of elements

15 lines -- {line: cost}.

16 line is frozenset([e1, e2])

17 cost is float in (0, 1] or 1 (if all lines are equal)

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

20 >>> g.fast_cliques()

21 Fast algorithm started

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

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

24 ... frozenset([2,3]): 0.1})

25 >>> g.fast_cliques()

26 Fast algorithm started

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

28 >>> g.bron_kerbosh()

29 Bron and Kerbosh algorithm started

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

31 """

33 def __init__(self, nodes=None, lines=None):

34 if not nodes:

35 nodes = set()

36 if not lines:

37 lines = dict()

38 self.nodes = copy(nodes)

39 self.lines = copy(lines)

41 @staticmethod

42 def line(k1, k2):

43 return frozenset([k1, k2])

45 def bounded(self, k1, k2):

46 return k1 == k2 or Graph.line(k1, k2) in self.lines

48 def count_one(self, node):

49 return len([node1 for node1 in self.nodes if self.bounded(node, node1)]) - 1

51 def cost_one(self, node):

52 return sum([self.lines.get(Graph.line(node, node1), 0) for \

53 node1 in self.nodes if node != node1])

55 def count_all(self):

56 c = dict([(node, 0) for node in self.nodes])

57 for line in self.lines:

58 for node in line:

59 c[node] += 1

60 return c

63 def drop_node(self, node):

64 for node1 in self.nodes:

65 self.lines.pop(Graph.line(node, node1), None)

66 self.nodes.discard(node)

68 def add_node(self, node, parent_graph):

69 self.nodes.add(node)

70 for node1 in self.nodes:

71 line = Graph.line(node, node1)

72 if line in parent_graph.lines:

73 self.lines[line] = parent_graph.lines[line]

75 def drop_nodes(self, nodes):

76 for node in nodes:

77 self.drop_node(node)

78 return bool(nodes)

80 def drop_if_count(self, minsize):

81 while True:

82 if not self.drop_nodes([node for (node, count) in \

83 self.nodes.count_all().items() if count < minsize]):

84 break

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

87 """

88 returns list of cliques

89 clique is frozenset

90 if timeout=-1, it means infinity

91 if timeout has happened, raises TimeoutError

93 lava flow

94 """

95 print 'Bron and Kerbosh algorithm started'

96 cliques = []

98 depth = 0

99 list_candidates = [copy(self.nodes)]

100 list_used = [set()]

101 compsub = []

102

103 start_time = datetime.now()

104

105 while True: # ????????...

106 if depth == -1:

107 break # ??????! ?????? ???????????????? (????????????????) ????????????????

108 candidates = copy(list_candidates[depth])

109 used = copy(list_used[depth])

110 if not candidates: # ???????? candidates ???? ??????????

111 depth -= 1

112 if compsub:

113 compsub.pop()

114 continue

115

116 # ?? used ???? ???????????????? ??????????????, ?????????????????????? ???? ?????????? ?????????????????? ???? candidates

117 # (?????? ???? used ???? ?????????????????? ???????? ???? ?? 1 ???? candidates)

118 used_candidates = False

119

120 for used1 in used:

121 for candidates1 in candidates:

122 if not self.bounded(used1, candidates1):

123 break

124 else:

125 used_candidates = True

126

127 if used_candidates:

128 depth -= 1

129

130 if compsub:

131 compsub.pop()

132 continue

133

134 # ???????????????? ?????????????? v ???? candidates ?? ?????????????????? ???? ?? compsub

135 v = candidates.pop()

136 candidates.add(v)

137 compsub.append(v)

138 # ?????????????????? new_candidates ?? new_used, ???????????? ???? candidates ?? used ??????????????, ???? ?????????????????????? ?? v

139 # (???? ????????, ???????????????? ???????????? ?????????????????????? ?? v)

140 new_candidates = set()

141 for candidates1 in candidates:

142 if self.bounded(candidates1, v) and candidates1 != v:

143 new_candidates.add(candidates1)

144

145 new_used = set()

146 for used1 in used:

147 if self.bounded(used1, v) and used1 != v:

148 new_used.add(used1)

149

150 # ?????????????? v ???? candidates ?? ???????????????? ?? used

151 list_candidates[depth].remove(v)

152 list_used[depth].add(v)

153 # ???????? new_candidates ?? new_used ??????????

154 if not new_candidates and not new_used:

155 # compsub ??? ??????????

156 if len(compsub) >= minsize:

157 cliques.append(frozenset(compsub))

158 else:

159 # ?????????? ???????????????????? ???????????????? bron_kerbosh(new_candidates, new_used)

160 depth += 1

161

162 # TIMEOUT check start

163 if timeout != -1:

164 if datetime.now() - start_time > timeout:

165 raise TimeoutError

166 # TIMEOUT check end

167

168 if depth >= len(list_candidates):

169 list_candidates.append(set())

170 list_used.append(set())

171

172 list_candidates[depth] = copy(new_candidates)

173 list_used[depth] = copy(new_used)

174

175 continue

176

177 # ?????????????? v ???? compsub

178 if compsub:

179 compsub.pop()

180

181 return cliques

182

183

184 def fast_cliques(self, minsize=1):

185 """

186 returns list of cliques

187 clique is frozenset

188 """

189 print 'Fast algorithm started'

190 cliques = []

191

192 while True:

193 graph = Graph(self.nodes, self.lines)

194 for clique in cliques:

195 graph.drop_nodes(clique)

196 if not graph.nodes or len(cliques) == 2:

197 break

198

199 while True:

200 # drop nodes, while its is possible

201 c = graph.count_all()

202 min_count = min(c.values())

203 bad_nodes = [node for (node, count) in c.items() if count == min_count]

204 if len(bad_nodes) == len(graph.nodes):

205 break

206

207 costs = dict([(node, graph.cost_one(node)) for node in bad_nodes])

208 min_cost = min(costs.values())

209 for node, cost in costs.items():

210 if cost == min_cost:

211 graph.drop_node(node)

212

213 while True:

214 # add nodes, while its is possible

215 candidats = {}

216 for node in self.nodes:

217 c = len([i for i in graph.nodes if self.bounded(node, i)])

218 if c == len(self.nodes):

219 graph1 = Graph(graph.nodes, graph.lines)

220 graph1.add_node(node, self)

221 candidats[node] = graph1.cost_one(node)

222 if not candidats:

223 break

224

225 max_cost = max(candidats.values())

226 node = [node for (node, cost) in candidats.items() if cost == max_cost][0]

227 graph.add_node(node, self)

228

229 cliques.append(frozenset(graph.nodes))

230

231 return cliques

232

233

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

235 """

236 returns length-sorted list of cliques

237 clique is frozenset

238

239 can change self!

240

241 try to execute bron_kerbosh

242 if it raises TimeoutError, executes fast_cliques

243 """

244

245 self.drop_if_count(minsize)

246

247 try:

248 cliques = self.bron_kerbosh(timeout, minsize)

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

250 except TimeoutError:

251 cliques = self.fast_cliques(minsize)

252 return cliques

253

254 if __name__ == "__main__":

255 import doctest

256 doctest.testmod()