1.1 --- a/lib/graph.py	Sat Oct 23 21:07:26 2010 +0400
     1.2 +++ b/lib/graph.py	Sat Oct 23 21:32:52 2010 +0400
     1.3 @@ -20,14 +20,21 @@
     1.4      >>> g.fast_cliques()
     1.5      Fast algorithm started
     1.6      [frozenset([1, 2]), frozenset([3])]
     1.7 +    >>> g = Graph(set([1,2,3]), {frozenset([1,2]): 1, frozenset([1,1]): 1})
     1.8 +    >>> g.fast_cliques()
     1.9 +    Fast algorithm started
    1.10 +    [frozenset([1, 2]), frozenset([3])]
    1.11      >>> g = Graph(set([1,2,3,4]), {frozenset([1,2]): 0.98, frozenset([1,3]): 0.98,
    1.12 -    ... frozenset([2,3]): 0.1})
    1.13 +    ... frozenset([2,3]): 0.1, frozenset([1,1]): 1})
    1.14      >>> g.fast_cliques()
    1.15      Fast algorithm started
    1.16      [frozenset([1, 2, 3]), frozenset([4])]
    1.17      >>> g.bron_kerbosh()
    1.18      Bron and Kerbosh algorithm started
    1.19      [frozenset([1, 2, 3]), frozenset([4])]
    1.20 +    >>> g.cliques()
    1.21 +    Bron and Kerbosh algorithm started
    1.22 +    [frozenset([1, 2, 3])]
    1.23      """
    1.24      
    1.25      def __init__(self, nodes=None, lines=None):
    1.26 @@ -36,8 +43,11 @@
    1.27          if not lines:
    1.28              lines = dict()
    1.29          self.nodes = copy(nodes)
    1.30 -        self.lines = copy(lines)
    1.31 -    
    1.32 +        self.lines = {}
    1.33 +        for line, cost in lines.items():
    1.34 +            if len(line) == 2 and line.issubset(self.nodes):
    1.35 +                self.lines[line] = cost
    1.36 +        
    1.37      @staticmethod
    1.38      def line(k1, k2):
    1.39          return frozenset([k1, k2])
    1.40 @@ -104,7 +114,7 @@
    1.41          """
    1.42          while True:
    1.43              if not self.drop_nodes([node for (node, count) in \
    1.44 -            self.nodes.count_all().items() if count < minsize]):
    1.45 +            self.count_all().items() if count < minsize]):
    1.46                  break
    1.47       
    1.48      def bron_kerbosh(self, timeout=-1, minsize=1):
    1.49 @@ -217,15 +227,17 @@
    1.50              graph = Graph(self.nodes, self.lines)
    1.51              for clique in cliques:
    1.52                  graph.drop_nodes(clique)
    1.53 -            if not graph.nodes or len(cliques) == 2:
    1.54 +            if not graph.nodes:
    1.55                  break
    1.56              
    1.57              while True: 
    1.58                  # drop nodes, while its is possible
    1.59 +                if len(graph.nodes) == 1:
    1.60 +                    break
    1.61                  c = graph.count_all()
    1.62                  min_count = min(c.values())
    1.63                  bad_nodes = [node for (node, count) in c.items() if count == min_count]
    1.64 -                if len(bad_nodes) == len(graph.nodes):
    1.65 +                if len(bad_nodes) == len(graph.nodes) and min_count != 0:
    1.66                      break
    1.67                  
    1.68                  costs = dict([(node, graph.cost_one(node)) for node in bad_nodes])
    1.69 @@ -233,6 +245,7 @@
    1.70                  for node, cost in costs.items():
    1.71                      if cost == min_cost:
    1.72                          graph.drop_node(node)
    1.73 +                        break
    1.74              
    1.75              while True:
    1.76                  # add nodes, while its is possible