Package com.jgalgo.graph

Interface IWeights<T>

  • Type Parameters:
    T - the weights type
    All Superinterfaces:
    Weights<Integer,​T>
    All Known Subinterfaces:
    IWeightsBool, IWeightsByte, IWeightsChar, IWeightsDouble, IWeightsFloat, IWeightsInt, IWeightsLong, IWeightsObj<T>, IWeightsShort
    public interface IWeights<T>
extends Weights<Integer,​T>
    Weights of int graph vertices or edges.

    This interface is a specific version of Weights for IntGraph.

    A weights object associated with the edges (vertices) of a graph support getting and setting a weight value for each edge (vertex). Such weights are useful for various algorithms such as ShortestPathSingleSource or MatchingAlgo to assigned the cost of edges. Another example is boolean weights used to represent the partition of vertices in bipartite graphs, which is used by algorithms such as Hopcroft-Karp algorithm for cardinality maximum matching.

    An exiting graph expose two methods to add new type of weights associated with its vertices or edges: Graph.addVerticesWeights(String, Class) and Graph.addEdgesWeights(String, Class). Weights of primitive types can be created by passing a primitive class to these methods, for example this snippet demonstrate how a double weights type can be added to a graph, and then passed to ShortestPathSingleSource algorithm: 

     
 // 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 + ")");
 }

    A default weight can be provided in the time of the weights container. The default weight will be returned for every edge (vertex) that was not explicitly set another value.

    There are type specific weights interfaces for both primitives and objects, such as IWeightsDouble, IWeightsInt, IWeightsObj, etc. The super interface IWeights allow to get and set weights as objects, and should not be used when the type of the weights is known. The sub interfaces expose methods to get and set weights as the specific type, for example IWeightsInt.get(int).

    If the weights container is associated with the edges of an index graph, and the graph implementation chooses to perform some swaps and renames to the edges, the weights container will update automatically (see IndexGraph.addEdgeRemoveListener(IndexRemoveListener)).

    The IWeights interface can be used for edges or vertices, depending on how it was created. In this documentation we use the term 'element' to refer to either an edge or a vertex.

    Author:
    Barak Ugav

    • Method Detail

      • getAsObj

        T getAsObj​(int id)
        Get the weight associated with the given id.
        Parameters:
        id - an id of edge/vertex
        Returns:
        the weight associated with the given id

      • getAsObj

        @Deprecated
default T getAsObj​(Integer id)
        Deprecated.
        Description copied from interface: Weights
        Get the weight associated with the given element.

        This method return the weight as an object, and should not be used when its known what type the weights are.

        Specified by:
        getAsObj in interface Weights<Integer,​T>
        Parameters:
        id - an element (edge/vertex)
        Returns:
        the weight associated with the given element

      • setAsObj

        void setAsObj​(int id,
              T weight)
        Set the weight associated with the given id.
        Parameters:
        id - an id of edge/vertex
        weight - new weight that will be associated with the given id

      • setAsObj

        @Deprecated
default void setAsObj​(Integer id,
                      T weight)
        Deprecated.
        Description copied from interface: Weights
        Set the weight associated with the given element.

        This method accept the weight as an object, and should not be used when its known what type the weights are.

        Specified by:
        setAsObj in interface Weights<Integer,​T>
        Parameters:
        id - an element (edge/vertex)
        weight - new weight that will be associated with the given element

      • createExternalVerticesWeights

        static <T,​WeightsT extends IWeights<T>> WeightsT createExternalVerticesWeights​(IntGraph g,
                                                                                     Class<? super T> type)
        Create an external vertex weights container.

        An external weights container is a container that associate a weight to each vertex in the graph, but does not update when the graph is updated. This method should be used only in cases where the graph is immutable.

        Type Parameters:
        T - the weights type
        WeightsT - the weights container, used to avoid casts of containers of primitive types such as IWeightsInt, IWeightsDouble ect.
        Parameters:
        g - a graph
        type - the type of the weights, used for primitive types weights
        Returns:
        a new weights container

      • createExternalVerticesWeights

        static <T,​WeightsT extends IWeights<T>> WeightsT createExternalVerticesWeights​(IntGraph g,
                                                                                     Class<? super T> type,
                                                                                     T defVal)
        Create an external vertex weights container with default values.

        An external weights container is a container that associate a weight to each vertex in the graph, but does not update when the graph is updated. This method should be used only in cases where the graph is immutable.

        Type Parameters:
        T - the weights type
        WeightsT - the weights container, used to avoid casts of containers of primitive types such as IWeightsInt, IWeightsDouble ect.
        Parameters:
        g - a graph
        type - the type of the weights, used for primitive types weights
        defVal - default value use for the weights container
        Returns:
        a new weights container

      • createExternalEdgesWeights

        static <T,​WeightsT extends IWeights<T>> WeightsT createExternalEdgesWeights​(IntGraph g,
                                                                                  Class<? super T> type)
        Create an external edge weights container.

        An external weights container is a container that associate a weight to each edge in the graph, but does not update when the graph is updated. This method should be used only in cases where the graph is immutable.

        Type Parameters:
        T - the weights type
        WeightsT - the weights container, used to avoid casts of containers of primitive types such as IWeightsInt, IWeightsDouble ect.
        Parameters:
        g - a graph
        type - the type of the weights, used for primitive types weights
        Returns:
        a new weights container

      • createExternalEdgesWeights

        static <T,​WeightsT extends IWeights<T>> WeightsT createExternalEdgesWeights​(IntGraph g,
                                                                                  Class<? super T> type,
                                                                                  T defVal)
        Create an external edge weights container with default values.

        An external weights container is a container that associate a weight to each edge in the graph, but does not update when the graph is updated. This method should be used only in cases where the graph is immutable.

        Type Parameters:
        T - the weights type
        WeightsT - the weights container, used to avoid casts of containers of primitive types such as IWeightsInt, IWeightsDouble ect.
        Parameters:
        g - a graph
        type - the type of the weights, used for primitive types weights
        defVal - default value use for the weights container
        Returns:
        a new weights container