class Slinky::Graph
The Graph
class describes a directed graph and provides various graph algorithms.
Attributes
edges[R]
nodes[R]
Public Class Methods
new(nodes, edges)
click to toggle source
Creates a new Graph
from an adjacency list
# File lib/slinky/graph.rb, line 12 def initialize nodes, edges @nodes = nodes @edges = edges end
Public Instance Methods
adjacency_matrix()
click to toggle source
Builds an adjacency matrix representation of the graph
# File lib/slinky/graph.rb, line 18 def adjacency_matrix return @adjacency_matrix if @adjacency_matrix # Convert from adjacency list to a map structure g = Hash.new{|h,k| h[k] = []} edges.each{|x| g[x[1]] << x[0] } @adjacency_matrix = g end
dependency_list()
click to toggle source
Uses the tsort library to build a list of files in topological order, so that when required in this order all dependencies are met.
# File lib/slinky/graph.rb, line 82 def dependency_list return @dependency_list if @dependency_list results = [] each_strongly_connected_component{|component| if component.size == 1 results << component.first else cycle = component.map{|x| x.source}.join(" -> ") raise DependencyError.new("Dependencies #{cycle} could not be satisfied") end } @dependency_list = results end
each() { |e| ... }
click to toggle source
# File lib/slinky/graph.rb, line 97 def each &block edges.each do |e| if block_given? block.call e else yield e end end end
transitive_closure()
click to toggle source
Builds the transitive closure of the dependency graph using Floyd–Warshall
# File lib/slinky/graph.rb, line 32 def transitive_closure return @transitive_closure if @transitive_closure g = adjacency_matrix index_map = {} nodes.each_with_index{|f, i| index_map[f] = i} size = nodes.size # The max int supported by the transitive closure C extension (2^30 - 1) maxint = 1073741823 # Set up the distance matrix dist = Array.new(size * size, maxint) nodes.each_with_index{|fi, i| dist[size * i + i] = 0 g[fi].each{|fj| dist[size * i + index_map[fj]] = 1 } } # Compute the all-paths costs Slinky::all_paths_costs(size, dist) # Compute the transitive closure in map form @transitive_closure = Hash.new{|h,k| h[k] = []} size.times{|i| size.times{|j| if dist[size * i + j] < maxint @transitive_closure[nodes[i]] << nodes[j] end } } @transitive_closure end
tsort_each_child(node, &block)
click to toggle source
# File lib/slinky/graph.rb, line 75 def tsort_each_child node, &block adjacency_matrix.fetch(node, []).each(&block) end
tsort_each_node(&block)
click to toggle source
Methods needed for TSort mixin
# File lib/slinky/graph.rb, line 71 def tsort_each_node &block nodes.each(&block) end