Module org.jgrapht.opt
Package org.jgrapht.opt.graph.sparse

Class SparseIntDirectedGraph

java.lang.Object
org.jgrapht.graph.AbstractGraph<java.lang.Integer,​java.lang.Integer>
org.jgrapht.opt.graph.sparse.specifics.AbstractSparseSpecificsGraph<org.jgrapht.opt.graph.sparse.specifics.SparseGraphSpecifics>
org.jgrapht.opt.graph.sparse.SparseIntDirectedGraph
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>
A sparse directed graph.

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.
Additional information about sparse representations can be found in the wikipedia.
Author:
Dimitrios Michail

  • Field Summary

    Fields 
    Modifier and Type Field Description
    protected static java.lang.String UNMODIFIABLE  

    Fields inherited from class org.jgrapht.opt.graph.sparse.specifics.AbstractSparseSpecificsGraph

    specifics

    Fields inherited from interface org.jgrapht.Graph

    DEFAULT_EDGE_WEIGHT

  • 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

    Methods inherited from class java.lang.Object

    clone, finalize, getClass, notify, notifyAll, wait, wait, wait

    Methods inherited from interface org.jgrapht.Graph

    iterables, setEdgeWeight

  • Field Details

  • 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 vertices
      edges - 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 vertices
      edges - the edge list
      incomingEdgesSupport - 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 vertices
      numEdges - the number of edges
      edges - the edge stream
      incomingEdgesSupport - whether to support incoming edges or not