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