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/DijkstraGraphSearch.java b/utils/misc/src/main/java/org/onlab/graph/DijkstraGraphSearch.java
index 4990718..0dd1898 100644
--- a/utils/misc/src/main/java/org/onlab/graph/DijkstraGraphSearch.java
+++ b/utils/misc/src/main/java/org/onlab/graph/DijkstraGraphSearch.java
@@ -27,16 +27,15 @@
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) {
// Use the default result to remember cumulative costs and parent
// edges to each each respective vertex.
DefaultResult result = new DefaultResult(src, dst, maxPaths);
// Cost to reach the source vertex is 0 of course.
- result.updateVertex(src, null, 0.0, false);
+ result.updateVertex(src, null, weigher.getInitialWeight(), false);
if (graph.getEdges().isEmpty()) {
result.buildPaths();
@@ -56,11 +55,12 @@
}
// Find its cost and use it to determine if the vertex is reachable.
- double cost = result.cost(nearest);
- if (cost < Double.MAX_VALUE) {
+ if (result.hasCost(nearest)) {
+ Weight cost = result.cost(nearest);
+
// If the vertex is reachable, relax all its egress edges.
for (E e : graph.getEdgesFrom(nearest)) {
- result.relaxEdge(e, cost, weight, true);
+ result.relaxEdge(e, cost, weigher, true);
}
}
@@ -84,8 +84,16 @@
@Override
public int compare(V v1, V v2) {
- double delta = result.cost(v2) - result.cost(v1);
- return delta < 0 ? -1 : (delta > 0 ? 1 : 0);
+ //not accessed vertices should be pushed to the back of the queue
+ if (!result.hasCost(v1) && !result.hasCost(v2)) {
+ return 0;
+ } else if (!result.hasCost(v1)) {
+ return -1;
+ } else if (!result.hasCost(v2)) {
+ return 1;
+ }
+
+ return result.cost(v2).compareTo(result.cost(v1));
}
}