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