Module: TSort

Defined in:
lib/tsort.rb

Overview

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.

A Simple Example

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 More Realistic Example

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')

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

    1. Tarjan, “Depth First Search and Linear Graph Algorithms”,

SIAM Journal on Computing, Vol. 1, No. 2, pp. 146-160, June 1972.

Defined Under Namespace

Classes: Cyclic

Class Method Summary collapse

Instance Method Summary collapse

Class Method Details

.each_strongly_connected_component(each_node, each_child) ⇒ Object

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]



342
343
344
345
346
347
348
349
350
351
352
353
354
355
 
# 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

.each_strongly_connected_component_from(node, each_child, id_map = {}, stack = []) ⇒ Object

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]



408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
 
# 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

.strongly_connected_components(each_node, each_child) ⇒ Object

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]]



280
281
282
 
# 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

.tsort(each_node, each_child) ⇒ Object

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



175
176
177
 
# File 'lib/tsort.rb', line 175

def TSort.tsort(each_node, each_child)
  TSort.tsort_each(each_node, each_child).to_a
end

.tsort_each(each_node, each_child) ⇒ Object

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



223
224
225
226
227
228
229
230
231
232
233
 
# 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

Instance Method Details

#each_strongly_connected_component(&block) ⇒ Object

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]



313
314
315
316
317
 
# 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

#each_strongly_connected_component_from(node, id_map = {}, stack = [], &block) ⇒ Object

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]



383
384
385
 
# 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

#strongly_connected_components ⇒ Object

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]]



254
255
256
257
258
 
# 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

#tsort ⇒ Object

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



149
150
151
152
153
 
# 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

#tsort_each(&block) ⇒ Object

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



202
203
204
205
206
 
# 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

#tsort_each_child(node) ⇒ Object

Should be implemented by a extended class.

#tsort_each_child is used to iterate for child nodes of node.

Raises:

  • (NotImplementedError) 


449
450
451
 
# File 'lib/tsort.rb', line 449

def tsort_each_child(node) # :yields: child
  raise NotImplementedError.new
end

#tsort_each_node ⇒ Object

Should be implemented by a extended class.

#tsort_each_node is used to iterate for all nodes over a graph.

Raises:

  • (NotImplementedError) 


441
442
443
 
# File 'lib/tsort.rb', line 441

def tsort_each_node # :yields: node
  raise NotImplementedError.new
end