Added iterative DFS algorithm.
diff --git a/utils/misc/src/main/java/org/onlab/graph/DepthFirstSearch.java b/utils/misc/src/main/java/org/onlab/graph/DepthFirstSearch.java
new file mode 100644
index 0000000..c4d3f83
--- /dev/null
+++ b/utils/misc/src/main/java/org/onlab/graph/DepthFirstSearch.java
@@ -0,0 +1,167 @@
+package org.onlab.graph;
+
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Map;
+import java.util.Set;
+import java.util.Stack;
+
+/**
+ * DFS graph search algorithm implemented via iteration rather than recursion.
+ */
+public class DepthFirstSearch<V extends Vertex, E extends Edge<V>>
+ extends AbstractGraphPathSearch<V, E> {
+
+ /**
+ * Graph edge types as classified by the DFS algorithm.
+ */
+ public static enum EdgeType {
+ TREE_EDGE, FORWARD_EDGE, BACK_EDGE, CROSS_EDGE
+ }
+
+ @Override
+ public SpanningTreeResult search(Graph<V, E> graph, V src, V dst,
+ EdgeWeight<V, E> weight) {
+ checkArguments(graph, src, dst);
+
+ // Prepare the search result.
+ SpanningTreeResult result = new SpanningTreeResult(src, dst);
+
+ // The source vertex has cost 0, of course.
+ result.updateVertex(src, null, 0.0, true);
+
+ // Track finished vertexes and keep a stack of vertexes that have been
+ // started; start this stack with the source on it.
+ Set<V> finished = new HashSet<>();
+ Stack<V> stack = new Stack<>();
+ stack.push(src);
+
+ while (!stack.isEmpty()) {
+ V vertex = stack.peek();
+ if (vertex.equals(dst)) {
+ // If we have reached our destination, bail.
+ break;
+ }
+
+ double cost = result.cost(vertex);
+ boolean tangent = false;
+
+ // Visit all egress edges of the current vertex.
+ for (E edge : graph.getEdgesFrom(vertex)) {
+ // If we have seen the edge already, skip it.
+ if (result.isEdgeMarked(edge)) {
+ continue;
+ }
+
+ // Examine the destination of the current edge.
+ V nextVertex = edge.dst();
+ if (!result.hasCost(nextVertex)) {
+ // If this vertex have not finished this vertex yet,
+ // not started it, then start it as a tree-edge.
+ result.markEdge(edge, EdgeType.TREE_EDGE);
+ double newCost = cost + (weight == null ? 1.0 : weight.weight(edge));
+ result.updateVertex(nextVertex, edge, newCost, true);
+ stack.push(nextVertex);
+ tangent = true;
+ break;
+
+ } else if (!finished.contains(nextVertex)) {
+ // We started the vertex, but did not yet finish it, so
+ // it must be a back-edge.
+ result.markEdge(edge, EdgeType.BACK_EDGE);
+ } else {
+ // The target has been finished already, so what we have
+ // here is either a forward-edge or a cross-edge.
+ result.markEdge(edge, isForwardEdge(result, edge) ?
+ EdgeType.FORWARD_EDGE : EdgeType.CROSS_EDGE);
+ }
+ }
+
+ // If we have not been sent on a tangent search and reached the
+ // end of the current scan normally, mark the node as finished
+ // and pop it off the vertex stack.
+ if (!tangent) {
+ finished.add(vertex);
+ stack.pop();
+ }
+ }
+
+ // Finally, but the paths on the search result and return.
+ result.buildPaths();
+ return result;
+ }
+
+ /**
+ * Determines whether the specified edge is a forward edge using the
+ * accumulated set of parent edges for each vertex.
+ *
+ * @param result search result
+ * @param edge edge to be classified
+ * @return true if the edge is a forward edge
+ */
+ protected boolean isForwardEdge(DefaultResult result, E edge) {
+ // Follow the parent edges until we hit the edge source vertex
+ V target = edge.src();
+ V vertex = edge.dst();
+ Set<E> parentEdges;
+ while ((parentEdges = result.parents.get(vertex)) != null) {
+ for (E parentEdge : parentEdges) {
+ vertex = parentEdge.src();
+ if (vertex.equals(target)) {
+ return true;
+ }
+ }
+ }
+ return false;
+ }
+
+ /**
+ * Graph search result which includes edge classification for building
+ * a spanning tree.
+ */
+ public class SpanningTreeResult extends DefaultResult {
+
+ protected final Map<E, EdgeType> edges = new HashMap<>();
+
+ /**
+ * Creates a new spanning tree result.
+ *
+ * @param src search source
+ * @param dst optional search destination
+ */
+ public SpanningTreeResult(V src, V dst) {
+ super(src, dst);
+ }
+
+ /**
+ * Returns the map of edge type.
+ *
+ * @return edge to edge type bindings
+ */
+ public Map<E, EdgeType> edges() {
+ return edges;
+ }
+
+ /**
+ * Indicates whether or not the edge has been marked with type.
+ *
+ * @param edge edge to test
+ * @return true if the edge has been marked already
+ */
+ boolean isEdgeMarked(E edge) {
+ return edges.containsKey(edge);
+ }
+
+ /**
+ * Marks the edge with the specified type.
+ *
+ * @param edge edge to mark
+ * @param type edge type
+ */
+ void markEdge(E edge, EdgeType type) {
+ edges.put(edge, type);
+ }
+
+ }
+
+}
diff --git a/utils/misc/src/test/java/org/onlab/graph/DepthFirstSearchTest.java b/utils/misc/src/test/java/org/onlab/graph/DepthFirstSearchTest.java
new file mode 100644
index 0000000..8881e84
--- /dev/null
+++ b/utils/misc/src/test/java/org/onlab/graph/DepthFirstSearchTest.java
@@ -0,0 +1,81 @@
+package org.onlab.graph;
+
+import org.junit.Test;
+
+import java.util.Set;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertTrue;
+import static org.onlab.graph.DepthFirstSearch.EdgeType;
+
+/**
+ * Test of the DFS algorithm.
+ */
+public class DepthFirstSearchTest extends AbstractGraphPathSearchTest {
+
+ @Override
+ protected DepthFirstSearch<TestVertex, TestEdge> graphSearch() {
+ return new DepthFirstSearch<>();
+ }
+
+ @Test
+ public void defaultGraphTest() {
+ executeDefaultTest(3, 6, 5.0, 12.0);
+ executeBroadSearch();
+ }
+
+ @Test
+ public void defaultHopCountWeight() {
+ weight = null;
+ executeDefaultTest(3, 6, 3.0, 6.0);
+ executeBroadSearch();
+ }
+
+ protected void executeDefaultTest(int minLength, int maxLength,
+ double minCost, double maxCost) {
+ g = new AdjacencyListsGraph<>(vertices(), edges());
+ DepthFirstSearch<TestVertex, TestEdge> search = graphSearch();
+
+ DepthFirstSearch<TestVertex, TestEdge>.SpanningTreeResult result =
+ search.search(g, A, H, weight);
+ Set<Path<TestVertex, TestEdge>> paths = result.paths();
+ assertEquals("incorrect path count", 1, paths.size());
+
+ Path path = paths.iterator().next();
+ System.out.println(path);
+ assertEquals("incorrect src", A, path.src());
+ assertEquals("incorrect dst", H, path.dst());
+
+ int l = path.edges().size();
+ assertTrue("incorrect path length " + l,
+ minLength <= l && l <= maxLength);
+ assertTrue("incorrect path cost " + path.cost(),
+ minCost <= path.cost() && path.cost() <= maxCost);
+
+ System.out.println(result.edges());
+ printPaths(paths);
+ }
+
+ public void executeBroadSearch() {
+ g = new AdjacencyListsGraph<>(vertices(), edges());
+ DepthFirstSearch<TestVertex, TestEdge> search = graphSearch();
+
+ // Perform narrow path search to a specific destination.
+ DepthFirstSearch<TestVertex, TestEdge>.SpanningTreeResult result =
+ search.search(g, A, null, weight);
+ assertEquals("incorrect paths count", 7, result.paths().size());
+
+ int[] types = new int[]{0, 0, 0, 0};
+ for (EdgeType t : result.edges().values()) {
+ types[t.ordinal()] += 1;
+ }
+ assertEquals("incorrect tree-edge count", 7,
+ types[EdgeType.TREE_EDGE.ordinal()]);
+ assertEquals("incorrect back-edge count", 1,
+ types[EdgeType.BACK_EDGE.ordinal()]);
+ assertEquals("incorrect cross-edge & forward-edge count", 4,
+ types[EdgeType.FORWARD_EDGE.ordinal()] +
+ types[EdgeType.CROSS_EDGE.ordinal()]);
+ }
+
+}