Module org.jgrapht.opt

Package org.jgrapht.opt.graph.sparse

Class SparseIntUndirectedWeightedGraph

java.lang.Object

org.jgrapht.graph.AbstractGraph<Integer,Integer>

org.jgrapht.opt.graph.sparse.specifics.AbstractSparseSpecificsGraph<org.jgrapht.opt.graph.sparse.specifics.SparseGraphSpecifics>

org.jgrapht.opt.graph.sparse.SparseIntUndirectedGraph

org.jgrapht.opt.graph.sparse.SparseIntUndirectedWeightedGraph

All Implemented Interfaces:

Serializable, Graph<Integer,Integer>

public class SparseIntUndirectedWeightedGraph
extends SparseIntUndirectedGraph
implements Serializable

Sparse undirected 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 the boolean incidence matrix of the graph (rows are vertices and columns are edges) as Compressed Sparse Rows (CSR). In order to also support constant time source and target lookups from an edge identifier we also store the transposed of the incidence matrix again in compressed sparse row format. 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 Summary

Fields

Modifier and Type	Field	Description
protected double[]	weights	The edge weights

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

specifics, UNMODIFIABLE

Fields inherited from interface org.jgrapht.Graph

DEFAULT_EDGE_WEIGHT

Constructor Summary

Constructors

Constructor	Description
SparseIntUndirectedWeightedGraph(int numVertices, int numEdges, Supplier<Stream<Triple<Integer,Integer,Double>>> edges)	Create a new graph from an edge stream
SparseIntUndirectedWeightedGraph(int numVertices, List<Triple<Integer,Integer,Double>> edges)	Create a new graph from an edge list

Method Summary

Modifier and Type	Method	Description
double	getEdgeWeight(Integer e)	Returns the weight assigned to a given edge.
GraphType	getType()	Get the graph type.
void	setEdgeWeight(Integer e, double weight)	Assigns a weight to an edge.

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, getVertexSupplier, incomingEdgesOf, inDegreeOf, outDegreeOf, outgoingEdgesOf, removeEdge, removeEdge, removeVertex, 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

weights

protected double[] weights

The edge weights

Constructor Details

SparseIntUndirectedWeightedGraph

public SparseIntUndirectedWeightedGraph(int numVertices,
 List<Triple<Integer,Integer,Double>> edges)

Create a new graph from an edge list

Parameters:

numVertices - number of vertices

edges - edge list with weights

SparseIntUndirectedWeightedGraph

public SparseIntUndirectedWeightedGraph(int numVertices,
 int numEdges,
 Supplier<Stream<Triple<Integer,Integer,Double>>> edges)

Create a new graph from an edge stream

Parameters:

numVertices - number of vertices

numEdges - number of edges

edges - a supplier of an edge stream with weights

Method Details

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<Integer,Integer>

Overrides:

getType in class org.jgrapht.opt.graph.sparse.specifics.AbstractSparseSpecificsGraph<org.jgrapht.opt.graph.sparse.specifics.SparseGraphSpecifics>

Returns:

the graph type

getEdgeWeight

public double getEdgeWeight(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<Integer,Integer>

Overrides:

getEdgeWeight in class org.jgrapht.opt.graph.sparse.specifics.AbstractSparseSpecificsGraph<org.jgrapht.opt.graph.sparse.specifics.SparseGraphSpecifics>

Parameters:

e - edge of interest

Returns:

edge weight

setEdgeWeight

public void setEdgeWeight(Integer e,
 double weight)

Description copied from interface: Graph

Assigns a weight to an edge.

Specified by:

setEdgeWeight in interface Graph<Integer,Integer>

Overrides:

setEdgeWeight in class org.jgrapht.opt.graph.sparse.specifics.AbstractSparseSpecificsGraph<org.jgrapht.opt.graph.sparse.specifics.SparseGraphSpecifics>

Parameters:

e - edge on which to set weight

weight - new weight for edge