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



291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
 
# File 'lib/philiprehberger/dependency_graph/graph.rb', line 291

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



356
357
358
359
360
361
 
# File 'lib/philiprehberger/dependency_graph/graph.rb', line 356

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) 


271
272
273
 
# File 'lib/philiprehberger/dependency_graph/graph.rb', line 271

def empty?
  @nodes.empty?
end

#in_degree(item) ⇒ Integer

Number of direct dependents for an item (how many items depend on it).

Returns 0 for unknown items, matching the defensive behavior of #dependents_of.

Parameters:

  • item (Object) —

    the item to query

Returns:

  • (Integer) —

    count of direct dependents



167
168
169
 
# File 'lib/philiprehberger/dependency_graph/graph.rb', line 167

def in_degree(item)
  @nodes.count { |_node, deps| deps.include?(item) }
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



315
316
317
318
319
320
321
 
# File 'lib/philiprehberger/dependency_graph/graph.rb', line 315

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



228
229
230
231
 
# File 'lib/philiprehberger/dependency_graph/graph.rb', line 228

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:



237
238
239
240
241
242
243
244
245
246
247
 
# File 'lib/philiprehberger/dependency_graph/graph.rb', line 237

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

#out_degree(item) ⇒ Integer

Number of direct dependencies for an item.

Returns 0 for unknown items, matching the defensive behavior of #dependencies_of.

Parameters:

  • item (Object) —

    the item to query

Returns:

  • (Integer) —

    count of direct dependencies



156
157
158
 
# File 'lib/philiprehberger/dependency_graph/graph.rb', line 156

def out_degree(item)
  (@nodes[item] || []).size
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



176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
 
# File 'lib/philiprehberger/dependency_graph/graph.rb', line 176

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



253
254
255
256
257
258
259
 
# File 'lib/philiprehberger/dependency_graph/graph.rb', line 253

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



278
279
280
281
282
283
284
285
 
# File 'lib/philiprehberger/dependency_graph/graph.rb', line 278

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



221
222
223
 
# File 'lib/philiprehberger/dependency_graph/graph.rb', line 221

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

#size ⇒ Integer

Total number of nodes in the graph

Returns:

  • (Integer) 


264
265
266
 
# File 'lib/philiprehberger/dependency_graph/graph.rb', line 264

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



204
205
206
207
208
209
210
211
212
213
214
215
216
 
# File 'lib/philiprehberger/dependency_graph/graph.rb', line 204

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



334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
 
# File 'lib/philiprehberger/dependency_graph/graph.rb', line 334

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