What's the most-used data structure in OCaml to represent a Graph?

Question

In Java or other imperative programming, a graph can represented as a matrix or adjacent list. The adjacent list might be most popular, because it is compact and convenient as it is using array.

In functional programming, we normally don't use mutable array. Then normally how do we present a graph in OCaml or other functional programming?

Replace the array with a map?

---

in ocaml 99, graph it lists 4 kinds of ways:

edge-clause form

One method is to list all edges, an edge being a pair of nodes. In this form, the graph depicted opposite is represented as the following expression:

['h', 'g';  'k', 'f';  'f', 'b';  'f', 'c';  'c', 'b']

We call this edge-clause form. Obviously, isolated nodes cannot be represented.

graph-term form

Another method is to represent the whole graph as one data object. According to the definition of the graph as a pair of two sets (nodes and edges), we may use the following OCaml type:

type 'a graph_term = { nodes : 'a list;  edges : ('a * 'a) list }

Then, the above example graph is represented by:

let example_graph =
{ nodes = ['b'; 'c'; 'd'; 'f'; 'g'; 'h'; 'k'];
  edges = ['h', 'g';  'k', 'f';  'f', 'b';  'f', 'c';  'c', 'b'] }

We call this graph-term form. Note, that the lists are kept sorted, they are really sets, without duplicated elements. Each edge appears only once in the edge list; i.e. an edge from a node x to another node y is represented as (x,y), the couple (y,x) is not present. The graph-term form is our default representation. You may want to define a similar type using sets instead of lists.

adjacency-list form

A third representation method is to associate with each node the set of nodes that are adjacent to that node. We call this the adjacency-list form.

human-friendly form

The representations we introduced so far well suited for automated processing, but their syntax is not very user-friendly. Typing the terms by hand is cumbersome and error-prone. We can define a more compact and "human-friendly" notation as follows: A graph (with char labelled nodes) is represented by a string of atoms and terms of the type X-Y. The atoms stand for isolated nodes, the X-Y terms describe edges. If an X appears as an endpoint of an edge, it is automatically defined as a node. Our example could be written as:

"b-c f-c g-h d f-b k-f h-g"

---

I think that none of the above 4 ways is good enough, considering processing efficiencies.

For the record type graph-term form, there is no efficient way to locate a node (O(n) always) and to locate an edge attached to a node.

Answer 1

You might be interested by the OCamlGraph library (http://ocamlgraph.lri.fr) which provides various implementations of graphs, either persistent or mutable, together with a bunch of classical algorithms.

Answer 2

There are two things to consider: representation of a graph, and intermediate data structures used in some graph algorithms.

I think the adjacency list form is the most memory efficient way to represent graphs. Could be improved a bit by having trees or maps of the type

type Graph a = Map a [a]

But when you want to run some algorithm like "strongly connected components" or "topological sort", then those algorithms will most likely use mutable arrays to implement it.

Note that in languaes like Haskell, the ST monad makes it possible to have temporary mutable state i.e. arrays), as opposed to global state. Functions that employ this are still overall pure.