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
This project has been split into smaller parts:
- int-graph-ml (Ocaml): the core of the ocaml part providing a graph representation with compact memory usage compared to ocamlgraph.
- weighted-diameter (C++): effcient computation of diameter, radius and all eccentricities of a graph (supports both directed/undirected and weighted/unweighted).
- hub-labeling (C++): compact representation of the distance matrix through a hub labeling (aka 2-hop labeling) of a weighted directed graph.
- contraction-hierarchies (C++): contracting a graph to a distance preserver allowing efficient shortest path computations.
- hl-csa-raptor (C++): classical public transit routing algorithms (inputing GTFS format) and supporting unrestricted walking through a hub labeling of the footpath graph.
The Version 0 is also available from
github.
More information