Package org.jgrapht.sux4j
This package contains implementations of immutable graphs based on the Elias–Fano quasisuccinct representation of monotone sequences. The positions of the nonzero entries of the adjacency matrix of a graph are represented as a monotone sequence of natural numbers.
The memory footprint of these implementation is close to the informationtheoretical lower bound
in the undirected case, and close to twice the informationtheoretical lower bound in the
directed case, because the transposed graph must be stored separately, but in the latter case you
have the choice to not support incoming edges and obtain, again, footprint close to the
informationtheoretical lower bound. The actual space used can be easily measured as all
implementations are serializable, and their inmemory footprint is very close to the ondisk
footprint. Usually the size is a few times smaller than that of a
SparseIntDirectedGraph
/SparseIntUndirectedGraph
.
We provide two classes mimicking SparseIntDirectedGraph
and SparseIntUndirectedGraph
, in the sense that both vertices and edges are integers (and they are
numbered contiguously). Thus, by definition these classes cannot represent graphs with more than
Integer.MAX_VALUE
edges.
SuccinctIntDirectedGraph
is an implementation for directed graphs. Enumeration of outgoing edges is quite fast, but enumeration of incoming edges is very slow. Adjacency tests are very fast and happen in almost constant time.SuccinctIntUndirectedGraph
is an implementation for undirected graphs. Enumeration of edges is very slow. Adjacency tests are very fast and happen in almost constant time.
The sometimes slow behavior of the previous classes is due to a clash between JGraphT's design
and the need of representing an edge with an Integer
, which cannot be
extended: there is no information that can be carried by the object representing the edge. This
limitation forces the two classes above to compute two expensive functions that are one the
inverse of the other.
As an alternative, we provide classes SuccinctDirectedGraph
and SuccinctUndirectedGraph
using the same amount of space, but having edges represented by pairs of
integers stored in an IntIntPair
(for directed
graphs) or an IntIntSortedPair
(for
undirected graphs). Storing the edges explicitly avoids the cumbersome backandforth
computations of the previous classes. All accessors are extremely fast. There is no limitation on
the number of edges.
Both classes provide methods
getEdgeFromIndex()
and
getIndexFromEdge()
that map bijectively the edge set into a contiguous set of longs. In this way
the user can choose when and how to use the feature (e.g., to store compactly data associated to
edges).
Finally, note that the best performance and compression can be obtained by representing the graph
using WebGraph's EFGraph
format and then accessing the graph using the suitable adapter; in particular, one can represent graphs with more than Integer.MAX_VALUE
vertices. However, the adapters do not provide methods mapping bijectively edges into a
contiguous set of integers.
Building and serializing with limited memory
All implementations provide a copy constructor taking a Graph
and a
constructor accepting a list of edges; the latter just builds a sparse graph and delegates to the
copy constructor. Both methods can be inconvenient if the graph to be represented is large, as
the list of edges might have too large a footprint.
There is however a simple strategy that makes it possible to build succinct representations using a relatively small amount of additional memory with respect to the representation itself:
 convert your graph to a WebGraph format such as
BVGraph
orEFGraph
;  if your graph is directed, use
Transform
to store the transpose of your graph in the same way;  use a suitable adapter to get a
Graph
representing your graph, taking care of loading the WebGraph representations usingImmutableGraph.loadMapped()
;  use the copy constructor to obtain a quasisuccinct representation.

Class Summary Class Description AbstractSuccinctDirectedGraph<E> An abstract base class for all succinct directed implementations.AbstractSuccinctDirectedGraph.CumulativeDegrees Iterates over the cumulative degrees (starts with a zero).AbstractSuccinctDirectedGraph.CumulativeSuccessors<E> Turns all edges x → y into a monotone sequence using the encoding x2^{⌈log n⌉} + y, or the encoding xn + y  e, where e is the index of the edge in lexicographical order, depending on the value of thestrict
parameter.AbstractSuccinctGraph<E> An abstract base class for all succinct implementations.AbstractSuccinctUndirectedGraph<E> An abstract base class for all succinct undirected implementations.AbstractSuccinctUndirectedGraph.CumulativeDegrees<E> Iterates over the cumulative degrees (starts with a zero).AbstractSuccinctUndirectedGraph.CumulativeSuccessors<E> Turns all edges x — y, x ≤ y, into a monotone sequence using the encoding x2^{⌈log n⌉} + y, or all edges x — y, x ≥ y, using the encoding xn + y  e, where e is the index of the edge in lexicographical order, depending on the value of thesorted
parameter.SuccinctDirectedGraph An immutable directed graph withIntIntPair
edges represented using quasisuccinct data structures.SuccinctIntDirectedGraph An immutable directed graph withInteger
edges represented using quasisuccinct data structures.SuccinctIntUndirectedGraph An immutable undirected graph withInteger
edges represented using quasisuccinct data structures.SuccinctUndirectedGraph An immutable undirected graph withIntIntSortedPair
edges represented using quasisuccinct data structures.