Module IntDigraph

Vertices are integers in the range 0..n-1. Edges are ordered pairs of vertices. The representation is suited for dense set of vertices (n should not be too big compared to the actual number of vertices).

The intended usage is construct, sort, and then compute : add edges to a graph, sort its edges, then make efficient computations on the graph (without modifying it).

The representation uses basically two int arrays and has pretty compact memory usage: 2n + m words if m edges with same source are added consecutively, and 2(n + m) words at most otherwise. (Assumes n <= max_int, and m <= max_int.)

It amounts to an array of adjency lists when edges are added in arbitrary order, and to an array of adjency arrays when edges are sorted.

A call to sort g sorts lexicographically the edges in O(n+m) time. (If edges were already sorted then nothing is done.) This reduces out-degree computation to O(1) time and edge detection to O(log degree) time (instead of O(degree) in both cases). Additionnally, it reduces the size to 2n + m words and the reverse graph can be obtained as a byproduct of the computation.

A guess n' of n must be provided at graph creation (a table of 2n' words is then provisioned). If edges are inserted for higher indices the table grows if it is dense engough. Otherwise (sparse indices), a hashtable is used (with additional cost of roughly 5n words).

Module IntLabeled provides graphs with int labels (both on edges and vertices). Module Labeled provides graphs with labels of any type.

When n < 2^31 and m < 2^48, functor Compact can provide graphs within 16n + 4m bytes using bigarrays.

When predecessors are accessed, the reverse graph is computed in O(n+m) time and the graph size doubles.

Example :

    let module G = IntDigraph in

    let g = G.create () in

    List.iter (fun (u,v) -> G.add_edge g u v) 

    [2,4; 1,8; 1,2; 2,4; 2,3; 3,4; 2,5; 4,1; 2,9; 1,9; 2,8; 1,7; 2,4; 2,7;] ;

    G.add_vertex g 17 ;

    G.sort g ;

    Printf.printf "-- Diraph with %d nodes and %d edges :\n%s" (G.n_mem g) (G.m g) (G.to_string g) ;

    let degrees = Array.make (G.n g) 0 in

    G.iter_vertex (fun u -> degrees.(u) <- G.in_degree g u + G.out_degree g u) g ;