philiprehberger-dependency_graph
Dependency resolver with topological sort and parallel batch scheduling
Requirements
- Ruby >= 3.1
Installation
Add to your Gemfile:
gem "philiprehberger-dependency_graph"
Or install directly:
gem install philiprehberger-dependency_graph
Usage
require "philiprehberger/dependency_graph"
graph = Philiprehberger::DependencyGraph.new
graph.add(:a)
graph.add(:b, depends_on: [:a])
graph.add(:c, depends_on: [:a])
graph.add(:d, depends_on: [:b, :c])
graph.resolve # => [:a, :b, :c, :d] (dependencies first)
Parallel Batches
graph = Philiprehberger::DependencyGraph.new
graph.add(:a)
graph.add(:b, depends_on: [:a])
graph.add(:c, depends_on: [:a])
graph.add(:d, depends_on: [:b, :c])
graph.parallel_batches
# => [[:a], [:b, :c], [:d]]
# Batch 1: run :a
# Batch 2: run :b and :c in parallel
# Batch 3: run :d
Cycle Detection
graph = Philiprehberger::DependencyGraph.new
graph.add(:a, depends_on: [:b])
graph.add(:b, depends_on: [:a])
graph.cycle? # => true
graph.cycles # => [[:a, :b, :a]]
Dependency Queries
graph = Philiprehberger::DependencyGraph.new
graph.add(:a)
graph.add(:b, depends_on: [:a])
graph.add(:c, depends_on: [:b])
graph.add(:d, depends_on: [:b, :c])
graph.dependencies_of(:d) # => [:b, :c]
graph.all_dependencies_of(:d) # => [:b, :c, :a]
graph.dependents_of(:b) # => [:c, :d]
Path Finding
graph.path(:d, :a) # => [:d, :b, :a]
graph.path(:a, :d) # => nil (no path in that direction)
Subgraph Extraction
sub = graph.subgraph(:a, :b, :c)
sub.resolve # => [:a, :b, :c]
# Edges to nodes outside the subgraph are excluded
Roots, Leaves, and Depth
graph.roots # => [:a] (no dependencies)
graph.leaves # => [:d] (nothing depends on it)
graph.depth(:d) # => 2 (longest path from a root)
Chaining
graph = Philiprehberger::DependencyGraph.new
graph.add(:a).add(:b, depends_on: [:a]).add(:c, depends_on: [:b])
graph.resolve # => [:a, :b, :c]
Graphviz Export
graph = Philiprehberger::DependencyGraph.new
graph.add(:a)
graph.add(:b, depends_on: [:a])
graph.add(:c, depends_on: [:b])
puts graph.to_dot
# digraph dependencies {
# "b" -> "a";
# "c" -> "b";
# }
graph.to_dot(name: 'MyDeps') # Customize the digraph name
API
| Method | Description |
|---|---|
DependencyGraph.new |
Create a new empty graph |
Graph#add(item, depends_on:) |
Add an item with dependencies |
Graph#resolve |
Topological sort, dependencies first |
Graph#parallel_batches |
Group into parallel execution batches |
Graph#cycle? |
Check if the graph contains cycles |
Graph#cycles |
List all detected cycles |
Graph#dependencies_of(item) |
Direct dependencies of an item |
Graph#all_dependencies_of(item) |
All transitive dependencies |
Graph#dependents_of(item) |
Items that directly depend on an item |
Graph#path(from, to) |
Shortest dependency path (BFS), or nil |
Graph#subgraph(*items) |
Extract a new graph with specified nodes |
Graph#roots |
Nodes with no dependencies |
Graph#leaves |
Nodes with no dependents |
Graph#depth(item) |
Maximum dependency depth of a node |
Graph#reverse |
Return a new graph with all edges flipped |
Graph#all_dependents_of(item) |
All transitive dependents of a node |
Graph#independent?(a, b) |
Whether two nodes are mutually unreachable |
#to_dot(name:) |
Graphviz DOT representation |
Development
bundle install
bundle exec rspec
bundle exec rubocop
Support
If you find this project useful: