DFS Assignment

The depth-first search algorithm is a recursive algorithm that has an initialization piece and a recursive piece. A high-level view of the algorithm is:

dfs(G)
reset the graph, and set the timestamp to 0
for each vertex u in V(G)
if u.mark is unvisited
dfs_visit(u)

dfs_visit(u)
u.mark = in-process
u.start = ++timestamp
for each v in Adjacent(u)
if v.mark == unvisited
v.predecessor = u
dfs_visit(v)
u.mark = processed
u.finish = ++timestamp

Implement this algorithm in the DFS.java template in the like named methods. Notice that the main() function builds the graph using Graph.factory() with the initial values in main() creating a Graph object which has an adjacency list representation of the graph. main() calls the method assignWeek9() which in turns calls dfs(). After dfs() returns, the method allEdges() is called with a Callback instance. The method call() is in the class CB1 at the end of the source code and should also be filled out. allEdges() will call CB1.call() for each edge (u,v) in the graph. call() should classify the edges according to the following.

tree edges should be mark as such in dfs_visit()
forward edges have timestamps that satisfy: start(u) < start(v) and finish(v) < finish(u)
back edges have timestamps that satisfy: start(v) < start(u) and finish(u) < finish(v)
cross edges are all other edges

call() should write the classification on System.out. It should look like:

s->z is a tree edge
s->w is a forward edge
z->y is a tree edge
z->w is a tree edge
y->x is a tree edge
x->z is a back edge
w->x is a cross edge
t->v is a tree edge
t->u is a tree edge
v->w is a cross edge
v->s is a cross edge
u->t is a back edge
u->v is a cross edge

Study the template code carefully. It should contain enough information to get you over any hurdles. The graph is the same graph that is in the lecture notes in the DFS discussion. ( You just have to edit the code below)