module Gem::TSort
Gem::TSort
implements topological sorting using Tarjan’s algorithm for strongly connected components.
Gem::TSort
is designed to be able to be used with any object which can be interpreted as a directed graph.
Gem::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 Gem::TSort
uses Hash internally.
A Simple Example¶ ↑
The following example demonstrates how to mix the Gem::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 'rubygems/vendor/tsort/lib/tsort' class Hash include Gem::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 More Realistic Example¶ ↑
A very simple ‘make’ like tool can be implemented as follows:
require 'rubygems/vendor/tsort/lib/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 Gem::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 Gem::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')
Bugs¶ ↑
-
‘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.
References¶ ↑
-
Tarjan, “Depth First Search and Linear Graph Algorithms”,
-
SIAM Journal on Computing, Vol. 1, No. 2, pp. 146-160, June 1972.
Constants
- VERSION
Public Class Methods
The iterator version of the Gem::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) } Gem::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) } Gem::TSort.each_strongly_connected_component(each_node, each_child) {|scc| p scc } #=> [4] # [2, 3] # [1]
# File rubygems/vendor/tsort/lib/tsort.rb, line 345 def self.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 each_strongly_connected_component_from(node, each_child, id_map, stack) {|c| yield c } end } nil 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.
Gem::TSort.each_strongly_connected_component_from is a class method and it doesn’t need a class to represent a graph which includes Gem::TSort
.
graph = {1=>[2], 2=>[3, 4], 3=>[2], 4=>[]} each_child = lambda {|n, &b| graph[n].each(&b) } Gem::TSort.each_strongly_connected_component_from(1, each_child) {|scc| p scc } #=> [4] # [2, 3] # [1]
# File rubygems/vendor/tsort/lib/tsort.rb, line 411 def self.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 = 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
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 Gem::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 Gem::TSort.strongly_connected_components(each_node, each_child) #=> [[4], [2, 3], [1]]
# File rubygems/vendor/tsort/lib/tsort.rb, line 283 def self.strongly_connected_components(each_node, each_child) each_strongly_connected_component(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, Gem::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 Gem::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 Gem::TSort.tsort(each_node, each_child) # raises Gem::TSort::Cyclic
# File rubygems/vendor/tsort/lib/tsort.rb, line 178 def self.tsort(each_node, each_child) tsort_each(each_node, each_child).to_a end
The iterator version of the Gem::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) } Gem::TSort.tsort_each(each_node, each_child) {|n| p n } #=> 4 # 2 # 3 # 1
# File rubygems/vendor/tsort/lib/tsort.rb, line 226 def self.tsort_each(each_node, each_child) # :yields: node return to_enum(__method__, each_node, each_child) unless block_given? 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
Public Instance Methods
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 Gem::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 rubygems/vendor/tsort/lib/tsort.rb, line 316 def each_strongly_connected_component(&block) # :yields: nodes each_node = method(:tsort_each_node) each_child = method(:tsort_each_child) Gem::TSort.each_strongly_connected_component(each_node, each_child, &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 Gem::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 rubygems/vendor/tsort/lib/tsort.rb, line 386 def each_strongly_connected_component_from(node, id_map={}, stack=[], &block) # :yields: nodes Gem::TSort.each_strongly_connected_component_from(node, method(:tsort_each_child), id_map, stack, &block) 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 Gem::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 rubygems/vendor/tsort/lib/tsort.rb, line 257 def strongly_connected_components each_node = method(:tsort_each_node) each_child = method(:tsort_each_child) Gem::TSort.strongly_connected_components(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, Gem::TSort::Cyclic
is raised.
class G include Gem::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 Gem::TSort::Cyclic
# File rubygems/vendor/tsort/lib/tsort.rb, line 152 def tsort each_node = method(:tsort_each_node) each_child = method(:tsort_each_child) Gem::TSort.tsort(each_node, each_child) 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, Gem::TSort::Cyclic
is raised.
class G include Gem::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 rubygems/vendor/tsort/lib/tsort.rb, line 205 def tsort_each(&block) # :yields: node each_node = method(:tsort_each_node) each_child = method(:tsort_each_child) Gem::TSort.tsort_each(each_node, each_child, &block) end
Should be implemented by a extended class.
tsort_each_child
is used to iterate for child nodes of node.
# File rubygems/vendor/tsort/lib/tsort.rb, line 452 def tsort_each_child(node) # :yields: child raise NotImplementedError.new end
Should be implemented by a extended class.
tsort_each_node
is used to iterate for all nodes over a graph.
# File rubygems/vendor/tsort/lib/tsort.rb, line 444 def tsort_each_node # :yields: node raise NotImplementedError.new end