A printable PDF is available.

# Assignment 6 - Due Thursday, December 1

**Objective:** The objective of this assignment is for you to
combine several algorithms and data structures that we have seen in
this class to implement an algorithm for finding strongly connected
components in a graph.

**Background:** A *strongly connected component* in a
directed graph is a maximal subgraph such that there is a directed
path between any two vertices in the component (in both
directions). In class, we wrote code for depth first search in order
to find regular connected components in an undirected graph, and in
this assignment you are to use depth first search to find strongly
connected components in a directed graph. The algorithm, described
below, requires two depth first search operations (slightly modified
from what we wrote in class), a stack (you can use the stack provided
by `java.util.Stack`

), and a graph transpose operation (which you
wrote for the previous assignment). To describe the algorithm,
consider the following graph, where the dark edges show the edges
explored in a depth first search of this graph:

To find strongly connected components, you should use "Kosaraju's algorithm", which works as follows:

- Use depth first search to explore the graph -- in our
example,
*A*is visited first, and then we follow the edge to*E*, and from*E*we first explore to neighbor*D*, etc. During the depth first search, push vertices onto a stack when the depth first search has finished exploring all neighbors and the algorithm is about to backtrack. In our example, vertices are pushed on the stack in the following order:*C,D,G,F,E,A,H,J,I,B*(another way of looking at what this is that we're doing a postorder traversal of the depth first search tree, pushing vertices on the stack during that traversal).*Hint: The stack should be a stack of vertex**names*, not vertex objects, since you'll need to find these vertices in a*different*graph below. - Next, take the transpose of the graph (pictured below for
our example -- ignore the dashed outlines for now).
- Finally, do the same depth first search exploration and
component printing for the transposed graph that we did in class,
*except*instead of a top-level loop that iterates through vertices using the`vertexMap`

, you'll iterate through the vertices by popping them off the stack you created in step 1. So in our example, we first pop "B" off the stack, and perform a depth first search to determine the vertices that are reachable from "B" in the transposed graph, giving*B,J,I*as the first strongly connected component. Next, "I" and "J" are popped off the stack, but since they have been visited we don't do anything with them. Next off the stack is "H" so we perform a depth first search from*H*and see that*H*is in a strongly connected component by itself. Continuing in this manner, we explore from*A*to get component*A,C,D,E*, and then from*F*to get component*F,G*. The dashed outlines on the graph show these components (while they are shown in the transposed graph, these are also strongly connected components in the original graph -- do you see why?).

**What To Do:** Start with the code in
Bitbucket, as in previous assignments: fork the "Assign6"
repository, rename it to include your username, grant read access to
the class administrators, and then use NetBeans on your computer to
clone it so you can work with it. This is just a copy of the code we
worked with in class, including our class-written depth first search
code (slightly cleaned up from class). The repository also contains
two data files, "`a6graph1.in`

" and "`a6graph2.in`

": the
first contains the example graph that we used in the discussion above,
and the second reflects results from a big chess tournament (we'll say
more about this in class). You should implement the algorithm
described above, printing out strongly connected components in the
same style as we printed regular connected components from an
undirected graph.

**Submission Instructions:** Using NetBeans, commit all changes
to your project and do a "push to
upstream" to put the most up-to-date files on the Bitbucket
server. Remember: Do *not* create a pull request --
I will clone your repository (if it exists
and you granted me access) at 12:30 on the due date, and will
assume that is your submission. If you intend to keep working on your
project and submit late, please let me know by email, and I will
ignore your repository until the late submission deadline.