Problems and Solutions

Whereas sets, maps, and priority queues emphasize efficient access to elements, graphs emphasize not only elements (vertices) but also their relationships (edges). The efficiency of a graph data structure depends on the underlying data structures used to represent its vertices and edges. How do graphs fit into our existing mental model of abstract data types (Java interfaces) and data structures or algorithms that implement them (Java classes)? We can frame things around problems and solutions.

In computing, a problem can is a task that can be represented, formalized, and/or solved using algorithms. In Java, we often represent problems using interfaces describing expected functionality. Sorting is the problem of rearranging elements according to an ordering relation, with different assumptions for comparison sorting versus count sorting. Sets are an example of an abstract data type that represents a collection of unique elements. Graph traversal is the problem of visiting/checking/processing each vertex in a graph. We can even say that the problem of Husky Maps is the problem of representing the real world as a computable graph.

In computing, a solution is a sequence of steps or a description of process that can be used to solve computational problems. In Java, we often represent solutions using classes with program logic that describes how to implement functionality. Insertion sort, selection sort, and merge sort are algorithms for sorting. Search trees and hash tables are algorithmic ideas for implementing sets. BFS and DFS are algorithms for graph traversal. Adjacency lists are the data structure solution underlying one representation for Husky Maps.

This relationships suggests that algorithmic problems like graph traversal can also be represented using interfaces, which are then implemented by solutions that are represented using classes. In Husky Maps, the graphs.shortestpaths package includes interfaces and classes for finding the shortest paths in a directed graph.

public interface ShortestPathSolver<V>
public class DijkstraSolver<V> implements ShortestPathSolver<V>
public class BellmanFordSolver<V> implements ShortestPathSolver<V>
public class SPFASolver<V> implements ShortestPathSolver<V>
public class ToposortDAGSolver<V> implements ShortestPathSolver<V>

Each of the four graph algorithms do most of their work in the class constructor. For example, If we wanted to add a BFS algorithm to this list (for unweighted shortest paths), it would take the bfs method we examined earlier and do most of the work inside of the constructor.

public class BreadthFirstSearch<V> {
    private final Map<V, Edge<V>> edgeTo;
    private final Map<V, Integer> distTo;

    public BreadthFirstSearch(Graph<V> graph, V start) {
        edgeTo = new HashMap<>();
        distTo = new HashMap<>();
        Queue<V> perimeter = new ArrayDeque<>();
        Set<V> visited = new HashSet<>();
        perimeter.add(start);
        visited.add(start);
        edgeTo.put(start, null);
        distTo.put(start, 0);
        while (!perimeter.isEmpty()) {
            V from = perimeter.remove();
            for (Edge<V> edge : graph.neighbors(from)) {
                V to = edge.to;
                if (!visited.contains(to)) {
                    edgeTo.put(to, edge);
                    distTo.put(to, distTo.get(from) + 1);
                    perimeter.add(to);
                    visited.add(to);
                }
            }
        }
    }

    /** Returns the unweighted shortest path from the start to the goal. */
    public List<V> solution(V goal) {
        List<V> path = new ArrayList<>();
        V curr = goal;
        path.add(curr);
        while (edgeTo.get(curr) != null) {
            curr = edgeTo.get(curr).from;
            path.add(curr);
        }
        Collections.reverse(path);
        return path;
    }
}

Why does the solution method call Collections.reverse?

The solution method begins at goal and uses edgeTo to trace the path back to start. Since we add elements to the end of the ArrayList (for efficiency!), we need to reverse the list before returning it.

There are hundreds of problems and algorithms for solving them. The field of graph theory investigates these graph problems and graph algorithms.