MBA UFRJ - Topological Sort

benchmark.rb

require "benchmark"

graphs = []

1.upto(10) do |i|
  graphs << GraphGenerator.new(i * 100)
end

Benchmark.bmbm(5) do |x|
  graphs.each do |graph|
    x.report("n = #{graph.vertices + graph.edges}") { DependencyResolver.new(graph.hash).tsort }
  end
end

benchmark_results.txt

Rehearsal -----------------------------------------------
n = 19111     0.010000   0.000000   0.010000 (  0.007953)
n = 69539     0.030000   0.000000   0.030000 (  0.030782)
n = 172672    0.080000   0.010000   0.090000 (  0.085827)
n = 293890    0.140000   0.000000   0.140000 (  0.137431)
n = 467062    0.220000   0.000000   0.220000 (  0.227211)
n = 662798    0.300000   0.010000   0.310000 (  0.315837)
n = 896491    0.420000   0.000000   0.420000 (  0.426038)
n = 1190799   0.580000   0.010000   0.590000 (  0.601938)
n = 1502211   0.720000   0.010000   0.730000 (  0.741710)
n = 1847494   0.910000   0.000000   0.910000 (  0.928112)
-------------------------------------- total: 3.450000sec

                  user     system      total        real
n = 19111     0.010000   0.000000   0.010000 (  0.009951)
n = 69539     0.030000   0.000000   0.030000 (  0.037544)
n = 172672    0.080000   0.000000   0.080000 (  0.086759)
n = 293890    0.140000   0.000000   0.140000 (  0.144722)
n = 467062    0.230000   0.010000   0.240000 (  0.232919)
n = 662798    0.330000   0.010000   0.340000 (  0.333813)
n = 896491    0.440000   0.010000   0.450000 (  0.455155)
n = 1190799   0.620000   0.010000   0.630000 (  0.631013)
n = 1502211   0.800000   0.000000   0.800000 (  0.817448)
n = 1847494   0.980000   0.000000   0.980000 (  1.009076)

dependency_resolver.rb

require "tsort"

class DependencyResolver
  include TSort

  attr_reader :graph

  def initialize(graph)
    @graph = graph
  end

  def tsort_each_node(&block)
    graph.each_key(&block)
  end

  def tsort_each_child(node, &block)
    graph.fetch(node).each(&block)
  end
end

graph_generator.rb

class GraphGenerator
  MIN_PER_RANK = 1
  MAX_PER_RANK = 5
  PERCENT = 30

  attr_reader :ranks, :hash

  def initialize(ranks)
    @ranks = ranks
    @hash = generate
  end

  def vertices
    hash.keys.count
  end

  def edges
    hash.values.flatten.count
  end

  private

  def generate
    nodes = 0
    hash = {}

    0.upto(ranks) do |i|
      new_nodes = MIN_PER_RANK + (rand(100) % (MAX_PER_RANK - MIN_PER_RANK + 1))

      0.upto(nodes) do |j|
        vertice = j.to_s
        hash[vertice] ||= []
        0.upto(new_nodes) do |k|
          if (rand(100) % 100) < PERCENT
            edge = (k + nodes).to_s
            hash[vertice] << edge
            hash[edge] ||= []
          end
        end
      end

      nodes += new_nodes
    end

    hash
  end
end