Directed graph path enumerator in Java - follow-up

Question

I have refactored the graph path enumerator. DirectedGraphNode was not changed, so refer to the link above in case you want to have a look at it. The node type is not of a big concert for me, however, I just need something to find paths through. Now, all five points made by Misha, except the second one (deferring the path search), are incorporated.

Am I going in the right direction?

net.coderodde.graph.GraphPathEnumerator:

package net.coderodde.graph;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.Objects;
import java.util.Set;

/**
 * This class implements an iterator over all possible directed paths between
 * two argument nodes.
 *
 * @author Rodion "rodde" Efremov
 * @version 1.6
 */
public class GraphPathEnumerator {

    /**
     * Returns an iterator that iterates all distinct paths from 'source' to 
     * 'target'.
     * 
     * @param source the source node of each path.
     * @param target the target node of each path.
     * @return an iterator over all possible {@code source, target} - paths.
     */
    public Iterable<List<DirectedGraphNode>> 
        enumerate(DirectedGraphNode source,
                  DirectedGraphNode target) {
        Objects.requireNonNull(source, "The source node is null.");
        Objects.requireNonNull(target, "The target node is null.");
        return new DirectedGraphPathIterable(source, target);
    }

    /**
     * This inner class implements the {@code Iterable} over all possible paths.
     */
    private static final class DirectedGraphPathIterable 
    implements Iterable<List<DirectedGraphNode>> {

        private final DirectedGraphNode source;
        private final DirectedGraphNode target;

        DirectedGraphPathIterable(DirectedGraphNode source,
                                  DirectedGraphNode target) {
            this.source = source;
            this.target = target;
        }

        @Override
        public Iterator<List<DirectedGraphNode>> iterator() {
            return new DirectedGraphPathIterator(source, target);
        }

        /**
         * This inner class is the actual implementation of a path search 
         * algorithm. Basically, this employs depth-first search strategy.
         */
        private static final class DirectedGraphPathIterator 
        implements Iterator<List<DirectedGraphNode>> {

            /**
             * The target node we want to reach.
             */
            private final DirectedGraphNode target;

            /**
             * The set of nodes already traversed. We need this in order to not
             * go looping through cycles indefinitely.
             */
            private final Set<DirectedGraphNode> visitedSet = new HashSet<>();

            /**
             * This deque is for keeping the current path in order to be able
             * to reconstruct a path once the target node is reached.
             */
            private final Deque<DirectedGraphNode> nodeStack 
                    = new ArrayDeque<>();

            /**
             * This deque stores the search state.
             */
            private final Deque<Iterator<DirectedGraphNode>> iteratorStack
                    = new ArrayDeque<>();

            /**
             * This list stores a path being returned next.
             */
            private List<DirectedGraphNode> nextPath;

            DirectedGraphPathIterator(DirectedGraphNode source,
                                      DirectedGraphNode target) {
                this.target = target;

                visitedSet.add(source);
                // We add the source node stuff twice, because the 
                // 'computeNextPath' method assumes that the topmost element in
                // the stacks correspond to the target node, since the previous
                // call found a path to target. So when the enumerator is called
                // for the first time, it remove one copy of source stuff from
                // the stacks, and proceeds normally to searching for paths to
                // the target node. 
                //
                // All in all, this hack eliminates an if statement from the 
                // actual search routine.
                nodeStack.addLast(source);
                nodeStack.addLast(source);
                iteratorStack.addLast(source.children().iterator());
                iteratorStack.addLast(source.children().iterator());

                computeNextPath();
            }

            @Override
            public boolean hasNext() {
                return nextPath != null;
            }

            @Override
            public List<DirectedGraphNode> next() {
                if (nextPath == null) {
                    throw new NoSuchElementException("No more paths available.");
                }

                List<DirectedGraphNode> path = nextPath;
                nextPath = null;
                computeNextPath();
                return path;
            }

            private void computeNextPath() {
                // Here we need to remove the topmost node in order to continue
                // searching for other paths.
                visitedSet.remove(nodeStack.removeLast());
                iteratorStack.removeLast();

                while (!nodeStack.isEmpty()) {
                    DirectedGraphNode top = nodeStack.getLast();

                    if (top.equals(target)) {
                        nextPath = new ArrayList<>(nodeStack);
                        return;
                    }

                    if (iteratorStack.getLast().hasNext()) {
                        DirectedGraphNode next = iteratorStack.getLast().next();

                        if (visitedSet.contains(next)) {
                            continue;
                        }

                        nodeStack.addLast(next);
                        visitedSet.add(next);
                        iteratorStack.addLast(next.children().iterator());
                    } else {
                        iteratorStack.removeLast();
                        visitedSet.remove(nodeStack.removeLast());
                    }
                }
            }
        }
    }
}

net.coderodde.graph.Demo:

package net.coderodde.graph;

import java.util.List;

public class Demo {

    public static void main(String[] args) {
        /* The graph:
         * 
         *   B   E
         *  / \ / \
         * A   D-F-H-I
         *  \ / \ / \
         *   C   G   J
         *    \_____/
         */

        DirectedGraphNode A = new DirectedGraphNode("A");
        DirectedGraphNode B = new DirectedGraphNode("B");
        DirectedGraphNode C = new DirectedGraphNode("C");
        DirectedGraphNode D = new DirectedGraphNode("D");
        DirectedGraphNode E = new DirectedGraphNode("E");
        DirectedGraphNode F = new DirectedGraphNode("F");
        DirectedGraphNode G = new DirectedGraphNode("G");
        DirectedGraphNode H = new DirectedGraphNode("H");
        DirectedGraphNode I = new DirectedGraphNode("I");
        DirectedGraphNode J = new DirectedGraphNode("J");

        A.addChild(B); // Create the *directed* edge A -> B.
        A.addChild(C); // Edge A -> C.
        B.addChild(D); // B -> D.
        C.addChild(D); // ...
        C.addChild(J);
        D.addChild(E);
        D.addChild(F);
        D.addChild(G);
        E.addChild(H);
        F.addChild(H);
        G.addChild(H);
        H.addChild(I);
        H.addChild(J);
        J.addChild(H);

        GraphPathEnumerator gpe = new GraphPathEnumerator();

        for (List<DirectedGraphNode> path : gpe.enumerate(A, I)) {
            printPath(path);
        }

        System.out.println();

        for (List<DirectedGraphNode> path : gpe.enumerate(C, I)) {
            printPath(path);
        }

        System.out.println();

        for (List<DirectedGraphNode> path : gpe.enumerate(C, C)) {
            printPath(path);
        }
    }

    static void printPath(List<DirectedGraphNode> path) {
        int i = 0;

        for (DirectedGraphNode node : path) {
            System.out.print(node.getName());

            if (i + 1 < path.size()) {
                System.out.print("->");
                i++;
            }
        }

        System.out.println();
    }
}

Answer 1

If you make the Iterator an inner class (not static) of the Iterable, you will not have to pass source and target to the Iterator. It will see the member variables of the enclosing instance.

I think your state management within the iterator is a bit more complex than it has to be. I did a little refactoring to reduce the amount of mutable state. I changed the method that computes the next path to communicate its success of failure via a return value instead of via a member variable. This refactoring will also wait to compute the next path until it's asked for. Of course, simplicity is somewhat in the eye of the beholder, so you may not find this any simpler. Here's the source of just the Iterator:

class GraphPathIterator implements Iterator<List<DirectedGraphNode>> {

    private final Set<DirectedGraphNode> visitedSet = new HashSet<>();
    private final Deque<DirectedGraphNode> nodeStack = new ArrayDeque<>();
    private final Deque<Iterator<DirectedGraphNode>> iteratorStack = new ArrayDeque<>();

    GraphPathIterator() {
        nodeStack.addLast(source);
        iteratorStack.addLast(source.children().iterator());
        visitedSet.add(source);
    }

    @Override
    public boolean hasNext() {
        return _hasNext();
    }

    @Override
    public List<DirectedGraphNode> next() {
        if (!_hasNext()) {
            throw new NoSuchElementException();
        }

        List<DirectedGraphNode> path = new ArrayList<>(nodeStack);
        backTrack();  // consume current path so next _hasNext() will advance forward
        return path;
    }

    private void backTrack() {
        iteratorStack.removeLast();
        visitedSet.remove(nodeStack.removeLast());
        assert nodeStack.size() == visitedSet.size();
    }

    // if currently at a valid path, return true;  otherwise try to find the next path
    private boolean _hasNext() {
        while (!nodeStack.isEmpty()) {
            if (target.equals(nodeStack.getLast())) {
                return true;
            } else if (iteratorStack.getLast().hasNext()) {
                DirectedGraphNode next = iteratorStack.getLast().next();

                if (visitedSet.add(next)) {
                    nodeStack.addLast(next);
                    iteratorStack.addLast(next.children().iterator());
                }
                assert nodeStack.size() == visitedSet.size();
            } else {
                backTrack();
            }
        }
        return false;
    }
}