method
strongly_connected_components
v2_2_9 -
Show latest stable
-
0 notes -
Class: TSort
- 1_8_6_287
- 1_8_7_72
- 1_8_7_330
- 1_9_1_378
- 1_9_2_180
- 1_9_3_125
- 1_9_3_392
- 2_1_10 (0)
- 2_2_9 (0)
- 2_4_6 (0)
- 2_5_5 (0)
- 2_6_3 (0)
- What's this?
strongly_connected_components(each_node, each_child)
public
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]]