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);
}
}