How to create an iterator wrapper for DAG structure in Java?

Question

I want to have an iterator over a data structure. For now I don't know what data structure is, mayebe it is a DAG (directed acyclic graph), but maybe it could be also a linked list. So I want to wrap it into an iterator and don't think now at particular data structure.

I know how to visit a DAG with a recursive-like visitor, but I can't figure out a simple and clean structure for implementing iterator methods next() and hasNext().

Inside the iterator I've created a current node instance and iterate with a for-loop over all children and then get back to the parent. An 'already-visited' flag is needed. So my DagElement has these more attributes:

DagElement parent
boolean alreadyVisited

I don't think this is a clean solution.

Any advice?

Answer 1

The quick-and-dirty method for converting a recursive heuristic to an iterative one is to use a (LIFO) stack or (LILO) queue to hold the "roads not taken" - paths found but not yet taken. In this case, the iterator would have an stack or queue instance variable. Something like:

    class DagIterator<T>
    extends Iterator<T> {

        private Stack<DagNode<T>> nodes;

        private DagIterator(Dag<T> dag) {
            nodes.push(dag.getRootNode());
        }

        public boolean hasNext() {
            return ! nodes.isEmpty();      
        }

        public T next() {
            final DagNode node = nodes.pop();
            for (final DagNode child : node.getChildren()) {
                nodes.push(child);
            }
            return node.getValue();
        }

    }

You tweak the visitation order based on the data structure (LIFO or LILO), the order in which the children are queued, and when they are queued. It wouldn't suprise me that some visitation orders may require queuing the entire set of nodes in the proper order right off the bat (in the constructor).