My goal is to write a GUI application where a user can create a maze and select an algorithm. The passage of the algorithm from a selected start and end point should be visualized.
The following shows only the Breadth-First Search algorithm. During programming, I paid attention to the following things:
- readable APIs
- SOLID-Principles
- short and readable methods
I am very grateful for a code review that focuses on the above points and things I don't yet have in mind.
Breadth-First Search Algorithm
An Example
// .. build graph .. BreadthFirstSearch breadthFirstSearch = BreadthFirstSearch.of(graph); TraversalTable traversalTable = breadthFirstSearch.searchFrom(a); Path path = traversalTable.to(b);
Breadth-First Search
public class BreadthFirstSearch {
private Graph graph;
private BreadthFirstSearch(Graph graph) {
this.graph = graph;
}
public static BreadthFirstSearch of(Graph graph) {
return new BreadthFirstSearch(graph);
}
public TraversalTable searchFrom(Vertex startVertex) {
Queue<Vertex> queue = new LinkedList<>();
TraversalTable traversalTable = new TraversalTable();
queue.add(startVertex);
traversalTable.add(new Traversal.Builder().withSuccessor(startVertex)
.withPredecessor(new NonVertex())
.withDistance(new Distance(0))
.build());
while (!queue.isEmpty()) {
Vertex currentVertex = queue.poll();
for (Vertex neighbor : graph.neighborsOf(currentVertex)) {
if (traversalTable.containsNot(neighbor)) {
Distance distance = traversalTable.distanceOf(currentVertex);
Traversal traversal = new Traversal.Builder().withSuccessor(neighbor)
.withPredecessor(currentVertex)
.withDistance(distance.increment())
.build();
traversalTable.add(traversal);
queue.add(neighbor);
}
}
}
return traversalTable;
}
}
TraversalTable
public class TraversalTable {
private static Traversal.Builder DEFAULT_TRAVERSAL_BUILDER = new Traversal.Builder().withPredecessor(new NonVertex())
.withDistance(Distance.INFINITE);
private final Map<Vertex, Traversal> vertexByPredecessor;
TraversalTable(Map<Vertex, Traversal> vertexByPredecessor) {
this.vertexByPredecessor = vertexByPredecessor;
}
TraversalTable() {
this.vertexByPredecessor = new HashMap<>();
}
public void add(Traversal traversal) {
vertexByPredecessor.put(traversal.getSuccessor(), traversal);
}
public Distance distanceOf(Vertex vertex) {
return traversalOf(vertex).getDistance();
}
public Vertex predecessorOf(Vertex vertex) {
return traversalOf(vertex).getPredecessor();
}
public Path to(Vertex vertex) {
return isNotAccessible(vertex)
? Path.empty()
: to(predecessorOf(vertex), Path.startWith(vertex));
}
private Path to(Vertex vertex, Path path) {
return vertex.isPresent()
? to(predecessorOf(vertex), path.append(vertex))
: path;
}
public boolean isAccessible(Vertex vertex) {
return distanceOf(vertex).isNotInfinite();
}
public boolean isNotAccessible(Vertex vertex) {
return !isAccessible(vertex);
}
public boolean containsNot(Vertex vertex) {
return !contains(vertex);
}
public boolean contains(Vertex vertex) {
return vertexByPredecessor.containsKey(vertex);
}
private Traversal traversalOf(Vertex vertex) {
return vertexByPredecessor
.getOrDefault(vertex, DEFAULT_TRAVERSAL_BUILDER.withSuccessor(vertex).build());
}
@Override
public boolean equals(Object o) { /* ... */ }
@Override
public int hashCode() { /* ... */ }
@Override
public String toString() { /* ... */ }
}
Looking for Recommendation
Recursion
In TraversalTable the method to calls a overloaded private method to which builds recursively the Path.
In my opinion it looks cleaner that the previous while loop
public Path to(Vertex vertex) { if (isAccessible(vertex)) return Path.empty(); Path path = Path.startWith(vertex); Vertex predecessor = predecessorOf(vertex); while (predecessor.isPresent()) { path.append(predecessor); predecessor = predecessorOf(predecessor); } return path; }
However, this method has the advantage of containing all the logic within a method, rather than my current solution where I shared the logic. Do you have a suggestion of legibility and maintainability?
Level Of Indentation
The method searchFrom in BreadthFirstSearch has a to high level of Indentation, but I left it that way because the algorithm is so well known.
public TraversalTable searchFrom(Vertex startVertex) { // 1 lvl while (!queue.isEmpty()) { // 2 lvl for (Vertex neighbor : graph.neighborsOf(currentVertex)) { // 3 lvl if (traversalTable.containsNot(neighbor)) { // 4 lvl } } } return traversalTable }
If I split the logic into my own methods, I can reduce the level of indentation, but because of the variables that share the lower methods with the root method, they must be delegated, which makes the method's signatures unclear to me..
public TraversalTable searchFrom(Vertex startVertex) {
Queue<Vertex> queue = new LinkedList<>();
TraversalTable traversalTable = new TraversalTable();
queue.add(startVertex);
traversalTable.add(new Traversal.Builder().withSuccessor(startVertex)
.withPredecessor(new NonVertex())
.withDistance(new Distance(0))
.build());
while (!queue.isEmpty()) {
Vertex currentVertex = queue.poll();
traversalAllNeighbors(currentVertex, traversalTable, queue);
}
}
private void traversal(Vertex successor, Vertex predecessor, TraversalTable traversalTable) {
Distance distance = traversalTable.distanceOf(currentVertex);
Traversal traversal = new Traversal.Builder().withSuccessor(neighbor)
.withPredecessor(currentVertex)
.withDistance(distance.increment())
.build();
traversalTable.add(traversal);
}
private void traversalAllNeighbors(Vertext vertex, TraversalTable traversalTable, Queue<Vertex> queue) {
for (Vertex neighbor : graph.neighborsOf(vertex)) {
if (traversalTable.containsNot(neighbor)) {
traversal(neighbor, vertex, traversalTable);
queue.add(neighbor);
}
}
}
Additional to these two classes I implemented a Path and Traversal but this does not add any logic to the algorithm.
