Class: Slinky::Graph

Inherits:
Object
  • Object
show all
Includes:
Enumerable, TSort
Defined in:
lib/slinky/graph.rb

Overview

The Graph class describes a directed graph and provides various graph algorithms.

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(nodes, edges) ⇒ Graph

Creates a new Graph from an adjacency list



12
13
14
15
 
# File 'lib/slinky/graph.rb', line 12

def initialize nodes, edges
  @nodes = nodes
  @edges = edges
end

Instance Attribute Details

#edges ⇒ Object (readonly)

Returns the value of attribute edges.



9
10
11
 
# File 'lib/slinky/graph.rb', line 9

def edges
  @edges
end

#nodes ⇒ Object (readonly)

Returns the value of attribute nodes.



9
10
11
 
# File 'lib/slinky/graph.rb', line 9

def nodes
  @nodes
end

Instance Method Details

#adjacency_matrix ⇒ Object

Builds an adjacency matrix representation of the graph



18
19
20
21
22
23
24
25
26
27
28
 
# 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 ⇒ Object

Uses the tsort library to build a list of files in topological order, so that when required in this order all dependencies are met.



82
83
84
85
86
87
88
89
90
91
92
93
94
95
 
# 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(&block) ⇒ Object 



97
98
99
100
101
102
103
104
105
 
# 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 ⇒ Object

Builds the transitive closure of the dependency graph using Floyd–Warshall



32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
 
# 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) ⇒ Object 



75
76
77
 
# File 'lib/slinky/graph.rb', line 75

def tsort_each_child node, &block
  adjacency_matrix.fetch(node, []).each(&block)
end

#tsort_each_node(&block) ⇒ Object

Methods needed for TSort mixin



71
72
73
 
# File 'lib/slinky/graph.rb', line 71

def tsort_each_node &block
  nodes.each(&block)
end