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