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