4
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$
new Traversal.Builder()
    .withSuccessor(...)
    .withPredecessor(currentVertex)
    .withDistance(distance.increment())
    .build();

Having to manually create the Builder instance with new goes against readability as it clutters the caller's code with knowledge of the Builder class. Explicit new operation binds the code to a certain class. I prefer

Traversal.withSuccessor(...)
    .withPredecessor(currentVertex)
    .withDistance(distance.increment())
    .build();

...where withSuccessor implicitely creates the Builder instance that corresponds to the meaning of withSuccessor(...). It allows a more readable way for instantiating objects when you have more than one way of instantiation. The Builder is still a public and visible to the caller, but they don't have to import it.

\$\endgroup\$
  • \$\begingroup\$ that was the only thinking i came up with... provide a builder for the initial traversal... new Traversal.InitalBuilder().withSuccessor(startVertex)) .build(); \$\endgroup\$ – Martin Frank Feb 18 at 11:55
  • \$\begingroup\$ @MartinFrank, @TorbenPutkonen. What do you think if the Traversal class is private and you would build up a Traversal trough the TraversalTable like: traversalTable.addTraversal().withSuccessor(...).withPredecessor(...).withDistance(...).build()? Thank you for your time! \$\endgroup\$ – Roman Feb 18 at 13:29
  • \$\begingroup\$ @Roman the builder pattern is in general a good option, but it is a bit clumsy for the initial traversal since the first traversal does not have a distance nor a predecessor... \$\endgroup\$ – Martin Frank Feb 18 at 13:38
  • 2
    \$\begingroup\$ @Roman since you already know these parameters are null when you create an initial traversal you could as well skip them... it's already know the initial traversal does not have a predecessor nor a distance. so use a initialBuilder instead of the default builder \$\endgroup\$ – Martin Frank Feb 18 at 14:01
  • 1
    \$\begingroup\$ @MartinFrank ahhh you mean that this are irrelevant information! I see.. maybe something like ..Builder().onlyWithSuccessor(...); Yes, I think this could look nice :P \$\endgroup\$ – Roman Feb 18 at 14:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.