Doh! Forgot to actually check for negative cycles in relaxEdge.
diff --git a/utils/misc/src/main/java/org/onlab/graph/AbstractGraphPathSearch.java b/utils/misc/src/main/java/org/onlab/graph/AbstractGraphPathSearch.java
index 7dad767..4217804 100644
--- a/utils/misc/src/main/java/org/onlab/graph/AbstractGraphPathSearch.java
+++ b/utils/misc/src/main/java/org/onlab/graph/AbstractGraphPathSearch.java
@@ -148,15 +148,22 @@
* If possible, relax the specified edge using the supplied base cost
* and edge-weight function.
*
- * @param e edge to be relaxed
- * @param cost base cost to reach the edge destination vertex
- * @param ew optional edge weight function
+ * @param e edge to be relaxed
+ * @param cost base cost to reach the edge destination vertex
+ * @param ew optional edge weight function
+ * @param forbidNegatives if true negative values will forbid the link
* @return true if the edge was relaxed; false otherwise
*/
- boolean relaxEdge(E e, double cost, EdgeWeight<V, E> ew) {
+ boolean relaxEdge(E e, double cost, EdgeWeight<V, E> ew,
+ boolean... forbidNegatives) {
V v = e.dst();
double oldCost = cost(v);
- double newCost = cost + (ew == null ? 1.0 : ew.weight(e));
+ double hopCost = ew == null ? 1.0 : ew.weight(e);
+ if (hopCost < 0 && forbidNegatives.length == 1 && forbidNegatives[0]) {
+ return false;
+ }
+
+ double newCost = cost + hopCost;
boolean relaxed = newCost < oldCost;
boolean same = Math.abs(newCost - oldCost) < samenessThreshold;
if (same || relaxed) {
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 535da09..8f1bad0 100644
--- a/utils/misc/src/main/java/org/onlab/graph/DijkstraGraphSearch.java
+++ b/utils/misc/src/main/java/org/onlab/graph/DijkstraGraphSearch.java
@@ -40,7 +40,7 @@
if (cost < Double.MAX_VALUE) {
// If the vertex is reachable, relax all its egress edges.
for (E e : graph.getEdgesFrom(nearest)) {
- result.relaxEdge(e, cost, weight);
+ result.relaxEdge(e, cost, weight, true);
}
}
diff --git a/utils/misc/src/test/java/org/onlab/graph/DijkstraGraphSearchTest.java b/utils/misc/src/test/java/org/onlab/graph/DijkstraGraphSearchTest.java
index 840eddd..ccc769f 100644
--- a/utils/misc/src/test/java/org/onlab/graph/DijkstraGraphSearchTest.java
+++ b/utils/misc/src/test/java/org/onlab/graph/DijkstraGraphSearchTest.java
@@ -91,4 +91,21 @@
executeSearch(graphSearch(), graph, A, E, weight, 3, 3.0);
}
+ @Test
+ public void negativeWeights() {
+ graph = new AdjacencyListsGraph<>(of(A, B, C, D, E, F, G),
+ of(new TestEdge(A, B, 1),
+ new TestEdge(A, C, -1),
+ new TestEdge(B, D, 1),
+ new TestEdge(D, A, -2),
+ new TestEdge(C, D, 1),
+ new TestEdge(D, E, 1),
+ new TestEdge(D, F, 1),
+ new TestEdge(E, G, 1),
+ new TestEdge(F, G, 1),
+ new TestEdge(G, A, -5),
+ new TestEdge(A, G, 4)));
+ executeSearch(graphSearch(), graph, A, G, weight, 3, 4.0);
+ }
+
}