akr	2013-10-17 12:32:15 +0900 (Thu, 17 Oct 2013)

  New Revision: 43326

  http://svn.ruby-lang.org/cgi-bin/viewvc.cgi?view=rev&revision=43326

  Log:
    * lib/tsort.rb (TSort.each_strongly_connected_component_from):
      Extracted from TSort#each_strongly_connected_component_from.

  Modified files:
    trunk/ChangeLog
    trunk/NEWS
    trunk/lib/tsort.rb
    trunk/test/test_tsort.rb
Index: ChangeLog
===================================================================
--- ChangeLog	(revision 43325)
+++ ChangeLog	(revision 43326)
@@ -1,3 +1,8 @@ https://github.com/ruby/ruby/blob/trunk/ChangeLog#L1
+Thu Oct 17 12:30:16 2013  Tanaka Akira  <akr@f...>
+
+	* lib/tsort.rb (TSort.each_strongly_connected_component_from):
+	  Extracted from TSort#each_strongly_connected_component_from.
+
 Thu Oct 17 11:07:06 2013  Eric Hodel  <drbrain@s...>
 
 	* lib/rubygems:  Update to RubyGems master 941c21a.  Changes:
Index: lib/tsort.rb
===================================================================
--- lib/tsort.rb	(revision 43325)
+++ lib/tsort.rb	(revision 43326)
@@ -195,18 +195,40 @@ module TSort https://github.com/ruby/ruby/blob/trunk/lib/tsort.rb#L195
   #
   # #each_strongly_connected_component_from doesn't call #tsort_each_node.
   #
-  def each_strongly_connected_component_from(node, id_map={}, stack=[]) # :yields: nodes
+  def each_strongly_connected_component_from(node, id_map={}, stack=[], &block) # :yields: nodes
+    TSort.each_strongly_connected_component_from(node, method(:tsort_each_child), id_map, stack, &block)
+  end
+
+  # Iterates over strongly connected components in a graph.
+  # The graph is represented by _node_ and _each_child_.
+  #
+  # _node_ is the first node.
+  # _each_child_ should have +call+ method which takes a node argument
+  # and yields for each adjacent node.
+  #
+  # Return value is unspecified.
+  #
+  # #TSort.each_strongly_connected_component_from is a class method and
+  # it doesn't need a class to represent a graph which includes TSort.
+  #
+  #   graph = {1=>[2], 2=>[3, 4], 3=>[2], 4=>[]}
+  #   each_child = lambda {|n, &b| graph[n].each(&b) }
+  #   TSort.each_strongly_connected_component_from(1, each_child) {|scc|
+  #     p scc #=> [4], [2, 3], [1]
+  #   }
+  #
+  def TSort.each_strongly_connected_component_from(node, each_child, id_map={}, stack=[]) # :yields: nodes
     minimum_id = node_id = id_map[node] = id_map.size
     stack_length = stack.length
     stack << node
 
-    tsort_each_child(node) {|child|
+    each_child.call(node) {|child|
       if id_map.include? child
         child_id = id_map[child]
         minimum_id = child_id if child_id && child_id < minimum_id
       else
         sub_minimum_id =
-          each_strongly_connected_component_from(child, id_map, stack) {|c|
+          TSort.each_strongly_connected_component_from(child, each_child, id_map, stack) {|c|
             yield c
           }
         minimum_id = sub_minimum_id if sub_minimum_id < minimum_id
Index: NEWS
===================================================================
--- NEWS	(revision 43325)
+++ NEWS	(revision 43326)
@@ -244,6 +244,10 @@ with all sufficient information, see the https://github.com/ruby/ruby/blob/trunk/NEWS#L244
     inside the block, by default, unless the exception class is given
     explicitly.
 
+* TSort
+  * New methods:
+    * TSort.each_strongly_connected_component_from
+
 * WEBrick
   * The body of a response may now be a StringIO or other IO-like that responds
     to #readpartial and #read.
Index: test/test_tsort.rb
===================================================================
--- test/test_tsort.rb	(revision 43325)
+++ test/test_tsort.rb	(revision 43326)
@@ -40,5 +40,15 @@ class TSortTest < Test::Unit::TestCase # https://github.com/ruby/ruby/blob/trunk/test/test_tsort.rb#L40
     assert_equal([[0], [1]],
       a.strongly_connected_components.map {|nodes| nodes.sort})
   end
+
+  def test_noclass
+    g = {1=>[2], 2=>[3, 4], 3=>[2], 4=>[]}
+    each_child = lambda {|n, &b| g[n].each(&b) }
+    r = []
+    TSort.each_strongly_connected_component_from(1, each_child) {|scc|
+      r << scc
+    }
+    assert_equal([[4], [2, 3], [1]], r)
+  end
 end
 

--
ML: ruby-changes@q...
Info: http://www.atdot.net/~ko1/quickml/