1.1 --- a/lib/graph.py	Sun Oct 24 22:25:36 2010 +0400
     1.2 +++ b/lib/graph.py	Sun Oct 24 23:12:15 2010 +0400
     1.3 @@ -9,7 +9,8 @@
     1.4  
     1.5  
     1.6  class Graph(object):
     1.7 -    """
     1.8 +    """ Undirected weighted graph
     1.9 +    
    1.10      Data:
    1.11      nodes -- set of elements
    1.12      lines -- {line: cost}. 
    1.13 @@ -56,22 +57,16 @@
    1.14          return k1 == k2 or Graph.line(k1, k2) in self.lines
    1.15      
    1.16      def count_one(self, node):
    1.17 -        """
    1.18 -        Returns number of connections of this node
    1.19 -        """
    1.20 +        """ Returns number of connections of this node """
    1.21          return len([node1 for node1 in self.nodes if self.bounded(node, node1)]) - 1
    1.22      
    1.23      def cost_one(self, node):
    1.24 -        """
    1.25 -        Returns sum of costs of all connections of this node
    1.26 -        """
    1.27 +        """ Returns sum of costs of all connections of this node """
    1.28          return sum([self.lines.get(Graph.line(node, node1), 0) 
    1.29          for node1 in self.nodes if node != node1])
    1.30      
    1.31      def count_all(self):
    1.32 -        """
    1.33 -        Returns {node: number of connections of this node}
    1.34 -        """
    1.35 +        """ Returns {node: number of connections of this node} """
    1.36          c = dict([(node, 0) for node in self.nodes])
    1.37          for line in self.lines:
    1.38              for node in line:
    1.39 @@ -80,16 +75,14 @@
    1.40      
    1.41      
    1.42      def drop_node(self, node):
    1.43 -        """
    1.44 -        Remove node and all involved lines
    1.45 -        """
    1.46 +        """ Remove node and all involved lines """
    1.47          for node1 in self.nodes:
    1.48              self.lines.pop(Graph.line(node, node1), None)
    1.49          self.nodes.discard(node)
    1.50      
    1.51      def add_node(self, node, parent_graph):
    1.52 -        """
    1.53 -        Add node and corresponding lines from parent_graph
    1.54 +        """ Add node and corresponding lines from parent_graph
    1.55 +        
    1.56          Added lines should be contained in self graph
    1.57          (takes care of hanging lines)
    1.58          """
    1.59 @@ -100,8 +93,7 @@
    1.60                  self.lines[line] = parent_graph.lines[line]
    1.61      
    1.62      def drop_nodes(self, nodes):
    1.63 -        """
    1.64 -        Run drop_node for each of given nodes
    1.65 +        """ Run drop_node for each of given nodes
    1.66          Returns if nodes was not empty (ugly beauty)
    1.67          """
    1.68          for node in nodes:
    1.69 @@ -109,16 +101,15 @@
    1.70          return bool(nodes)
    1.71      
    1.72      def drop_if_count(self, minsize):
    1.73 -        """
    1.74 -        Run drop_node for each node, that has less than minsize lines
    1.75 -        """
    1.76 +        """ Run drop_node for each node, that has less than minsize lines """
    1.77          while True:
    1.78              if not self.drop_nodes([node for (node, count) 
    1.79              in self.count_all().items() if count < minsize]):
    1.80                  break
    1.81       
    1.82      def bron_kerbosh(self, timeout=-1, minsize=1):
    1.83 -        """
    1.84 +        """ Bron and Kerboch algorithm implementation
    1.85 +        
    1.86          returns list of cliques
    1.87          clique is frozenset
    1.88          if timeout=-1, it means infinity
    1.89 @@ -217,8 +208,8 @@
    1.90  
    1.91      
    1.92      def fast_cliques(self, minsize=1):
    1.93 -        """
    1.94 -        returns list of cliques
    1.95 +        """ returns list of cliques
    1.96 +        
    1.97          clique is frozenset
    1.98          """
    1.99          print 'Fast algorithm started'
   1.100 @@ -270,8 +261,8 @@
   1.101          
   1.102      
   1.103      def cliques(self, timeout=-1, minsize=1):
   1.104 -        """
   1.105 -        returns length-sorted list of cliques
   1.106 +        """ returns length-sorted list of cliques
   1.107 +        
   1.108          clique is frozenset
   1.109          
   1.110          can change self!