Shortest Paths

Designing and analyzing shortest paths.

Seam finding interfaces
Graph interfaces
Reference implementation
1. Node interface
Design and implement
Analyze and compare
1. Experimental analysis
2. Algorithm engineering

In addition to implementing navigation directions in Husky Maps, shortest paths is also useful for seam carving: a technique for image resizing where the size of an image is reduced by one pixel in height (by removing a horizontal seam) or width (by removing a vertical seam) at a time. Rather cropping pixels from the edges or scaling the entire image, seam carving is considered content-aware image resizing because it attempts to identify and preserve the most important content in an image.

In this project, we will compare 2 graph representations, 2 graph algorithms, and 1 dynamic programming algorithm for seam carving. By the end of this project, students will be able to:

Design and implement graph representations and algorithms for seam finding.
Analyze and compare implementation runtime and adaptibility to new metrics.

What am I submitting at the end of this project?

Satisfactory completion of the project requires two Canvas submissions: one individual writeup and a link to your src folder on GitLab that addresses all the green callouts in the Design and Implement section, and one video-recorded team presentation that addresses all the green callouts in the Analyze and Compare section. Your writeup should also include two links: one to your src/graphs/shortestpaths folder, and one to your src/seamfinding folder on GitLab. Remember to push all your project code to GitLab by the time you submit in Canvas.

The project instructions contain a lot of details to provide context, clarify common confusions, and help students get started. Your Canvas submisisons only need to address tasks that are described in green callouts like this one.

Seam finding interfaces

The SeamCarver class depends on algorithms that can find a least-noticeable horizontal or vertical seam. The interfaces for seam finding are defined in the src/seamfinding folder.

SeamFinder: An interface specifying a single method, findHorizontal, for finding a least-noticeable horizontal seam in a given Picture according to the EnergyFunction. The horizontal seam is returned as a list of integer indices representing the y-value (vertical) pixel indices for each pixel in the width of the picture.
Picture: A class representing a digital image where the color of each pixel is an int. In image processing, pixel (x, y) refers to the pixel in column x and row y where pixel (0, 0) is the upper-left corner and the lower-right corner is the pixel with the largest coordinates.

This is opposite to linear algebra, where (i, j) is row i column j and (0, 0) is the lower-left corner.

EnergyFunction: An interface specifying a single method, apply, for computing the importance of a given pixel in the picture. The higher the energy of a pixel, the more noticeable it is in the picture.

Seam finder implementations work by applying the EnergyFunction to each pixel in the given Picture. Then, we can use a shortest paths algorithm to find the least-noticeable horizontal seam from the left side of the picture to the right side of the picture.

Graph interfaces

The graph interfaces and algorithms are defined in the src/graphs folder.

Graph: An interface representing a directed weighted graph with a single method that returns a list of the neighbors of a given vertex. The directed Edge class provides 3 fields: the origin vertex from, the destination vertex to, and the edge weight.
ShortestPathSolver: An interface for finding a shortest paths tree in a Graph. Implementations of this interface must provide a public constructor that accepts two parameters: a Graph and a start vertex. The solution method returns the list of vertices representing a shortest path from the start vertex to the given goal vertex.

The generic type V is used throughout the graphs package to indicate the vertex data type. For seam carving, all vertices will be of the interface type Node (described below).

Reference implementation

AdjacencyListSeamFinder implements SeamFinder by building an adjacency list graph representation of the picture and then running a single-source shortest paths algorithm to find a lowest-cost horizontal seam.

public List<Integer> findHorizontal(Picture picture, EnergyFunction f) {
    PixelGraph graph = new PixelGraph(picture, f);
    List<Node> seam = sps.run(graph, graph.source).solution(graph.sink);
    seam = seam.subList(1, seam.size() - 1); // Skip the source and sink nodes
    List<Integer> result = new ArrayList<>(seam.size());
    for (Node node : seam) {
        // All remaining nodes must be Pixels
        PixelGraph.Pixel pixel = (PixelGraph.Pixel) node;
        result.add(pixel.y);
    }
    return result;
}

Here’s an explanation of each line of code in this method. Given a Picture and an EnergyFunction that defines the way that we want to measure the importance of each pixel:

PixelGraph graph = new PixelGraph(picture, f): The first line creates a PixelGraph where each vertex represents a pixel and each edge represents the energy cost for the neighboring pixel. The PixelGraph constructor creates a new Pixel (node) for each pixel in the image. It also creates a source node and a sink node.
List<Node> seam = sps.run(graph, graph.source).solution(graph.sink): sps.run calls the ShortestPathSolver (such as DijkstraSolver) to find the shortest path in the PixelGraph from the source and immediately asks for a shortest path to the sink. The seam stores the solution to the shortest path problem.
seam = seam.subList(1, seam.size() - 1): The seam includes the source and sink, which we don’t need in our final solution.
for (Node node : seam) { ... }: Since the remaining nodes in the seam must be Pixel nodes, add each pixel’s y index to the result list and return the result.

Look inside the AdjacencyListSeamFinder class to find a static nested class called PixelGraph. PixelGraph implements Graph<Node> by constructing a 2-dimensional grid storing each Node in the seam carving graph. This class also includes two fields called source and sink.

Node interface

Node is an interface that adapts the Graph.neighbors method for use with different types of nodes in the AdjacencyListSeamFinder. This is helpful because not all nodes are the same. Although most nodes represent pixels that have x and y coordinates, the graph also contains source and sink nodes that don’t have x or y coordinates! Using the Node interface allows for these different kinds of nodes to all work together in a single program.

Inside of the PixelGraph class, you’ll find the three types of nodes implemented as follows.

source: A field that implements Node.neighbors by returning a list of picture.height() outgoing edges to each Pixel in the first column of the picture. The weight for each outgoing edge represents the energy of the corresponding pixel in the leftmost column.
Pixel: An inner class representing an (x, y) pixel in the picture with directed edges to its right-up, right-middle, and right-down neighbors. Most pixels have 3 adjacent neighbors except for pixels at the boundary of the picture that only have 2 adjacent neighbors. The weight of an edge represents the energy of the neighboring to-side pixel.
sink: A field that implements Node.neighbors by returning an empty list. It has one incoming edge from each Pixel in the rightmost column of the picture.

The source and sink are defined using a feature in Java called anonymous classes. Anonymous classes are great for objects that implement an interface but only need to be instantiated once.

Design and implement

Design and implement 1 graph representation, 1 graph algorithm, and 1 dynamic programming algorithm for seam finding.

If you choose to collaborate on project code, all team members must work together and fully understand each implementation. Do not assign each implementation to individual team members. The implementations are described in order of increasing complexity so later implementations will require significantly more work.

Students are expected to follow Washington state law on the Student Conduct Code for the University of Washington. In this course, students must:

Indicate on your submission any assistance received, including materials distributed in this course.
Not receive, generate, or otherwise acquire any substantial portion or walkthrough for an assignment.
Not aid, assist, attempt, or tolerate prohibited academic conduct in others.

In your writeup, cite any sources you used in the implementation or debugging process, including lecture materials, section materials, and collaboration with peers. If you used any kind of computer technology to help prepare your project deliverable, include the queries and/or prompts.

Submitted work that is not consistent with sources may be subject to the student conduct process.

GenerativeSeamFinder

A graph representation that implements SeamFinder. Similar to AdjacencyListSeamFinder but rather than creating the neighbors for every node in the PixelGraph constructor ahead of time, this approach only creates vertices and edges when Pixel.neighbors is called.

Study the AdjacencyListSeamFinder.PixelGraph constructor, which constructs the entire graph and represents it as a Pixel[][].
Adapt the ideas to implement GenerativeSeamFinder.PixelGraph.Pixel.neighbors, which should return the list of neighbors for a given Pixel. Create a new Pixel for each neighbor.
Then, define the source and sink nodes.

The slides below show how a PixelGraph is constructed in AdjacencyListSeamFinder and explain how this differs from GenerativeSeamFinder. Click on the image below to advance to the next slide.

Explain the part of the GenerativeSeamFinder class that you’re most proud of programming.

ToposortDAGSolver

A graph algorithm that implements ShortestPathSolver. Finds a shortest paths tree in a directed acyclic graph using topological sorting.

Initialize edgeTo and distTo data structures just as in DijkstraSolver.
List all reachable vertices in depth-first search postorder. Then, Collections.reverse the list.
For each node in reverse DFS postorder, relax each neighboring edge.

Edge relaxation: If the new distance to the neighboring node using this edge is better than the best-known distTo the node, update distTo and edgeTo accordingly.

DynamicProgrammingSeamFinder

A dynamic programming algorithm that implements SeamFinder. The dynamic programming approach processes pixels in a topological order: start from the leftmost column and work your way right, using the previous columns to help identify the best shortest paths. The difference is that dynamic programming does not create a graph representation (vertices and edges) nor does it use a graph algorithm.

How does dynamic programming solve the seam finding problem? We need to first generate a dynamic programming table storing the accumulated path costs, where each entry represents the total energy cost of the least-noticeable path from the left edge to the given pixel.

Initialize a 2-d double[picture.width()][picture.height()] array.
Fill out the leftmost column in the 2-d array with the energy for each pixel.
For each pixel in each of the remaining columns, determine the lowest-energy predecessor to the pixel: the minimum of its left-up, left-middle, and left-down neighbors. Compute the total energy cost to the current pixel by adding its energy to the total cost for the least-noticeable predecessor.

The slides below show how the DynamicProgrammingSeamFinder implementation works and highlight key ideas to account for in your code. Click on the image below to advance to the next slide.

Once we’ve generated this table, we can use it to find the shortest path.

Add the y value of the least-noticeable pixel in the rightmost column to the result.
Follow the path back to the left by adding the y-value of each predecessor to the result.
Finally, to get the coordinates from left to right, Collections.reverse the result.

Explain the part of the DynamicProgrammingSeamFinder class that you’re most proud of programming.

Run all the tests for all 5 implementations in IntelliJ and include a screenshot in your writeup showing a summary of the results. If the implementations pass all the test cases, explain an interesting bug that you addressed during your programming process. If the implementations do not pass all the test cases, explain what you think could be causing the problem.

Analyze and compare

Experimental analysis

Run the provided RuntimeExperiments to compare the real-world runtime of each implementation. For each implementation, RuntimeExperiments constructs an empty instance and records the number of seconds to findHorizontal through randomly-generated pictures of increasing resolution.

Copy-paste the text into plotting software such as Desmos. Plot the runtimes of all 5 approaches on the same graph.

AdjacencyListSeamFinder(DijkstraSolver::new)
AdjacencyListSeamFinder(ToposortDAGSolver::new)
GenerativeSeamFinder(DijkstraSolver::new)
GenerativeSeamFinder(ToposortDAGSolver::new)
DynamicProgrammingSeamFinder()

Compare the runtimes across all 5 approaches. Are certain algorithms faster than others? What might explain the differences? How does the choice of SeamFinder and the choice of ShortestPathSolver affect the runtime?

Here are some factors to consider in your discussion:

What differences between ToposortDAGSolver and DijkstraSolver might affect runtimes? How many times does each implementation traverse the pixel graph?
How might the number of traversals from the ShortestPathSolver affect the number of calls to the neighbors() method in the SeamFinder?
What differences between GenerativeSeamFinder and AdjacencyListSeamFinder might affect runtimes? How might the runtimes of their respective neighbors() methods compare?

Algorithm engineering

Apply the provided patch to incorporate Project Sidewalk roadway access scores to navigation directions in Husky Maps. Access scores in Project Sidewalk are decimal values between 0 and 1 that are used to modify the edge weights. Read the code in src/MapGraph.java and identify how access scores are used in Husky Maps.

Explain the mathematics behind how the patch incorporates access scores. What is the default roadway access score for roadways that are not in the dataset? What are the consequences of the mathematics and this default score for roadways that are not in the dataset?

This approach of modifying edge weights works, but forces all navigation directions to incorporate access scores.

Explain how to modify the provided approach to allow users to choose whether they want to use access scores. Then, take the alternative approach discussed during class and modify it to also allow users to choose whether they want to use access scores. Your modifications should be plain English descriptions; this is not yet the stage to implement the design into the project.