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

    • Field Detail

      • CardinalityWeightFunction

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

    • Method Detail

      • 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

      • 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