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]

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

Development

bundle install
bundle exec rspec
bundle exec rubocop

Support

If you find this project useful:

⭐ Star the repo

🐛 Report issues

💡 Suggest features

❤️ Sponsor development

🌐 All Open Source Projects

💻 GitHub Profile

🔗 LinkedIn Profile

License

MIT