1.1 --- a/allpy/graph.py	Thu Feb 24 11:26:47 2011 +0300
     1.2 +++ b/allpy/graph.py	Thu Feb 24 17:37:28 2011 +0300
     1.3 @@ -65,15 +65,14 @@
     1.4          """ if these two vertices of the graph are bounded with edge """
     1.5          return k1 is k2 or Graph.edge(k1, k2) in self.edges
     1.6  
     1.7 -    def count_one(self, vertex):
     1.8 -        """ Returns number of connections of this vertex """
     1.9 -        return len([vertex1 for vertex1 in self.vertices
    1.10 -            if self.bounded(vertex, vertex1)]) - 1
    1.11 -
    1.12 -    def weight_one(self, vertex):
    1.13 +    def weight_all(self):
    1.14          """ Returns sum of weights of all connections of this vertex """
    1.15 -        return sum([self.edges.get(Graph.edge(vertex, vertex1), 0)
    1.16 -        for vertex1 in self.vertices if vertex is not vertex1])
    1.17 +        w = dict([(vertex, 0) for vertex in self.vertices])
    1.18 +        for edge, weight in self.edges.items():
    1.19 +            if edge.issubset(self.vertices):
    1.20 +                for vertex in edge:
    1.21 +                    w[vertex] += weight
    1.22 +        return w
    1.23  
    1.24      def count_all(self):
    1.25          """ Returns {vertex: number of connections of this vertex} """
    1.26 @@ -131,13 +130,15 @@
    1.27                  g = Graph(call.candidates, self.edges)
    1.28                  c = g.count_all()
    1.29                  max_count = max(c.values())
    1.30 -                best_vertices = [vertex for (vertex, count) in c.items()
    1.31 -                    if count == max_count]
    1.32 +                best_vertices = set([vertex for (vertex, count) in c.items()
    1.33 +                    if count == max_count])
    1.34                  if len(best_vertices) == 1:
    1.35 -                    return best_vertices[0]
    1.36 -                weights = dict([(g.weight_one(v), v) for v in best_vertices])
    1.37 -                max_weight = max(weights.keys())
    1.38 -                return weights[max_weight]
    1.39 +                    return best_vertices.pop()
    1.40 +                weights = g.weight_all()
    1.41 +                _rev = dict([(v,k) for (k,v) in weights.items()
    1.42 +                    if k in best_vertex])
    1.43 +                max_weight = max(_rev.keys())
    1.44 +                return _rev[max_weight]
    1.45  
    1.46              def get_v_from_candidates(call):
    1.47                  """ return some v from candidates """
    1.48 @@ -191,39 +192,40 @@
    1.49          """ drop vertices untill self becomes a clique """
    1.50          while True:
    1.51              # drop vertices, while its is possible
    1.52 -            if len(self.vertices) == 1:
    1.53 +            if len(self.vertices) <= 1:
    1.54                  break
    1.55              c = self.count_all()
    1.56              min_count = min(c.values())
    1.57              bad_vertices = [vertex for (vertex, count) in c.items()
    1.58                  if count == min_count]
    1.59 +            if min_count == 0:
    1.60 +                self.drop_vertices(bad_vertices)
    1.61 +                continue
    1.62              if len(bad_vertices) == len(self.vertices) and min_count != 0:
    1.63                  break
    1.64 -            weights = dict([(vertex, self.weight_one(vertex)) for vertex
    1.65 -                in bad_vertices])
    1.66 -            min_weight = min(weights.values())
    1.67 -            for vertex, weight in weights.items():
    1.68 -                if weight == min_weight:
    1.69 -                    self.drop_vertex(vertex)
    1.70 -                    break
    1.71 +            weights = self.weight_all()
    1.72 +            _rev = dict([(v,k) for (k,v) in weights.items()
    1.73 +                if k in bad_vertices])
    1.74 +            min_weight = min(_rev.keys())
    1.75 +            self.drop_vertex(_rev[min_weight])
    1.76  
    1.77      def expand_to_max_clique(self, parent_graph):
    1.78          """ add vertices untill self becomes a nonextendible clique """
    1.79          while True:
    1.80              # add vertices, while its is possible
    1.81 -            candidats = {}
    1.82 +            candidats = set()
    1.83              for vertex in parent_graph.vertices:
    1.84                  c = len([i for i in self.vertices
    1.85                      if parent_graph.bounded(vertex, i)])
    1.86                  if c == len(parent_graph.vertices):
    1.87 -                    g = Graph(self.vertices, copy(self.edges))
    1.88 -                    g.add_vertex(vertex, parent_graph)
    1.89 -                    candidats[vertex] = g.weight_one(vertex)
    1.90 +                    candidats.add(vertex)
    1.91              if not candidats:
    1.92                  break
    1.93 -            max_weight = max(candidats.values())
    1.94 -            vertex = [vertex for (vertex, weight) in candidats.items()
    1.95 -                if weight == max_weight][0]
    1.96 +            weights = parent_graph.weight_all()
    1.97 +            _rev = dict([(v,k) for (k,v) in weights.items()
    1.98 +                if k in candidats])
    1.99 +            max_weight = max(_rev.keys())
   1.100 +            vertex = _rev[max_weight]
   1.101              self.add_vertex(vertex, parent_graph)
   1.102  
   1.103      def fast_cliques(self, minsize=1):