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

Class SparseIntDirectedWeightedGraph

  • All Implemented Interfaces:
    java.io.Serializable, Graph<java.lang.Integer,​java.lang.Integer>
    public class SparseIntDirectedWeightedGraph
extends SparseIntDirectedGraph
implements java.io.Serializable
    Sparse directed weighted 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 edge weights are maintained in an array indexed by the edge identifier.

    The graph is weighted. While unmodifiable with respect to the structure of the graph, the edge weights can be changed even after the graph is constructed.

    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
    See Also:
    Serialized Form

    • Field Detail

      • weights

        protected double[] weights
        The edge weights

    • Constructor Detail

      • SparseIntDirectedWeightedGraph

        public SparseIntDirectedWeightedGraph​(int numVertices,
                                      java.util.List<Triple<java.lang.Integer,​java.lang.Integer,​java.lang.Double>> edges)
        Create a new graph from an edge list.
        Parameters:
        numVertices - the number of vertices
        edges - the edge list with additional weights

    • Method Detail

      • getType

        public GraphType getType()
        Description copied from interface: Graph
        Get the graph type. The graph type can be used to query for additional metadata such as whether the graph supports directed or undirected edges, self-loops, multiple (parallel) edges, weights, etc.
        Specified by:
        getType in interface Graph<java.lang.Integer,​java.lang.Integer>
        Overrides:
        getType in class SparseIntDirectedGraph
        Returns:
        the graph type

      • getEdgeWeight

        public double getEdgeWeight​(java.lang.Integer e)
        Description copied from interface: Graph
        Returns the weight assigned to a given edge. Unweighted graphs return 1.0 (as defined by Graph.DEFAULT_EDGE_WEIGHT), allowing weighted-graph algorithms to apply to them when meaningful.
        Specified by:
        getEdgeWeight in interface Graph<java.lang.Integer,​java.lang.Integer>
        Overrides:
        getEdgeWeight in class SparseIntDirectedGraph
        Parameters:
        e - edge of interest
        Returns:
        edge weight

      • setEdgeWeight

        public void setEdgeWeight​(java.lang.Integer e,
                          double weight)
        Description copied from interface: Graph
        Assigns a weight to an edge.
        Specified by:
        setEdgeWeight in interface Graph<java.lang.Integer,​java.lang.Integer>
        Overrides:
        setEdgeWeight in class SparseIntDirectedGraph
        Parameters:
        e - edge on which to set weight
        weight - new weight for edge