Class: Slinky::Graph
- Inherits:
-
Object
- Object
- Slinky::Graph
- 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
-
#edges ⇒ Object
readonly
Returns the value of attribute edges.
-
#nodes ⇒ Object
readonly
Returns the value of attribute nodes.
Instance Method Summary collapse
-
#adjacency_matrix ⇒ Object
Builds an adjacency matrix representation of the graph.
-
#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.
- #each(&block) ⇒ Object
-
#initialize(nodes, edges) ⇒ Graph
constructor
Creates a new Graph from an adjacency list.
-
#transitive_closure ⇒ Object
Builds the transitive closure of the dependency graph using Floyd–Warshall.
- #tsort_each_child(node, &block) ⇒ Object
-
#tsort_each_node(&block) ⇒ Object
Methods needed for TSort mixin.
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 |