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 type

E - the graph edge type

All Implemented Interfaces:

Serializable, Graph<V,E>

public class AsWeightedGraph<V,E>
extends GraphDelegator<V,E>
implements 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:

1. Explicitly through a map which contains a mapping from an edge to a weight
2. Implicitly through a function which computes a weight for a given edge

In the first way, the map is used to lookup edge weights. In the second way, a function is provided to calculate the weight of an edge. If the map does not contain a particular edge, or the function does not provide a weight for a particular edge, the @link{getEdgeWeight} call is propagated to the backing graph. Finally, the view provides a @link{setEdgeWeight} method. This method behaves differently depending on how the view is constructed. See @link{setEdgeWeight} for details.

See Also:

Serialized Form

Field Summary

Fields inherited from interface org.jgrapht.Graph

DEFAULT_EDGE_WEIGHT

Constructor Summary

Constructors

Constructor and Description
AsWeightedGraph(Graph<V,E> graph, Function<E,Double> weightFunction, boolean cacheWeights, boolean writeWeightsThrough) Constructor for AsWeightedGraph which uses a weight function to compute edge weights.
AsWeightedGraph(Graph<V,E> graph, Map<E,Double> weights) Constructor for AsWeightedGraph where the weights are provided through a map.
AsWeightedGraph(Graph<V,E> graph, Map<E,Double> weights, boolean writeWeightsThrough) Constructor for AsWeightedGraph which allows weight write propagation to be requested explicitly.

Method Summary

Modifier and Type	Method and 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,
                       Map<E,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:

NullPointerException - if the graph or the weights are null.

AsWeightedGraph

public AsWeightedGraph(Graph<V,E> graph,
                       Map<E,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 created

weights - the map containing the edge weights

writeWeightsThrough - if set to true, the weights will get propagated to the backing graph in the setEdgeWeight() method.

Throws:

NullPointerException - if the graph or the weights are null

IllegalArgumentException - if writeWeightsThrough is set to true and graph is not a weighted graph

AsWeightedGraph

public AsWeightedGraph(Graph<V,E> graph,
                       Function<E,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. If cacheWeights is set to true, the weight of an edge returned by the weightFunction 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. If cacheWeights is set to false, 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 created

weightFunction - function which maps an edge to a weight

cacheWeights - if set to true, weights are cached once computed by the weight function

writeWeightsThrough - if set to true, the weight set directly by the @link{setEdgeWeight} method will be propagated to the backing graph.

Throws:

NullPointerException - if the graph or the weight function is null

IllegalArgumentException - if writeWeightsThrough is set to true and graph 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, if cacheWeights is set to true 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 interface Graph<V,E>

Overrides:

getEdgeWeight in class GraphDelegator<V,E>

Parameters:

e - edge of interest

Returns:

the edge weight

Throws:

NullPointerException - if the edge is null

setEdgeWeight

public void setEdgeWeight(E e,
                          double weight)

Assigns a weight to an edge. If writeWeightsThrough is set to true, 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 when cacheWeights 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 interface Graph<V,E>

Overrides:

setEdgeWeight in class GraphDelegator<V,E>

Parameters:

e - edge on which to set weight

weight - new weight for edge

Throws:

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.

Specified by:

getType in interface Graph<V,E>

Overrides:

getType in class GraphDelegator<V,E>

Returns:

the graph type