summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorakr <akr@b2dd03c8-39d4-4d8f-98ff-823fe69b080e>2013-10-17 15:59:40 +0000
committerakr <akr@b2dd03c8-39d4-4d8f-98ff-823fe69b080e>2013-10-17 15:59:40 +0000
commit4c5bfb9fbd82585a0c7d7744fc3fc054cb3f4e42 (patch)
treeb7b20227660dabb6767739619051a901c136a293
parentb0c19be2849d4957d4b6b230004c9ce351ad8545 (diff)
* 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. git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@43342 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
-rw-r--r--ChangeLog9
-rw-r--r--NEWS4
-rw-r--r--lib/tsort.rb118
-rw-r--r--test/test_tsort.rb48
4 files changed, 170 insertions, 9 deletions
diff --git a/ChangeLog b/ChangeLog
index f9e17ac..4de9538 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,12 @@
+Fri Oct 18 00:57:07 2013 Tanaka Akira <akr@fsij.org>
+
+ * 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@atdot.net>
* gc.c (CALC_EXACT_MALLOC_SIZE_CHECK_OLD_SIZE): introduced.
diff --git a/NEWS b/NEWS
index eb1af33..fe4ae53 100644
--- a/NEWS
+++ b/NEWS
@@ -246,6 +246,10 @@ with all sufficient information, see the ChangeLog file.
* TSort
* New methods:
+ * TSort.tsort
+ * TSort.tsort_each
+ * TSort.strongly_connected_components
+ * TSort.each_strongly_connected_component
* TSort.each_strongly_connected_component_from
* WEBrick
diff --git a/lib/tsort.rb b/lib/tsort.rb
index 13718dd..cb8f67e 100644
--- a/lib/tsort.rb
+++ b/lib/tsort.rb
@@ -145,8 +145,34 @@ module TSort
# 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
# # 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
# 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
# # [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
#
# _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.
#
diff --git a/test/test_tsort.rb b/test/test_tsort.rb
index a732064..bd60f69 100644
--- a/test/test_tsort.rb
+++ b/test/test_tsort.rb
@@ -41,7 +41,53 @@ class TSortTest < Test::Unit::TestCase # :nodoc:
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 = []