1.1 --- a/pair_cores/patch_structure.py	Sun Mar 25 21:41:26 2012 +0400
     1.2 +++ b/pair_cores/patch_structure.py	Sun Mar 25 21:51:52 2012 +0400
     1.3 @@ -10,7 +10,7 @@
     1.4  from Bio.PDB import Select
     1.5  from Bio.PDB import Superimposer, CaPPBuilder, PDBIO
     1.6  
     1.7 -from allpy.graph import Graph
     1.8 +from allpy.graph import *
     1.9  from allpy.homology import MonomerHomology
    1.10  from allpy.structure import *
    1.11  from allpy import base, processors, config, structure
    1.12 @@ -503,6 +503,93 @@
    1.13      g.close()
    1.14      return next_class_id - 1
    1.15  
    1.16 +def fast_cliques(self, minsize=1):
    1.17 +    """ returns list of cliques
    1.18 +
    1.19 +    clique is frozenset
    1.20 +    """
    1.21 +    cliques = []
    1.22 +    while True:
    1.23 +        graph = self.copy()
    1.24 +        for clique in cliques:
    1.25 +            for v in clique:
    1.26 +                if v in graph:
    1.27 +                    graph.drop_vertex(v)
    1.28 +        if not graph:
    1.29 +            break
    1.30 +        graph.drop_bad_vertices()
    1.31 +        graph.expand_to_max_clique(self)
    1.32 +        clique = copy(frozenset(graph))
    1.33 +        if len(clique) >= minsize:
    1.34 +            cliques.append(clique)
    1.35 +        else:
    1.36 +            break
    1.37 +    return cliques
    1.38 +
    1.39 +def bron_kerbosh(self, timeout=-1, minsize=1):
    1.40 +    """ Bron and Kerboch algorithm implementation
    1.41 +
    1.42 +    returns list of cliques
    1.43 +    clique is frozenset
    1.44 +    if timeout=-1, it means infinity
    1.45 +    if timeout has happened, raises TimeoutError
    1.46 +    """
    1.47 +    if timeout == 0:
    1.48 +        raise TimeoutError()
    1.49 +    cliques = []
    1.50 +
    1.51 +    class ExtendCall(object):
    1.52 +        def __init__(call, candidates, used, compsub):
    1.53 +            call.candidates = candidates
    1.54 +            call.used = used
    1.55 +            call.compsub = compsub
    1.56 +
    1.57 +        def get_v_from_candidates(call):
    1.58 +            """ return some v from candidates """
    1.59 +            return iter(call.candidates).next()
    1.60 +
    1.61 +        def used_candidates(call):
    1.62 +            """ if v from used connected with all from candidates """
    1.63 +            for u in call.used:
    1.64 +                for c in call.candidates:
    1.65 +                    if not self.get(u,{}).get(c,None):
    1.66 +                        break
    1.67 +                else:
    1.68 +                    return True
    1.69 +            return False
    1.70 +
    1.71 +        def __call__(call):
    1.72 +            """ process call and return list of recursive calls """
    1.73 +            while call.candidates and not call.used_candidates():
    1.74 +                v = call.get_v_from_candidates()
    1.75 +                call.compsub.add(v)
    1.76 +                new_candidates = set([i for i in call.candidates
    1.77 +                    if i is not v and self.get(i,{}).get(v,None)])
    1.78 +                new_used = set([i for i in call.used
    1.79 +                    if i is not v and self.get(i,{}).get(v,None)])
    1.80 +                if (not new_candidates) and (not new_used):
    1.81 +                    if len(call.compsub) >= minsize:
    1.82 +                        cliques.append(copy(frozenset(call.compsub)))
    1.83 +                else:
    1.84 +                    yield ExtendCall(new_candidates,
    1.85 +                        new_used, copy(call.compsub))
    1.86 +                call.compsub.remove(v)
    1.87 +                call.candidates.remove(v)
    1.88 +                call.used.add(v)
    1.89 +
    1.90 +    stop_time = datetime.now() + timedelta(0, timeout)
    1.91 +    stack = [ExtendCall(copy(set(self)), set(), set())()]
    1.92 +    while stack:
    1.93 +        if timeout != -1 and datetime.now() > stop_time:
    1.94 +            raise TimeoutError()
    1.95 +        top = stack[-1]
    1.96 +        try:
    1.97 +            call = top.next()
    1.98 +            stack.append(call())
    1.99 +        except StopIteration:
   1.100 +            stack.pop()
   1.101 +    return cliques
   1.102 +
   1.103  structure.pdb_id_parse = pdb_id_parse
   1.104  structure.DownloadPdb = DownloadPdb
   1.105  structure.download_pdb = download_pdb
   1.106 @@ -516,4 +603,6 @@
   1.107  structure.BlockMixin.pair_core_parts = pair_core_parts
   1.108  structure.BlockMixin.blocks3d = blocks3d
   1.109  MonomerHomology.case_homology = staticmethod(case_homology)
   1.110 +Graph.fast_cliques = fast_cliques
   1.111 +Graph.bron_kerbosh = bron_kerbosh
   1.112