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:
    IWeightFunctionInt

    • Field Detail

      • CardinalityWeightFunction

        static final IWeightFunctionInt 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:
        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

      • 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