BigGraphTools

BigGraphTools is a library providing an ocaml graph implementation with pretty low memory usage and some graph algorithms. A graph with n nodes and m edges is represented within 2n+m words when edges with same source are added consecutively. Using bigarrays, unweighted graphs with less than 2^31 nodes can be represented within 12n+4m bytes. The library is in early development phase.

Tools provided for the moment : Computing the diameter and radius of a graph. (Diameter is the maximum excentricity of a node, and radius minimum excentricity.) Computing skeleton graphs. (A skeleton of a graph is a small dominating subgraph with similar distances.)

Author

Laurent Viennot

Download

Version 0 is also available from github.

More information