Class: Philiprehberger::DependencyGraph::Graph

Inherits:
Object
  • Object
show all
Defined in:
lib/philiprehberger/dependency_graph/graph.rb

Overview

Directed acyclic graph for dependency resolution

Constant Summary collapse

Error = 
DependencyGraph::Error

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ Graph

Returns a new instance of Graph.



12
13
14
 
# File 'lib/philiprehberger/dependency_graph/graph.rb', line 12

def initialize
  @nodes = {}
end

Instance Attribute Details

#nodes ⇒ Hash (readonly)

Returns the adjacency list (item => dependencies).

Returns:

  • (Hash) —

    the adjacency list (item => dependencies)



10
11
12
 
# File 'lib/philiprehberger/dependency_graph/graph.rb', line 10

def nodes
  @nodes
end

Instance Method Details

#add(item, depends_on: []) ⇒ self

Add an item with its dependencies

Parameters:

  • item (Object) —

    the item to add

  • depends_on (Array) (defaults to: []) —

    the items this item depends on

Returns:

  • (self) 


21
22
23
24
25
26
27
28
 
# File 'lib/philiprehberger/dependency_graph/graph.rb', line 21

def add(item, depends_on: [])
  @nodes[item] ||= []
  depends_on.each do |dep|
    @nodes[dep] ||= []
    @nodes[item] << dep unless @nodes[item].include?(dep)
  end
  self
end

#all_dependencies_of(item) ⇒ Array

Return all transitive dependencies of an item (direct + indirect)

Parameters:

  • item (Object) —

    the item to query

Returns:

  • (Array) —

    all dependencies in no particular order



120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
 
# File 'lib/philiprehberger/dependency_graph/graph.rb', line 120

def all_dependencies_of(item)
  return [] unless @nodes.key?(item)

  visited = {}
  queue = @nodes[item].dup
  result = []

  until queue.empty?
    dep = queue.shift
    next if visited[dep]

    visited[dep] = true
    result << dep
    queue.concat(@nodes[dep] || [])
  end

  result
end

#all_dependents_of(item) ⇒ Array

Return all transitive dependents of an item (direct + indirect)

Parameters:

  • item (Object) —

    the item to query

Returns:

  • (Array) —

    all items that depend on this item, directly or transitively



269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
 
# File 'lib/philiprehberger/dependency_graph/graph.rb', line 269

def all_dependents_of(item)
  return [] unless @nodes.key?(item)

  visited = {}
  queue = dependents_of(item)
  result = []

  until queue.empty?
    dep = queue.shift
    next if visited[dep]

    visited[dep] = true
    result << dep
    queue.concat(dependents_of(dep))
  end

  result
end

#cycle? ⇒ Boolean

Check if the graph contains any cycles

Returns:

  • (Boolean) 


87
88
89
 
# File 'lib/philiprehberger/dependency_graph/graph.rb', line 87

def cycle?
  !cycles.empty?
end

#cycles ⇒ Array<Array>

Find all cycles in the graph

Returns:

  • (Array<Array>) —

    list of cycles, each cycle is an array of items



94
95
96
97
98
99
100
101
102
103
104
105
106
 
# File 'lib/philiprehberger/dependency_graph/graph.rb', line 94

def cycles
  found_cycles = []
  visited = {}
  stack = {}

  @nodes.each_key do |node|
    next if visited[node]

    detect_cycles(node, visited, stack, [], found_cycles)
  end

  found_cycles
end

#dependencies_of(item) ⇒ Array

Return direct dependencies of an item

Parameters:

  • item (Object) —

    the item to query

Returns:

  • (Array) —

    direct dependencies, or empty array if item is unknown



112
113
114
 
# File 'lib/philiprehberger/dependency_graph/graph.rb', line 112

def dependencies_of(item)
  (@nodes[item] || []).dup
end

#dependents_of(item) ⇒ Array

Return items that directly depend on the given item (reverse lookup)

Parameters:

  • item (Object) —

    the item to query

Returns:

  • (Array) —

    direct dependents



143
144
145
146
147
 
# File 'lib/philiprehberger/dependency_graph/graph.rb', line 143

def dependents_of(item)
  @nodes.each_with_object([]) do |(node, deps), acc|
    acc << node if deps.include?(item)
  end
end

#depth(item) ⇒ Integer

Calculate maximum dependency depth for a node (longest path from any root to this node)

Parameters:

  • item (Object) —

    the item to query

Returns:

  • (Integer) —

    the depth, or 0 if the item is a root or unknown



334
335
336
337
338
339
 
# File 'lib/philiprehberger/dependency_graph/graph.rb', line 334

def depth(item)
  return 0 unless @nodes.key?(item)

  memo = {}
  compute_depth(item, memo)
end

#empty? ⇒ Boolean

Whether the graph has no nodes

Returns:

  • (Boolean) 


249
250
251
 
# File 'lib/philiprehberger/dependency_graph/graph.rb', line 249

def empty?
  @nodes.empty?
end

#independent?(node_a, node_b) ⇒ Boolean

Check whether two nodes are independent (neither depends on the other transitively)

Parameters:

  • node_a (Object)
  • node_b (Object)

Returns:

  • (Boolean) —

    true if neither node is reachable from the other



293
294
295
296
297
298
299
 
# File 'lib/philiprehberger/dependency_graph/graph.rb', line 293

def independent?(node_a, node_b)
  return false if node_a == node_b
  return false unless @nodes.key?(node_a) && @nodes.key?(node_b)

  !all_dependencies_of(node_a).include?(node_b) &&
    !all_dependencies_of(node_b).include?(node_a)
end

#leaves ⇒ Array

Return nodes with no dependents (no other node depends on them)

Returns:

  • (Array) —

    leaf nodes



206
207
208
209
 
# File 'lib/philiprehberger/dependency_graph/graph.rb', line 206

def leaves
  depended_on = @nodes.values.flatten.uniq
  @nodes.keys.reject { |node| depended_on.include?(node) }
end

#merge(other) ⇒ self

Merge another graph into this one, combining nodes and dependencies

Parameters:

  • other (Graph) —

    another graph to merge

Returns:

  • (self)

Raises:



215
216
217
218
219
220
221
222
223
224
225
 
# File 'lib/philiprehberger/dependency_graph/graph.rb', line 215

def merge(other)
  raise Error, 'Can only merge Graph instances' unless other.is_a?(self.class)

  other.nodes.each do |node, deps|
    @nodes[node] ||= []
    deps.each do |dep|
      @nodes[node] << dep unless @nodes[node].include?(dep)
    end
  end
  self
end

#parallel_batches ⇒ Array<Array>

Group items into parallel execution batches

Returns:

  • (Array<Array>) —

    batches where items in each batch can run in parallel

Raises:

  • (Error) —

    if a cycle is detected



62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
 
# File 'lib/philiprehberger/dependency_graph/graph.rb', line 62

def parallel_batches
  raise Error, "Cycle detected: #{cycles.first.join(' -> ')}" if cycle?

  remaining = @nodes.keys.dup
  resolved = []
  batches = []

  until remaining.empty?
    batch = remaining.select do |item|
      @nodes[item].all? { |dep| resolved.include?(dep) }
    end

    raise Error, 'Unable to resolve dependencies' if batch.empty?

    batches << batch
    resolved.concat(batch)
    remaining -= batch
  end

  batches
end

#path(from, to) ⇒ Array?

Find shortest dependency path between two nodes using BFS

Parameters:

  • from (Object) —

    the starting node

  • to (Object) —

    the target node

Returns:

  • (Array, nil) —

    array of nodes forming the path, or nil if no path exists



154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
 
# File 'lib/philiprehberger/dependency_graph/graph.rb', line 154

def path(from, to)
  return nil unless @nodes.key?(from) && @nodes.key?(to)
  return [from] if from == to

  visited = { from => nil }
  queue = [from]

  until queue.empty?
    current = queue.shift
    (@nodes[current] || []).each do |dep|
      next if visited.key?(dep)

      visited[dep] = current
      if dep == to
        return build_path(visited, from, to)
      end

      queue << dep
    end
  end

  nil
end

#remove(item) ⇒ Boolean

Remove a node and all edges referencing it

Parameters:

  • item (Object) —

    the item to remove

Returns:

  • (Boolean) —

    true if the node existed, false otherwise



231
232
233
234
235
236
237
 
# File 'lib/philiprehberger/dependency_graph/graph.rb', line 231

def remove(item)
  return false unless @nodes.key?(item)

  @nodes.delete(item)
  @nodes.each_value { |deps| deps.delete(item) }
  true
end

#resolve ⇒ Array

Resolve dependencies using topological sort (Kahn’s algorithm)

Returns:

  • (Array) —

    items in dependency order (dependencies first)

Raises:

  • (Error) —

    if a cycle is detected



34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
 
# File 'lib/philiprehberger/dependency_graph/graph.rb', line 34

def resolve
  raise Error, "Cycle detected: #{cycles.first.join(' -> ')}" if cycle?

  in_degree = Hash.new(0)
  @nodes.each_key { |node| in_degree[node] ||= 0 }
  @nodes.each_value do |deps|
    deps.each { |dep| in_degree[dep] += 1 }
  end

  queue = @nodes.keys.select { |node| in_degree[node].zero? }
  result = []

  until queue.empty?
    node = queue.shift
    result << node
    @nodes[node].each do |dep|
      in_degree[dep] -= 1
      queue << dep if in_degree[dep].zero?
    end
  end

  result.reverse
end

#reverse ⇒ Graph

Return a new graph with all edges reversed (dependents become dependencies)

Returns:

  • (Graph) —

    a new graph where each edge direction is flipped



256
257
258
259
260
261
262
263
 
# File 'lib/philiprehberger/dependency_graph/graph.rb', line 256

def reverse
  new_graph = self.class.new
  @nodes.each_key { |node| new_graph.instance_variable_get(:@nodes)[node] ||= [] }
  @nodes.each do |node, deps|
    deps.each { |dep| new_graph.add(dep, depends_on: [node]) }
  end
  new_graph
end

#roots ⇒ Array

Return nodes that have no dependencies

Returns:

  • (Array) —

    root nodes



199
200
201
 
# File 'lib/philiprehberger/dependency_graph/graph.rb', line 199

def roots
  @nodes.select { |_node, deps| deps.empty? }.keys
end

#size ⇒ Integer

Total number of nodes in the graph

Returns:

  • (Integer) 


242
243
244
 
# File 'lib/philiprehberger/dependency_graph/graph.rb', line 242

def size
  @nodes.size
end

#subgraph(*items) ⇒ Graph

Extract a subgraph containing only the specified nodes and edges between them

Parameters:

  • items (Array<Object>) —

    nodes to include

Returns:

  • (Graph) —

    a new graph with only the specified nodes



182
183
184
185
186
187
188
189
190
191
192
193
194
 
# File 'lib/philiprehberger/dependency_graph/graph.rb', line 182

def subgraph(*items)
  item_set = items.flatten.to_h { |i| [i, true] }
  new_graph = self.class.new

  items.flatten.each do |item|
    next unless @nodes.key?(item)

    matching_deps = (@nodes[item] || []).select { |dep| item_set[dep] }
    new_graph.add(item, depends_on: matching_deps)
  end

  new_graph
end

#to_dot(name: 'dependencies') ⇒ String

Export the graph in Graphviz DOT format.

Nodes are emitted in alphabetical order (cast to string for sort key), and edges within a node are sorted alphabetically for deterministic output. Nodes that participate in at least one edge (incoming or outgoing) are emitted implicitly via the edge lines; truly isolated nodes are declared explicitly so they still appear in the rendered graph. Works on graphs containing cycles.

Parameters:

  • name (String) (defaults to: 'dependencies') —

    the digraph name used in the ‘digraph` header

Returns:

  • (String) —

    Graphviz DOT source, terminated by a newline



312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
 
# File 'lib/philiprehberger/dependency_graph/graph.rb', line 312

def to_dot(name: 'dependencies')
  output = "digraph #{name} {\n"
  depended_on = @nodes.each_with_object({}) do |(_node, deps), acc|
    deps.each { |dep| acc[dep] = true }
  end
  sorted_nodes = @nodes.keys.sort_by(&:to_s)
  sorted_nodes.each do |node|
    deps = (@nodes[node] || []).sort_by(&:to_s)
    if deps.empty?
      output << "  #{dot_quote(node)};\n" unless depended_on[node]
    else
      deps.each { |dep| output << "  #{dot_quote(node)} -> #{dot_quote(dep)};\n" }
    end
  end
  output << "}\n"
  output
end