# Shortest Paths

Designing and analyzing shortest paths.

- Seam finding interfaces
- Graph interfaces
- Reference implementation
- Design and implement
- Analyze and compare

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.

## Can I work with someone else on this project?

Although this project requires an individual submission, you may find it useful to discuss overarching ideas with your classmates. Our primary rule is that we ask that you do not claim to be responsible for work that is not yours. If you get some help from someone else or from an online resource, cite it. I believe that there is a lot of value in learning from others so long as you do not deprive yourself (or others) of the opportunity to learn.

We are comfortable doing this because each submission in this class comes in the form of a video that you record. Your video is a demonstration of everything that you learned throughout the process of working on an assignment. Our goal is for students to support each other and find community through this course. The real advantage of taking a course on-campus at a university is to be able to connect with others who share common interests in learning.

## What am I submitting at the end of this project?

Satisfactory completion of the project requires one Canvas submission including: a **video-recorded individual presentation**, some kind of **visually-organizing structure, such as slides or a document** and **a link to your src/main/java folder on GitLab** that addresses all the green callouts.

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

Your video presentation should meet the following requirements:

- Your presentation should not be much longer than 8 minutes (9 minutes maximum) and should include your voiceover. (Your video is appreciated but not necessary.)
- Your video presentation should include some kind of visually-organizing structure, such as slides or a document.
- After submitting to Canvas, add a submission comment linking to your slides or document, a link to your
`src/main/java`

folder on GitLab, and a list of your citations and references used. Remember to`commit`

and`push`

to Gitlab and check that the associated status for your latest Pipeline is a green checkmark!

**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 assignment submissions 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 a **canvas comment** turned in with your video presentation, you must cite any sources you used, 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.

## 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 to create five different approaches for seam finding.

`AdjacencyListSeamFinder(DijkstraSolver::new)`

`AdjacencyListSeamFinder(ToposortDAGSolver::new)`

`GenerativeSeamFinder(DijkstraSolver::new)`

`GenerativeSeamFinder(ToposortDAGSolver::new)`

`DynamicProgrammingSeamFinder()`

Make sure to pass all the `tests`

for all 5 implementations, push your code to Gitlab, and check that the associated status for your latest Pipeline is passing. If the implementations do not pass all the test cases, explain in your video what you think could be causing the problem.

### 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.

Walkthrough how you adapted the ideas from `AdjacencyListSeamFinder.PixelGraph`

to implement `GenerativeSeamFinder.PixelGraph.Pixel.neighbors`

. Make sure to also point out the key similarities and differences between the two implementations.

### 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 a bug you avoided or fixed (or one you are currently fixing) while implementing the `DynamicProgrammingSeamFinder`

class that you found challenging. Point out the lines of code that the bug was (or is) most applicable to and explain the logic of the code.

## 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.

To let `RuntimeExperiments`

run, make sure to comment out the `@Disabled`

line before it. Make sure to keep `@Nested`

. Once you are done running `RuntimeExperiments`

, please uncomment the `@Disabled`

line to ensure that our pipeline to check your tests will work!

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 you should 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?

### Picture analysis

Run the SeamCarver on two images and share it during the presentation.

- Run one picture that is the most
*seamless*: the “after” looks the most natural, you can barely tell it was seam carved. - Run another picture that is the most
*messed-up*: the “after” looks the most distorted, seam carving really messed it up.

For the two pictures, show both the before and after pictures, along with the dimensions you chose to carve to, and analyze why the seam carver peformed the way it did.

- Add your own image to
`data/seamcarving`

. Java supports GIF, PNG, JPEG, BMP, and WBMP images.- In
`src/seamcarving/SeamCarver.java`

, change the`INPUT_PATH`

and`OUTPUT_PATH`

fields to your desired input and output locations. You can also change the implementation of SeamFinder to use (some may be faster than others)!- Run the SeamCarver class and follow the prompts to resize your own images!