Package com.jgalgo.graph

Interface IWeightFunction

All Superinterfaces:
Comparator<Integer>, IntComparator, WeightFunction<Integer>
All Known Subinterfaces:
IWeightFunctionInt, IWeightsByte, IWeightsDouble, IWeightsFloat, IWeightsInt, IWeightsLong, IWeightsShort
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 IWeightFunction extends WeightFunction<Integer>, IntComparator
Weight function that maps graph edges or vertices of IntGraph to weights.

This interface is a specification of WeightFunction for IntGraph.

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 a directed graph with three vertices and edges between them
 IntGraph g = IntGraph.newDirected();
 int v1 = g.addVertex();
 int v2 = g.addVertex();
 int v3 = g.addVertex();
 int e1 = g.addEdge(v1, v2);
 int e2 = g.addEdge(v2, v3);
 int e3 = g.addEdge(v1, v3);

 // Assign some weights to the edges
 IWeightsDouble weights = g.addEdgesWeights("weightsKey", double.class);
 weights.set(e1, 1.2);
 weights.set(e2, 3.1);
 weights.set(e3, 15.1);
 IWeightFunction weightFunc = weights;

 // Calculate the shortest paths from v1 to all other vertices
 ShortestPathSingleSource ssspAlgo = ShortestPathSingleSource.newInstance();
 ShortestPathSingleSource.Result ssspRes = ssspAlgo.computeShortestPaths(g, weightFunc, v1);

 // Print the shortest path from v1 to v3
 assert ssspRes.distance(v3) == 4.3;
 assert ssspRes.getPath(v3).edges().equals(IntList.of(e1, e2));
 System.out.println("Distance from v1 to v3 is: " + ssspRes.distance(v3));
 System.out.println("The shortest path from v1 to v3 is:");
 for (int e : ssspRes.getPath(v3).edges()) {
 	int u = g.edgeSource(e), v = g.edgeTarget(e);
 	System.out.println(" " + e + "(" + u + ", " + v + ")");
 }
Author:
Barak Ugav
See Also:

  • Field Details

    • CardinalityWeightFunction

      static final IWeightFunctionInt CardinalityWeightFunction
      A weight function that assign a weight of 1 to any element.

  • Method Details

    • weight

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

    • weight

      @Deprecated default double weight(Integer element)
      Deprecated.
      Please use weight(int) instead to avoid un/boxing.
      Get the weight of an element.
      Specified by:
      weight in interface WeightFunction<Integer>
      Parameters:
      element - an element identifier
      Returns:
      the weight of the element

    • compare

      default int compare(int e1, int e2)
      Compare two elements by their weights.
      Specified by:
      compare in interface IntComparator

    • compare

      @Deprecated default int compare(Integer e1, Integer e2)
      Deprecated.
      Please use compare(int, int) instead to avoid un/boxing.
      Compare two elements by their weights.
      Specified by:
      compare in interface Comparator<Integer>
      Specified by:
      compare in interface IntComparator
      Specified by:
      compare in interface WeightFunction<Integer>

    • weightSum

      default double weightSum(Iterable<Integer> elements)
      Description copied from interface: WeightFunction
      Get the sum of the weights of multiple elements.
      Specified by:
      weightSum in interface WeightFunction<Integer>
      Parameters:
      elements - a collection of elements
      Returns:
      the sum of the weights of the elements

    • weightSum

      static double weightSum(IWeightFunction weightFunc, IntIterable 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.

      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

    • replaceNullWeightFunc

      static IWeightFunction replaceNullWeightFunc(IWeightFunction weightFunc)
      Replace null weight function with CardinalityWeightFunction.
      Parameters:
      weightFunc - the weight function to replace
      Returns:
      CardinalityWeightFunction if weightFunc is null, otherwise weightFunc

    • replaceNullWeightFunc

      static IWeightFunctionInt replaceNullWeightFunc(IWeightFunctionInt weightFunc)
      Replace null weight function with CardinalityWeightFunction.
      Parameters:
      weightFunc - the weight function to replace
      Returns:
      CardinalityWeightFunction if weightFunc is null, otherwise weightFunc