Non-Recursive DFS implementation by using a Stack

DFSNonrecursive.java

package graph.search.dfs;

import graph.entity.Vertex;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Stack;

/**
 * Non-Recursive DFS implementation by using an exclusive stack. Moreover, we have to keep <bold>iterators</bold> of  adjacency lists of each vertex,
 * so that iterators will continue to iterate from their final position.
 *
 */
public class DFSNonrecursive {

    public static int time = 0;

    public void dfsNonrecursive(ArrayList<Vertex> graph, Vertex source) {

        if (graph == null || source == null) {

            throw new IllegalArgumentException("Parameters can not be null");
        }

        initVertices(graph, source);

        HashMap<String, Iterator<Vertex>> iterMap = new HashMap<>();

        // add iterators into a hashmap with label of each vertex as key
        for (Vertex vertex : graph) {

            iterMap.put(vertex.getLabel(), vertex.getAdjList().iterator());
        }

        Stack<Vertex> stack = new Stack<>();

        time = time + 1;
        source.setExplored(true);
        source.setDiscoveryTime(time);
        stack.push(source);

        while (!stack.isEmpty()) {

            Vertex peek = stack.peek();

            // get the iterator of peek so that iterator will continue
            // from its last position.
            Iterator<Vertex> iterator = iterMap.get(peek.getLabel());

            if (iterator.hasNext()) {

                Vertex adjVertex = iterator.next();

                if (!adjVertex.isExplored()) {

                    time = time + 1;
                    adjVertex.setDiscoveryTime(time);
                    adjVertex.setExplored(true);
                    stack.push(adjVertex);
                }
            } else {

                time = time + 1;
                peek.setFinishedTime(time);
                stack.pop();
            }
        }

    }

    /**
     * Make all vertices undiscovered
     * 
     * @param graph
     */
    private void initVertices(ArrayList<Vertex> graph, Vertex source) {

        for (Vertex vertex : graph) {

            if (vertex != source)
                vertex.setExplored(false);
        }
    }
}

DFSNonRecursiveTest.java

package graph.search.dfs;

import static org.junit.Assert.assertEquals;
import graph.entity.Vertex;

import java.util.ArrayList;
import java.util.Arrays;

import org.junit.Before;
import org.junit.Test;

/**
 * Non-Recursive version of DFS.
 * 
 * @author buraktas
 *
 */
public class DFSNonRecursiveTest {

    private DFSNonrecursive   testClass;
    private ArrayList<Vertex> graph;

    @Before
    public void setUp() {

        testClass = new DFSNonrecursive();
        graph = new ArrayList<>();
    }

    @Test(expected = IllegalArgumentException.class)
    public void testNullGraph() {

        Vertex q = new Vertex("q");
        testClass.dfsNonrecursive(null, q);
    }

    @Test(expected = IllegalArgumentException.class)
    public void testNullSource() {

        testClass.dfsNonrecursive(graph, null);
    }

    @Test
    public void testDFS() {

        initGraph();
        testClass.dfsNonrecursive(graph, graph.get(0));

        assertEquals(10, graph.get(9).getDiscoveryTime());
        assertEquals(14, graph.get(8).getFinishedTime());

        for (Vertex vertex : graph) {

            System.out.println("Vertex : "
                               + vertex.getLabel()
                               + " Dis. Time : "
                               + vertex.getDiscoveryTime()
                               + " Fin. Time : "
                               + vertex.getFinishedTime());
        }
    }

    private void initGraph() {

        Vertex q = new Vertex("q");
        Vertex s = new Vertex("s");
        Vertex v = new Vertex("v");
        Vertex w = new Vertex("w");
        Vertex t = new Vertex("t");
        Vertex x = new Vertex("x");
        Vertex y = new Vertex("y");
        Vertex z = new Vertex("z");
        Vertex r = new Vertex("r");
        Vertex u = new Vertex("u");

        q.setAdjList(new ArrayList<>(Arrays.asList(s, t, w)));
        s.setAdjList(new ArrayList<>(Arrays.asList(v)));
        v.setAdjList(new ArrayList<>(Arrays.asList(w)));
        w.setAdjList(new ArrayList<>(Arrays.asList(s)));
        t.setAdjList(new ArrayList<>(Arrays.asList(x, y)));
        x.setAdjList(new ArrayList<>(Arrays.asList(z)));
        z.setAdjList(new ArrayList<>(Arrays.asList(x)));
        y.setAdjList(new ArrayList<>(Arrays.asList(q)));
        r.setAdjList(new ArrayList<>(Arrays.asList(u, y)));
        u.setAdjList(new ArrayList<>(Arrays.asList(y)));

        graph.add(q);
        graph.add(r);
        graph.add(s);
        graph.add(t);
        graph.add(u);
        graph.add(v);
        graph.add(w);
        graph.add(x);
        graph.add(y);
        graph.add(z);
    }
}

Vertex.java

package graph.entity;

import java.util.ArrayList;

public class Vertex {

    private boolean           explored;
    private ArrayList<Vertex> adjList;
    private final String      label;
    private int               discoveryTime;
    private int               finishedTime;

    public int getDiscoveryTime() {
        return discoveryTime;
    }

    public void setDiscoveryTime(int discoveryTime) {
        this.discoveryTime = discoveryTime;
    }

    public int getFinishedTime() {
        return finishedTime;
    }

    public void setFinishedTime(int finishedTime) {
        this.finishedTime = finishedTime;
    }

    public Vertex(String label) {
        this.label = label;
    }

    public boolean isExplored() {
        return explored;
    }

    public void setExplored(boolean explored) {
        this.explored = explored;
    }

    public ArrayList<Vertex> getAdjList() {
        return adjList;
    }

    public void setAdjList(ArrayList<Vertex> adjList) {
        this.adjList = adjList;
    }

    public String getLabel() {
        return label;
    }

}