diff options
| -rw-r--r-- | ChangeLog | 5 | ||||
| -rw-r--r-- | NEWS | 4 | ||||
| -rw-r--r-- | lib/tsort.rb | 28 | ||||
| -rw-r--r-- | test/test_tsort.rb | 10 |
4 files changed, 44 insertions, 3 deletions
@@ -1,3 +1,8 @@ +Thu Oct 17 12:30:16 2013 Tanaka Akira <akr@fsij.org> + + * 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@segment7.net> * lib/rubygems: Update to RubyGems master 941c21a. Changes: @@ -244,6 +244,10 @@ with all sufficient information, see the ChangeLog file. 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. diff --git a/lib/tsort.rb b/lib/tsort.rb index d0f3cd4caa..6061cd73fe 100644 --- a/lib/tsort.rb +++ b/lib/tsort.rb @@ -195,18 +195,40 @@ module TSort # # #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 diff --git a/test/test_tsort.rb b/test/test_tsort.rb index 38018c49c0..a732064f31 100644 --- a/test/test_tsort.rb +++ b/test/test_tsort.rb @@ -40,5 +40,15 @@ class TSortTest < Test::Unit::TestCase # :nodoc: 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 |