Graph Algorithms

A Ruby library implementing classic graph algorithms with a focus on clarity and correctness. Each algorithm solves a concrete problem — dependency ordering and shortest-path routing — and ships with executable examples and a full Minitest suite.

Built as a learning-oriented codebase, the implementations favor readable, idiomatic Ruby over premature optimization, making them easy to study, extend, and test.

---

Algorithms

Algorithm	Class	Problem	Time Complexity
Kahn's Algorithm	GraphAlgorithms::Kahn	Topological sort of a directed acyclic graph (DAG)	O(V + E)
Dijkstra's Algorithm	GraphAlgorithms::Dijkstra	Single-source shortest paths in a weighted undirected graph	O(V²)

Kahn's Algorithm — Topological Sort

Given a directed graph where each vertex maps to the set of its incoming edges (dependencies), Kahn's algorithm produces a valid linear ordering of vertices such that every dependency appears before the vertices that require it.

• Input: Hash{ Integer => Set<Integer> } — vertex → set of prerequisite vertices
• Output: Set<Integer> — topologically sorted vertices
• Cycle detection: raises StandardError with message "Circular Dependency" when the graph contains a cycle

Dijkstra's Algorithm — Shortest Paths

Given a weighted undirected graph represented as an adjacency matrix, Dijkstra's algorithm computes the minimum-cost path from a source vertex to every other reachable vertex.

• Input: Array<Array<Integer|nil>> — adjacency matrix (nil = no edge; positive integer = edge weight)
• Output: Array<Hash> — each entry contains :vertex, :cost, and :path (e.g. "0-1-5")
• Source vertex: defaults to 0, but any vertex index can be passed as the second argument

---

Project Structure

graph-algorithms/
├── lib/
│   ├── graph_algorithms.rb          # Entry point — loads all algorithms
│   └── graph_algorithms/
│       ├── kahn.rb                    # Topological sort
│       └── dijkstra.rb                # Shortest paths
├── exe/
│   ├── problem_1                      # Runnable Kahn example
│   └── problem_2                      # Runnable Dijkstra example
└── test/
    ├── kahn_test.rb
    ├── dijkstra_test.rb
    └── support/test_helper.rb

---

Getting Started

Requirements

• Ruby 2.5+
• Bundler

Install Dependencies

bundle install

Run the Sample Problems

Problem 1 — Topological Sort (Kahn):

./exe/problem_1

Expected output:

Order of dependencies: [0, 1, 4, 3, 2, 5, 6, 7]

Problem 2 — Shortest Paths (Dijkstra):

./exe/problem_2

Expected output:

Vertex,  Cost,   Path
1,       2,      0-1
2,       14,     0-1-5-2
3,       10,     0-1-3
4,       3,      0-4
5,       11,     0-1-5
6,       8,      0-1-6
7,       12,     0-4-7

Run Tests

bundle exec rake test

Test coverage is collected automatically via SimpleCov.

Interactive Usage (IRB)

Load the library in an IRB session to experiment with custom inputs:

irb -I . -r lib/graph_algorithms

Kahn example:

graph = {
  0 => Set.new([]),
  1 => Set.new([]),
  2 => Set.new([1]),
  3 => Set.new([0]),
  4 => Set.new([]),
  5 => Set.new([3]),
  6 => Set.new([2, 4, 5]),
  7 => Set.new([5, 6])
}

GraphAlgorithms::Kahn.new.execute(graph)
# => #<Set: {0, 1, 4, 3, 2, 5, 6, 7}>

Dijkstra example:

graph = [
  [nil, 2, nil, nil, 3, nil, nil, nil],
  [2, nil, nil, 8, nil, 9, 6, nil],
  [nil, nil, nil, nil, nil, 3, 7, nil],
  [nil, 8, nil, nil, nil, nil, nil, 6],
  [3, nil, nil, nil, nil, nil, 5, 9],
  [nil, 9, 3, nil, nil, nil, 4, 5],
  [nil, 6, 7, nil, 5, 4, nil, nil],
  [nil, nil, nil, 6, 9, 5, nil, nil]
]

GraphAlgorithms::Dijkstra.new.execute(graph)
# => [{ vertex: 1, cost: 2, path: "0-1" }, ...]

# From a different source vertex:
GraphAlgorithms::Dijkstra.new.execute(graph, 2)

---

Input Reference

Problem 1 — Dependency Graph

Vertices are integers. Each key in the hash is a vertex; its value is a Set of vertices that must come before it (incoming edges / prerequisites).

{
  0 => Set.new([]),          # no dependencies
  1 => Set.new([]),          # no dependencies
  2 => Set.new([1]),         # depends on vertex 1
  3 => Set.new([0]),         # depends on vertex 0
  4 => Set.new([]),
  5 => Set.new([3]),
  6 => Set.new([2, 4, 5]),   # depends on 2, 4, and 5
  7 => Set.new([5, 6])
}

Problem 2 — Adjacency Matrix

An n × n matrix where matrix[i][j] is the weight of the edge between vertex i and vertex j. Use nil for absent edges. The graph is undirected, so the matrix is symmetric.

[
  [nil, 2, nil, nil, 3, nil, nil, nil],
  [2, nil, nil, 8, nil, 9, 6, nil],
  # ...
]

---

Design Notes

• Kahn mutates the input graph in place while processing — the hash is emptied as vertices are resolved. This keeps memory usage low and mirrors the classic BFS-based approach.
• Dijkstra uses a linear scan to find the nearest unvisited vertex (O(V) per iteration), yielding O(V²) overall. A priority-queue version would improve this to O((V + E) log V) for sparse graphs.
• Both algorithms live under the GraphAlgorithms module and expose a single #execute method, keeping the public API consistent and minimal.

---

License

This project is open source. Feel free to use, study, and adapt the code.