Added short-circuit to Dijkstra when there are no edges.
Change-Id: I7e647ffceeae9de1736c5f36159c33d882bdb9f2
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 e0628c1..eada84c 100644
--- a/utils/misc/src/main/java/org/onlab/graph/DijkstraGraphSearch.java
+++ b/utils/misc/src/main/java/org/onlab/graph/DijkstraGraphSearch.java
@@ -38,6 +38,11 @@
// Cost to reach the source vertex is 0 of course.
result.updateVertex(src, null, 0.0, false);
+ if (graph.getEdges().isEmpty()) {
+ result.buildPaths();
+ return result;
+ }
+
// Use the min priority queue to progressively find each nearest
// vertex until we reach the desired destination, if one was given,
// or until we reach all possible destinations.
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 eceeab4..e11ccb2 100644
--- a/utils/misc/src/test/java/org/onlab/graph/DijkstraGraphSearchTest.java
+++ b/utils/misc/src/test/java/org/onlab/graph/DijkstraGraphSearchTest.java
@@ -17,6 +17,8 @@
import org.junit.Test;
+import java.text.DecimalFormat;
+import java.util.HashSet;
import java.util.Set;
import static com.google.common.collect.ImmutableSet.of;
@@ -123,4 +125,37 @@
executeSearch(graphSearch(), graph, A, G, weight, 3, 4.0);
}
+ @Test
+ public void disconnectedPerf() {
+ disconnected();
+ disconnected();
+ disconnected();
+ disconnected();
+ disconnected();
+ disconnected();
+ disconnected();
+ disconnected();
+ disconnected();
+ disconnected();
+ }
+
+
+ @Test
+ public void disconnected() {
+ Set<TestVertex> vertexes = new HashSet<>();
+ for (int i = 0; i < 200; i++) {
+ vertexes.add(new TestVertex("v" + i));
+ }
+
+ graph = new AdjacencyListsGraph<>(vertexes, of());
+
+ long start = System.nanoTime();
+ for (TestVertex src : vertexes) {
+ executeSearch(graphSearch(), graph, src, null, null, 0, 0);
+ }
+ long end = System.nanoTime();
+ DecimalFormat fmt = new DecimalFormat("#,###");
+ System.out.println("Compute cost is " + fmt.format(end - start) + " nanos");
+ }
+
}