After using OCaml for a separate project and liking it, I decided to challenge myself by implementing a selection of graph algorithms — partly to learn the language more deeply, partly because I wanted a library I could actually use.
OCaml describes itself as a functional language with an emphasis on safety and correctness. It also supports an imperative style (loops, mutability, etc.), but I gravitate toward its functional features.
I collected everything into a library so I could pull it into other projects. The main design constraints I set were:
- No external dependencies (outside of testing)
- Adjacency-set representation
- Directed and undirected edges via back-edges
- Functional style throughout — the graph is semi-persistent by default. Edge data lives in non-persistent hash-tables, which the algorithms account for.
The result is Fungi. Algorithms implemented include:
- Tarjan and Kosaraju strongly connected components
- Bron-Kerbosch clique finding
- Gale-Shapley stable matching
- Dijkstra, Bellman-Ford, Johnson's, and Floyd-Warshall shortest paths
- Kruskal and Prim minimum spanning tree
- Ford-Fulkerson and Edmonds-Karp max-flow
- DFS, BFS, and various other traversal and manipulation utilities
A Fibonacci heap and a UnionFind disjoint-set were also added — both were fun to research and implement.
There are a few known limitations worth mentioning. Because undirected graphs rely on back-edges, having multiple edges with different weights between the same two vertices can be ambiguous — edges are stored in hash-tables, so duplicates are silently overwritten. The reliance on non-persistent data structures also makes some algorithms slower than a fully persistent approach would be.
If you want to try it, you can install directly from GitHub or via opam. I plan to add more algorithms as part of my own learning — no promises on timeline.
Now available on opam.
← back to home