Package com.jgalgo.graph

Interface WeightFunction

  • All Superinterfaces:
    Comparator<Integer>, IntComparator
    All Known Subinterfaces:
    WeightFunction.Int, Weights.Byte, Weights.Double, Weights.Float, Weights.Int, Weights.Long, Weights.Short
    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
extends IntComparator
    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 MatchingAlgorithm 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 vertex cover.

    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
 Graph g = GraphFactory.newDirected().newGraph();
 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
 Weights.Double weights = g.addEdgesWeights("weightsKey", double.class);
 weights.set(e1, 1.2);
 weights.set(e2, 3.1);
 weights.set(e3, 15.1);
 EdgeWeightFunc weightFunc = weights;

 // Calculate the shortest paths from v1 to all other vertices
 ShortestPathSingleSource ssspAlgo = ShortestPathSingleSource.newBuilder().build();
 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).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)) {
 	int u = g.edgeSource(e), v = g.edgeTarget(e);
 	System.out.println(" " + e + "(" + u + ", " + v + ")");
 }
    Author:
    Barak Ugav

    • Field Detail

      • CardinalityWeightFunction

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

    • Method Detail

      • weight

        double weight​(int element)
        Get the weight of an element.
        Parameters:
        element - an element identifier
        Returns:
        the weight of the element
        Throws:
        IndexOutOfBoundsException - if element is not a valid element identifier in the graph

      • compare

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