171 |
171 |
# p TSort.tsort(each_node, each_child) # raises TSort::Cyclic
|
172 |
172 |
#
|
173 |
173 |
def TSort.tsort(each_node, each_child)
|
174 |
|
result = []
|
175 |
|
TSort.tsort_each(each_node, each_child) {|element| result << element}
|
176 |
|
result
|
|
174 |
TSort.tsort_each(each_node, each_child).to_a
|
177 |
175 |
end
|
178 |
176 |
|
179 |
177 |
# The iterator version of the #tsort method.
|
... | ... | |
221 |
219 |
# # 1
|
222 |
220 |
#
|
223 |
221 |
def TSort.tsort_each(each_node, each_child) # :yields: node
|
|
222 |
return to_enum(__method__, each_node, each_child) unless block_given?
|
|
223 |
|
224 |
224 |
TSort.each_strongly_connected_component(each_node, each_child) {|component|
|
225 |
225 |
if component.size == 1
|
226 |
226 |
yield component.first
|
... | ... | |
276 |
276 |
# #=> [[4], [2, 3], [1]]
|
277 |
277 |
#
|
278 |
278 |
def TSort.strongly_connected_components(each_node, each_child)
|
279 |
|
result = []
|
280 |
|
TSort.each_strongly_connected_component(each_node, each_child) {|component| result << component}
|
281 |
|
result
|
|
279 |
TSort.each_strongly_connected_component(each_node, each_child).to_a
|
282 |
280 |
end
|
283 |
281 |
|
284 |
282 |
# The iterator version of the #strongly_connected_components method.
|
... | ... | |
340 |
338 |
# # [1]
|
341 |
339 |
#
|
342 |
340 |
def TSort.each_strongly_connected_component(each_node, each_child) # :yields: nodes
|
|
341 |
return to_enum(__method__, each_node, each_child) unless block_given?
|
|
342 |
|
343 |
343 |
id_map = {}
|
344 |
344 |
stack = []
|
345 |
345 |
each_node.call {|node|
|
... | ... | |
404 |
404 |
# # [1]
|
405 |
405 |
#
|
406 |
406 |
def TSort.each_strongly_connected_component_from(node, each_child, id_map={}, stack=[]) # :yields: nodes
|
|
407 |
return to_enum(__method__, node, each_child, id_map, stack) unless block_given?
|
|
408 |
|
407 |
409 |
minimum_id = node_id = id_map[node] = id_map.size
|
408 |
410 |
stack_length = stack.length
|
409 |
411 |
stack << node
|