allpy: 578bc81d5e62 blocks3d/Kliki.py

allpy

view blocks3d/Kliki.py @ 303:578bc81d5e62

Added explanation for algorithm to add gapped line to base Alignment

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

line source

1 # -*- coding: cp1251 -*-

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

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

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

10 """

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

13 Usage:

15 from Kliki import Kliki

16 l = Kliki(graf)

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

18 """

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

100

101 if c < min_size:

102

103 del connections[atom]

104

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

117

118 if not bank_l.has_key(c):

119 bank_l[c] = []

120

121 bank_l[c].append(atom)

122

123

124 keys = []

125

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

135

136 if self.timeout != 0:

137

138 self.bron_kerbosh(keys[:])

139

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]) # ??????????? ??????

155

156 bank_l = {}

157

158 for klika in self.kliki:

159 klika.sort()

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

161

162 if l >= min_size:

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

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

165

166 if not bank_l.has_key(l):

167 bank_l[l] = []

168

169 bank_l[l].append(klika)

173 kliki=[]

175 #print self.cost

177 if len(bank_l.keys()):

178

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

180 r.reverse()

181

182 for l in r:

183 if (bank_l.has_key(l)):

184

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

206

207 for j in klika:

208

209 if j == i:

210 break

211

212

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

214 continue

215

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

217

218 costs.append(c)

219

220 costs1 = costs[:]

221

222 costs1.sort(reverse=1)

223

224 k1 = []

225

226 for c in costs1:

227

228 n = costs.index(c)

229

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

231

232 del k[n]

233 del costs[n]

234

235 k = k1

236

237 kliki.extend(k)

238

239 ## kliki.reverse()

240

241 if limit_count:

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

243 kliki = kliki[:limit_count]

244

245

246 self.kliki = kliki[:]

257 def bron_kerbosh (self, keys):

258

259 """

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

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

262

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

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

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

266 """

267

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

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

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

271

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

273

274

275 print 'Bron and Kerbosh algorithm started'

276

277 start_time = time.time()

278

279 # ????...

280 while 1:

281

282 if depth == -1:

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

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

290

291 #print depth

292

293 candidates = list_candidates[depth][:]

294 used = list_used[depth][:]

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

300 if len(candidates)==0:

301 depth -= 1

302

303 if compsub:

304 compsub.pop()

305 continue

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

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

314

315 used_candidates = 0

316

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

323

324 if used_candidates:

325 depth -= 1

326

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)

351

352

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)

364

365

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

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

368 # compsub ? ?????

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

370

371 else:

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

373

374 depth += 1

375

376

377 # TIMEOUT check start

378 if self.timeout != -1:

379

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

381

382 self.kliki = []

383 return

384 # TIMEOUT check end

389 if depth >= len(list_candidates):

390 list_candidates.append([])

391 list_used.append([])

392

393

394 list_candidates[depth] = new_candidates[:]

395 list_used[depth] = new_used[:]

396

397 continue

398

399

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

401 if compsub:

402 compsub.pop()

413 def fast_algorithm (self, keys):

414

415 """

416 Fast algorithm

417 """

418

419

420 self.kliki = []

421

422 print 'Fast algorithm started'

423

424

425

426 while 1:

427 # try find new klika

428

429

430 # exclude previous klika atoms

431 excluded = {}

432

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)

445

446 if len(keys1) == 0:

447 break

448

449 while 1:

450

451 # exclude some atoms

452

453

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

455

456 for i in keys1:

457

458 connections[i] = 0

459

460 for j in keys1:

461

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

463 connections[i] += 1

464

465

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

467 # all atoms are equal

468 break

469

470

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

474 if self.cost:

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

478

479 for i in keys1:

480

481 cost_sum[i] = 0

482

483 if connections[i] == exclude_connect:

484

485 for j in keys1:

486

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

488

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

490

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

495 keys2 = []

497 for i in keys1:

499 if connections[i] == exclude_connect:

500

501 if cost_sum[i] == exclude_cost:

502

503 continue

504

505 keys2.append(i)

506

507 keys1 = clon(keys2)

509 else:

511 keys2 = []

513 for i in keys1:

515 if connections[i] == exclude_connect:

516

517 continue

518

519 keys2.append(i)

520

521 keys1 = clon(keys2)

522

523

524

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

542

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[:])

560