Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Provides the performance demonstration for DelayedGraphSearchLibrary algorithm vs. bidirectional BFS.
import java.util.ArrayList;
import java.util.List;
import net.coderodde.graph.pathfinding.uniform.delayed.AbstractNodeExpander;
public class BackwardDigraphNodeExpander
extends AbstractNodeExpander<DigraphNode> {
@Override
public List<DigraphNode> expand(DigraphNode node) {
return new ArrayList<>(node.getParents());
}
@Override
public boolean isValidNode(DigraphNode node) {
return true;
}
}
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Deque;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import net.coderodde.graph.pathfinding.uniform.delayed.AbstractDelayedGraphPathFinder;
import net.coderodde.graph.pathfinding.uniform.delayed.AbstractNodeExpander;
import net.coderodde.graph.pathfinding.uniform.delayed.ProgressLogger;
public class BidirectionalBFSPathFinder extends AbstractDelayedGraphPathFinder<DigraphNode> {
@Override
public List<DigraphNode> search(
DigraphNode source,
DigraphNode target,
AbstractNodeExpander<DigraphNode> forwardSearchNodeExpander,
AbstractNodeExpander<DigraphNode> backwardSearchNodeExpander,
ProgressLogger<DigraphNode> forwardSearchProgressLogger,
ProgressLogger<DigraphNode> backwardSearchProgressLogger,
ProgressLogger<DigraphNode> sharedSearchProgressLogger) {
if (source.equals(target)) {
return new ArrayList<>(Arrays.asList(source));
}
Deque<DigraphNode> QUEUEA = new ArrayDeque<>();
Deque<DigraphNode> QUEUEB = new ArrayDeque<>();
Map<DigraphNode, DigraphNode> PARENTSA = new HashMap<>();
Map<DigraphNode, DigraphNode> PARENTSB = new HashMap<>();
Map<DigraphNode, Integer> DISTANCEA = new HashMap<>();
Map<DigraphNode, Integer> DISTANCEB = new HashMap<>();
QUEUEA.add(source);
QUEUEB.add(target);
PARENTSA.put(source, null);
PARENTSB.put(target, null);
DISTANCEA.put(source, 0);
DISTANCEB.put(target, 0);
DigraphNode touchNode = null;
int bestPathLengthSoFar = Integer.MAX_VALUE;
while (!QUEUEA.isEmpty() && !QUEUEB.isEmpty()) {
if (touchNode != null) {
DigraphNode headA = QUEUEA.getFirst();
DigraphNode headB = QUEUEB.getFirst();
if (DISTANCEA.get(headA) + DISTANCEB.get(headB)
>= bestPathLengthSoFar) {
return tracebackPath(touchNode, PARENTSA, PARENTSB);
}
}
DigraphNode currentNode = QUEUEA.removeFirst();
if (PARENTSB.containsKey(currentNode)) {
int currentDistance = DISTANCEA.get(currentNode) +
DISTANCEB.get(currentNode);
if (bestPathLengthSoFar > currentDistance) {
bestPathLengthSoFar = currentDistance;
touchNode = currentNode;
}
}
for (DigraphNode child :
forwardSearchNodeExpander.expand(currentNode)) {
if (!PARENTSA.containsKey(child)) {
PARENTSA.put(child, currentNode);
DISTANCEA.put(child, DISTANCEA.get(currentNode) + 1);
QUEUEA.addLast(child);
}
}
currentNode = QUEUEB.removeFirst();
if (PARENTSA.containsKey(currentNode)) {
int currentDistance = DISTANCEA.get(currentNode) +
DISTANCEB.get(currentNode);
if (bestPathLengthSoFar > currentDistance) {
bestPathLengthSoFar = currentDistance;
touchNode = currentNode;
}
}
for (DigraphNode parent :
backwardSearchNodeExpander.expand(currentNode)) {
if (!PARENTSB.containsKey(parent)) {
PARENTSB.put(parent, currentNode);
DISTANCEB.put(parent, DISTANCEB.get(currentNode) + 1);
QUEUEB.addLast(parent);
}
}
}
return Collections.<DigraphNode>emptyList();
}
protected static List<DigraphNode>
tracebackPath(DigraphNode touch,
Map<DigraphNode, DigraphNode> PARENTSA,
Map<DigraphNode, DigraphNode> PARENTSB) {
List<DigraphNode> path = new ArrayList<>();
DigraphNode current = touch;
while (current != null) {
path.add(current);
current = PARENTSA.get(current);
}
Collections.<DigraphNode>reverse(path);
if (PARENTSB != null) {
current = PARENTSB.get(touch);
while (current != null) {
path.add(current);
current = PARENTSB.get(current);
}
}
return path;
}
protected static List<DigraphNode>
tracebackPath(DigraphNode target,
Map<DigraphNode, DigraphNode> PARENTS) {
return tracebackPath(target, PARENTS, null);
}
}
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import net.coderodde.graph.pathfinding.uniform.delayed.AbstractDelayedGraphPathFinder;
import net.coderodde.graph.pathfinding.uniform.delayed.support.ThreadPoolBidirectionalPathFinder;
public class Demo {
private static final int NODES = 1_000;
private static final int EDGES = 5_000;
private static final int NUMBER_OF_THREADS = 16;
public static void main(String[] args) {
long seed = System.nanoTime();
Random random = new Random(seed);
List<DigraphNode> graph = createRandomDigraph(NODES, EDGES, random);
System.out.println("Seed = " + seed);
AbstractDelayedGraphPathFinder<DigraphNode> pathFinder1 =
new ThreadPoolBidirectionalPathFinder<>(NUMBER_OF_THREADS);
DigraphNode source = choose(graph, random);
DigraphNode target = choose(graph, random);
System.out.println("Source node = " + source);
System.out.println("Target node = " + target);
long start = System.nanoTime();
List<DigraphNode> path1 =
pathFinder1.search(source,
target,
new ForwardDigraphNodeExpander(),
new BackwardDigraphNodeExpander(),
null,
null,
null);
long end = System.nanoTime();
System.out.printf("%s done in %.1f milliseconds.\n",
pathFinder1.getClass().getSimpleName(),
(end - start) / 1e6);
System.out.println("Path:");
path1.forEach(System.out::println);
AbstractDelayedGraphPathFinder<DigraphNode> pathFinder2 =
new BidirectionalBFSPathFinder();
start = System.nanoTime();
List<DigraphNode> path2 =
pathFinder2.search(source,
target,
new ForwardDigraphNodeExpander(),
new BackwardDigraphNodeExpander(),
null,
null,
null);
end = System.nanoTime();
System.out.printf("%s done in %.1f milliseconds.\n",
pathFinder2.getClass().getSimpleName(),
(end - start) / 1e6);
System.out.println("Path:");
path2.forEach(System.out::println);
}
private static List<DigraphNode> createRandomDigraph(int nodes,
int edges,
Random random) {
List<DigraphNode> digraphNodeList = new ArrayList<>(nodes);
for (int id = 0; id < nodes; ++id) {
digraphNodeList.add(new DigraphNode(id));
}
while (edges-- > 0) {
DigraphNode tail = choose(digraphNodeList, random);
DigraphNode head = choose(digraphNodeList, random);
tail.addChild(head);
}
return digraphNodeList;
}
private static <T> T choose(List<T> list, Random random) {
return list.get(random.nextInt(list.size()));
}
}
import java.util.HashSet;
import java.util.Random;
import java.util.Set;
public class DigraphNode {
private final int id;
private final Set<DigraphNode> parents = new HashSet<>();
private final Set<DigraphNode> children = new HashSet<>();
private final Random random = new Random();
public DigraphNode(int id) {
this.id = id;
}
public void addChild(DigraphNode child) {
children.add(child);
child.parents.add(this);
}
Set<DigraphNode> getChildren() {
delay();
return children;
}
Set<DigraphNode> getParents() {
delay();
return parents;
}
@Override
public int hashCode() {
return id;
}
@Override
public boolean equals(Object o) {
if (o == null) {
return false;
}
if (!o.getClass().equals(getClass())) {
return false;
}
return id == ((DigraphNode) o).id;
}
@Override
public String toString() {
return "[DigraphNode " + id + "]";
}
private void delay() {
try {
Thread.sleep(200L + (long)(30.0 * random.nextGaussian()));
} catch (Exception ignore) {
}
}
}
import java.util.ArrayList;
import java.util.List;
import net.coderodde.graph.pathfinding.uniform.delayed.AbstractNodeExpander;
public class ForwardDigraphNodeExpander
extends AbstractNodeExpander<DigraphNode>{
@Override
public List<DigraphNode> expand(DigraphNode node) {
return new ArrayList<>(node.getChildren());
}
@Override
public boolean isValidNode(DigraphNode node) {
return true;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.