ruby-changes:31261
From: akr <ko1@a...>
Date: Thu, 17 Oct 2013 21:55:31 +0900 (JST)
Subject: [ruby-changes:31261] akr:r43340 (trunk): [DOC]
akr 2013-10-17 21:55:27 +0900 (Thu, 17 Oct 2013) New Revision: 43340 http://svn.ruby-lang.org/cgi-bin/viewvc.cgi?view=rev&revision=43340 Log: [DOC] Modified files: trunk/lib/tsort.rb Index: lib/tsort.rb =================================================================== --- lib/tsort.rb (revision 43339) +++ lib/tsort.rb (revision 43340) @@ -123,20 +123,33 @@ module TSort https://github.com/ruby/ruby/blob/trunk/lib/tsort.rb#L123 class Cyclic < StandardError 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. # # If there is a cycle, TSort::Cyclic is raised. # + # class G + # include TSort + # def initialize(g) + # @g = g + # end + # def tsort_each_child(n, &b) @g[n].each(&b) end + # def tsort_each_node(&b) @g.each_key(&b) end + # end + # + # graph = G.new({1=>[2, 3], 2=>[4], 3=>[2, 4], 4=>[]}) + # p graph.tsort #=> [4, 2, 3, 1] + # + # graph = G.new({1=>[2], 2=>[3, 4], 3=>[2], 4=>[]}) + # p graph.tsort # raises TSort::Cyclic + # def tsort result = [] tsort_each {|element| result << element} result end - # # The iterator version of the #tsort method. # <tt><em>obj</em>.tsort_each</tt> is similar to <tt><em>obj</em>.tsort.each</tt>, but # modification of _obj_ during the iteration may lead to unexpected results. @@ -144,6 +157,22 @@ module TSort https://github.com/ruby/ruby/blob/trunk/lib/tsort.rb#L157 # #tsort_each returns +nil+. # If there is a cycle, TSort::Cyclic is raised. # + # class G + # include TSort + # def initialize(g) + # @g = g + # end + # def tsort_each_child(n, &b) @g[n].each(&b) end + # def tsort_each_node(&b) @g.each_key(&b) end + # end + # + # graph = G.new({1=>[2, 3], 2=>[4], 3=>[2, 4], 4=>[]}) + # graph.tsort_each {|n| p n } + # #=> 4 + # # 2 + # # 3 + # # 1 + # def tsort_each # :yields: node each_strongly_connected_component {|component| if component.size == 1 @@ -154,26 +183,60 @@ module TSort https://github.com/ruby/ruby/blob/trunk/lib/tsort.rb#L183 } 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. # + # class G + # include TSort + # def initialize(g) + # @g = g + # end + # def tsort_each_child(n, &b) @g[n].each(&b) end + # def tsort_each_node(&b) @g.each_key(&b) end + # end + # + # graph = G.new({1=>[2, 3], 2=>[4], 3=>[2, 4], 4=>[]}) + # p graph.strongly_connected_components #=> [[4], [2], [3], [1]] + # + # graph = G.new({1=>[2], 2=>[3, 4], 3=>[2], 4=>[]}) + # p graph.strongly_connected_components #=> [[4], [2, 3], [1]] + # def strongly_connected_components result = [] each_strongly_connected_component {|component| result << component} result end - # # The iterator version of the #strongly_connected_components method. # <tt><em>obj</em>.each_strongly_connected_component</tt> is similar to # <tt><em>obj</em>.strongly_connected_components.each</tt>, but # modification of _obj_ during the iteration may lead to unexpected results. # - # # #each_strongly_connected_component returns +nil+. # + # class G + # include TSort + # def initialize(g) + # @g = g + # end + # def tsort_each_child(n, &b) @g[n].each(&b) end + # def tsort_each_node(&b) @g.each_key(&b) end + # end + # + # graph = G.new({1=>[2, 3], 2=>[4], 3=>[2, 4], 4=>[]}) + # graph.each_strongly_connected_component {|scc| p scc } + # #=> [4] + # # [2] + # # [3] + # # [1] + # + # graph = G.new({1=>[2], 2=>[3, 4], 3=>[2], 4=>[]}) + # graph.each_strongly_connected_component {|scc| p scc } + # #=> [4] + # # [2, 3] + # # [1] + # def each_strongly_connected_component # :yields: nodes id_map = {} stack = [] @@ -187,7 +250,6 @@ module TSort https://github.com/ruby/ruby/blob/trunk/lib/tsort.rb#L250 nil end - # # Iterates over strongly connected component in the subgraph reachable from # _node_. # @@ -195,6 +257,25 @@ module TSort https://github.com/ruby/ruby/blob/trunk/lib/tsort.rb#L257 # # #each_strongly_connected_component_from doesn't call #tsort_each_node. # + # class G + # include TSort + # def initialize(g) + # @g = g + # end + # def tsort_each_child(n, &b) @g[n].each(&b) end + # def tsort_each_node(&b) @g.each_key(&b) end + # end + # + # graph = G.new({1=>[2, 3], 2=>[4], 3=>[2, 4], 4=>[]}) + # graph.each_strongly_connected_component_from(2) {|scc| p scc } + # #=> [4] + # # [2] + # + # graph = G.new({1=>[2], 2=>[3, 4], 3=>[2], 4=>[]}) + # graph.each_strongly_connected_component_from(2) {|scc| p scc } + # #=> [4] + # # [2, 3] + # 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 @@ -214,8 +295,11 @@ module TSort https://github.com/ruby/ruby/blob/trunk/lib/tsort.rb#L295 # 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] + # 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 @@ -244,7 +328,6 @@ module TSort https://github.com/ruby/ruby/blob/trunk/lib/tsort.rb#L328 minimum_id end - # # Should be implemented by a extended class. # # #tsort_each_node is used to iterate for all nodes over a graph. @@ -253,7 +336,6 @@ module TSort https://github.com/ruby/ruby/blob/trunk/lib/tsort.rb#L336 raise NotImplementedError.new end - # # Should be implemented by a extended class. # # #tsort_each_child is used to iterate for child nodes of _node_. -- ML: ruby-changes@q... Info: http://www.atdot.net/~ko1/quickml/