Iterative depth-first search and topological sort in Java

Question

This is the iterative depth-first search, that does not abuse the stack. Also, I gathered some information from DFS that may be useful; for example, I am able to do topological sort using the result information of DFS, and use topologically sorted graph node set in order to solve the shortest path problem in directed acyclic graphs (in literature, shortly dag). This post will present only DFS and topological sort. (I use this for the graph data structure.)

DepthFirstSearch.java:

package net.coderodde.graph.algo.traversal;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Objects;
import net.coderodde.graph.AbstractGraph;

/**
 * This class implements the depth-first search.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Jan 13, 2016)
 */
public class DepthFirstSearch {

    public DepthFirstSearch() {

    }

    private DepthFirstSearch(AbstractGraph graph) {
        int size      = graph.size();
        this.graph    = graph;
        colors        = new LinkedHashMap<>(size);
        startTimes    = new LinkedHashMap<>(size);
        endTimes      = new LinkedHashMap<>(size);
        parents       = new LinkedHashMap<>(size);
        nodeStack     = new ArrayDeque<>(size);
        iteratorStack = new ArrayDeque<>(size);
        isAcyclic     = true;
    }

    private int                      time;
    private boolean                  isAcyclic;
    private Map<Integer, NodeColor>  colors;
    private Map<Integer, Integer>    startTimes;
    private Map<Integer, Integer>    endTimes;
    private Map<Integer, Integer>    parents;
    private AbstractGraph            graph;
    private Deque<Integer>           nodeStack;
    private Deque<Iterator<Integer>> iteratorStack;

    public DepthFirstSearchResult traverseGraph(AbstractGraph graph) {
        Objects.requireNonNull(graph, "The input graph is nul.");
        DepthFirstSearch state = new DepthFirstSearch(graph);
        return state.traverseGraph();
    }

    private DepthFirstSearchResult traverseGraph() {
        // Preprocess the graph.
        for (Integer nodeId : graph.getAllNodes()) {
            colors.put(nodeId, NodeColor.WHITE);
            parents.put(nodeId, null);
        }

        // Make sure every node is visited, i.e., there is no nodes left
        // with white color.
        for (Integer nodeId : graph.getAllNodes()) {
            if (colors.get(nodeId).equals(NodeColor.WHITE)) {
                nodeStack.addLast(nodeId);
                iteratorStack.addLast(graph.getChildrenOf(nodeId).iterator());
                visit();
            }
        }

        return new DepthFirstSearchResult(isAcyclic,
                                          colors,
                                          startTimes,
                                          endTimes,
                                          parents);
    }

    private void visit() {
        outer:
        while (!nodeStack.isEmpty()) {
            Integer currentNodeId = nodeStack.getLast();
            Iterator<Integer> currentNodeChildIterator = iteratorStack.getLast();

            if (!startTimes.containsKey(currentNodeId)) {
                startTimes.put(currentNodeId, ++time);
            }

            colors.put(currentNodeId, NodeColor.GRAY);

            while (currentNodeChildIterator.hasNext()) {
                Integer childNodeId = currentNodeChildIterator.next();

                if (colors.get(childNodeId).equals(NodeColor.WHITE)) {
                    nodeStack.addLast(childNodeId);
                    iteratorStack.addLast(graph.getChildrenOf(childNodeId).iterator());
                    parents.put(childNodeId, currentNodeId);
                    continue outer;
                } else if (colors.get(childNodeId).equals(NodeColor.GRAY)) {
                    isAcyclic = false;
                }
            }

            while (!iteratorStack.isEmpty() && !iteratorStack.getLast().hasNext()) {
                iteratorStack.removeLast();
                Integer nodeId = nodeStack.removeLast();
                endTimes.put(nodeId, ++time);
                colors.put(nodeId, NodeColor.BLACK);
            }
        }
    }
}

DepthFirstSearchResult.java:

package net.coderodde.graph.algo.traversal;

import java.util.Map;

/**
 * This class holds all result data computed by a depth-first search traversal.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Jan 13, 2016)
 */
public class DepthFirstSearchResult {

    private final boolean isAcyclic;
    private final Map<Integer, Integer> startingTimeMap;
    private final Map<Integer, Integer> finishingTimeMap;
    private final Map<Integer, Integer> parentMap;

    DepthFirstSearchResult(boolean isAcyclic,
                           Map<Integer, NodeColor> nodeColorMap,
                           Map<Integer, Integer> startingTimeMap,
                           Map<Integer, Integer> finishingTimeMap,
                           Map<Integer, Integer> parentMap) {
        this.isAcyclic        = isAcyclic;
        this.startingTimeMap  = startingTimeMap;
        this.finishingTimeMap = finishingTimeMap;
        this.parentMap        = parentMap;
    }

    public boolean isAcyclic() {
        return isAcyclic;
    }

    public Map<Integer, Integer> getStartingTimeMap() {
        return startingTimeMap;
    }

    public Map<Integer, Integer> getFinishingTimeMap() {
        return finishingTimeMap;
    }

    public Map<Integer, Integer> getParentMap() {
        return parentMap;
    }
}

NodeColor.java:

package net.coderodde.graph.algo.traversal;

/**
 * This enumeration enumerates all three colors considered by a depth-first
 * search traversal: 
 * <ul>
 *   <li>white,</li>
 *   <li>gray,</li>
 *   <li>black.</li>
 * </ul>
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Jan 13, 2016)
 */
enum NodeColor {
    WHITE,
    GRAY,
    BLACK
}

GraphIsNotAcyclicException.java:

package net.coderodde.graph.algo.misc;

/**
 * This class implements an exception thrown whenever an acyclic graph is
 * expected and none is available.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Jan 15, 2016)
 */
public class GraphIsNotAcyclicException extends RuntimeException {

    public GraphIsNotAcyclicException() {
        super("The graph is not acyclic.");
    }
}

TopologicalSort.java:

package net.coderodde.graph.algo.misc;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import net.coderodde.graph.DirectedGraph;
import net.coderodde.graph.algo.traversal.DepthFirstSearch;
import net.coderodde.graph.algo.traversal.DepthFirstSearchResult;

/**
 * This class implements the topological sort.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Jan 15, 2016)
 */
public class TopologicalSort {

    /**
     * Computes a topological sort of a directed graph. The order might not be
     * unique.
     * 
     * @param graph the graph to topologically sort.
     * @return the list of nodes in some topological order.
     * @throws GraphIsNotAcyclicException if the input graph is not acyclic.
     */
    public List<Integer> sort(DirectedGraph graph) {
        Objects.requireNonNull(graph, "The input graph is null.");
        DepthFirstSearchResult data = 
                new DepthFirstSearch().traverseGraph(graph);

        if (!data.isAcyclic()) {
            throw new GraphIsNotAcyclicException();
        }

        List<Integer> ret = new ArrayList<>(graph.getAllNodes());
        Map<Integer, Integer> map = data.getFinishingTimeMap();

        Collections.sort(ret, (Integer a, Integer b) -> {
            return Integer.compare(map.get(b), map.get(a));
        });

        return ret;
    }
}

So, how am I doing here?

Answer 1

There are some things here that I definitely don't like. Let's go with one thing at a time

---

Labels

This can be seen as a personal preference, but I'd avoid them. On SO there's a good discussion regarding them.

---

Naming

The naming seems good except for one case where you used ret instead of result or something similar.

---

Logic

This is the area I'd suggest some improvements. First of all, TopologicalSort and DepthFirstSearch are algorithms and not objects. They should become methods of graphs rather than independent classes.

That's the main issue IMO. Other than that, the NodeColor enum can be ignored. If I understood correctly you have a color for each status - not visited, visiting, visited - of the node. That logic can be replaced with the use of appropriate data structures. The graph already contains all the nodes. The visited nodes can be kept - for DFS - in a hash table. The nodes you are visiting can be kept - for DFS - in a stack. With the NodeColor enum you increase the quantity of memory needed for a node and that is gone for the entire lifetime of the node. If you use data structures you use the necessary memory only when you need it.

Let me know if anything's unclear.