Package com.jgalgo.graph

Interface Weights<K,T>

Type Parameters:
K - the elements (vertices/edges) type
T - the weights type
All Known Subinterfaces:
IWeights<T>, IWeightsBool, IWeightsByte, IWeightsChar, IWeightsDouble, IWeightsFloat, IWeightsInt, IWeightsLong, IWeightsObj<T>, IWeightsShort, WeightsBool<K>, WeightsByte<K>, WeightsChar<K>, WeightsDouble<K>, WeightsFloat<K>, WeightsInt<K>, WeightsLong<K>, WeightsObj<K,T>, WeightsShort<K>
public interface Weights<K,T>
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). 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). When a new weights is added to the edges (vertices) of a graph, it is added to ALL edges (vertices) of the graph. 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 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 + ")");
 }

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 WeightsDouble, WeightsInt, WeightsObj, etc. The super interface Weights 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 WeightsInt.get(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.addEdgeRemoveListener(IndexRemoveListener)).

The Weights 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 Details

    • getAsObj

      T getAsObj(K element)
      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.

      Parameters:
      element - an element (edge/vertex)
      Returns:
      the weight associated with the given element

    • setAsObj

      void setAsObj(K element, T weight)
      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.

      Parameters:
      element - an element (edge/vertex)
      weight - new weight that will be associated with the given element

    • defaultWeightAsObj

      T defaultWeightAsObj()
      Get the default weight of this weights container.

      The default weight is the weight associated with all ids that were not explicitly set. This method return the default weight as an object, and should not be used when its known what type the weights are.

      Returns:
      the default weight of this weights container

    • createExternalVerticesWeights

      static <V, T, WeightsT extends Weights<V, T>> WeightsT createExternalVerticesWeights(Graph<V,?> 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.

      The created weights container will have a default weight of null or 0 for primitives.

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

    • createExternalVerticesWeights

      static <V, T, WeightsT extends Weights<V, T>> WeightsT createExternalVerticesWeights(Graph<V,?> 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:
      V - the vertices type
      T - the weights type
      WeightsT - the weights container, used to avoid casts of containers of primitive types such as WeightsInt, WeightsDouble 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 <E, T, WeightsT extends Weights<E, T>> WeightsT createExternalEdgesWeights(Graph<?,E> 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.

      The created weights container will have a default weight of null or 0 for primitives.

      Type Parameters:
      E - the edges type
      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 <E, T, WeightsT extends Weights<E, T>> WeightsT createExternalEdgesWeights(Graph<?,E> 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:
      E - the edges type
      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