Package com.jgalgo.graph

Interface WeightFunction<K>

Type Parameters:
K - the elements (vertices/edges) type
All Superinterfaces:
Comparator<K>
All Known Subinterfaces:
IWeightFunction, IWeightFunctionInt, IWeightsByte, IWeightsDouble, IWeightsFloat, IWeightsInt, IWeightsLong, IWeightsShort, WeightFunctionInt<K>, WeightsByte<K>, WeightsDouble<K>, WeightsFloat<K>, WeightsInt<K>, WeightsLong<K>, WeightsShort<K>
Functional Interface:
This is a functional interface and can therefore be used as the assignment target for a lambda expression or method reference.
@FunctionalInterface public interface WeightFunction<K> extends Comparator<K>
Weight function that maps graph edges or vertices to weights.

This interface is usually used as weight function of edges, for example in algorithms such as ShortestPathSingleSource, MinimumSpanningTree and MatchingAlgo, in which the algorithm try to find a set of edges satisfying some constraint while minimizing/maximizing some objective function based on the weights of the edges. But it can represent weights assigned to vertices, in algorithms such as VertexCover.

An instance of this interface represent weights of edges only or vertices only, and never both. As this function represent weights for either edges or vertex, the documentation refer to these edges/vertices as elements. 

 
 // Create an undirected graph with three vertices and edges between them
 Graph<String, Integer> g = Graph.newUndirected();
 g.addVertex("Berlin");
 g.addVertex("Leipzig");
 g.addVertex("Dresden");
 g.addEdge("Berlin", "Leipzig", 9);
 g.addEdge("Berlin", "Dresden", 13);
 g.addEdge("Dresden", "Leipzig", 14);

 // Assign some weights to the edges
 WeightsDouble<Integer> w = g.addEdgesWeights("distance-km", double.class);
 w.set(9, 191.1);
 w.set(13, 193.3);
 w.set(14, 121.3);

 // Calculate the shortest paths from Berlin to all other cities
 ShortestPathSingleSource ssspAlgo = ShortestPathSingleSource.newInstance();
 ShortestPathSingleSource.Result<String, Integer> ssspRes = ssspAlgo.computeShortestPaths(g, w, "Berlin");

 // Print the shortest path from Berlin to Leipzig
 System.out.println("Distance from Berlin to Leipzig is: " + ssspRes.distance("Leipzig"));
 System.out.println("The shortest path from Berlin to Leipzig is:");
 for (Integer e : ssspRes.getPath("Leipzig").edges()) {
 	String u = g.edgeSource(e), v = g.edgeTarget(e);
 	System.out.println(" " + e + "(" + u + ", " + v + ")");
 }
Author:
Barak Ugav
See Also:

  • Field Details

    • CardinalityWeightFunction

      static final WeightFunctionInt<?> CardinalityWeightFunction
      A weight function that assign a weight of 1 to any element.

  • Method Details

    • weight

      double weight(K element)
      Get the weight of an element.
      Parameters:
      element - an element identifier
      Returns:
      the weight of the element
      Throws:
      NoSuchVertexException - if this weight function maps vertices and element is not a valid vertex identifier in the graph
      NoSuchEdgeException - if this weight function maps edges and element is not a valid edge identifier in the graph

    • compare

      default int compare(K e1, K e2)
      Compare two elements by their weights.
      Specified by:
      compare in interface Comparator<K>

    • weightSum

      default double weightSum(Iterable<K> elements)
      Get the sum of the weights of multiple elements.
      Parameters:
      elements - a collection of elements
      Returns:
      the sum of the weights of the elements

    • weightSum

      static <K> double weightSum(WeightFunction<K> weightFunc, Iterable<K> elements)
      Get the sum of the weights of multiple elements.

      This method is equivalent to weightSum(Iterable), but it also support null weight function, which is treated is cardinality weight function.

      Type Parameters:
      K - the elements (vertices/edges) type
      Parameters:
      weightFunc - the weight function to use, or null to use cardinality weight function
      elements - a collection of elements
      Returns:
      the sum of the weights of the elements

    • cardinalityWeightFunction

      static <K> WeightFunctionInt<K> cardinalityWeightFunction()
      Get the cardinality weight function.

      The cardinality weight function assign a weight of 1 to any element. The function always return the same object, which can be accessed directed via CardinalityWeightFunction. This is method is exposed only to avoid unchecked casts with generics.

      Type Parameters:
      K - the type of the elements
      Returns:
      the cardinality weight function

    • replaceNullWeightFunc

      static <K> WeightFunction<K> replaceNullWeightFunc(WeightFunction<K> weightFunc)
      Replace null weight function with CardinalityWeightFunction.
      Type Parameters:
      K - the elements (vertices/edges) type
      Parameters:
      weightFunc - the weight function to replace
      Returns:
      CardinalityWeightFunction if weightFunc is null, otherwise weightFunc

    • replaceNullWeightFunc

      static <K> WeightFunctionInt<K> replaceNullWeightFunc(WeightFunctionInt<K> weightFunc)
      Replace null weight function with CardinalityWeightFunction.
      Type Parameters:
      K - the elements (vertices/edges) type
      Parameters:
      weightFunc - the weight function to replace
      Returns:
      CardinalityWeightFunction if weightFunc is null, otherwise weightFunc

    • isCardinality

      static boolean isCardinality(WeightFunction<?> weightFunc)
      Check if the given weight function is the cardinality weight function.

      This function does not checks that the weight function maps every element to 1, but only compares it to the static weight functions CardinalityWeightFunction and IWeightFunction.CardinalityWeightFunction, or null.

      Parameters:
      weightFunc - the weight function to check
      Returns:
      true if the weight function is the cardinality weight function, false

    • isInteger

      static boolean isInteger(WeightFunction<?> weightFunc)
      Check if the given weight function is an integer weight function.

      This function does not checks that the weight function maps every element to an integer, but only checks that the weight function is an instance of WeightFunctionInt or it is null.

      Parameters:
      weightFunc - the weight function to check
      Returns:
      true if the weight function is an integer weight function, false