Skip to content

Instantly share code, notes, and snippets.

@wpolicarpo
Last active November 25, 2015 03:50
Show Gist options
  • Save wpolicarpo/52a638c174d66b77b774 to your computer and use it in GitHub Desktop.
Save wpolicarpo/52a638c174d66b77b774 to your computer and use it in GitHub Desktop.
MBA UFRJ - Topological Sort
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
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)
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
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment