1.1 --- a/blocks3d/Kliki.py	Wed Dec 15 02:22:38 2010 +0300
     1.2 +++ b/blocks3d/Kliki.py	Wed Dec 15 18:30:19 2010 +0300
     1.3 @@ -34,14 +34,14 @@
     1.4  
     1.5      compsub - полный подграф для данного шага
     1.6      """
     1.7 -            
     1.8  
     1.9 -        
    1.10  
    1.11  
    1.12  
    1.13  
    1.14 -    
    1.15 +
    1.16 +
    1.17 +
    1.18      def __init__ (self, graf, cost = None, limit_count=0, min_size=0, timeout=10):
    1.19  
    1.20          """
    1.21 @@ -57,7 +57,7 @@
    1.22              хранит цены связей между элементами.
    1.23              чем больше цена, тем выше ценится эта связь
    1.24              используется для fast_algorithm и для сортировки клик
    1.25 -            
    1.26 +
    1.27  
    1.28          limit_count - максимальное число клик, которые хотят
    1.29              Если задать 0, то возвратятся все клики
    1.30 @@ -65,15 +65,15 @@
    1.31          min_size - min size of returning klika
    1.32  
    1.33          timeout - time in sec. for BRON-KERBOSH algorithm
    1.34 -            
    1.35 +
    1.36          """
    1.37  
    1.38 -        
    1.39 +
    1.40  
    1.41          self.graf = graf
    1.42          self.cost = cost
    1.43  
    1.44 -        
    1.45 +
    1.46          self.kliki = []
    1.47  
    1.48          self.timeout = timeout
    1.49 @@ -95,40 +95,40 @@
    1.50          while deleted:
    1.51  
    1.52              deleted = 0
    1.53 -            
    1.54 +
    1.55              for atom, c in connections.items():
    1.56 -                
    1.57 +
    1.58                  if c < min_size:
    1.59 -                    
    1.60 +
    1.61                      del connections[atom]
    1.62 -                    
    1.63 +
    1.64                      for atom1, connect in graf[atom].items():
    1.65                          if connect == 1 and connections.has_key(atom1):
    1.66                              connections[atom1] -= 1
    1.67                              deleted = 1
    1.68  
    1.69 -                
    1.70 -                        
    1.71 -        
    1.72 +
    1.73 +
    1.74 +
    1.75  
    1.76          bank_l = {}
    1.77 -        
    1.78 +
    1.79          for atom, c in connections.items():
    1.80 -            
    1.81 +
    1.82              if not bank_l.has_key(c):
    1.83                  bank_l[c] = []
    1.84 -                
    1.85 +
    1.86              bank_l[c].append(atom)
    1.87  
    1.88  
    1.89 -        keys = []            
    1.90 -        
    1.91 +        keys = []
    1.92 +
    1.93          if len(bank_l.keys()):
    1.94              for c in xrange(min(bank_l.keys()), max(bank_l.keys())+1):
    1.95                  if bank_l.has_key(c):
    1.96                      keys.extend(bank_l[c])
    1.97 -            
    1.98 -            
    1.99 +
   1.100 +
   1.101  
   1.102  
   1.103          # RUN BRON-KERBOSH
   1.104 @@ -141,7 +141,7 @@
   1.105              self.fast_algorithm(keys[:]) # run fast algorithm
   1.106  
   1.107  
   1.108 -        
   1.109 +
   1.110  
   1.111  
   1.112          # упорядочим полученные клики по убыванию числа элементов в них
   1.113 @@ -154,7 +154,7 @@
   1.114  ##        min_l=len(self.kliki[0]) # минимальный размер
   1.115  
   1.116          bank_l = {}
   1.117 -        
   1.118 +
   1.119          for klika in self.kliki:
   1.120              klika.sort()
   1.121              l = len(klika) # длина текущей клики
   1.122 @@ -173,12 +173,12 @@
   1.123          kliki=[]
   1.124  
   1.125          #print self.cost
   1.126 -        
   1.127 +
   1.128          if len(bank_l.keys()):
   1.129 -            
   1.130 +
   1.131              r = range(min(bank_l.keys()), max(bank_l.keys())+1)
   1.132              r.reverse()
   1.133 -            
   1.134 +
   1.135              for l in r:
   1.136                  if (bank_l.has_key(l)):
   1.137  
   1.138 @@ -191,7 +191,7 @@
   1.139  
   1.140                          # отсортируем их по убыванию общей цены cost
   1.141  
   1.142 -                       
   1.143 +
   1.144  
   1.145                          costs = []
   1.146  
   1.147 @@ -200,7 +200,7 @@
   1.148                              c = 0
   1.149  
   1.150                              for i in klika:
   1.151 -                                
   1.152 +
   1.153                                  if not self.cost.has_key(i):
   1.154                                      continue
   1.155  
   1.156 @@ -209,7 +209,7 @@
   1.157                                      if j == i:
   1.158                                          break
   1.159  
   1.160 -                                    
   1.161 +
   1.162                                      if not self.cost[i].has_key(j):
   1.163                                          continue
   1.164  
   1.165 @@ -233,15 +233,15 @@
   1.166                              del costs[n]
   1.167  
   1.168                          k = k1
   1.169 -                    
   1.170 +
   1.171                      kliki.extend(k)
   1.172 -                
   1.173 +
   1.174  ##        kliki.reverse()
   1.175  
   1.176          if limit_count:
   1.177              if len(kliki) > limit_count: # наложим ограничение на число клик
   1.178                  kliki = kliki[:limit_count]
   1.179 -            
   1.180 +
   1.181  
   1.182          self.kliki = kliki[:]
   1.183  
   1.184 @@ -249,10 +249,10 @@
   1.185  
   1.186  
   1.187  
   1.188 -        
   1.189 -            
   1.190  
   1.191 -    
   1.192 +
   1.193 +
   1.194 +
   1.195  
   1.196      def bron_kerbosh (self, keys):
   1.197  
   1.198 @@ -273,9 +273,9 @@
   1.199  
   1.200  
   1.201          print 'Bron and Kerbosh algorithm started'
   1.202 -        
   1.203 +
   1.204          start_time = time.time()
   1.205 -    
   1.206 +
   1.207          # ПОКА...
   1.208          while 1:
   1.209  
   1.210 @@ -284,14 +284,14 @@
   1.211  
   1.212  
   1.213  
   1.214 -            
   1.215 +
   1.216  
   1.217              # создадим candidates и used из списка
   1.218  
   1.219              #print depth
   1.220 -            
   1.221 +
   1.222              candidates = list_candidates[depth][:]
   1.223 -            used = list_used[depth][:]          
   1.224 +            used = list_used[depth][:]
   1.225  
   1.226  
   1.227  
   1.228 @@ -301,25 +301,25 @@
   1.229                  depth -= 1
   1.230  
   1.231                  if compsub:
   1.232 -                    compsub.pop()                
   1.233 +                    compsub.pop()
   1.234                  continue
   1.235  
   1.236 -                       
   1.237  
   1.238  
   1.239 -            
   1.240 -            
   1.241 +
   1.242 +
   1.243 +
   1.244              # И used НЕ содержит вершины, СОЕДИНЕННОЙ СО ВСЕМИ вершинами из candidates
   1.245              # (все из used НЕ соединены хотя бы с 1 из candidates)
   1.246  
   1.247              used_candidates = 0
   1.248 -        
   1.249 +
   1.250              for used1 in used:
   1.251                  for candidates1 in candidates:
   1.252                      if self.graf[used1][candidates1] == 0:
   1.253                          break
   1.254                  else:
   1.255 -                    used_candidates = 1             
   1.256 +                    used_candidates = 1
   1.257  
   1.258              if used_candidates:
   1.259                  depth -= 1
   1.260 @@ -327,8 +327,8 @@
   1.261                  if compsub:
   1.262                      compsub.pop()
   1.263                  continue
   1.264 -                
   1.265 -       
   1.266 +
   1.267 +
   1.268  
   1.269  
   1.270  
   1.271 @@ -341,7 +341,7 @@
   1.272  
   1.273  
   1.274  
   1.275 -            
   1.276 +
   1.277              # Формируем new_candidates и new_used, удаляя из candidates и used вершины, НЕ соединенные с v
   1.278              # (то есть, оставляя только соединенные с v)
   1.279              new_candidates = []
   1.280 @@ -349,7 +349,7 @@
   1.281                  if self.graf[candidates1][v] == 1 and candidates1 != v:
   1.282                      new_candidates.append(candidates1)
   1.283  
   1.284 -                                                            
   1.285 +
   1.286              new_used = []
   1.287              for used1 in used:
   1.288                  if self.graf[used1][v] == 1 and used1 != v:
   1.289 @@ -358,7 +358,7 @@
   1.290  
   1.291  
   1.292  
   1.293 -            # Удаляем v из candidates и помещаем в used                   
   1.294 +            # Удаляем v из candidates и помещаем в used
   1.295              del list_candidates[depth][0]
   1.296              list_used[depth].append(v)
   1.297  
   1.298 @@ -367,33 +367,33 @@
   1.299              if len(new_candidates) == 0 and len(new_used) == 0:
   1.300                  # compsub - клика
   1.301                  self.kliki.append(compsub[:])
   1.302 -                
   1.303 +
   1.304              else:
   1.305                  # ИНАЧЕ рекурсивно вызываем bron_kerbosh(new_candidates, new_used)
   1.306  
   1.307                  depth += 1
   1.308 -                
   1.309 +
   1.310  
   1.311                  # TIMEOUT check start
   1.312                  if self.timeout != -1:
   1.313 -                    
   1.314 +
   1.315                      if time.time() - start_time > self.timeout:
   1.316  
   1.317                          self.kliki = []
   1.318                          return
   1.319                  # TIMEOUT check end
   1.320  
   1.321 -                    
   1.322 -                    
   1.323 -                
   1.324 +
   1.325 +
   1.326 +
   1.327                  if depth >= len(list_candidates):
   1.328                      list_candidates.append([])
   1.329                      list_used.append([])
   1.330  
   1.331 -                
   1.332 +
   1.333                  list_candidates[depth] = new_candidates[:]
   1.334                  list_used[depth] = new_used[:]
   1.335 -                
   1.336 +
   1.337                  continue
   1.338  
   1.339  
   1.340 @@ -442,7 +442,7 @@
   1.341  
   1.342                  if not excluded.has_key(i):
   1.343                      keys1.append(i)
   1.344 -                
   1.345 +
   1.346              if len(keys1) == 0:
   1.347                  break
   1.348  
   1.349 @@ -454,9 +454,9 @@
   1.350                  connections = {} # index - atom, value -  connections value
   1.351  
   1.352                  for i in keys1:
   1.353 -                    
   1.354 +
   1.355                      connections[i] = 0
   1.356 -                    
   1.357 +
   1.358                      for j in keys1:
   1.359  
   1.360                          if i != j and self.graf[i][j]:
   1.361 @@ -466,8 +466,8 @@
   1.362                  if max(connections.values()) == min(connections.values()):
   1.363                      # all atoms are equal
   1.364                      break
   1.365 -                
   1.366 -                                                    
   1.367 +
   1.368 +
   1.369                  exclude_connect = min(connections.values()) # excluded atoms connections
   1.370  
   1.371  
   1.372 @@ -479,7 +479,7 @@
   1.373                      for i in keys1:
   1.374  
   1.375                          cost_sum[i] = 0
   1.376 -                        
   1.377 +
   1.378                          if connections[i] == exclude_connect:
   1.379  
   1.380                              for j in keys1:
   1.381 @@ -495,13 +495,13 @@
   1.382                      keys2 = []
   1.383  
   1.384                      for i in keys1:
   1.385 -                        
   1.386 +
   1.387                          if connections[i] == exclude_connect:
   1.388  
   1.389                              if cost_sum[i] == exclude_cost:
   1.390  
   1.391                                  continue
   1.392 -                        
   1.393 +
   1.394                          keys2.append(i)
   1.395  
   1.396                      keys1 = clon(keys2)
   1.397 @@ -511,11 +511,11 @@
   1.398                      keys2 = []
   1.399  
   1.400                      for i in keys1:
   1.401 -                        
   1.402 +
   1.403                          if connections[i] == exclude_connect:
   1.404  
   1.405                              continue
   1.406 -                        
   1.407 +
   1.408                          keys2.append(i)
   1.409  
   1.410                      keys1 = clon(keys2)
   1.411 @@ -546,22 +546,22 @@
   1.412  
   1.413  
   1.414                          break
   1.415 -                        
   1.416 -                    
   1.417 +
   1.418 +
   1.419                  else:
   1.420                      # no new atoms
   1.421                      break
   1.422 -                    
   1.423 -            
   1.424 +
   1.425 +
   1.426  
   1.427              # keys1 is klika
   1.428  
   1.429              self.kliki.append(keys1[:])
   1.430  
   1.431 -            
   1.432  
   1.433 -            
   1.434 -                
   1.435 -                
   1.436  
   1.437 -        
   1.438 +
   1.439 +
   1.440 +
   1.441 +
   1.442 +