Package com.jgalgo.graph

Interface Weights<W>

  • Type Parameters:
    W - the weights type
    All Known Subinterfaces:
    Weights.Bool, Weights.Byte, Weights.Char, Weights.Double, Weights.Float, Weights.Int, Weights.Long, Weights.Short
    public interface Weights<W>
    Weights of graph vertices or edges.

    A weights object associated with the edges (vertices) of a graph support getting and setting a weight value for each edge (vertex) using the get(int) and set(int, Object) methods. Such weights are useful for various algorithms such as ShortestPathSingleSource or MatchingAlgorithm 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 in bipartite graphs.

    An exiting graph expose two methods to add new type of weights associated with its vertices or edges: Graph.addVerticesWeights(Object, Class) and Graph.addEdgesWeights(Object, 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
 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 w = g.addEdgesWeights("weightsKey", double.class);
 w.set(e1, 1.2);
 w.set(e2, 3.1);
 w.set(e3, 15.1);

 // Calculate the shortest paths from v1 to all other vertices
 ShortestPathSingleSource ssspAlgo = ShortestPathSingleSource.newBuilder().build();
 ShortestPathSingleSource.Result ssspRes = ssspAlgo.computeShortestPaths(g, w, 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 + ")");
 }

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

    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.addEdgeSwapListener(IndexSwapListener)).

    Author:
    Barak Ugav

    • Field Detail

      • DefaultBipartiteWeightKey

        static final Object DefaultBipartiteWeightKey
        The default vertices weight key of the bipartite property.

        A bipartite graph is a graph in which the vertices are partitioned into two sets V1,V2 and there are no edges between two vertices u,v if they are both in V1 or both in V2. Some algorithms expect a bipartite graph as an input, and the partition V1,V2 is expected to be a vertex boolean weight keyed by DefaultBipartiteWeightKey. To use a different key, the algorithms expose a setBipartiteVerticesWeightKey(Object) function.

    • Method Detail

      • get

        W get​(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

      • set

        void set​(int id,
         W 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

      • defaultWeight

        W defaultWeight()
        Get the default weight of this weights container.

        The default weight is the weight associated with all ids that were not explicitly set using set(int, Object).

        Returns:
        the default weight of this weights container.

      • createExternalVerticesWeights

        static <E,​WeightsT extends Weights<E>> WeightsT createExternalVerticesWeights​(Graph g,
                                                                                    Class<? super E> 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:
        E - the weights type
        WeightsT - the weights container, used to avoid casts of containers of primitive types
        Parameters:
        g - a graph
        type - the type of the weights, used for primitive types weights
        Returns:
        a new weights container

      • createExternalVerticesWeights

        static <E,​WeightsT extends Weights<E>> WeightsT createExternalVerticesWeights​(Graph g,
                                                                                    Class<? super E> type,
                                                                                    E 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:
        E - the weights type
        WeightsT - the weights container, used to avoid casts of containers of primitive types
        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 <E,​WeightsT extends Weights<E>> WeightsT createExternalEdgesWeights​(Graph g,
                                                                                 Class<? super E> 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:
        E - the weights type
        WeightsT - the weights container, used to avoid casts of containers of primitive types
        Parameters:
        g - a graph
        type - the type of the weights, used for primitive types weights
        Returns:
        a new weights container

      • createExternalEdgesWeights

        static <E,​WeightsT extends Weights<E>> WeightsT createExternalEdgesWeights​(Graph g,
                                                                                 Class<? super E> type,
                                                                                 E 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:
        E - the weights type
        WeightsT - the weights container, used to avoid casts of containers of primitive types
        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