 All Implemented Interfaces:
Serializable
,Graph<Integer,
Integer>
Integer
edges represented using quasisuccinct data
structures.
The graph representation of this implementation is similar to that of
SparseIntDirectedGraph
: nodes and edges are initial intervals of the natural numbers.
Under the hood, however, this class uses the Elias–Fano representation of monotone sequences to represent the positions of ones in the
(linearized) adjacency matrix of the graph. Instances are serializable and thread safe.
If the vertex set is compact (i.e., vertices are numbered from 0 consecutively), space usage will
be close to twice the informationtheoretical lower bound (typically, a few times smaller than a
SparseIntDirectedGraph
). If you drop
support for incoming edges
the space will close to the informationtheoretical lower bound .
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.
SuccinctDirectedGraph
is a much faster implementation with a similar footprint using
IntIntPair
as edge type. Please read the class
documentation for more information.
 Author:
 Sebastiano Vigna
 See Also:

Nested Class Summary
Nested classes/interfaces inherited from class org.jgrapht.sux4j.AbstractSuccinctDirectedGraph
AbstractSuccinctDirectedGraph.CumulativeDegrees, AbstractSuccinctDirectedGraph.CumulativeSuccessors<E>

Field Summary
Fields inherited from class org.jgrapht.sux4j.AbstractSuccinctGraph
m, n, sourceShift, targetMask, UNMODIFIABLE
Fields inherited from interface org.jgrapht.Graph
DEFAULT_EDGE_WEIGHT

Constructor Summary
ConstructorDescriptionSuccinctIntDirectedGraph
(int numVertices, int numEdges, Supplier<Stream<Pair<Integer, Integer>>> edges) Creates a new immutable succinct directed graph from a supplier of streams of edges, supporting both outgoing and incoming edges.SuccinctIntDirectedGraph
(int numVertices, int numEdges, Supplier<Stream<Pair<Integer, Integer>>> edges, boolean incomingEdgesSupport) Creates a new immutable succinct directed graph from a supplier of streams of edges, choosing whether to support incoming edges.SuccinctIntDirectedGraph
(int numVertices, List<Pair<Integer, Integer>> edges) Creates a new immutable succinct directed graph from an edge list, supporting both outgoing and incoming edges.SuccinctIntDirectedGraph
(int numVertices, List<Pair<Integer, Integer>> edges, boolean incomingEdgesSupport) Creates a new immutable succinct directed graph from an edge list, choosing whether to support incoming edges.SuccinctIntDirectedGraph
(Graph<Integer, E> graph) Creates a new immutable succinct directed graph from a given directed graph, supporting both outgoing and incoming edges.SuccinctIntDirectedGraph
(Graph<Integer, E> graph, boolean incomingEdgesSupport) Creates a new immutable succinct directed graph from a given directed graph, choosing whether to support incoming edges. 
Method Summary
Modifier and TypeMethodDescriptionprotected boolean
Ensures that the specified edge exists in this graph, or else throws exception.boolean
Returnstrue
if this graph contains the specified edge.boolean
containsEdge
(Integer sourceVertex, Integer targetVertex) Returnstrue
if and only if this graph contains an edge going from the source vertex to the target vertex.edgeSet()
Returns a set of the edges contained in this graph.it.unimi.dsi.fastutil.ints.IntSet
Returns a set of all edges touching the specified vertex.Returns an edge connecting source vertex to target vertex if such vertices and such edge exist in this graph.Returns the source vertex of an edge.Returns the target vertex of an edge.it.unimi.dsi.fastutil.ints.IntSet
incomingEdgesOf
(Integer target) Returns a set of all edges incoming into the specified vertex.int
inDegreeOf
(Integer vertex) Returns the "in degree" of the specified vertex.Access the graph using theGraphIterables
interface.int
outDegreeOf
(Integer vertex) Returns the "out degree" of the specified vertex.it.unimi.dsi.fastutil.ints.IntSet
outgoingEdgesOf
(Integer vertex) Returns a set of all edges outgoing from the specified vertex.Methods inherited from class org.jgrapht.sux4j.AbstractSuccinctDirectedGraph
degreeOf, getType
Methods inherited from class org.jgrapht.sux4j.AbstractSuccinctGraph
addEdge, addEdge, addVertex, addVertex, assertVertexExist, containsVertex, getAllEdges, getEdgeSupplier, getEdgeWeight, getVertexSupplier, removeEdge, removeEdge, removeVertex, setEdgeWeight, vertexSet
Methods inherited from class org.jgrapht.graph.AbstractGraph
equals, hashCode, removeAllEdges, removeAllEdges, removeAllEdges, removeAllVertices, toString, toStringFromSets
Methods inherited from class java.lang.Object
clone, finalize, getClass, notify, notifyAll, wait, wait, wait
Methods inherited from interface org.jgrapht.Graph
setEdgeWeight

Constructor Details

SuccinctIntDirectedGraph
Creates a new immutable succinct directed graph from a given directed graph, choosing whether to support incoming edges. Type Parameters:
E
 the graph edge type Parameters:
graph
 a directed graph: for good results, vertices should be numbered consecutively starting from 0.incomingEdgesSupport
 whether to support incoming edges or not.

SuccinctIntDirectedGraph
Creates a new immutable succinct directed graph from a given directed graph, supporting both outgoing and incoming edges. Type Parameters:
E
 the graph edge type Parameters:
graph
 a directed graph: for good results, vertices should be numbered consecutively starting from 0.

SuccinctIntDirectedGraph
public SuccinctIntDirectedGraph(int numVertices, List<Pair<Integer, Integer>> edges, boolean incomingEdgesSupport) Creates a new immutable succinct directed graph from an edge list, choosing whether to support incoming edges.This constructor just builds a
SparseIntDirectedGraph
and delegates to the main constructor. Parameters:
numVertices
 the number of vertices.edges
 the edge list.incomingEdgesSupport
 whether to support incoming edges or not. See Also:

SuccinctIntDirectedGraph
Creates a new immutable succinct directed graph from an edge list, supporting both outgoing and incoming edges.This constructor just builds a
SparseIntDirectedGraph
and delegates to the main constructor. Parameters:
numVertices
 the number of vertices.edges
 the edge list. See Also:

SuccinctIntDirectedGraph
public SuccinctIntDirectedGraph(int numVertices, int numEdges, Supplier<Stream<Pair<Integer, Integer>>> edges, boolean incomingEdgesSupport) Creates a new immutable succinct directed graph from a supplier of streams of edges, choosing whether to support incoming edges.This constructor just builds a
SparseIntDirectedGraph
and delegates to the main constructor. Parameters:
numVertices
 the number of vertices.numEdges
 the number of edges.edges
 a supplier of streams of edges.incomingEdgesSupport
 whether to support incoming edges or not. See Also:

SuccinctIntDirectedGraph
public SuccinctIntDirectedGraph(int numVertices, int numEdges, Supplier<Stream<Pair<Integer, Integer>>> edges) Creates a new immutable succinct directed graph from a supplier of streams of edges, supporting both outgoing and incoming edges.This constructor just builds a
SparseIntDirectedGraph
and delegates to the main constructor. Parameters:
numVertices
 the number of vertices.numEdges
 the number of edges.edges
 a supplier of streams of edges. See Also:


Method Details

containsEdge
Description copied from interface:Graph
Returnstrue
if this graph contains the specified edge. More formally, returnstrue
if and only if this graph contains an edgee2
such thate.equals(e2)
. If the specified edge isnull
returnsfalse
. Specified by:
containsEdge
in interfaceGraph<Integer,
Integer>  Parameters:
e
 edge whose presence in this graph is to be tested. Returns:
true
if this graph contains the specified edge.

edgeSet
Description copied from interface:Graph
Returns a set of the edges contained in this graph. The set is backed by the graph, so changes to the graph are reflected in the set. If the graph is modified while an iteration over the set is in progress, the results of the iteration are undefined.The graph implementation may maintain a particular set ordering (e.g. via
LinkedHashSet
) for deterministic iteration, but this is not required. It is the responsibility of callers who rely on this behavior to only use graph implementations which support it. 
edgesOf
Description copied from interface:Graph
Returns a set of all edges touching the specified vertex. If no edges are touching the specified vertex returns an empty set. 
inDegreeOf
Description copied from interface:Graph
Returns the "in degree" of the specified vertex.The "in degree" of a vertex in a directed graph is the number of inward directed edges from that vertex. See http://mathworld.wolfram.com/Indegree.html.
In the case of undirected graphs this method returns the number of edges touching the vertex. Edges with same source and target vertices (selfloops) are counted twice.
 Specified by:
inDegreeOf
in interfaceGraph<Integer,
Integer>  Parameters:
vertex
 vertex whose degree is to be calculated. Returns:
 the degree of the specified vertex.

incomingEdgesOf
Description copied from interface:Graph
Returns a set of all edges incoming into the specified vertex.In the case of undirected graphs this method returns all edges touching the vertex, thus, some of the returned edges may have their source and target vertices in the opposite order.
 Specified by:
incomingEdgesOf
in interfaceGraph<Integer,
Integer>  Parameters:
target
 the vertex for which the list of incoming edges to be returned. Returns:
 a set of all edges incoming into the specified vertex.

outDegreeOf
Description copied from interface:Graph
Returns the "out degree" of the specified vertex.The "out degree" of a vertex in a directed graph is the number of outward directed edges from that vertex. See http://mathworld.wolfram.com/Outdegree.html.
In the case of undirected graphs this method returns the number of edges touching the vertex. Edges with same source and target vertices (selfloops) are counted twice.
 Specified by:
outDegreeOf
in interfaceGraph<Integer,
Integer>  Parameters:
vertex
 vertex whose degree is to be calculated. Returns:
 the degree of the specified vertex.

outgoingEdgesOf
Description copied from interface:Graph
Returns a set of all edges outgoing from the specified vertex.In the case of undirected graphs this method returns all edges touching the vertex, thus, some of the returned edges may have their source and target vertices in the opposite order.
 Specified by:
outgoingEdgesOf
in interfaceGraph<Integer,
Integer>  Parameters:
vertex
 the vertex for which the list of outgoing edges to be returned. Returns:
 a set of all edges outgoing from the specified vertex.

getEdgeSource
Description copied from interface:Graph
Returns the source vertex of an edge. For an undirected graph, source and target are distinguishable designations (but without any mathematical meaning). Specified by:
getEdgeSource
in interfaceGraph<Integer,
Integer>  Parameters:
e
 edge of interest Returns:
 source vertex

getEdgeTarget
Description copied from interface:Graph
Returns the target vertex of an edge. For an undirected graph, source and target are distinguishable designations (but without any mathematical meaning). Specified by:
getEdgeTarget
in interfaceGraph<Integer,
Integer>  Parameters:
e
 edge of interest Returns:
 target vertex

getEdge
Description copied from interface:Graph
Returns an edge connecting source vertex to target vertex if such vertices and such edge exist in this graph. Otherwise returnsnull
. If any of the specified vertices isnull
returnsnull
In undirected graphs, the returned edge may have its source and target vertices in the opposite order.

containsEdge
Description copied from interface:Graph
Returnstrue
if and only if this graph contains an edge going from the source vertex to the target vertex. In undirected graphs the same result is obtained when source and target are inverted. If any of the specified vertices does not exist in the graph, or if isnull
, returnsfalse
. Specified by:
containsEdge
in interfaceGraph<Integer,
Integer>  Overrides:
containsEdge
in classAbstractGraph<Integer,
Integer>  Parameters:
sourceVertex
 source vertex of the edge.targetVertex
 target vertex of the edge. Returns:
true
if this graph contains the specified edge. See Also:

assertEdgeExist
Ensures that the specified edge exists in this graph, or else throws exception. Parameters:
e
 edge Returns:
true
if this assertion holds. Throws:
IllegalArgumentException
 if specified edge does not exist in this graph.

iterables
Description copied from interface:Graph
Access the graph using theGraphIterables
interface. This allows accessing graphs without the restrictions imposed by 32bit arithmetic. Moreover, graph implementations are free to implement this interface without explicitly materializing intermediate results.
