TSort implements topological sorting using Tarjan's algorithm for strongly connected components.
TSort is designed to be able to be used with any object which can be interpreted as a directed graph.
TSort requires two methods to interpret an object as a graph, tsort_each_node and tsort_each_child.
tsort_each_node is used to iterate for all nodes over a graph.
tsort_each_child is used to iterate for child nodes of a given node.
The equality of nodes are defined by eql? and hash since TSort uses Hash internally.
The following example demonstrates how to mix the TSort module into an existing class (in this case, Hash). Here, we're treating each key in the hash as a node in the graph, and so we simply alias the required tsort_each_node method to Hash's each_key method. For each key in the hash, the associated value is an array of the node's child nodes. This choice in turn leads to our implementation of the required tsort_each_child method, which fetches the array of child nodes and then iterates over that array using the user-supplied block.
require 'tsort'
class Hash
include TSort
alias tsort_each_node each_key
def tsort_each_child(node, &block)
fetch(node).each(&block)
end
end
{1=>[2, 3], 2=>[3], 3=>[], 4=>[]}.tsort
#=> [3, 2, 1, 4]
{1=>[2], 2=>[3, 4], 3=>[2], 4=>[]}.strongly_connected_components
#=> [[4], [2, 3], [1]]
A very simple `make' like tool can be implemented as follows:
require 'tsort'
class Make
def initialize
@dep = {}
@dep.default = []
end
def rule(outputs, inputs=[], &block)
triple = [outputs, inputs, block]
outputs.each {|f| @dep[f] = [triple]}
@dep[triple] = inputs
end
def build(target)
each_strongly_connected_component_from(target) {|ns|
if ns.length != 1
fs = ns.delete_if {|n| Array === n}
raise TSort::Cyclic.new("cyclic dependencies: #{fs.join ', '}")
end
n = ns.first
if Array === n
outputs, inputs, block = n
inputs_time = inputs.map {|f| File.mtime f}.max
begin
outputs_time = outputs.map {|f| File.mtime f}.min
rescue Errno::ENOENT
outputs_time = nil
end
if outputs_time == nil ||
inputs_time != nil && outputs_time <= inputs_time
sleep 1 if inputs_time != nil && inputs_time.to_i == Time.now.to_i
block.call
end
end
}
end
def tsort_each_child(node, &block)
@dep[node].each(&block)
end
include TSort
end
def command(arg)
print arg, "\n"
system arg
end
m = Make.new
m.rule(%w[t1]) { command 'date > t1' }
m.rule(%w[t2]) { command 'date > t2' }
m.rule(%w[t3]) { command 'date > t3' }
m.rule(%w[t4], %w[t1 t3]) { command 'cat t1 t3 > t4' }
m.rule(%w[t5], %w[t4 t2]) { command 'cat t4 t2 > t5' }
m.build('t5')
'tsort.rb' is wrong name because this library uses Tarjan's algorithm for strongly connected components. Although 'strongly_connected_components.rb' is correct but too long.
Tarjan, “Depth First Search and Linear Graph Algorithms”,
SIAM Journal on Computing, Vol. 1, No. 2, pp. 146-160, June 1972.
# File lib/tsort.rb, line 342
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|
unless id_map.include? node
TSort.each_strongly_connected_component_from(node, each_child, id_map, stack) {|c|
yield c
}
end
}
nil
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]
# File lib/tsort.rb, line 408
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
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 =
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
end
}
if node_id == minimum_id
component = stack.slice!(stack_length .. -1)
component.each {|n| id_map[n] = nil}
yield component
end
minimum_id
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 child 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]
# File lib/tsort.rb, line 280 def TSort.strongly_connected_components(each_node, each_child) TSort.each_strongly_connected_component(each_node, each_child).to_a 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]]
# File lib/tsort.rb, line 175 def TSort.tsort(each_node, each_child) TSort.tsort_each(each_node, each_child).to_a 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
# File lib/tsort.rb, line 223
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
else
raise Cyclic.new("topological sort failed: #{component.inspect}")
end
}
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
# File lib/tsort.rb, line 313 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 strongly_connected_components method. obj.each_strongly_connected_component is similar to obj.strongly_connected_components.each, but modification of obj during the iteration may lead to unexpected results.
each_strongly_connected_component returns nil.
class G
include TSort
def initialize(g)
@g = g
end
def tsort_each_child(n, &b) @g[n].each(&b) end
def tsort_each_node(&b) @g.each_key(&b) end
end
graph = G.new({1=>[2, 3], 2=>[4], 3=>[2, 4], 4=>[]})
graph.each_strongly_connected_component {|scc| p scc }
#=> [4]
# [2]
# [3]
# [1]
graph = G.new({1=>[2], 2=>[3, 4], 3=>[2], 4=>[]})
graph.each_strongly_connected_component {|scc| p scc }
#=> [4]
# [2, 3]
# [1]
# File lib/tsort.rb, line 383
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 component in the subgraph reachable from node.
Return value is unspecified.
each_strongly_connected_component_from doesn't call tsort_each_node.
class G
include TSort
def initialize(g)
@g = g
end
def tsort_each_child(n, &b) @g[n].each(&b) end
def tsort_each_node(&b) @g.each_key(&b) end
end
graph = G.new({1=>[2, 3], 2=>[4], 3=>[2, 4], 4=>[]})
graph.each_strongly_connected_component_from(2) {|scc| p scc }
#=> [4]
# [2]
graph = G.new({1=>[2], 2=>[3, 4], 3=>[2], 4=>[]})
graph.each_strongly_connected_component_from(2) {|scc| p scc }
#=> [4]
# [2, 3]
# File lib/tsort.rb, line 254 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.
class G
include TSort
def initialize(g)
@g = g
end
def tsort_each_child(n, &b) @g[n].each(&b) end
def tsort_each_node(&b) @g.each_key(&b) end
end
graph = G.new({1=>[2, 3], 2=>[4], 3=>[2, 4], 4=>[]})
p graph.strongly_connected_components #=> [[4], [2], [3], [1]]
graph = G.new({1=>[2], 2=>[3, 4], 3=>[2], 4=>[]})
p graph.strongly_connected_components #=> [[4], [2, 3], [1]]
# File lib/tsort.rb, line 149 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.
If there is a cycle, TSort::Cyclic is raised.
class G
include TSort
def initialize(g)
@g = g
end
def tsort_each_child(n, &b) @g[n].each(&b) end
def tsort_each_node(&b) @g.each_key(&b) end
end
graph = G.new({1=>[2, 3], 2=>[4], 3=>[2, 4], 4=>[]})
p graph.tsort #=> [4, 2, 3, 1]
graph = G.new({1=>[2], 2=>[3, 4], 3=>[2], 4=>[]})
p graph.tsort # raises TSort::Cyclic
# File lib/tsort.rb, line 202 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 method. obj.tsort_each is similar to obj.tsort.each, but modification of obj during the iteration may lead to unexpected results.
tsort_each returns nil. If there is a cycle, TSort::Cyclic is raised.
class G
include TSort
def initialize(g)
@g = g
end
def tsort_each_child(n, &b) @g[n].each(&b) end
def tsort_each_node(&b) @g.each_key(&b) end
end
graph = G.new({1=>[2, 3], 2=>[4], 3=>[2, 4], 4=>[]})
graph.tsort_each {|n| p n }
#=> 4
# 2
# 3
# 1
# File lib/tsort.rb, line 449 def tsort_each_child(node) # :yields: child raise NotImplementedError.new end
Should be implemented by a extended class.
tsort_each_child is used to iterate for child nodes of node.
# File lib/tsort.rb, line 441 def tsort_each_node # :yields: node raise NotImplementedError.new end
Should be implemented by a extended class.
tsort_each_node is used to iterate for all nodes over a graph.
Ruby Core © 1993–2020 Yukihiro Matsumoto
Licensed under the Ruby License.
Ruby Standard Library © contributors
Licensed under their own licenses.