Creating and publishing Fungi - A simple Graph implementation for Ocaml

After using the Ocaml programming language for a separate project and liking it, I decided to challenge myself by trying to implement some select graph algorithms in order to get a taste of a majority of the language.

Ocaml describes itself as a functional programming language with an emphasis safety and correctness. The language also supports an imperative approach to programming (traditional loops - mutability .. etc) but I revere its functional features.

There already exists a graph library for Ocaml - Ocamlgraph . I skimmed over its source code and noticed that it used functorial interfaces for most algorithms. e.g. here is how Dijkstra is implemented

module Dijkstra
                    (G: G)
                    (W: Sig.WEIGHT with type edge = G.E.t) :
                    sig

                    val shortest_path : G.t -> G.V.t -> G.V.t -> G.E.t list * W.t
                    end
                

Here, Dijkstra is a module which takes in a graph module and the weight signature for the edges (as far as i understand). Then internally the module will call the shortest_path function. Here is how this looks in our graph. dijkstra becomes a simple function and not a functor

(* The Top Module *) 
module MakeGraph(Unique: GraphElt): Graph with type elt := Unique.t and type edge := Unique.edge = struct

    type elt  = Unique.t
    type edge = Unique.edge
    (** ... more graph functions ... *)

    module Path = struct
        (* ... path algos ... *)

        module Compute(Measure: Measurable with type t = edge and type edge = edge) = struct
            type measure = Measure.t wrap 

            (* other short path algos ... *)
            let dijkstra start target graph =
                let startp = (viapath start start start (`Val Measure.zero)) in 
                (** rest of the algorithm *)
                ()
            ;;

        end

    end
end

    

The library works well for the most part. For my library i made some different considerations.

• No external dependencies (outside of testing)
• The Graph would use an adjacency set representation
• The Graph will be able to represent directed and undirected edges using the presence back-edges.
• Most graph algorithms will use a functional style. This means the graph is (semi) persistent by default. Edge information however is held in non-persistent hash-tables. the graph algorithms take this into account. Persistent means previous versions of the graph are accessible after modification.

The result is the Fungi library. It has implementations of some popular graph algorithms including:

• Tarjan and Kosaraju strongly connected components
• Bron-Kerbosch clique
• Gale-Shapely matching
• Dijkstra, Bellman-Ford, Johnsons and Floyd-Warshall path algorithms
• Kruskal and Prims Minimum Spanning Tree
• Ford-Fulkerson and Edmonds-Karp flow algorithms
• Various other graph manipulation algorithms and traversal algorithms (DFS and BFS)

In addition - there is an elementary implementation of an unbalanced set data structure to support the graphs adacency sets. Also a Fibonacci heap was added that was quite a blast to research and implement as also was the UnionFind disjoint set.

However there are several weaknesses with this graph implementation. For example, since it relies on back-edges for representing undirected graphs having multiple edges with different edge values but same vertices can be confusing since internally edges are stored in hash-tables. This isn't an issue for most algorithms but worth considering if you are going to use the graph. Also the implementation relies of non-persistent data structures which makes some algorithms slow.

If you do plan to use you can get from github directly or via opam (pending). I plan to add more advanced algorithms mostly as part of my own personal learning effort :-).

Now available opam