Sux4J-Based Implementations

Sux4J is a library containing implementations of succinct data structures in Java. Such structures can be used to store graphs in a very compact form. For example, the memory footprint of the English Wikipedia graph in 2013 would be a few gigabytes in a trivial object-based representation, it is 1.6GB in JGraphT’s sparse representation, but it is just 500MB in a succinct representation. The denser the graph, the more marked these differences will be.

The implementations in the package org.jgrapht.sux4j make it possible to use succinct representation of graphs in JGraphT. The implementations are serializable, and you can download ready-made graphs in this form from the LAW web site.

The typical use case for these adapters is:

• You need a compact format.
• You have less than 2³¹ vertices and less than 2³¹ edges.
• You have metadata associated with the vertices and with the edges.
• Optionally, you need fast adjacency tests.

Such metadata can be easily stored in an array or list indexed by the vertices or the edges. If you have metadata on the vertices only, or if your number of vertices or edges does not satisfy the limitations above, a WebGraph adapter might be more appropriate. A separate guide is available for WebGraph adapters.

The two main implementations are SuccinctDirectedGraph and SuccinctUndirectedGraph. They both use pairs to represent edges, but you can easily map edges in a contiguous segment of integers starting from zero; the mapping is reasonably fast.

Note that one of the benefits of the succinct representation used by these classes is that adjacency tests are very fast.

If you need, however, an implementation whose vertex and edge type is Integer (for example, for usage with Python bindings), there are classes SuccinctIntDirectedGraph and SuccinctIntUndirectedGraph. These classes, however, are fairly slow due to the necessity of continuously remapping edges from pairs to indices. We suggest that you use them only in the directed case and for outgoing arcs. However, in some cases they might provide the only representation of this type that is small enough to be loaded in main memory.