1module StringMap = Map.Make(String)
2
3type graph = string list StringMap.t
4
5let add_vertex g v =
6  if StringMap.mem v g then g else StringMap.add v [] g
7
8let add_edge g src dst =
9  let g = add_vertex (add_vertex g src) dst in
10  let neighbors = StringMap.find src g in
11  StringMap.add src (dst :: neighbors) g
12
13let graph_of_edges edges =
14  List.fold_left (fun g (src, dst) -> add_edge g src dst) StringMap.empty edges

1module StringMap = Map.Make(String)
2
3type graph = string list StringMap.t
4
5let compute_in_degree (g : graph) =
6  let init =
7    StringMap.fold (fun v _ acc -> StringMap.add v 0 acc) g StringMap.empty
8  in
9  StringMap.fold
10    (fun _ neighbors acc ->
11      List.fold_left
12        (fun m n ->
13          let count = match StringMap.find_opt n m with Some c -> c | None -> 0 in
14          StringMap.add n (count + 1) m)
15        acc
16        neighbors)
17    g
18    init
19
20let topological_sort (g : graph) =
21  let in_degree = compute_in_degree g in
22  let zero_start =
23    StringMap.fold
24      (fun v degree acc -> if degree = 0 then v :: acc else acc)
25      in_degree
26      []
27  in
28  let rec loop queue in_deg sorted visited =
29    match queue with
30| [] -> if visited = StringMap.cardinal g then Ok (List.rev sorted) else Error "Cycle detected: topological order does not exist" | v :: rest -> let neighbors = match StringMap.find_opt v g with Some xs -> xs | None -> [] in let in_deg', rest' = List.fold_left (fun (m, q) n -> let c = (match StringMap.find_opt n m with Some x -> x | None -> 0) - 1 in let m' = StringMap.add n c m in if c = 0 then (m', n :: q) else (m', q)) (in_deg, rest) neighbors in loop rest' in_deg' (v :: sorted) (visited + 1) in loop zero_start in_degree [] 0 ``` The function returns an `Ok` list when sorting succeeds and an `Error` message when a cycle is present. That explicit result type is important in production code because cyclic dependency data is common in configuration systems. ## Run the Algorithm on Sample Data The next snippet shows how to build and sort a dependency graph for a toy build pipeline. ```ocaml let edges = [ ("parse", "typecheck"); ("typecheck", "optimize"); ("parse", "lint"); ("lint", "package"); ("optimize", "package") ] let g = graph_of_edges edges let () = match topological_sort g with | Ok order -> Printf.printf "Topological order: %s\n" (String.concat " -> " order) | Error msg -> Printf.printf "Error: %s\n" msg ``` You may get a different but still valid ordering because several vertices can have in degree zero at the same step. If deterministic output matters, sort the queue after each insertion or use a priority queue. ## Common Pitfalls A frequent bug is forgetting to include vertices that only appear as destinations. That creates missing keys and broken in degree counts. Always initialize every vertex in your graph map before sorting. Another issue is assuming the output is unique. Topological sort often has many valid answers, so tests should verify dependency constraints rather than comparing with a single hard coded list. A third problem is ignoring cycle handling. Returning a partial list can hide data quality problems. Prefer an explicit error branch so callers can fail fast and report a useful message. ## Summary * Topological sort orders vertices so every dependency appears before dependents. * In OCaml, an adjacency `Map` plus an in degree map gives a clear Kahn implementation. * Return `Ok` or `Error` instead of silent partial results when cycles appear. * Include destination only vertices to keep the graph representation complete. * Validate constraints in tests, because many valid sort orders can exist.