Project

General

Profile

Download (3.27 KB)

Feature #10508 ยป 0001-Return-enumerator-in-TSort-each_-methods.patch

ptico (Andrey Savchenko), 11/13/2014 09:04 PM

View differences:

lib/tsort.rb
# p TSort.tsort(each_node, each_child) # raises TSort::Cyclic
#
def TSort.tsort(each_node, each_child)
result = []
TSort.tsort_each(each_node, each_child) {|element| result << element}
result
TSort.tsort_each(each_node, each_child).to_a
end
# The iterator version of the #tsort method.
......
# # 1
#
def TSort.tsort_each(each_node, each_child) # :yields: node
return to_enum(__method__, each_node, each_child) unless block_given?
TSort.each_strongly_connected_component(each_node, each_child) {|component|
if component.size == 1
yield component.first
......
# #=> [[4], [2, 3], [1]]
#
def TSort.strongly_connected_components(each_node, each_child)
result = []
TSort.each_strongly_connected_component(each_node, each_child) {|component| result << component}
result
TSort.each_strongly_connected_component(each_node, each_child).to_a
end
# The iterator version of the #strongly_connected_components method.
......
# # [1]
#
def TSort.each_strongly_connected_component(each_node, each_child) # :yields: nodes
return to_enum(__method__, each_node, each_child) unless block_given?
id_map = {}
stack = []
each_node.call {|node|
......
# # [1]
#
def TSort.each_strongly_connected_component_from(node, each_child, id_map={}, stack=[]) # :yields: nodes
return to_enum(__method__, node, each_child, id_map, stack) unless block_given?
minimum_id = node_id = id_map[node] = id_map.size
stack_length = stack.length
stack << node
test/test_tsort.rb
r = []
TSort.tsort_each(each_node, each_child) {|n| r << n }
assert_equal([4, 2, 3, 1], r)
r = TSort.tsort_each(each_node, each_child).map {|n| n.to_s }
assert_equal(['4', '2', '3', '1'], r)
end
def test_s_strongly_connected_components
......
r << scc
}
assert_equal([[4], [2, 3], [1]], r)
r = TSort.each_strongly_connected_component(each_node, each_child).map {|scc|
scc.map(&:to_s)
}
assert_equal([['4'], ['2', '3'], ['1']], r)
end
def test_s_each_strongly_connected_component_from
......
r << scc
}
assert_equal([[4], [2, 3], [1]], r)
r = TSort.each_strongly_connected_component_from(1, each_child).map {|scc|
scc.map(&:to_s)
}
assert_equal([['4'], ['2', '3'], ['1']], r)
end
end
    (1-1/1)