2
\$\begingroup\$

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?

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ How should I go about "packaging" algorithms? Should I have a factory class and provide static methods performing them? \$\endgroup\$ – coderodde Jan 15 '16 at 14:23
  • 1
    \$\begingroup\$ @coderodde Well, DFS is a way to traverse - iterate through - the graph. You could build an iterator for the graph that traverses it in a depth-first fashion. The Topological Sort algorithm just sorts the nodes of a graph, so it just needs to return an enumeration - sorted enumeration - of the nodes. That can be done in a method of the Graph class. \$\endgroup\$ – Gentian Kasa Jan 15 '16 at 14:34
  • \$\begingroup\$ @coderodde another way is to implement DFS as a method and make it return and enumeration of the visited nodes (in the order they were visited). \$\endgroup\$ – Gentian Kasa Jan 15 '16 at 14:39
  • \$\begingroup\$ The 201x Java fad for handling one after the other may be Stream/Spliterator. Don't even mention legacy classes. I like (occasional) "multi"-level continue/breaks - just don't continue with an else-statement. \$\endgroup\$ – greybeard Jan 15 '16 at 19:12
  • \$\begingroup\$ @greybeard I'm taking your word for it. I stopped working with Java 5 years ago so I don't know the current API very much. I agree with you on the (occasional) continue/break thing, but that's just a matter of personal taste I'd say. \$\endgroup\$ – Gentian Kasa Jan 15 '16 at 21:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.