- Поиск путей Java в общих деревьях. Часть 1/4: классы моделей
- Поиск пути Java в общих деревьях — Часть 2/4: алгоритмы
- Поиск пути Java в общих деревьях — часть 3/4: демонстрация (этот пост)
- Поиск пути Java в общих деревьях — часть 4/4: модульные тесты
В этом посте представлены средства для проведения демонстрации.
com.github.coderodde.pathfinding.StarTreeBuilder.java:
package com.github.coderodde.pathfinding;
import com.github.coderodde.pathfinding.WeightedTree.WeightedTreeNode;
import java.util.Objects;
import java.util.Random;
/**
* This class is responsible for creating a star-shaped tree.
*
* @author Rodion "rodde" Efremov
* @version 1.6 (Nov 5, 2022)
* @since 1.6 (Nov 5, 2022)
*/
public final class StarTreeBuilder {
private final int degree;
private final int radius;
private final Random random;
private WeightedTree tree;
private int currentId;
public StarTreeBuilder(int degree, int radius, Random random) {
this.degree = checkDegree(degree);
this.radius = checkRadius(radius);
this.random = Objects.requireNonNull(random, "Random is null.");
}
public WeightedTree build() {
tree = new WeightedTree();
currentId = 0;
WeightedTreeNode root = tree.addTreeNode(currentId++);
if (radius == 0) {
return tree;
}
for (int i = 0; i < degree; i++) {
WeightedTreeNode node = tree.addTreeNode(currentId++);
tree.connect(root.getId(), node.getId(), random.nextDouble());
createWeightedTreeUtil(node, radius - 1);
}
return tree;
}
private void createWeightedTreeUtil(WeightedTreeNode node, int radius) {
if (radius == -1) {
return;
}
for (int i = 0; i < degree - 1; i++) {
WeightedTreeNode newNode = tree.addTreeNode(currentId++);
tree.connect(newNode.getId(), node.getId(), random.nextDouble());
createWeightedTreeUtil(newNode, radius - 1);
}
}
private int checkDegree(int degree) {
if (degree < 2) {
throw new IllegalArgumentException(
"The degree is too small: "
+ degree
+ ". Must be at least 2.");
}
return degree;
}
private int checkRadius(int radius) {
if (radius < 0) {
throw new IllegalArgumentException(
"The radius is too small: "
+ radius
+ ". Must be at least 0.");
}
return radius;
}
}
com.github.coderodde.pathfinding.Demo.java:
package com.github.coderodde.pathfinding;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
public final class Demo {
private static final int RADIUS = 12;
private static final int DEGREE = 4;
private static final List<Pathfinder> pathfinders = new ArrayList<>(5);
static {
pathfinders.add(new BreadthFirstSearchPathfinder());
pathfinders.add(new BidirectionalBreadthFirstSearchPathfinder());
pathfinders.add(new DepthFirstSearchPathfinder());
pathfinders.add(new IterativeDeepeningDepthFirstSearchPathfinder());
pathfinders.add(
new BidirectionalIterativeDeepeningDepthFirstSearchPathfinder());
}
public static void main(String[] args) {
long seed = System.nanoTime();
Random random = new Random(seed);
System.out.println("<<< Seed = " + seed + " >>>");
long startTime = System.currentTimeMillis();
WeightedTree tree = new StarTreeBuilder(DEGREE, RADIUS, random).build();
long endTime = System.currentTimeMillis();
long duration = endTime - startTime;
System.out.println("Built the tree in " + duration + " milliseconds.");
System.out.println(
"Number of nodes in the tree: " + tree.getNumberOfNodes());
startTime = System.currentTimeMillis();
boolean isCyclic = tree.isCyclic();
endTime = System.currentTimeMillis();
duration = endTime - startTime;
System.out.println("The tree candidate is cyclic: " + isCyclic);
System.out.println(
"Acyclicity check in "
+ duration
+ " milliseconds.");
startTime = System.currentTimeMillis();
warmup(tree, new Random(seed + 1L));
endTime = System.currentTimeMillis();
duration = endTime - startTime;
System.out.println("Warmup in " + duration + " milliseconds");
startTime = System.currentTimeMillis();
benchmark(tree, new Random(seed + 1L));
endTime = System.currentTimeMillis();
duration = endTime - startTime;
System.out.println("Benchmark in " + duration + " milliseconds");
}
private static void warmup(WeightedTree tree, Random random) {
run(tree, false, random);
}
private static void benchmark(WeightedTree tree, Random random) {
run(tree, true, random);
}
private static void run(WeightedTree tree, boolean print, Random random) {
int sourceNodeId = random.nextInt(tree.getNumberOfNodes());
int targetNodeId = random.nextInt(tree.getNumberOfNodes());
if (print) {
System.out.println("Source: " + tree.getNode(sourceNodeId));
System.out.println("Target: " + tree.getNode(targetNodeId));
}
List<WeightedPath> paths = new ArrayList<>();
if (print) {
System.out.println("---------------------------------------------");
}
for (Pathfinder pathfinder : pathfinders) {
long startTime = System.currentTimeMillis();
WeightedPath path = pathfinder.search(tree,
sourceNodeId,
targetNodeId);
long endTime = System.currentTimeMillis();
long duration = endTime - startTime;
paths.add(path);
if (print) {
System.out.println(
pathfinder.getClass().getSimpleName()
+ " in "
+ duration
+ " milliseconds.");
}
}
if (print) {
System.out.println("---------------------------------------------");
}
if (print) {
boolean pathsEqual = pathsAreEqual(paths);
if (!pathsEqual) {
System.out.println("Path mismatch!");
} else {
System.out.println("Algorithms agree on a path.");
System.out.println();
System.out.println("Shortest path:");
System.out.println(paths.get(0));
System.out.println(
"Shortest path distance: "
+ paths.get(0).getTotalCost());
}
}
}
private static boolean pathsAreEqual(List<WeightedPath> paths) {
for (int i = 0; i < paths.size() - 1; i++) {
if (!paths.get(i).equals(paths.get(i + 1))) {
return false;
}
}
return true;
}
}
Типичный вывод
<<< Seed = 103563124048700 >>>
Built the tree in 2309 milliseconds.
Number of nodes in the tree: 3188645
The tree candidate is cyclic: false
Acyclicity check in 1024 milliseconds.
Warmup in 1713 milliseconds
Source: [WeightedTreeNode, id = 1122646]
Target: [WeightedTreeNode, id = 485067]
---------------------------------------------
BreadthFirstSearchPathfinder in 638 milliseconds.
BidirectionalBreadthFirstSearchPathfinder in 3 milliseconds.
DepthFirstSearchPathfinder in 110 milliseconds.
IterativeDeepeningDepthFirstSearchPathfinder in 512 milliseconds.
BidirectionalIterativeDeepeningDepthFirstSearchPathfinder in 4 milliseconds.
---------------------------------------------
Algorithms agree on a path.
Shortest path:
[WeightedTreeNode, id = 1122646]
[WeightedTreeNode, id = 1122644]
[WeightedTreeNode, id = 1122639]
[WeightedTreeNode, id = 1122625]
[WeightedTreeNode, id = 1122544]
[WeightedTreeNode, id = 1122301]
[WeightedTreeNode, id = 1121936]
[WeightedTreeNode, id = 1121935]
[WeightedTreeNode, id = 1121934]
[WeightedTreeNode, id = 1121933]
[WeightedTreeNode, id = 1062884]
[WeightedTreeNode, id = 1062883]
[WeightedTreeNode, id = 797162]
[WeightedTreeNode, id = 0]
[WeightedTreeNode, id = 1]
[WeightedTreeNode, id = 265722]
[WeightedTreeNode, id = 442869]
[WeightedTreeNode, id = 472394]
[WeightedTreeNode, id = 482236]
[WeightedTreeNode, id = 482237]
[WeightedTreeNode, id = 484424]
[WeightedTreeNode, id = 484789]
[WeightedTreeNode, id = 485032]
[WeightedTreeNode, id = 485033]
[WeightedTreeNode, id = 485060]
[WeightedTreeNode, id = 485065]
[WeightedTreeNode, id = 485067]
Shortest path distance: 15.283136830490866
Benchmark in 1281 milliseconds
Запрос критики
Как всегда, пожалуйста, расскажите мне все, что приходит на ум.
кодродде