Interface Weights<K,T>
- Type Parameters:
K
- the elements (vertices/edges) typeT
- 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>
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 Summary
Modifier and TypeMethodDescriptionstatic <E,
T, WeightsT extends Weights<E, T>>
WeightsTcreateExternalEdgesWeights
(Graph<?, E> g, Class<? super T> type) Create an external edge weights container.static <E,
T, WeightsT extends Weights<E, T>>
WeightsTcreateExternalEdgesWeights
(Graph<?, E> g, Class<? super T> type, T defVal) Create an external edge weights container with default values.static <V,
T, WeightsT extends Weights<V, T>>
WeightsTcreateExternalVerticesWeights
(Graph<V, ?> g, Class<? super T> type) Create an external vertex weights container.static <V,
T, WeightsT extends Weights<V, T>>
WeightsTcreateExternalVerticesWeights
(Graph<V, ?> g, Class<? super T> type, T defVal) Create an external vertex weights container with default values.Get the default weight of this weights container.Get the weight associated with the given element.void
Set the weight associated with the given element.
-
Method Details
-
getAsObj
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
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 createExternalVerticesWeightsWeightsT extends Weights<V, T>> (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
or0
for primitives.- Type Parameters:
V
- the vertices typeT
- the weights typeWeightsT
- the weights container, used to avoid casts of containers of primitive types such asWeightsInt
,WeightsDouble
ect.- Parameters:
g
- a graphtype
- the type of the weights, used for primitive types weights- Returns:
- a new weights container
-
createExternalVerticesWeights
static <V,T, WeightsT createExternalVerticesWeightsWeightsT extends Weights<V, T>> (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 typeT
- the weights typeWeightsT
- the weights container, used to avoid casts of containers of primitive types such asWeightsInt
,WeightsDouble
ect.- Parameters:
g
- a graphtype
- the type of the weights, used for primitive types weightsdefVal
- default value use for the weights container- Returns:
- a new weights container
-
createExternalEdgesWeights
static <E,T, WeightsT createExternalEdgesWeightsWeightsT extends Weights<E, T>> (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
or0
for primitives.- Type Parameters:
E
- the edges typeT
- the weights typeWeightsT
- the weights container, used to avoid casts of containers of primitive types such asIWeightsInt
,IWeightsDouble
ect.- Parameters:
g
- a graphtype
- the type of the weights, used for primitive types weights- Returns:
- a new weights container
-
createExternalEdgesWeights
static <E,T, WeightsT createExternalEdgesWeightsWeightsT extends Weights<E, T>> (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 typeT
- the weights typeWeightsT
- the weights container, used to avoid casts of containers of primitive types such asIWeightsInt
,IWeightsDouble
ect.- Parameters:
g
- a graphtype
- the type of the weights, used for primitive types weightsdefVal
- default value use for the weights container- Returns:
- a new weights container
-