Package org.jgrapht.graph
Class AsWeightedGraph<V,E>
- java.lang.Object
-
- org.jgrapht.graph.AbstractGraph<V,E>
-
- org.jgrapht.graph.GraphDelegator<V,E>
-
- org.jgrapht.graph.AsWeightedGraph<V,E>
-
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- All Implemented Interfaces:
java.io.Serializable
,Graph<V,E>
public class AsWeightedGraph<V,E> extends GraphDelegator<V,E> implements java.io.Serializable, Graph<V,E>
Provides a weighted view of a graph. The class stores edge weights internally. All @link{getEdgeWeight} calls are handled by this view; all other graph operations are propagated to the graph backing this view.This class can be used to make an unweighted graph weighted, to override the weights of a weighted graph, or to provide different weighted views of the same underlying graph. For instance, the edges of a graph representing a road network might have two weights associated with them: a travel time and a travel distance. Instead of creating two weighted graphs of the same network, one would simply create two weighted views of the same underlying graph.
This class offers two ways to associate a weight with an edge:
- Explicitly through a map which contains a mapping from an edge to a weight
- Implicitly through a function which computes a weight for a given edge
- See Also:
- Serialized Form
-
-
Field Summary
-
Fields inherited from interface org.jgrapht.Graph
DEFAULT_EDGE_WEIGHT
-
-
Constructor Summary
Constructors Constructor Description AsWeightedGraph(Graph<V,E> graph, java.util.function.Function<E,java.lang.Double> weightFunction, boolean cacheWeights, boolean writeWeightsThrough)
Constructor for AsWeightedGraph which uses a weight function to compute edge weights.AsWeightedGraph(Graph<V,E> graph, java.util.Map<E,java.lang.Double> weights)
Constructor for AsWeightedGraph where the weights are provided through a map.AsWeightedGraph(Graph<V,E> graph, java.util.Map<E,java.lang.Double> weights, boolean writeWeightsThrough)
Constructor for AsWeightedGraph which allows weight write propagation to be requested explicitly.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description double
getEdgeWeight(E e)
Returns the weight assigned to a given edge.GraphType
getType()
Get the graph type.void
setEdgeWeight(E e, double weight)
Assigns a weight to an edge.-
Methods inherited from class org.jgrapht.graph.GraphDelegator
addEdge, addEdge, addVertex, addVertex, containsEdge, containsVertex, degreeOf, edgeSet, edgesOf, getAllEdges, getDelegate, getEdge, getEdgeSource, getEdgeSupplier, getEdgeTarget, getVertexSupplier, incomingEdgesOf, inDegreeOf, outDegreeOf, outgoingEdgesOf, removeEdge, removeEdge, removeVertex, toString, vertexSet
-
Methods inherited from class org.jgrapht.graph.AbstractGraph
assertVertexExist, containsEdge, equals, hashCode, removeAllEdges, removeAllEdges, removeAllEdges, removeAllVertices, toStringFromSets
-
Methods inherited from class java.lang.Object
clone, finalize, getClass, notify, notifyAll, wait, wait, wait
-
Methods inherited from interface org.jgrapht.Graph
addEdge, addEdge, addVertex, addVertex, containsEdge, containsEdge, containsVertex, degreeOf, edgeSet, edgesOf, getAllEdges, getEdge, getEdgeSource, getEdgeSupplier, getEdgeTarget, getVertexSupplier, incomingEdgesOf, inDegreeOf, outDegreeOf, outgoingEdgesOf, removeAllEdges, removeAllEdges, removeAllVertices, removeEdge, removeEdge, removeVertex, setEdgeWeight, vertexSet
-
-
-
-
Constructor Detail
-
AsWeightedGraph
public AsWeightedGraph(Graph<V,E> graph, java.util.Map<E,java.lang.Double> weights)
Constructor for AsWeightedGraph where the weights are provided through a map. Invocations of the @link{setEdgeWeight} method will update the map. Moreover, calls to @link{setEdgeWeight} are propagated to the underlying graph.- Parameters:
graph
- the backing graph over which a weighted view is to be created.weights
- the map containing the edge weights.- Throws:
java.lang.NullPointerException
- if the graph or the weights are null.
-
AsWeightedGraph
public AsWeightedGraph(Graph<V,E> graph, java.util.Map<E,java.lang.Double> weights, boolean writeWeightsThrough)
Constructor for AsWeightedGraph which allows weight write propagation to be requested explicitly.- Parameters:
graph
- the backing graph over which an weighted view is to be createdweights
- the map containing the edge weightswriteWeightsThrough
- if set to true, the weights will get propagated to the backing graph in thesetEdgeWeight()
method.- Throws:
java.lang.NullPointerException
- if the graph or the weights are nulljava.lang.IllegalArgumentException
- ifwriteWeightsThrough
is set to true andgraph
is not a weighted graph
-
AsWeightedGraph
public AsWeightedGraph(Graph<V,E> graph, java.util.function.Function<E,java.lang.Double> weightFunction, boolean cacheWeights, boolean writeWeightsThrough)
Constructor for AsWeightedGraph which uses a weight function to compute edge weights. When the weight of an edge is queried, the weight function is invoked. IfcacheWeights
is set totrue
, the weight of an edge returned by theweightFunction
after its first invocation is stored in a map. The weight of an edge returned by subsequent calls to @link{getEdgeWeight} for the same edge will then be retrieved directly from the map, instead of re-invoking the weight function. IfcacheWeights
is set tofalse
, each invocation of the @link{getEdgeWeight} method will invoke the weight function. Caching the edge weights is particularly useful when pre-computing all edge weights is expensive and it is expected that the weights of only a subset of all edges will be queried.- Parameters:
graph
- the backing graph over which an weighted view is to be createdweightFunction
- function which maps an edge to a weightcacheWeights
- if set totrue
, weights are cached once computed by the weight functionwriteWeightsThrough
- if set totrue
, the weight set directly by the @link{setEdgeWeight} method will be propagated to the backing graph.- Throws:
java.lang.NullPointerException
- if the graph or the weight function is nulljava.lang.IllegalArgumentException
- ifwriteWeightsThrough
is set to true andgraph
is not a weighted graph
-
-
Method Detail
-
getEdgeWeight
public double getEdgeWeight(E e)
Returns the weight assigned to a given edge. If weights are provided through a map, first a map lookup is performed. If the edge is not found, the @link{getEdgeWeight} method of the underlying graph is invoked instead. If, on the other hand, the weights are provided through a function, this method will first attempt to lookup the weight of an edge in the cache (that is, ifcacheWeights
is set totrue
in the constructor). If caching was disabled, or the edge could not be found in the cache, the weight function is invoked. If the function does not provide a weight for a given edge, the call is again propagated to the underlying graph.- Specified by:
getEdgeWeight
in interfaceGraph<V,E>
- Overrides:
getEdgeWeight
in classGraphDelegator<V,E>
- Parameters:
e
- edge of interest- Returns:
- the edge weight
- Throws:
java.lang.NullPointerException
- if the edge is null
-
setEdgeWeight
public void setEdgeWeight(E e, double weight)
Assigns a weight to an edge. IfwriteWeightsThrough
is set totrue
, the same weight is set in the backing graph. If this class was constructed using a weight function, it only makes sense to invoke this method whencacheWeights
is set to true. This method can then be used to preset weights in the cache, or to overwrite existing values.- Specified by:
setEdgeWeight
in interfaceGraph<V,E>
- Overrides:
setEdgeWeight
in classGraphDelegator<V,E>
- Parameters:
e
- edge on which to set weightweight
- new weight for edge- Throws:
java.lang.NullPointerException
- if the edge is null
-
getType
public GraphType getType()
Description copied from class:GraphDelegator
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.
-
-