Lab 8: Graphs

Copyright RIT 2009
$Id: writeup.xml,v 1.16 2009/04/26 20:34:37 vcss233 Exp $

Goal

1. Gain a better understanding of graphs.
2. Work with a graph interface.
3. Write code that implements a basic graph based algorithm.

Team Setup

You are to work on this lab completely on your own.

Overview

This lab provides you the opportunity to work with the DiGraph interface. You will write two short programs: the first will build a graph from data entered from standard input, and the second will print a depth-first traversal of a graph.

Pre - Lab Work

1. Review your class notes on graphs

2. Study the DiGraph interface.

3. Write a pseudo-code version of the DFS algorithm.

In-Lab Activities

Activity #1 : Build a graph from a data file

In this activity you will write the BuildGraph class that builds and prints a digraph. The information that will be used to build the graph will be provided by the user from standard input. Click here (http://www.cs.rit.edu/~vcss233/pub/lab08/Binaries/lab8.jar) to download the jar file that you will need to complete this activity.

In the jar (http://www.cs.rit.edu/~vcss233/pub/lab08/Binaries/lab8.jar) that you just downloaded you will find the class files that provide a simple array based implementation of a DiGraph named ArrayDiGraph. Take a few minutes to look over the Javadoc pages for both the DiGraph interface and the ArrayDiGraph class.

The BuildGraph program that you will write in this activity reads information from standard input that will be used to construct a digraph. (Recall that when you write a program that reads from standard input, you have the option when running your program by either entering data directly or redirecting input from a data file that you have previously constructed.) Each line that your program reads contains information that will be used to construct either a vertex or an edge in a graph. Lines that define a vertex consist of a single character which defines the name of the vertex. The first two characters in a line that defines an edge specify the name of the vertex where the edge begins and the name of the vertex where it ends. The rest of the information on an edge line defines the data that is to be associated with the edge - the cost can be more than one character in length. For example, the input below:

A B C AB1 AC2 D BC3 CD4 BD5

Defines the graph illustrated below:

A graph

When writing your program you may assume that a vertex will be defined before it is used in an edge and that the input is correct. In other words don't put a lot of effort into checking the input to see if it is valid. The purpose of this lab is for you to learn how to work with the DiGraph interface and not to process dirty input.

After building the graph, the BuildGraph program will print the graph on standard output. The output shows the structure of the graph by listing the number of vertices followed by the names of the vertices in alphabetic order. For each vertex the output shows the number of neighbors for the vertex, followed by the names of the neighbors and the data associated with the edges that lead to the neighbor. The edges are listed in alphabetic order by the name of the destination vertex.

Running the BuildGraph program on the data given above produces the following output:

Num Vertices: 4 A (in degree == 0, out degree == 2) to B cost 1 to C cost 2 B (in degree == 1, out degree == 2) to C cost 3 to D cost 5 C (in degree == 2, out degree == 1) to D cost 4 D (in degree == 2, out degree == 0)

If any exceptions occur while the program is running, the program should print a brief message to standard error that describes the nature of the exception (printing the message included with the exception should suffice) and then should terminate.

How To Submit

Remember that in order for your program to be considered correct, it must produce the exact same output shown above. When you are sure that your program can build a graph and print it, submit your work by typing the following command:

try grd-233 lab8-1 BuildGraph.java

Activity #2 : Implement the DFS algorithm

A depth-first search (DFS) of a graph starts at a given vertex and visits the vertices in the graph one branch at a time.

One algorithm to perform a depth-first search on an arbitrary graph is outlined below:

• Push the starting vertex into a stack
• While the stack is not empty
  • Pop the vertex currently at the top of the stack
  • If the node has not been visited
    • Print the name of the vertex
    • Mark the vertex as having been visited
    • Push the un-marked neighbors of the vertex onto the stack

Look at the following graph.

A graph

The actions taken by running the DFS algorithm starting at vertex A are listed below:

1. Push A on to the stack
2. Pop the top of the stack --> A
3. Since A has not been visited
   1. Print A
   2. Mark A as visited
   3. Push A's unmarked neighbors (B,C) on to the stack in that order
4. Pop the top of the stack --> C
5. Since C has not been visited
   1. Visit C
   2. Mark C as visited
   3. Push C's unmarked neighbor (D) on to the stack
6. Pop the top of the stack --> D
7. Since D has not been visited
   1. Visit D
   2. Mark D as visited
   3. D has no neighbors!
8. Pop the top of the stack --> B
9. Since B has not been visited
   1. Visit B
   2. Mark B as visited
   3. B has no unmarked neighbors
10. Stack is empty, you're done

In this activity you are to write a program named DFS that will perform a depth-first search on a graph entered on standard input. The DFS program will read the graph in the same way that the BuildGraph program does (in fact you would be wise to start by copying the code you wrote in activity 1). The search will start at the first vertex read when building the graph. The DFS algorithm that you will implement in this program will follow the algorithm given above, except that the neighbors of the node that you are visiting must be added to the stack in alphabetical order by name - however, note that this means they are actually visited in reverse alphabetical order! (i.e. the neighbors of A are pushed on in the order B followed by C, not C followed by B). The output of the program should consist of one line for each vertex visited in the graph, where the vertices will be printed out in the order they were visited.

It is also easy to write a DFS function in a recursive fashion. Simply, instead of pushing an unmarked vertex on to a stack, you immediately start a DFS from that vertex. As long as you properly mark each node, this will be sufficient - you are essentially using the call stack as your data structure! You are welcome to implement your DFS function in this way, but make sure to stick to the ordering defined above, that is, starting DFS on the neighbors of a given node in reverse-alphabetical order.

Running the DFS program on the graph shown above will produce the following output:

A C D B

As in activity 1, you may assume that the input to the program will be in the proper format. Your task here is to implement the DFS algorithm not handle dirty input. If any exceptions are encountered while the program is running, a brief message describing the nature of the exception should be printed to standard error and the program will terminate.

Also, you do not have to find or implement a stack class for this lab. Just use a List and restrict your code to use only those methods that would be appropriate for last-in-first-out (LIFO) operation.

How To Submit

When you are sure that your program is working correctly, submit your work by executing the following command:

try grd-233 lab8-2 DFS.java

Grade Computation

Grade Breakdown:

• In-lab participation: 3 points
• Build a graph from a data file: 10 points (submitted)
• Implement the DFS algorithm: 13 points (submitted)
• Style: 4 points