HW6: Graph Algorithms

25 points; due Mon 4/21 @ 11am.

Goals

To implement some algorithms that involve graph traversal, and in so doing get experience with using the Stack, Queue, and Graph ADTs.

Setup and Requirements

In this assignment you will write a single class with at least two static methods, each one implementing a particular algorithm that computes some property of a given graph. (You will also write a main method that tests your algorithm implementations.)

Working with a partner is strongly suggested (but optional) for this assignment. If you'd like to work in a pair, please figure out who you'd like to work with via Piazza or email, and then email me once your pair is decided. Make sure to put both people's names at the top of each file. Write your code by pair-programming: code together, at the same computer, and switch off who's at the keyboard. Note that it is not acceptable for one of you to work on one algorithm while the other works on the other; you should be working together to solve each problem as a pair. Only one of you should ultimately submit your team's code via Moodle.

The code that you write for this assignment will build on top of a variety of ADT interfaces and implementations (including List, Stack, Queue, and Graph). Download the following zip file and unzip its contents into the same directory where you write your code for this assignment:

You may also find the documentation useful, as well as the example code that we wrote together in class on Wednesday.

The hand-in for this assignment is a single file, GraphTraversal.java. Create this file and an empty class GraphTraversal inside of it. (Remember to put your and your partner's name at the top!) Each of the next two sections describes a problem that can be solved using graph traversal, and describes an algorithm that solves it. Implement each algorithm in a static method with the name and signature given in that section.

A general requirement of this assignment is that you are allowed to write only static methods. The class GraphTraversal cannot have any non-static data members or methods; it is meant only as a container for the functions that you write. You may write static helper methods if you'd like, but the class should hold no state and no code you write should create any instances of the GraphTraversal class. In addition, you may not write any additional classes, nor use any of Java's built-in container types. (This is all fairly contrary to Java's object-oriented design philosophy, but graph algorithms are much clearer if you write them in a functional style.)

As you write your algorithms, you should make sure to test them on a variety of input graphs. Write your tests in the main method of the class. Your test suite will be evaluated as part of your grade, so try to make it thorough, and make sure to test weird edge cases (like empty graphs, or graphs with many connected components, or complete graphs).

Problem 1: Detecting a Connected Component

The Problem

This is the task of computing the set of all the vertices in the connected component of a given vertex. For example, in the following graph, the connected component that includes vertex 5 is the vertex set $\{5, 8, 3, 2, 4\}$:

The Algorithm

Given a graph $G = (V, E)$ and a vertex $s$ in that graph, an algorithm to compute the connected component of $s$ may be built on top of breadth-first search. Here's how it works:

  • Let $n = |V|$. ($|V|$ is the number of vertices in the graph.)
  • Create an empty queue called $Q$.
  • Create a list, $D$, of length $n$. (This list will store the number of edges it takes to get from $s$ to each other vertex $i$.)
  • Set $D[i] = -1$ for all $i = 0, 1, 2 \ldots (n-1)$. (At the beginning of the algorithm, we don't know how many steps it takes to get from $s$ to any other node, so we use the sentinel value -1 to indicate that.)
  • Set $D[s] = 0$ and enqueue $s$ in $Q$.
  • While $Q$ is not empty:
    • Dequeue a vertex from $Q$ and call it $v$.
    • For each neighbor $u$ of $v$:
      • If $D[u] = -1$, set $D[u] = D[v] + 1$ and enqueue $u$ in $Q$.
  • We have now computed the connected component of $s$: each vertex $i$ for which $D[i] \ge 0$ is in $s$'s connected component.

Take a few minutes to think through why this algorithm works. What makes this a breadth-first search? (The answer is more fundamental than “it uses a queue”.) How do we know that all the vertices in $s$'s connected component have been given a non-negative value in $D$ by the time the while loop exits? How do we know that this algorithm will terminate (that is, that it won't run forever)?

Your Implementation Instructions

Implement the above algorithm in a method with the following signature:

/**
 * Computes and returns the list of all vertices in the graph G that are in the
 * same connected component as a specified node.
 * 
 * @param          G The graph in which to search.
 * @param targetNode The ID of a node in G.
 * 
 * @return A List of node IDs (with no repeats) of the nodes in G that are in
 * targetNode's connected component.
 */
public static List<Integer> connectedComponent(Graph G, int targetNode)

Note that the algorithm was described in prose using mathematical notation, so the variable names are very short, as is standard in math. When you implement it in code, you should use descriptive variable names.

An Extra Challenge

This step is optional; it's just here for fun if you want to try implementing an extra feature.

Create another method that computes all of a graph's connected components:

/**
 * Computes and returns all the connected components of a graph.
 * 
 * @param G The graph in which to search.
 * 
 * @return A List of Lists of node IDs.  Each inner list represents a single
 * connected component of G: its contents are the IDs (with no repeats) of all
 * the nodes in the component.  The full output accounts for every node in G,
 * and lists each node only once.
 */
public static List<List<Integer>> allConnectedComponents(Graph G)

The algorithm to do this involves just a small modification to the single-component algorithm given above.

Problem 2: Detecting a Cycle

The Problem

This is the task of computing a set of vertices that form a cycle somewhere in the connected component of a given vertex. For example, in the following graph, the cycle $(2, 4, 8, 5)$ is in the connected component that includes vertex 3:

The Algorithm

Given a graph $G = (V,E)$ and a vertex $s$ in that graph, an algorithm to detect a cycle in $s$'s connected component (if there is one) may be built on top of depth-first search. Here's how it works:

First, set everything up to do the search:

  • Let $n = |V|$.
  • Create an empty stack called $S$.
  • Create a list, $P$, of length $n$. (For each vertex $i$, $P[i]$ will store $i$'s “predecessor” — the vertex we came from to get to $i$.)
  • Set $P[i] = -1$ for all $i = 0, 1, 2 \ldots (n-1)$. (We haven't visited anything yet.)
  • Set $P[s] = s$ and push $s$ onto $S$.
  • Let $c = -1$. ($c$ will be the ID of a single node in a cycle, if we find one.)

Then search the graph for a cycle:

  • While $S$ is not empty and $c = -1$:
    • Pop a vertex from the top of $S$ and call it $v$.
    • For each neighbor $u$ of $v$:
      • If $P[u] = -1$:
        • Set $P[u] = v$.
        • Push $u$ onto $S$.
      • Otherwise, if $u \ne P[v]$:
        • Set $c = u$. (We've detected a cycle!)
        • Set $P[P[u]] = u$.
        • Set $P[u] = v$.
        • Immediately break out of the for loop.

Finally, reconstruct the cycle from the values you computed.

  • If $c = -1$, then there are no cycles in $s$'s connected component, and we're done.
  • Otherwise, the values in $P$ tell us how to walk backward around the cycle from $c$. So:
    • Create an empty list, $C$.
    • Add $c$ to the end of the list, and let $v = P[c]$.
    • While $v \ne c$:
      • Add $v$ to the end of the list.
      • Let $v = P[v]$.
    • Return $C$.

Take a few minutes to think through why this algorithm works. What makes it a depth-first search? How can we be certain we'll find a cycle if there is one to be found in $s$'s connected component? How do we know, when we perform the “Otherwise, ...” step, that the vertex $c$ is a member of a cycle? Why do we have to check the condition $u \ne P[v]$ before we decide that? (What would happen if we didn't check?)

Your Implementation Instructions

Implement the above algorithm in a method with the following signature:

/**
 * Computes and returns a list of vertices in some cycle in the connected
 * component of a specified vertex in a graph.
 * 
 * @param          G The graph in which to search.
 * @param targetNode The ID of a node in G.
 * 
 * @return An empty list if there are no cycles in targetNode's connected
 * component.  Otherwise, a list of node IDs (with no repeats), in order, around
 * some cycle.  There is an edge between the first and last nodes in this list.
 */
public static List<Integer> findCycle(Graph G, int targetNode)

Submission and Grading

Submit your GraphTraversal.java file on Moodle.

Start early, ask lots of questions, and have fun!

Assignment requirements

This is a partial list of the things that we'll be looking for when evaluating your work:

Grading