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();
}
}