philiprehberger-dependency_graph
v0.4.0399,983 downloadsMIT
Dependency resolver with topological sort and parallel batch scheduling
$
gem install philiprehberger-dependency_graphREADME
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]
graph.out_degree(:d) # => 2
graph.in_degree(:b) # => 2
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#remove(item) | Remove a node and all incident edges; returns true when present, false otherwise |
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#in_degree(item) | Count of direct dependents for an item |
Graph#out_degree(item) | Count of direct dependencies for 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: