lib/rgl/connected_components.rb in rgl-0.4.0 vs lib/rgl/connected_components.rb in rgl-0.5.0

@@ -9,106 +9,112 @@
 module RGL
 
   module Graph
 
     # Compute the connected components of an undirected graph, using a
-    # DFS (Depth-first search)-based approach.  A _connected component_ of
+    # DFS (Depth-first search)-based approach. A _connected component_ of
     # an undirected graph is a set of vertices that are all reachable
     # from each other.
     #
     # The function is implemented as an iterator which calls the client
     # with an array of vertices for each component.
     #
     # It raises an exception if the graph is directed.
-
+    #
     def each_connected_component
       raise NotUndirectedError,
-        "each_connected_component only works " +
-        "for undirected graphs." if directed?
+            "each_connected_component only works " +
+                "for undirected graphs." if directed?
+
       comp = []
       vis  = DFSVisitor.new(self)
       vis.set_finish_vertex_event_handler { |v| comp << v }
-      vis.set_start_vertex_event_handler { |v|
+
+      vis.set_start_vertex_event_handler do |v|
         yield comp unless comp.empty?
         comp = []
-      }
+      end
+
       depth_first_search(vis) { |v| }
       yield comp unless comp.empty?
     end
 
     # This GraphVisitor is used by strongly_connected_components to compute
     # the strongly connected components of a directed graph.
-
+    #
     class TarjanSccVisitor < DFSVisitor
 
       attr_reader :comp_map
 
       # Creates a new TarjanSccVisitor for graph _g_, which should be directed.
-
-      def initialize (g)
+      #
+      def initialize(g)
         super g
         @root_map           = {}
         @comp_map           = {}
         @discover_time_map  = {}
         @dfs_time           = 0
         @c_index            = 0
         @stack              = []
       end
 
-      def handle_examine_vertex (v)
-        @root_map[v] =  v
-        @comp_map[v] =  -1
-        @dfs_time    += 1
+      def handle_examine_vertex(v)
+        @root_map[v] = v
+        @comp_map[v] = -1
+        @dfs_time += 1
         @discover_time_map[v] = @dfs_time
         @stack.push(v)
       end
 
-      def handle_finish_vertex (v)
+      def handle_finish_vertex(v)
         # Search adjacent vertex w with earliest discover time
         root_v = @root_map[v]
+
         graph.each_adjacent(v) do |w|
           if @comp_map[w] == -1
             root_v = min_discover_time(root_v, @root_map[w])
           end
         end
+
         @root_map[v] = root_v
-        if root_v == v                  # v is topmost vertex of a SCC
-          begin                         # pop off all vertices until v
+
+        if root_v == v # v is topmost vertex of a SCC
+          begin # pop off all vertices until v
             w = @stack.pop
             @comp_map[w] = @c_index
           end until w == v
           @c_index += 1
         end
       end
 
       # Return the number of components found so far.
-
+      #
       def num_comp
         @c_index
       end
 
       private
 
-      def min_discover_time (u, v)
+      def min_discover_time(u, v)
         @discover_time_map[u] < @discover_time_map[v] ? u : v
       end
 
-    end		# class TarjanSccVisitor
+    end # class TarjanSccVisitor
 
     # This is Tarjan's algorithm for strongly connected components, from his
-    # paper "Depth first search and linear graph algorithms".  It calculates
-    # the components in a single application of DFS.  We implement the
+    # paper "Depth first search and linear graph algorithms". It calculates
+    # the components in a single application of DFS. We implement the
     # algorithm with the help of the DFSVisitor TarjanSccVisitor.
     #
     # === Definition
-    # 
+    #
     # A _strongly connected component_ of a directed graph G=(V,E) is a
     # maximal set of vertices U which is in V, such that for every pair of
-    # vertices u and  v in U, we have both a path from u to v and a path
+    # vertices u and v in U, we have both a path from u to v and a path
     # from v to u. That is to say, u and v are reachable from each other.
-    # 
-    # @Article{Tarjan:1972:DFS,
+    #
+    # @Article!{Tarjan:1972:DFS,
     #   author =       "R. E. Tarjan",
     #   key =          "Tarjan",
     #   title =        "Depth First Search and Linear Graph Algorithms",
     #   journal =      "SIAM Journal on Computing",
     #   volume =       "1",
@@ -119,20 +125,22 @@
     #   CODEN =        "SMJCAT",
     #   ISSN =         "0097-5397 (print), 1095-7111 (electronic)",
     #   bibdate =      "Thu Jan 23 09:56:44 1997",
     #   bibsource =    "Parallel/Multi.bib, Misc/Reverse.eng.bib",
     # }
-    # 
+    #
     # The output of the algorithm is recorded in a TarjanSccVisitor _vis_.
     # vis.comp_map will contain numbers giving the component ID assigned to
     # each vertex. The number of components is vis.num_comp.
-
+    #
     def strongly_connected_components
       raise NotDirectedError,
-        "strong_components only works for directed graphs." unless directed?
+            "strong_components only works for directed graphs." unless directed?
+
       vis = TarjanSccVisitor.new(self)
       depth_first_search(vis) { |v| }
       vis
     end
 
-  end                           # module Graph
-end                             # module RGL
+  end # module Graph
+
+end # module RGL