Graph Algorithms

Overview

A complete graph library built with OCaml's module system. Supports both directed and undirected graphs with adjacency list representation using Map.Make functors. Includes BFS traversal, DFS traversal, shortest path (BFS), connected components, cycle detection (3-color DFS), and topological sort (Kahn's algorithm).

This example brings together nearly every concept from the earlier examples — and introduces OCaml modules, functors, record types, and imperative queues.

Graph Representation

Use Map.Make(Int) to create a type-safe integer map for adjacency lists. The graph record holds both the adjacency data and whether edges are directed:

module IntMap = Map.Make(Int)
module IntSet = Set.Make(Int)

type graph = {
  adj: int list IntMap.t;   (* adjacency list *)
  directed: bool;
}

Key Algorithms

BFS — Breadth-First Search

Uses OCaml's Queue module for O(1) enqueue/dequeue. Returns vertices in discovery order:

let bfs g start =
  let visited = Hashtbl.create 16 in
  let queue = Queue.create () in
  Queue.push start queue;
  Hashtbl.replace visited start true;
  while not (Queue.is_empty queue) do
    let v = Queue.pop queue in
    (* process v, enqueue unvisited neighbors *)
  done

BFS Shortest Path

Finds the shortest unweighted path between two vertices by tracking parent pointers during BFS, then reconstructing the path:

let bfs_path g start goal =
  (* BFS with parent tracking *)
  let rec build_path v acc =
    if v = start then v :: acc
    else build_path (Hashtbl.find parent v) (v :: acc)
  in Some (build_path goal [])

DFS — Depth-First Search

Natural recursive DFS — no explicit stack needed, OCaml's call stack handles it:

let dfs g start =
  let visited = Hashtbl.create 16 in
  let rec explore v =
    if not (Hashtbl.mem visited v) then begin
      Hashtbl.replace visited v true;
      List.iter explore (neighbors g v)
    end
  in explore start

Cycle Detection (3-Color DFS)

Uses White/Gray/Black coloring. A back-edge to a Gray node means a cycle exists:

type color = White | Gray | Black

let has_cycle g =
  (* DFS: Gray->Gray edge = back edge = cycle *)
  match Hashtbl.find color w with
  | Gray -> found_cycle := true
  | White -> visit w
  | Black -> ()

Topological Sort (Kahn's Algorithm)

Computes in-degrees, processes zero-in-degree vertices first. Returns None if a cycle is detected:

let topological_sort g =
  if has_cycle g then None
  else begin
    (* Compute in-degrees, process queue *)
    Some (List.rev !result)
  end

Output

=== Undirected Graph ===
Undirected graph: 7 vertices, 6 edges
  1 -> [2; 3]
  2 -> [1; 4]
  3 -> [1; 4]
  4 -> [2; 3; 5]
  5 -> [4]
  6 -> [7]
  7 -> [6]

BFS from 1: [1; 2; 3; 4; 5]
DFS from 1: [1; 2; 4; 3; 5]

Shortest path 1->5: [1; 2; 4; 5]
No path from 1 to 7 (different component)

Connected components: 2
  Component 1: [1; 2; 3; 4; 5]
  Component 2: [6; 7]

=== Directed Acyclic Graph (DAG) ===
Directed graph: 5 vertices, 5 edges
Has cycle: false
Topological order: [1; 3; 2; 4; 5]

=== Directed Graph with Cycle ===
Directed graph: 4 vertices, 4 edges
Has cycle: true
Topological sort failed (cycle detected)

=== BFS/DFS on Directed Graph ===
BFS from 1: [1; 2; 3; 4; 5; 6]
DFS from 1: [1; 2; 4; 5; 6; 3]
Shortest path 1->6: [1; 2; 4; 5; 6]

Concepts Introduced

• Modules & Functors: Map.Make(Int) and Set.Make(Int) generate type-safe, efficient collections from a minimal signature
• Record types: The graph record bundles adjacency data with a directed flag — cleaner than tuples for multi-field data
• Imperative queues: Queue.create/push/pop for O(1) BFS operations — OCaml embraces imperative style when it fits
• Variant types for state: White | Gray | Black colors make cycle detection's three states explicit and pattern-matchable
• Mixed paradigms: Functional graph construction + imperative BFS/DFS traversal — use whichever fits the algorithm