Problem
I have this iterator class that expects in its constructor two directed graph nodes, source and target, and upon each next() generates another possible directed path from source to target, that was not generated previously.
What comes to algorithm, it is basically a depth-first search. Since the nodes store their children in a sorted set, the path seem to be enumerated in lexicographic order.
So, tell me anything that comes to mind.
net.coderodde.graph.GraphPathEnumerator:
package net.coderodde.graph;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.NoSuchElementException;
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
implements Iterable<List<DirectedGraphNode>>,
Iterator<List<DirectedGraphNode>> {
private final DirectedGraphNode source;
private final DirectedGraphNode target;
private final Set<DirectedGraphNode> visitedSet;
private final Deque<DirectedGraphNode> nodeStack;
private final Deque<Iterator<DirectedGraphNode>> iteratorStack;
private List<DirectedGraphNode> nextPath;
public GraphPathEnumerator(DirectedGraphNode source,
DirectedGraphNode target) {
this.source = source;
this.target = target;
this.visitedSet = new HashSet<>();
this.nodeStack = new LinkedList<>();
this.iteratorStack = new LinkedList<>();
computeNextPath();
}
@Override
public Iterator<List<DirectedGraphNode>> iterator() {
return this;
}
private void computeNextPath() {
if (nodeStack.isEmpty()) {
nodeStack.addLast(source);
iteratorStack.addLast(source.children().iterator());
visitedSet.add(source);
} else {
visitedSet.remove(nodeStack.removeLast());
iteratorStack.removeLast();
}
while (nodeStack.size() > 0) {
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());
}
}
}
@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;
}
}
net.coderodde.graph.DirectedGraphNode:
package net.coderodde.graph;
import java.util.Collections;
import java.util.Set;
import java.util.TreeSet;
/**
* This class implements a node in directed graph.
*
* @author Rodion "rodde" Efremov
*/
public class DirectedGraphNode implements Comparable<DirectedGraphNode> {
private final String name;
private final Set<DirectedGraphNode> children;
public DirectedGraphNode(String name) {
this.name = name;
this.children = new TreeSet<>();
}
/**
* Attempts to add {@code child} to the set of children of this node.
*
* @param child the node to add.
* @return {@code false} if {@code child} is {@code null} or it is already
* in the set. {@code true} otherwise.
*/
public boolean addChild(DirectedGraphNode child) {
if (child == null) {
return false;
}
return children.add(child);
}
/**
* Checks that this node and object {@code o} encode the same graph node.
* Two nodes are considered "same" if and only if they have identical names.
*
* @param o the object to compare against.
* @return {@code true} if both the objects encode the same nodes.
*/
@Override
public boolean equals(Object o) {
if (!(o instanceof DirectedGraphNode)) {
return false;
}
return name.equals(((DirectedGraphNode) o).name);
}
/**
* Returns the hash code of this graph node.
*
* @return the hash code.
*/
@Override
public int hashCode() {
return name.hashCode();
}
public String getName() {
return name;
}
/**
* Compares this node with {@code o} by name.
*
* @param o the node to compare against.
* @return a negative value if this node precedes {@code o}, a positive
* value if {@code o} precedes this node, or zero if both have the
* same name.
*/
@Override
public int compareTo(DirectedGraphNode o) {
return name.compareTo(o.name);
}
/**
* Returns all the children of this node.
*
* @return child nodes of this node.
*/
public Set<DirectedGraphNode> children() {
return Collections.unmodifiableSet(children);
}
}
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);
for (List<DirectedGraphNode> path : new GraphPathEnumerator(A, I)) {
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();
}
}
The demo program outputs:
A->B->D->E->H->I A->B->D->F->H->I A->B->D->G->H->I A->C->D->E->H->I A->C->D->F->H->I A->C->D->G->H->I A->C->J->H->I
Solution
~ I get a warning when trying it out with Java 7, as you have not implemented the remove method from the Iterator class.
And with Java 6, you cannot declare something like
new Tree<>();
without giving the type of the generic. I’ve not checked it with Java 8, but even if it allows this, you might want to do it in a more backwards compatible way.
~ Some general comment as to how the algorithm works would be nice. 🙂 I would like to comment on it, but cannot get exactly the idea of how it works. If I had to implement something like this, it would be as a Depth First Search that yields a result every time it reaches the target, and whose state is just the list of nodes for the last path.
~ I find it strange to implement both the Iterable and Iterator as the same class. I would expect the DirectedGraphNode to be the Iterable and the Iterator a different class. If you check the standard library, Collection is Iterable, and concrete classes implement the iterators as internal classes.
~ Related to the previous comment: I would also expect a Graph class (that is Iterable) as a separate entity from the Node, which would be a generic type.
~ The data allows for cycles, but the algorithm ignores them. So it’s kind of a Graph, but your iterator treats it as a Tree. I suggest you decide what it is and make the algorithm and data structure match.
Iterable returning the same Iterator every time
This is a very bad design and a sneaky bug waiting to happen. Consider the following code:
GraphPathEnumerator gpe = new GraphPathEnumerator(A, I);
for (List<DirectedGraphNode> path : gpe) {
// do something
}
for (List<DirectedGraphNode> path : gpe) {
// do something else
}
The second loop will do nothing because the iterator was already used up. These types of bugs can be very hard to find. If you absolutely cannot return a fresh iterator every time iterator() is called, you should make sure to throw IllegalStateException if iterator() is called the second time and document that fact. But in this case, there’s really no reason to do this. It takes just a couple extra lines of code to do it right.
Iterator is searching for the first path immediately as it is created.
While not a bug, this needlessly violates the principle of least astonishment. People generally don’t expect an Iterator to perform costly operations until it’s actually used. Given that it’s just as easy to defer the computation until hasNext() or next() is called, it would be preferable.
Initialization of iteration state should be in the constructor
It’s not immediately obvious that the first few lines of computeNextPath are intended to only run once to initialize the search state:
if (nodeStack.isEmpty()) {
nodeStack.addLast(source);
iteratorStack.addLast(source.children().iterator());
visitedSet.add(source);
}
If you move the body of that if into the constructor, it will make it clear that this just initialization and not something that might be run again. It will also keep the path computation logic shorter and simpler.
Prefer ArrayDeque over LinkedList
Since java 6, ArrayDeque class is available. It is a better choice for a stack than LinkedList.
Consider initializing fields at their declaration where appropriate
private final Set<DirectedGraphNode> visitedSet = new HashSet<>();
private final Deque<DirectedGraphNode> nodeStack = new ArrayDeque<>();
private final Deque<Iterator<DirectedGraphNode>> iteratorStack = new ArrayDeque<>();
This is definitely a matter of preference, but the advantage of this approach is that it keeps the constructor focused on what it’s doing with constructor arguments.