Lab 9: Graphs

Lectures needed for this lab: Lecture 21 (Tree and Graph Traversals), Lecture 22 (Graph Traversals and Implementations), and Lecture 23 (Shortest Paths), or Chapters 20, 21, and 22.

Here are the slides presented in lab for your reference.

FAQ

Each assignment will have an FAQ linked at the top. You can also access it by adding “/faq” to the end of the URL. The FAQ for Lab 9 is located here.

Introduction

In lecture, we talked about the following graph traversals:

  • Depth First Search (DFS)
  • Breadth First Search (BFS)
  • Dijkstra’s

Each of these traversals starts from a single node, then traverses the graph in a specific order. That is:

  • DFS visits nodes “depth first”.
  • BFS visits nodes “breadth first” (smallest number of links from source).
  • Dijkstra’s visits nodes “closest first” (minimum total weight from source).

In this lab, we’ll provide you with a graph class implementation. You’ll implement DFS and BFS. As a stretch goal, you can also implement Dijkstra’s.

We also provide a web browser based visualizer so you can see the graph and your implemented traversals.

Goals and Outcomes

By the end of this lab, you will…

  • Know how to interact with a graph class.
  • Be able to implement depth first search and breadth first search on an undirected graph, and read preorder, postorder, and BFS orders off of them.
  • Stretch goal: Be able to implement Dijkstra’s algorithm using a priority queue that supports changePriority.

Setup

Follow the Assignment Workflow Guide to get started with this assignment. This starter code is in the lab09 folder. NOTE as with previous labs you do not need to submit this assignment. Instead, you will get credit by completing a checkpoint with your TA during lab.

The code is split into three folders:

Folder What’s in it
lab9lib Lab9Graph and ExtrinsicMinPQ, the two data structures you’ll build on. No need to open or modify these files.
lab9main Main, which builds an example graph and opens the visualizer. The other file in this package is the visualizer’s internals, and you don’t need to open it.
lab9algorithms Lab9DFS, Lab9BFS, and Lab9Dijkstras. This is where you write code.

The visualizer uses Javalin to serve a web page, which comes from library-fa26, so make sure the library is attached to your project as described in the workflow guide.

Lab9Graph

In this lab, you’ll be using a provided graph class called Lab9Graph.

Lab9Graph is an undirected graph whose nodes are Strings and whose edges have int weights. It has six methods:

Method What it does
void addNode(String s) Adds node s. Does nothing if s is already in the graph.
void addEdge(String u, String v, int w) Adds an undirected edge between u and v with weight w. If u or v isn’t in the graph yet, it is added.
boolean hasEdge(String u, String v) Returns whether there is an edge between u and v.
int edgeWeight(String u, String v) Returns the weight of the edge between u and v. Throws an exception if there is no such edge.
List<String> neighbors(String u) Returns the neighbors of u.
List<String> nodes() Returns every node in the graph.

In 61B, all graphs are simple, i.e. we do not allow self-edges (e.g. cow - cow) or parallel edges (two edges between cow - dog). The Lab9Graph class has the property that nodes and edges are returned by nodes and neighbors in the order added, though not all real world graph classes do this.

Open lab9algorithms/Lab9DFS.java. Like the DepthFirstPaths class from lecture, it does all of its work in the constructor.

public Lab9DFS(Lab9Graph g, String start)

The constructor runs a DFS of g from start, recording information as it goes in the provided instance variables.

A Lab9DFS object has the following methods:

Method What it returns
boolean reachable(String s) Whether the search reached s, i.e. whether there is a path from start to s. The starter code already throws IllegalArgumentException if s is not in the graph.
List<String> preOrder() The DFS preorder: each node is added as soon as it is visited, before its neighbors are explored. start is always first.
List<String> postOrder() The DFS postorder: each node is added only after all of its not-yet-visited neighbors have been fully explored. start is always last.

Your Lab9DFS should use the same basic algorithm as DepthFirstPaths from lecture 22. If you want to see it in action again, step through the DepthFirstPaths demo from lecture 21.

Implement the constructor of Lab9DFS. The three query methods are already written for you; they just read off the instance variables that your constructor fills in. Use the provided tests to verify the correctness of your solution.

Main

After passing the tests, to see your DFS in action, open the Main class and run its main method. Then go to http://localhost:4567 in your web browser. Click Compute and the program will use your Lab9DFS to compute the DFS preorder. You can also use the Visualize button to see an animation of your computed DFS preorder. You can also use the Order dropdown to switch from DFS preorder to DFS postorder.

You can select other Start nodes if you’d like.

To check off your lab, show the results of running “Visualize” for both the DFS preorder and the DFS postorder from the arbitrary starting point of your choice. The server keeps running until you stop the program, so when you’re done looking, stop Main in IntelliJ. You will also answer 1 checkoff question.

If you see an error about port 4567 already being in use, you probably have an earlier run of the visualizer still going. Stop it and try again.

Since you haven’t implemented BFS or Dijkstra’s, these orders will not work yet.

Now open lab9algorithms/Lab9BFS.java. It has the same shape as Lab9DFS: the constructor Lab9BFS(Lab9Graph g, String start) runs a breadth first search from start, and three query methods read off the answers:

Method What it returns
boolean reachable(String s) Whether there is a path from start to s. Starter code throws if s is not in the graph.
int distTo(String s) The distance from start to s. Or -1 if it is unreachable.
List<String> order() The BFS order: the order in which nodes were removed from the queue. start is always first.

You should use the same algorithm that we saw in lecture 22. If you want to see it in action again, step through the BFS demo from that lecture.

This time we have not provided the instance variables for you. You’ll need to pick those yourself.

Implement the constructor, reachable, distTo, and order in Lab9BFS.

When you’re done, you can use the Main.main() method again.

Part 3: Dijkstra’s Algorithm

As a stretch goal, you can also implement Dijkstra’s algorithm. To do this, open lab9algorithms/Lab9Dijkstras.java.

public Lab9Dijkstras(Lab9Graph g, String source)

The constructor runs Dijkstra’s algorithm from source, treating every edge weight as a distance, and stores the resulting shortest paths tree. The three query methods then just read off the answers:

Method What it returns
boolean hasPathTo(String v) Whether there is any path from the source to v. The source always has a path to itself.
int distTo(String v) The total weight of the shortest path from the source to v. Throws IllegalArgumentException if there is no path.
List<String> shortestPathTo(String v) The shortest path as a list of nodes, starting with the source and ending with v. For the source itself this is the one-element list [source]. Throws IllegalArgumentException if there is no path.

This time, we’ve provided the needed instance variables for you. As before, the starter constructor already throws IllegalArgumentException if source is not a node of g.

The algorithm

Recall Dijkstra’s from lecture 23 (the demo is a good refresher). It keeps track of:

  • distTo: the best known distance from the source to each node, and
  • edgeTo: the node we came from on that best known path.

Then:

  1. Set distTo[source] = 0. Add every node to an ExtrinsicMinPQ with priority equal to its distTo (use a large value like Integer.MAX_VALUE for nodes you haven’t reached yet).
  2. While the priority queue is not empty, remove the node u with the smallest priority. If its distance is still “infinite”, every remaining node is unreachable and you can stop.
  3. For each neighbor v of u, relax the edge: if distTo[u] + edgeWeight(u, v) is less than distTo[v], update distTo[v] and edgeTo[v], and call changePriority(v, distTo[v]).

To answer shortestPathTo(v), walk edgeTo backwards from v to the source, then reverse the result.

You’ll need to use the provided ExtrinsicMinPQ class described in the next section.

Only relax edges to nodes that are still in the priority queue. Once a node has been removed, its distance is final, and calling changePriority on an item that isn’t in the queue throws an exception. contains is available to check if an item is in the queue.

Implement the constructor and the three query methods of Lab9Dijkstras.

ExtrinsicMinPQ

ExtrinsicMinPQ is a priority queue of Strings, where each item’s priority is an int supplied from the outside (hence “extrinsic”). You’ll use it for the fringe in Dijkstra’s algorithm. The methods you need:

Method What it does
void add(String x, int priority) Adds x with the given priority. Throws if x is already present.
String removeSmallest() Removes and returns the item with the smallest priority.
int size() Returns the number of items in the queue.
void changePriority(String x, int p) Changes the priority of x to p. Throws if x isn’t in the queue.
boolean contains(String x) Returns whether x is in the queue.

This project is called an extrinsicMinPQ because the priorities of an item are set extrinsically to the item. That is, the priority of a given String isn’t given by its alphabetical order or its length or anything like that, but rather the integer that is arbitrarily assigned to it.

Checkpoint

As you work through the lab, check in with your TA as a group to get attendance credit. Your TA will explain how check-ins work in your section.

You do not need to have everything 100% correct to get credit. Keep working on the lab while you wait for your TA!

Deliverables

There is nothing to submit for this lab. You get credit by checking in with your TA during your lab section.

Files that you need to modify:

  • lab9algorithms/Lab9DFS.java
  • lab9algorithms/Lab9BFS.java
  • lab9algorithms/Lab9Dijkstras.java