Lazier lazy path search
Change-Id: I6f966e221a07d0886742d9315439d94c1e2ce1bd
diff --git a/utils/misc/src/main/java/org/onlab/graph/LazyKShortestPathsSearch.java b/utils/misc/src/main/java/org/onlab/graph/LazyKShortestPathsSearch.java
index 5039c51..106508d 100644
--- a/utils/misc/src/main/java/org/onlab/graph/LazyKShortestPathsSearch.java
+++ b/utils/misc/src/main/java/org/onlab/graph/LazyKShortestPathsSearch.java
@@ -27,9 +27,11 @@
import java.util.Queue;
import java.util.Set;
import java.util.Spliterator;
+import java.util.function.Supplier;
import java.util.stream.Stream;
import java.util.stream.StreamSupport;
+import com.google.common.base.Suppliers;
import com.google.common.collect.ComparisonChain;
import com.google.common.collect.ImmutableList;
import com.google.common.collect.Sets;
@@ -81,7 +83,7 @@
final List<Path<V, E>> resultPaths = new ArrayList<>(); // A
final Queue<Path<V, E>> potentialPaths = new PriorityQueue<>(pathComparator); // B
- Path<V, E> next;
+ Supplier<Path<V, E>> next;
ShortestPathIterator(Graph<V, E> graph,
V src, V dst,
@@ -92,25 +94,32 @@
this.weigher = checkNotNull(weigher);
maskingWeigher = new InnerEdgeWeigher(weigher);
- next = shortest.search(graph, src, dst, weigher, 1)
- .paths().stream().findFirst().orElse(null);
+ next = Suppliers.ofInstance(
+ shortest.search(graph, src, dst, weigher, 1)
+ .paths().stream().findFirst().orElse(null));
}
@Override
public boolean hasNext() {
- return next != null;
+ return next.get() != null;
}
@Override
public Path<V, E> next() {
- if (next == null) {
+ if (next.get() == null) {
throw new NoSuchElementException("No more path between " + src + "-" + dst);
}
// lastPath: the path to return at the end of this call
- Path<V, E> lastPath = next;
+ Path<V, E> lastPath = next.get();
resultPaths.add(lastPath);
+ next = Suppliers.memoize(() -> computeNext(lastPath));
+
+ return lastPath;
+ }
+
+ private Path<V, E> computeNext(Path<V, E> lastPath) {
/// following is basically Yen's k-shortest path algorithm
// start searching for next path
@@ -133,11 +142,12 @@
shortest.search(graph, spurNode, dst, maskingWeigher, 1)
.paths().stream().findAny().ifPresent(spurPath -> {
+
List<E> totalPath = ImmutableList.<E>builder()
.addAll(rootPathEdgeList)
.addAll(spurPath.edges())
.build();
- potentialPaths.add(path(totalPath));
+ potentialPaths.add(path(totalPath));
});
// Restore all removed paths and nodes
@@ -145,12 +155,10 @@
}
if (potentialPaths.isEmpty()) {
- next = null;
+ return null;
} else {
- next = potentialPaths.poll();
+ return potentialPaths.poll();
}
-
- return lastPath;
}
private Path<V, E> path(List<E> edges) {