allpy: 9ad22a1848fc blocks3d/Kliki.py

Документ взят из кэша поисковой машины. Адрес оригинального документа : http://kodomo.fbb.msu.ru/hg/allpy/file/9ad22a1848fc/blocks3d/Kliki.py
Дата изменения: Unknown
Дата индексирования: Sun Mar 2 06:56:04 2014
Кодировка:

allpy: 9ad22a1848fc blocks3d/Kliki.py

allpy

view blocks3d/Kliki.py @ 310:9ad22a1848fc

Added calls to super to all classes in allpy.base The calls are not exactly correct. This WILL fail in certain inheritance situations. There are two bad situations: * inheritance from object; __init__ of object does not accept any arguments, so it is not compatible with interface of any of our classes * inheritance of Block(Alignment). The situation here is relatively easy to fix: we should force compatibility of function interfaces for Block and Alignment.

author	Daniil Alexeyevsky <me.dendik@gmail.com>
date	Thu, 16 Dec 2010 21:08:03 +0300
parents	3161cdaf2ff9
children

line source

1 # -*- coding: cp1251 -*-

3 #########################################################################

4 # ???????? ?????-???????: ????? ????????????? ????????/?????????

5 #########################################################################

11 ?????????? ????? ? ??????? ?????????? ????? ????????? ? ???

13 Usage:

15 from Kliki import Kliki

16 l = Kliki(graf)

17 l.kliki # ??? ????? ?????

21 import time

22 from clon import clon

26 class Kliki:

30 """

31 graf[???????1][???????2] = 1 - ???? ?????, 0 - ??? ?????

33 kliki - ?????? ????, ????? - ?????? ??????? ?????????, ???????? ? ?????? ???????

35 compsub - ?????? ??????? ??? ??????? ????

36 """

45 def __init__ (self, graf, cost = None, limit_count=0, min_size=0, timeout=10):

47 """

48 ??????? ??????? ??????

50 graf - ??????? ????????.

51 ???? graf[1][2] == 1, ?? 1 ???????? ? 2

52 ???? graf[1][2] == 0, ?? 1 ?? ???????? ? 2

54 graf[N][N] = 1 ??? ???? N

56 cost - ??????? ?????????? graf (??????????????)

57 ?????? ???? ?????? ????? ??????????.

58 ??? ?????? ????, ??? ???? ??????? ??? ?????

59 ???????????? ??? fast_algorithm ? ??? ?????????? ????

62 limit_count - ???????????? ????? ????, ??????? ?????

63 ???? ?????? 0, ?? ??????????? ??? ?????

65 min_size - min size of returning klika

67 timeout - time in sec. for BRON-KERBOSH algorithm

69 """

73 self.graf = graf

74 self.cost = cost

77 self.kliki = []

79 self.timeout = timeout

83 connections = {} # index - atom, value - count of connections

85 for atom in self.graf.keys():

86 connections[atom] = self.graf[atom].values().count(1)

92 # delete atoms which have not enough number of connections

93 deleted = 1

95 while deleted:

97 deleted = 0

99 for atom, c in connections.items():

101 if c < min_size:

103 del connections[atom]

105 for atom1, connect in graf[atom].items():

106 if connect == 1 and connections.has_key(atom1):

107 connections[atom1] -= 1

108 deleted = 1

114 bank_l = {}

116 for atom, c in connections.items():

118 if not bank_l.has_key(c):

119 bank_l[c] = []

121 bank_l[c].append(atom)

124 keys = []

126 if len(bank_l.keys()):

127 for c in xrange(min(bank_l.keys()), max(bank_l.keys())+1):

128 if bank_l.has_key(c):

129 keys.extend(bank_l[c])

134 # RUN BRON-KERBOSH

136 if self.timeout != 0:

138 self.bron_kerbosh(keys[:])

140 if len(self.kliki) == 0:

141 self.fast_algorithm(keys[:]) # run fast algorithm

147 # ?????????? ?????????? ????? ?? ???????? ????? ????????? ? ???

153 ## max_l=0 # ???????????? ??????

154 ## min_l=len(self.kliki[0]) # ??????????? ??????

156 bank_l = {}

158 for klika in self.kliki:

159 klika.sort()

160 l = len(klika) # ????? ??????? ?????

162 if l >= min_size:

163 ## max_l = max(max_l,len(klika))

164 ## min_l = min(min_l,len(klika))

166 if not bank_l.has_key(l):

167 bank_l[l] = []

169 bank_l[l].append(klika)

173 kliki=[]

175 #print self.cost

177 if len(bank_l.keys()):

179 r = range(min(bank_l.keys()), max(bank_l.keys())+1)

180 r.reverse()

182 for l in r:

183 if (bank_l.has_key(l)):

185 k = bank_l[l] # ??? ????? ????? l

188 if self.cost:

190 ## print l

192 # ??????????? ?? ?? ???????? ????? ???? cost

196 costs = []

198 for klika in k:

200 c = 0

202 for i in klika:

204 if not self.cost.has_key(i):

205 continue

207 for j in klika:

209 if j == i:

210 break

213 if not self.cost[i].has_key(j):

214 continue

216 c += self.cost[i][j]

218 costs.append(c)

220 costs1 = costs[:]

222 costs1.sort(reverse=1)

224 k1 = []

226 for c in costs1:

228 n = costs.index(c)

230 k1.append(k[n][:])

232 del k[n]

233 del costs[n]

235 k = k1

237 kliki.extend(k)

239 ## kliki.reverse()

241 if limit_count:

242 if len(kliki) > limit_count: # ??????? ??????????? ?? ????? ????

243 kliki = kliki[:limit_count]

246 self.kliki = kliki[:]

257 def bron_kerbosh (self, keys):

259 """

260 ???????? ?????-??????? ?????? ????????????? ??????? ????????

261 http://ru.wikipedia.org/wiki/????????_?????_?_???????

263 compsub - ?????? ?????? ????

264 candidates - ?????? ??????????????? ?????????? ? ????

265 used - ?????? ????????????? ?????????? ? ????

266 """

268 depth = 0 # ??????? "????????"

269 list_candidates = [keys] # ?????? ???????? candidates ???? "????????"

270 list_used = [[]] #?????? ???????? used ???? "????????"

272 compsub = [] # ?????? compsub

275 print 'Bron and Kerbosh algorithm started'

277 start_time = time.time()

279 # ????...

280 while 1:

282 if depth == -1:

283 break # ???! ??? ???????? (????????) ????????

289 # ???????? candidates ? used ?? ??????

291 #print depth

293 candidates = list_candidates[depth][:]

294 used = list_used[depth][:]

299 # ???? candidates ?? ?????

300 if len(candidates)==0:

301 depth -= 1

303 if compsub:

304 compsub.pop()

305 continue

312 # ? used ?? ???????? ???????, ??????????? ?? ????? ????????? ?? candidates

313 # (??? ?? used ?? ????????? ???? ?? ? 1 ?? candidates)

315 used_candidates = 0

317 for used1 in used:

318 for candidates1 in candidates:

319 if self.graf[used1][candidates1] == 0:

320 break

321 else:

322 used_candidates = 1

324 if used_candidates:

325 depth -= 1

327 if compsub:

328 compsub.pop()

329 continue

337 # ???????? ??????? v ?? candidates ? ????????? ?? ? compsub

338 v = candidates[0]

339 compsub.append(v)

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

346 # (?? ????, ???????? ?????? ??????????? ? v)

347 new_candidates = []

348 for candidates1 in candidates:

349 if self.graf[candidates1][v] == 1 and candidates1 != v:

350 new_candidates.append(candidates1)

353 new_used = []

354 for used1 in used:

355 if self.graf[used1][v] == 1 and used1 != v:

356 new_used.append(used1)

361 # ??????? v ?? candidates ? ???????? ? used

362 del list_candidates[depth][0]

363 list_used[depth].append(v)

366 # ???? new_candidates ? new_used ?????

367 if len(new_candidates) == 0 and len(new_used) == 0:

368 # compsub ? ?????

369 self.kliki.append(compsub[:])

371 else:

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

374 depth += 1

377 # TIMEOUT check start

378 if self.timeout != -1:

380 if time.time() - start_time > self.timeout:

382 self.kliki = []

383 return

384 # TIMEOUT check end

389 if depth >= len(list_candidates):

390 list_candidates.append([])

391 list_used.append([])

394 list_candidates[depth] = new_candidates[:]

395 list_used[depth] = new_used[:]

397 continue

400 # ??????? v ?? compsub

401 if compsub:

402 compsub.pop()

413 def fast_algorithm (self, keys):

415 """

416 Fast algorithm

417 """

420 self.kliki = []

422 print 'Fast algorithm started'

426 while 1:

427 # try find new klika

430 # exclude previous klika atoms

431 excluded = {}

433 for klika in self.kliki:

435 for i in klika:

437 excluded[i] = 1

439 keys1 = []

441 for i in keys:

443 if not excluded.has_key(i):

444 keys1.append(i)

446 if len(keys1) == 0:

447 break

449 while 1:

451 # exclude some atoms

454 connections = {} # index - atom, value - connections value

456 for i in keys1:

458 connections[i] = 0

460 for j in keys1:

462 if i != j and self.graf[i][j]:

463 connections[i] += 1

466 if max(connections.values()) == min(connections.values()):

467 # all atoms are equal

468 break

471 exclude_connect = min(connections.values()) # excluded atoms connections

474 if self.cost:

477 cost_sum = {} # index - atom, value - cost sum

479 for i in keys1:

481 cost_sum[i] = 0

483 if connections[i] == exclude_connect:

485 for j in keys1:

487 if i != j and self.graf[i][j]:

489 cost_sum[i] += self.cost[i][j]

491 exclude_cost = min(cost_sum.values()) # excluded atoms cost sum

495 keys2 = []

497 for i in keys1:

499 if connections[i] == exclude_connect:

501 if cost_sum[i] == exclude_cost:

503 continue

505 keys2.append(i)

507 keys1 = clon(keys2)

509 else:

511 keys2 = []

513 for i in keys1:

515 if connections[i] == exclude_connect:

517 continue

519 keys2.append(i)

521 keys1 = clon(keys2)

525 # try add other atoms

528 while 1:

531 for i in keys:

533 if i in keys1:

534 continue

537 for j in keys1:

540 if not self.graf[i][j]:

541 break

543 else:

544 # add atom i

545 keys1.append(i)

548 break

551 else:

552 # no new atoms

553 break

557 # keys1 is klika

559 self.kliki.append(keys1[:])