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:
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
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
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.