ruby-changes:31263
From: akr <ko1@a...>
Date: Fri, 18 Oct 2013 00:59:49 +0900 (JST)
Subject: [ruby-changes:31263] akr:r43342 (trunk): * lib/tsort.rb (TSort.tsort): Extracted from TSort#tsort.
akr 2013-10-18 00:59:40 +0900 (Fri, 18 Oct 2013) New Revision: 43342 http://svn.ruby-lang.org/cgi-bin/viewvc.cgi?view=rev&revision=43342 Log: * lib/tsort.rb (TSort.tsort): Extracted from TSort#tsort. (TSort.tsort_each): Extracted from TSort#tsort_each. (TSort.strongly_connected_components): Extracted from TSort#strongly_connected_components. (TSort.each_strongly_connected_component): Extracted from TSort#each_strongly_connected_component. Modified files: trunk/ChangeLog trunk/NEWS trunk/lib/tsort.rb trunk/test/test_tsort.rb Index: ChangeLog =================================================================== --- ChangeLog (revision 43341) +++ ChangeLog (revision 43342) @@ -1,3 +1,12 @@ https://github.com/ruby/ruby/blob/trunk/ChangeLog#L1 +Fri Oct 18 00:57:07 2013 Tanaka Akira <akr@f...> + + * lib/tsort.rb (TSort.tsort): Extracted from TSort#tsort. + (TSort.tsort_each): Extracted from TSort#tsort_each. + (TSort.strongly_connected_components): Extracted from + TSort#strongly_connected_components. + (TSort.each_strongly_connected_component): Extracted from + TSort#each_strongly_connected_component. + Thu Oct 17 18:50:08 2013 Koichi Sasada <ko1@a...> * gc.c (CALC_EXACT_MALLOC_SIZE_CHECK_OLD_SIZE): introduced. Index: lib/tsort.rb =================================================================== --- lib/tsort.rb (revision 43341) +++ lib/tsort.rb (revision 43342) @@ -145,8 +145,34 @@ module TSort https://github.com/ruby/ruby/blob/trunk/lib/tsort.rb#L145 # p graph.tsort # raises TSort::Cyclic # def tsort + each_node = method(:tsort_each_node) + each_child = method(:tsort_each_child) + TSort.tsort(each_node, each_child) + end + + # Returns a topologically sorted array of nodes. + # The array is sorted from children to parents, i.e. + # the first element has no child and the last node has no parent. + # + # The graph is represented by _each_node_ and _each_child_. + # _each_node_ should have +call+ method which yields for each node in the graph. + # _each_child_ should have +call+ method which takes a node argument and yields for each child node. + # + # If there is a cycle, TSort::Cyclic is raised. + # + # g = {1=>[2, 3], 2=>[4], 3=>[2, 4], 4=>[]} + # each_node = lambda {|&b| g.each_key(&b) } + # each_child = lambda {|n, &b| g[n].each(&b) } + # p TSort.tsort(each_node, each_child) #=> [4, 2, 3, 1] + # + # g = {1=>[2], 2=>[3, 4], 3=>[2], 4=>[]} + # each_node = lambda {|&b| g.each_key(&b) } + # each_child = lambda {|n, &b| g[n].each(&b) } + # p TSort.tsort(each_node, each_child) # raises TSort::Cyclic + # + def TSort.tsort(each_node, each_child) result = [] - tsort_each {|element| result << element} + TSort.tsort_each(each_node, each_child) {|element| result << element} result end @@ -173,8 +199,29 @@ module TSort https://github.com/ruby/ruby/blob/trunk/lib/tsort.rb#L199 # # 3 # # 1 # - def tsort_each # :yields: node - each_strongly_connected_component {|component| + def tsort_each(&block) # :yields: node + each_node = method(:tsort_each_node) + each_child = method(:tsort_each_child) + TSort.tsort_each(each_node, each_child, &block) + end + + # The iterator version of the TSort.tsort method. + # + # The graph is represented by _each_node_ and _each_child_. + # _each_node_ should have +call+ method which yields for each node in the graph. + # _each_child_ should have +call+ method which takes a node argument and yields for each child node. + # + # g = {1=>[2, 3], 2=>[4], 3=>[2, 4], 4=>[]} + # each_node = lambda {|&b| g.each_key(&b) } + # each_child = lambda {|n, &b| g[n].each(&b) } + # TSort.tsort_each(each_node, each_child) {|n| p n } + # #=> 4 + # # 2 + # # 3 + # # 1 + # + def TSort.tsort_each(each_node, each_child) # :yields: node + TSort.each_strongly_connected_component(each_node, each_child) {|component| if component.size == 1 yield component.first else @@ -203,8 +250,34 @@ module TSort https://github.com/ruby/ruby/blob/trunk/lib/tsort.rb#L250 # p graph.strongly_connected_components #=> [[4], [2, 3], [1]] # def strongly_connected_components + each_node = method(:tsort_each_node) + each_child = method(:tsort_each_child) + TSort.strongly_connected_components(each_node, each_child) + end + + # Returns strongly connected components as an array of arrays of nodes. + # The array is sorted from children to parents. + # Each elements of the array represents a strongly connected component. + # + # The graph is represented by _each_node_ and _each_child_. + # _each_node_ should have +call+ method which yields for each node in the graph. + # _each_child_ should have +call+ method which takes a node argument and yields for each child node. + # + # g = {1=>[2, 3], 2=>[4], 3=>[2, 4], 4=>[]} + # each_node = lambda {|&b| g.each_key(&b) } + # each_child = lambda {|n, &b| g[n].each(&b) } + # p TSort.strongly_connected_components(each_node, each_child) + # #=> [[4], [2], [3], [1]] + # + # g = {1=>[2], 2=>[3, 4], 3=>[2], 4=>[]} + # each_node = lambda {|&b| g.each_key(&b) } + # each_child = lambda {|n, &b| g[n].each(&b) } + # p TSort.strongly_connected_components(each_node, each_child) + # #=> [[4], [2, 3], [1]] + # + def TSort.strongly_connected_components(each_node, each_child) result = [] - each_strongly_connected_component {|component| result << component} + TSort.each_strongly_connected_component(each_node, each_child) {|component| result << component} result end @@ -237,12 +310,41 @@ module TSort https://github.com/ruby/ruby/blob/trunk/lib/tsort.rb#L310 # # [2, 3] # # [1] # - def each_strongly_connected_component # :yields: nodes + def each_strongly_connected_component(&block) # :yields: nodes + each_node = method(:tsort_each_node) + each_child = method(:tsort_each_child) + TSort.each_strongly_connected_component(each_node, each_child, &block) + end + + # The iterator version of the TSort.strongly_connected_components method. + # + # The graph is represented by _each_node_ and _each_child_. + # _each_node_ should have +call+ method which yields for each node in the graph. + # _each_child_ should have +call+ method which takes a node argument and yields for each child node. + # + # g = {1=>[2, 3], 2=>[4], 3=>[2, 4], 4=>[]} + # each_node = lambda {|&b| g.each_key(&b) } + # each_child = lambda {|n, &b| g[n].each(&b) } + # TSort.each_strongly_connected_component(each_node, each_child) {|scc| p scc } + # #=> [4] + # # [2] + # # [3] + # # [1] + # + # g = {1=>[2], 2=>[3, 4], 3=>[2], 4=>[]} + # each_node = lambda {|&b| g.each_key(&b) } + # each_child = lambda {|n, &b| g[n].each(&b) } + # TSort.each_strongly_connected_component(each_node, each_child) {|scc| p scc } + # #=> [4] + # # [2, 3] + # # [1] + # + def TSort.each_strongly_connected_component(each_node, each_child) # :yields: nodes id_map = {} stack = [] - tsort_each_node {|node| + each_node.call {|node| unless id_map.include? node - each_strongly_connected_component_from(node, id_map, stack) {|c| + TSort.each_strongly_connected_component_from(node, each_child, id_map, stack) {|c| yield c } end @@ -285,7 +387,7 @@ module TSort https://github.com/ruby/ruby/blob/trunk/lib/tsort.rb#L387 # # _node_ is the first node. # _each_child_ should have +call+ method which takes a node argument - # and yields for each adjacent node. + # and yields for each child node. # # Return value is unspecified. # Index: NEWS =================================================================== --- NEWS (revision 43341) +++ NEWS (revision 43342) @@ -246,6 +246,10 @@ with all sufficient information, see the https://github.com/ruby/ruby/blob/trunk/NEWS#L246 * TSort * New methods: + * TSort.tsort + * TSort.tsort_each + * TSort.strongly_connected_components + * TSort.each_strongly_connected_component * TSort.each_strongly_connected_component_from * WEBrick Index: test/test_tsort.rb =================================================================== --- test/test_tsort.rb (revision 43341) +++ test/test_tsort.rb (revision 43342) @@ -41,7 +41,53 @@ class TSortTest < Test::Unit::TestCase # https://github.com/ruby/ruby/blob/trunk/test/test_tsort.rb#L41 a.strongly_connected_components.map {|nodes| nodes.sort}) end - def test_noclass + def test_s_tsort + g = {1=>[2, 3], 2=>[4], 3=>[2, 4], 4=>[]} + each_node = lambda {|&b| g.each_key(&b) } + each_child = lambda {|n, &b| g[n].each(&b) } + assert_equal([4, 2, 3, 1], TSort.tsort(each_node, each_child)) + g = {1=>[2], 2=>[3, 4], 3=>[2], 4=>[]} + assert_raise(TSort::Cyclic) { TSort.tsort(each_node, each_child) } + end + + def test_s_tsort_each + g = {1=>[2, 3], 2=>[4], 3=>[2, 4], 4=>[]} + each_node = lambda {|&b| g.each_key(&b) } + each_child = lambda {|n, &b| g[n].each(&b) } + r = [] + TSort.tsort_each(each_node, each_child) {|n| r << n } + assert_equal([4, 2, 3, 1], r) + end + + def test_s_strongly_connected_components + g = {1=>[2, 3], 2=>[4], 3=>[2, 4], 4=>[]} + each_node = lambda {|&b| g.each_key(&b) } + each_child = lambda {|n, &b| g[n].each(&b) } + assert_equal([[4], [2], [3], [1]], + TSort.strongly_connected_components(each_node, each_child)) + g = {1=>[2], 2=>[3, 4], 3=>[2], 4=>[]} + assert_equal([[4], [2, 3], [1]], + TSort.strongly_connected_components(each_node, each_child)) + end + + def test_s_each_strongly_connected_component + g = {1=>[2, 3], 2=>[4], 3=>[2, 4], 4=>[]} + each_node = lambda {|&b| g.each_key(&b) } + each_child = lambda {|n, &b| g[n].each(&b) } + r = [] + TSort.each_strongly_connected_component(each_node, each_child) {|scc| + r << scc + } + assert_equal([[4], [2], [3], [1]], r) + g = {1=>[2], 2=>[3, 4], 3=>[2], 4=>[]} + r = [] + TSort.each_strongly_connected_component(each_node, each_child) {|scc| + r << scc + } + assert_equal([[4], [2, 3], [1]], r) + end + + def test_s_each_strongly_connected_component_from g = {1=>[2], 2=>[3, 4], 3=>[2], 4=>[]} each_child = lambda {|n, &b| g[n].each(&b) } r = [] -- ML: ruby-changes@q... Info: http://www.atdot.net/~ko1/quickml/