Intro to Ocamlgraph

Ocamlgraph is a library for OCaml that gives the programmer several different types of graph data structure. Basically, you can mix and match the aspects of the graph that you want, finally resulting in an implementation you can use. Along with this, the library provides a number of common algorithms that work on any of the graphs you can create. How does all of this get done? Functors.

I will say, having started using the library before I knew what functors were, that making your library use functors is setting up a fairly steep barrier to entry. Not many people will want to spend time learning about how to use and write functors, just to use this library. And believe me if you want to do anything with a graph whose vertices and edges aren’t labeled with integers, you need to know functors.

One upside is that the library contains a graph implementation already constructed for you. Pack.Graph is an imperative undirected graph implementation, containing most of the useful algorithms implemented in the library. Algorithms for DFS, BFS, Dijkstra’s shortest path, Ford Fulkerson, Kruskal’s, and Topological sort. Also included are input and output functions; input builds a graph from a dot file and output can either create a dot file or run the graphviz program given the dot file.

Sounds wonderful except for the integer labeled vertices and edges. As soon as you want to label your vertices with strings and your edges with floats, you’re going to have to dive into functor land. Thankfully the existence of Pack.Graph makes figuring out how to make your own graph easier.

Say we’re creating a graph to model a map and we want to label each city (vertex) with its name (string) and each road (edge) with its distance (float). We’ll need to create a new graph structure since there is no ready-made version. Assuming the graph is undirected, and that we’ll be using an imperative graph (despite the name of the blog), let’s take a look at the Imperative.Graph module. You’ll see we’ve got 4 choices to make. Let’s choose ConcreteLabeled because our vertices aren’t abstract, and we do want the edges labeled. The signature of ConcreteLabeled:

module ConcreteLabeled: functor (V : Sig.COMPARABLE) ->
  functor (E : Sig.ORDERED_TYPE_DFT) -> Sig.I

So, we need to provide two structures, of the given types. Here they are:

module V = struct
  type t = string
  let compare = Pervasives.compare
  let hash = Hashtbl.hash
  let equal = (=)
end
module E = struct
  type t = float
  let compare = Pervasives.compare
  let default = 0.0
end

Now, because of the power of functors, creating the basic graph structure is one line of code:

module Graph = Imperative.Graph.ConcreteLabeled(V)(E)

Not only that, but the V and E structure will work for persistent and directed graphs that are concretelabeled, and you can switch by replacing Imperative with Persistent, and Graph with Digraph.

To get an implementation of Dijkstra’s algorithm for our newly created graph having looked at the signature of the functor (Path.Dijkstra). It requires the structure of the graph, and a weight structure that we use to tell the algorithm how to translate an edge’s label into a weight. Since we’ve labeled our edges with floats, the translation is trivial:

module W = struct
  type label = float
  type t = float
  let weight x = x
  let compare = Pervasives.compare
  let add = (+.)
  let zero = 0.0
end

And now, like our creation of the graph structure, creation of the algorithm’s structure is one line of code:

module Dijkstra = Path.Dijkstra(Graph)(W)

Finally, calling Dijkstra.shortest_path g v1 v2 will produce a list of edges signifying the path taken and a total weight.

The power of functors is that for an algorithm like Dijkstra’s that shouldn’t care about the structure of the graph or the labels on its edges, you can write the algorithm so that it doesn’t have to care about those things. The Path.Dijkstra functor works for both graphs and digraphs, and doesn’t have to care about edge labels because the programmer provides a way to translate between edge labels and weights.

Next time I’ll be talking about writing your own graph algorithm using functors, in the context of graph drawing.