Vector cost proposed to TST on 2016-07-13
First part implemented: weight interface introduced and integrated, default weight implementation added.
Change-Id: Ia46f1b44139069aa171a3c13faf168351bd7cc56
diff --git a/utils/misc/src/main/java/org/onlab/graph/BellmanFordGraphSearch.java b/utils/misc/src/main/java/org/onlab/graph/BellmanFordGraphSearch.java
index 88aca6b..9bd6c63 100644
--- a/utils/misc/src/main/java/org/onlab/graph/BellmanFordGraphSearch.java
+++ b/utils/misc/src/main/java/org/onlab/graph/BellmanFordGraphSearch.java
@@ -23,22 +23,21 @@
extends AbstractGraphPathSearch<V, E> {
@Override
- public Result<V, E> search(Graph<V, E> graph, V src, V dst,
- EdgeWeight<V, E> weight, int maxPaths) {
- checkArguments(graph, src, dst);
+ protected Result<V, E> internalSearch(Graph<V, E> graph, V src, V dst,
+ EdgeWeigher<V, E> weigher, int maxPaths) {
// Prepare the graph search result.
DefaultResult result = new DefaultResult(src, dst, maxPaths);
// The source vertex has cost 0, of course.
- result.updateVertex(src, null, 0.0, true);
+ result.updateVertex(src, null, weigher.getInitialWeight(), true);
int max = graph.getVertexes().size() - 1;
for (int i = 0; i < max; i++) {
// Relax, if possible, all egress edges of the current vertex.
for (E edge : graph.getEdges()) {
if (result.hasCost(edge.src())) {
- result.relaxEdge(edge, result.cost(edge.src()), weight);
+ result.relaxEdge(edge, result.cost(edge.src()), weigher);
}
}
}
@@ -46,7 +45,7 @@
// Remove any vertexes reached by traversing edges with negative weights.
for (E edge : graph.getEdges()) {
if (result.hasCost(edge.src())) {
- if (result.relaxEdge(edge, result.cost(edge.src()), weight)) {
+ if (result.relaxEdge(edge, result.cost(edge.src()), weigher)) {
result.removeVertex(edge.dst());
}
}
@@ -56,5 +55,4 @@
result.buildPaths();
return result;
}
-
}