Package org.jgrapht.graph

Class 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

    • 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