Shortest Paths
Designing and analyzing shortest paths.
This page is under construction. All content is subject to change.
- 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 than 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, a link to your filled-out [slide template] for Shortest Paths and a link to your src/main/java
folder on GitLab from your projects repo that addresses all deliverables (in green).
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 7 minutes (8 minutes maximum) and should include your voiceover. (Your video is appreciated but not necessary.)
- Your video presentation must include or use our provided slide template for Shortest Paths. This is done intentionally to help guide you toward the correct solution.
- After submitting to Canvas, add a submission comment linking to your slides or document and a link to your
src/main/java
folder on GitLab. Remember tocommit
andpush
to Gitlab and check the associated status for your latest Pipeline is a green checkmark! Please be sure to check access permissions on your slides and video, so any TA can view your 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 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.
Within the provided slide template, you must cite any external sources you used, either through collaboration or online resources. If you consulted any Generative AI on this project, you must include all prompts and outputs. Online sources should be cited with a simple link. Collaboration with peers must include names and the extent of that collaboration. The more detail, the better!
Submitted work that is not consistent with sources will require makeups in Office Hours.
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/main/java/seamfinding
folder.
SeamFinder
- An interface specifying a single method,
findHorizontal
, for finding a least-noticeable horizontal seam in a givenPicture
according to theEnergyFunction
. 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/main/java/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 directedEdge
class provides 3 fields: the origin vertexfrom
, the destination vertexto
, and the edgeweight
. 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: aGraph
and a start vertex. Thesolution
method returns the list of vertices representing a shortest path from the start vertex to the givengoal
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. ThePixelGraph
constructor creates a newPixel
(node) for each pixel in the image. It also creates asource
node and asink
node. List<Node> seam = sps.run(graph, graph.source).solution(graph.sink)
sps.run
calls theShortestPathSolver
(such asDijkstraSolver
) to find the shortest path in thePixelGraph
from thesource
and immediately asks for a shortest path to thesink
. Theseam
stores the solution to the shortest path problem.seam = seam.subList(1, seam.size() - 1)
- The
seam
includes thesource
andsink
, which we don’t need in our final solution. for (Node node : seam) { ... }
- Since the remaining nodes in the
seam
must bePixel
nodes, add each pixel’sy
index to theresult
list and return theresult
.
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 ofpicture.height()
outgoing edges to eachPixel
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 eachPixel
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.
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. Include a link to the passing pipeline of your projects repository in the provided slide template.
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.
To approach this implementation, consider the following steps:
- Study the
AdjacencyListSeamFinder.PixelGraph
constructor, which constructs the entire graph and represents it as aPixel[][]
. - Adapt the ideas to implement
GenerativeSeamFinder.PixelGraph.Pixel.neighbors
, which should return the list of neighbors for a givenPixel
. Create a newPixel
for each neighbor.- For this method, you should identify where the code in
AdjacencyListSeamFinder
connects a givenPixel
to its right-up, right-middle, and right-down neighbors. - You should also be wary of any potential edge cases, based on the restrictions of the picture’s height and width, as well as the
source
andsink
nodes.
- For this method, you should identify where the code in
- Then, define the
source
andsink
nodes. You should implement their respectiveNode.neighbors
methods.- Recall that the source node serves as the starting point for establishing the leftmost column of pixels. What are the bounds of your picture? Which edges must be created?
- Recall that the sink node serves as the ending point from the rightmost column of pixels. Accordingly, how should it implement the method?
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.
Walk through how you adapted the code from AdjacencyListSeamFinder.PixelGraph
to implement GenerativeSeamFinder.PixelGraph.Pixel.neighbors
. What are the key similarities and differences between these two implementations?
ToposortDAGSolver
A graph algorithm that implements ShortestPathSolver
. Finds a shortest paths tree in a directed acyclic graph (DAG) using topological sorting.
You may find it useful to consult the Shortest Path Trees lesson and review the Topological Sorting algorithm.
- Initialize
edgeTo
anddistTo
data structures just as inDijkstraSolver
.- Recall that
edgeTo
is aMap
used to store the previous edge used to reach some givento
vertex. We trace through the values of thisMap
from goal until we reach some desired start node (like backpointers), then reverse the output to determine the path from start to finish. - Recall that
distTo
is aMap
used to store the summed shortest distance from start up to some givento
vertex. Based on the SPT we create for some start node, we can extract any value to determine the length of the path to reach that goal node.
- Recall that
- List all reachable vertices in depth-first search postorder. Then,
Collections.reverse
the list.- Recall that DFS postorder adds vertices to the result list once you reach the dead end of a path, at a node whose neighbors have all been visited. This differs from preorder, where nodes are added to the result list as soon as they are reached.
- For each node in reverse DFS postorder, relax each neighboring edge.
- This means that the process of creating your SPT and determining the shortest possible edges to use should start from the end of your result list that you create using postorder DFS. This is to ensure you respect all dependencies in the graph and visit nodes in order from “parent” to “child” in a hierarchical manner.
- Edge relaxation
- If the new distance to the neighboring node using this edge is better than the best-known
distTo
the node, updatedistTo
andedgeTo
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.- Recall that (x, y) refers to column x and row y.
- 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.
- Consider how the traversals in
GenerativeSeamFinder
andAdjacencyListSeamFinder
overlap with this process of computing energy pixel-by-pixel for a given column by looking at its previous 3 (or 2) neighbors. - It is preferred that you create a separate method for this table filling process entirely.
- Consider how the traversals in
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.
- We can simply determine the minimum value in this column first.
- Follow the path back to the left by adding the y-value of each predecessor to the result.
- To trace through each predecessor and its respective neighbors, consider what extra field you should store besides the value of the minimum energy cost.
- It is preferred that you create a separate method for this minimum seam process entirely.
- Finally, to get the coordinates from left to right,
Collections.reverse
the result.
Walk through your implementation for DynamicProgrammingSeamFinder
. First, discuss the portion of your code that fills the table with energy costs. How does it select the minimum from its neighbors? How does the code handle pixels at the edges of the image? Next, discuss the portion of your code that determines the shortest path and finds the seam with the lowest energy cost. How is the first minimum found in the rightmost column? Afterwards, how do we continue to select previous neighbors with the minimum energy cost?
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.
RuntimeExperiments
are disabled by default. Comment-out the @Disabled
tag above the RuntimeExperiments
class header to enable it.
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()
Once you are done running RuntimeExperiments, please uncomment the @Disabled
line to ensure that our pipeline to check your tests will work!
Display a legible and labelled plot to compare runtimes across all 5 implementations. Which implementation is the fastest, and why?
Determine how differences in SeamFinders
and ShortestPathSolvers
impact their respective runtimes. How do the two SeamFinders
differ in computing neighbors
? How do the two ShortestPathSolvers
differ in the number of times they traverse the PixelGraph
? Based on these properties, determine which combinations of SeamFinders
and ShortestPathSolvers
lead to the fastest runtimes, and the slowest runtimes.
Consider the following questions to facilitate your discussion:
- What differences between
ToposortDAGSolver
andDijkstraSolver
might affect runtimes? How many times does each implementation traverse the pixel graph?- Hint: Consider the difference in the number of steps required between these approaches.
- Hint: Consider the total number of vertices explored in the two algorithms.
- What differences between
GenerativeSeamFinder
andAdjacencyListSeamFinder
might affect runtimes? How might the runtimes of their respectiveneighbors()
methods compare?- Hint: Based on the number of traversals, consider which
SeamFinder
may be faster. - Hint: Based on the number of vertices explored, consider which
SeamFinder
may be faster.
- Hint: Based on the number of traversals, consider which
- Although we don’t require asymptotic analysis for this project, does the experimental analysis agree with your expected asymptotic analysis?