Документ взят из кэша поисковой машины. Адрес оригинального документа : http://kodomo.fbb.msu.ru/hg/allpy/raw-rev/223df1ee4c21 Дата изменения: Unknown Дата индексирования: Tue Oct 2 07:09:46 2012 Кодировка:

# HG changeset patch
# User boris
# Date 1296733773 -10800
# Node ID 223df1ee4c21dc5a1b88da878a48a164263c2c83
# Parent 2ac62edd1c3e5822d4d92cc80b0deb3d50cc43a8
graph: reimplement bron_kerbosh with yields

diff -r 2ac62edd1c3e -r 223df1ee4c21 allpy/graph.py
--- a/allpy/graph.py Thu Feb 03 13:56:57 2011 +0300
+++ b/allpy/graph.py Thu Feb 03 14:49:33 2011 +0300
@@ -143,7 +143,6 @@

def __call__(call):
""" process call and return list of recursive calls """
- children = []
while call.candidates and not call.used_candidates():
v = call.get_v_from_candidates()
call.compsub.add(v)
@@ -155,26 +154,24 @@
if len(call.compsub) >= minsize:
cliques.append(copy(frozenset(call.compsub)))
else:
- children.append(ExtendCall(new_candidates,
- new_used, copy(call.compsub)))
+ yield ExtendCall(new_candidates,
+ new_used, copy(call.compsub))
call.compsub.remove(v)
call.candidates.remove(v)
call.used.add(v)
- return children

stop_time = datetime.now() + timedelta(0, timeout)
- stack = [[ExtendCall(copy(set(self.vertices)), set(), set())]]
+ stack = [ExtendCall(copy(set(self.vertices)), set(), set())()]
while stack:
if timeout != -1 and datetime.now() > stop_time:
raise TimeoutError()
top = stack[-1]
- if top:
- call = top.pop()
- children = call()
- if children:
- stack.append(children)
- else:
+ try:
+ call = top.next()
+ stack.append(call())
+ except StopIteration:
stack.pop()
+
cliques.sort(key=lambda clique: len(clique), reverse=True)
return cliques