Документ взят из кэша поисковой машины. Адрес оригинального документа : http://kodomo.fbb.msu.ru/hg/allpy/rev/223df1ee4c21
Дата изменения: Unknown
Дата индексирования: Mon Oct 1 23:30:37 2012
Кодировка:
allpy: 223df1ee4c21

allpy

changeset 398:223df1ee4c21

graph: reimplement bron_kerbosh with yields
author boris <bnagaev@gmail.com>
date Thu, 03 Feb 2011 14:49:33 +0300
parents 2ac62edd1c3e
children 66b7d7db070e
files allpy/graph.py
diffstat 1 files changed, 8 insertions(+), 11 deletions(-) [+]
line diff
     1.1 --- a/allpy/graph.py	Thu Feb 03 13:56:57 2011 +0300
     1.2 +++ b/allpy/graph.py	Thu Feb 03 14:49:33 2011 +0300
     1.3 @@ -143,7 +143,6 @@
     1.4  
     1.5              def __call__(call):
     1.6                  """ process call and return list of recursive calls """
     1.7 -                children = []
     1.8                  while call.candidates and not call.used_candidates():
     1.9                      v = call.get_v_from_candidates()
    1.10                      call.compsub.add(v)
    1.11 @@ -155,26 +154,24 @@
    1.12                          if len(call.compsub) >= minsize:
    1.13                              cliques.append(copy(frozenset(call.compsub)))
    1.14                      else:
    1.15 -                        children.append(ExtendCall(new_candidates,
    1.16 -                            new_used, copy(call.compsub)))
    1.17 +                        yield ExtendCall(new_candidates,
    1.18 +                            new_used, copy(call.compsub))
    1.19                      call.compsub.remove(v)
    1.20                      call.candidates.remove(v)
    1.21                      call.used.add(v)
    1.22 -                return children
    1.23  
    1.24          stop_time = datetime.now() + timedelta(0, timeout)
    1.25 -        stack = [[ExtendCall(copy(set(self.vertices)), set(), set())]]
    1.26 +        stack = [ExtendCall(copy(set(self.vertices)), set(), set())()]
    1.27          while stack:
    1.28              if timeout != -1 and datetime.now() > stop_time:
    1.29                  raise TimeoutError()
    1.30              top = stack[-1]
    1.31 -            if top:
    1.32 -                call = top.pop()
    1.33 -                children = call()
    1.34 -                if children:
    1.35 -                    stack.append(children)
    1.36 -            else:
    1.37 +            try:
    1.38 +                call = top.next()
    1.39 +                stack.append(call())
    1.40 +            except StopIteration:
    1.41                  stack.pop()
    1.42 +
    1.43          cliques.sort(key=lambda clique: len(clique), reverse=True)
    1.44          return cliques
    1.45