- All Implemented Interfaces:
Graph<java.lang.Integer,java.lang.Integer>
- Direct Known Subclasses:
SparseIntDirectedWeightedGraph
public class SparseIntDirectedGraph
extends org.jgrapht.opt.graph.sparse.specifics.AbstractSparseSpecificsGraph<org.jgrapht.opt.graph.sparse.specifics.SparseGraphSpecifics>
Assuming the graph has $n$ vertices, the vertices are numbered from $0$ to $n-1$. Similarly, edges are numbered from $0$ to $m-1$ where $m$ is the total number of edges.
It stores two boolean incidence matrix of the graph (rows are vertices and columns are edges) as Compressed Sparse Rows (CSR). Constant time source and target lookups are provided by storing the edge lists in arrays. This is a classic format for write-once read-many use cases. Thus, the graph is unmodifiable.
The question of whether a sparse or dense representation is more appropriate is highly dependent on various factors such as the graph, the machine running the algorithm and the algorithm itself. Wilkinson defined a matrix as "sparse" if it has enough zeros that it pays to take advantage of them. For more details see
- Wilkinson, J. H. 1971. Linear algebra; part II: the algebraic eigenvalue problem. In Handbook for Automatic Computation, J. H. Wilkinson and C. Reinsch, Eds. Vol. 2. Springer-Verlag, Berlin, New York.
- Author:
- Dimitrios Michail
-
Field Summary
Fields Modifier and Type Field Description protected static java.lang.String
UNMODIFIABLE
-
Constructor Summary
Constructors Constructor Description SparseIntDirectedGraph(int numVertices, int numEdges, java.util.function.Supplier<java.util.stream.Stream<Pair<java.lang.Integer,java.lang.Integer>>> edges, IncomingEdgesSupport incomingEdgesSupport)
Create a new graph from an edge stream.SparseIntDirectedGraph(int numVertices, java.util.List<Pair<java.lang.Integer,java.lang.Integer>> edges)
Create a new graph from an edge list.SparseIntDirectedGraph(int numVertices, java.util.List<Pair<java.lang.Integer,java.lang.Integer>> edges, IncomingEdgesSupport incomingEdgesSupport)
Create a new graph from an edge list. -
Method Summary
Methods inherited from class org.jgrapht.opt.graph.sparse.specifics.AbstractSparseSpecificsGraph
addEdge, addEdge, addVertex, addVertex, containsEdge, containsVertex, degreeOf, edgeSet, edgesOf, getAllEdges, getEdge, getEdgeSource, getEdgeSupplier, getEdgeTarget, getEdgeWeight, getType, getVertexSupplier, incomingEdgesOf, inDegreeOf, outDegreeOf, outgoingEdgesOf, removeEdge, removeEdge, removeVertex, setEdgeWeight, vertexSet
Methods inherited from class org.jgrapht.graph.AbstractGraph
assertVertexExist, containsEdge, equals, hashCode, removeAllEdges, removeAllEdges, removeAllEdges, removeAllVertices, toString, toStringFromSets
-
Field Details
-
UNMODIFIABLE
protected static final java.lang.String UNMODIFIABLE- See Also:
- Constant Field Values
-
-
Constructor Details
-
SparseIntDirectedGraph
public SparseIntDirectedGraph(int numVertices, java.util.List<Pair<java.lang.Integer,java.lang.Integer>> edges)Create a new graph from an edge list.- Parameters:
numVertices
- the number of verticesedges
- the edge list
-
SparseIntDirectedGraph
public SparseIntDirectedGraph(int numVertices, java.util.List<Pair<java.lang.Integer,java.lang.Integer>> edges, IncomingEdgesSupport incomingEdgesSupport)Create a new graph from an edge list.- Parameters:
numVertices
- the number of verticesedges
- the edge listincomingEdgesSupport
- whether to support incoming edges or not
-
SparseIntDirectedGraph
public SparseIntDirectedGraph(int numVertices, int numEdges, java.util.function.Supplier<java.util.stream.Stream<Pair<java.lang.Integer,java.lang.Integer>>> edges, IncomingEdgesSupport incomingEdgesSupport)Create a new graph from an edge stream.- Parameters:
numVertices
- the number of verticesnumEdges
- the number of edgesedges
- the edge streamincomingEdgesSupport
- whether to support incoming edges or not
-