module TSort

TSort implementiert topologische Sortierung mittels Tarjans Algorithmus für stark verbundene Komponenten.

TSort ist so konzipiert, dass es mit jedem Objekt verwendet werden kann, das als gerichteter Graph interpretiert werden kann.

TSort erfordert zwei Methoden zur Interpretation eines Objekts als Graph: tsort_each_node und tsort_each_child.

Die Gleichheit von Knoten wird durch eql? und hash definiert, da TSort intern Hash verwendet.

Ein einfaches Beispiel

Das folgende Beispiel zeigt, wie das Modul TSort in eine bestehende Klasse (in diesem Fall Hash) gemischt werden kann. Hier behandeln wir jeden Schlüssel im Hash als einen Knoten im Graphen und leiten einfach die erforderliche Methode tsort_each_node an die each_key-Methode von Hash weiter. Für jeden Schlüssel im Hash ist der zugehörige Wert ein Array der Kindknoten des Knotens. Diese Wahl führt wiederum zu unserer Implementierung der erforderlichen Methode tsort_each_child, die das Array der Kindknoten abruft und dann über dieses Array mittels des vom Benutzer bereitgestellten Blocks iteriert.

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

Ein realistischeres Beispiel

Ein sehr einfaches 'make'-ähnliches Werkzeug kann wie folgt implementiert werden

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

Fehler

Referenzen

    1. Tarjan, "Depth First Search and Linear Graph Algorithms",

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