CMSC-341 Fall 2002

Project 5

Assigned 20 Nov 2002
Due 10 Dec 2002 by 11:59PM
Updates 21 Nov 2002 - Because the sample graph below contains no cycles each node is its own strongly connected component, as indicated by the associated sample output.

Background

Despite the fact that depth-first search (DFS) and breadth-first search (BFS) are among the simplest of graph algorithms, they produce a wealth of useful information. In this project, you will use DFS to identify strongly connected components and perform topological sorting in directed graphs.

Recall from class that a strongly connected component in a directed graph is a subset of the vertices such that a path exists from each element of that set to every other element. Also, a topological sort of a directed graph is an ordering of the vertices such that if (u, v) is an edge in the graph then vertex u occurs before vertex v in the ordering. Only graphs without cycles can be topologically sorted.

The description for this project is intentionally much less specific than the descriptions for the previous four projects. At this point in the semester you should have a well developed sense for how to design and implement classes. Spend time working out design details before you start coding.

As usual, be sure to answer the questions posed in the following file and to submit your answers along with your code: /afs/umbc.edu/users/o/a/oates/pub/CMSC341/Proj5/341-Fall02-p5_questions.txt

Description

Your project will read a description of a directed graph from a file and do the following:
  1. Run DFS on the graph to compute discover and finish times.
  2. Determine if the graph contains any cycles.
  3. If the graph is acyclic, print a topological sort of the graph.
  4. Print the strongly connected components in the graph.
DFS - Pseudocode for DFS that computes discover and finish times is given in the lecture notes. Model your code on the algorithm given on slide 16 in the first set of lecture notes on graphs.

Cycles - A directed graph contains no cycles if and only if DFS yields no back edges. Recall that edge (u, v) is a back edge if and only if 

d[v] < d[u] < f[u] < f[v]
You need to write a routine that takes a graph in which the vertices have discover and finish times as computed by DFS and checks to see if any of the edges are back edges. If there are one or more back edges, the graph contains one or more cycle, otherwise it does not.

Topological sorting - Do not use the algorithm in the text for topological sorting. Instead, you will simply print nodes in the graph in reverse order of finish times.

Strongly connected components - Given graph G, let G' be the graph obtained by reversing the direction of all of the edges in G. Then the following algorithm finds the strongly connected components of G: 

STRONGLY-CONNECTED-COMPONENTS(G)
1. run DFS on G to compute finish times
2. compute G'
3. run DFS on G', but when selecting which node to vist do so
   in order of decreasing finish times (as computed in step 1)
4. output the vertices of each tree in the depth-first forest 
   of step 3 as a separate strongly connected component
Note that the DFS algorithm on slide 16 of the lecture notes is actually two algorithms. The first of these algorithms loops over all of the vertices in the graph and starts a DFS from each vertex that has not yet been discovered. Typically, in this loop you can iterate over the vertices in any order. However, in step 3 of the algorithm for discovering strongly connected components, you must iterate over them in order of decreasing finish times as computed in step 1. The second algorithm on slide 16 runs DFS starting from a given vertex and outputs a list of vertices visited. Every such list of vertices corresponds to a strongly connected component in step 4 of the algorithm above.

All classes that you design and implement must support the "Big-4", even if the default behavior provided by the compiler would be acceptable - default constructor, destructor, copy constructor, assignment operator.

You will need to implement at least the following classes:

  1. vertex - a single node in a graph
  2. graph - a collection of vertices and edges
You may use whatever representation for edges you think is best, e.g. adjacency matrix, adjacency list, etc.

The Command Line

Project 5 will be invoked with a command line that consists of a single argument - the name of a file describing a graph. The format of this file is described below. After validating the command line, you should create a graph based on the contents of the file and then perform the operations described above.

The Data File

The data file will describe a single directed graph. The format of this file is as follows: The following is a valid data file: 
4
3
0 1
1 3
0 2
The graph that it describes looks like this: 
    0 ------> 1
    |         |
    |         |
    |         |
    v         v
    2         3
The number of nodes will always be an integer greater than zero. The number of edges will always be an integer greater than or equal to zero. If the file says there are M nodes and N edges, there will always be N + 2 lines in the file and lines 3 through N+2 will contain a pair of integers between 0 and M - 1.

For the graph above, your output might look like this: 

The graph does not contain any cycles.

Topological sort: 0 1 3 2

Strongly connected components:
 
0

1

2

3
NOTE: There may be multiple valid topological sorts for a graph, as there are for the graph above. Also, if the graph is acyclic, it can be toplogically sorted, but no strongly connected component will contain more than one node. If the graph has cycles, it cannot be topologically sorted, but some strongly connected component will contain more than one node.

Project Submission

Submit all files required to build your project.
Submit Tools
There are a number of tools available to you to check on your submittal. It is your responsibility to ensure that the submittal is correct and will result in a successful compilation of your project. Do not wait till the last minute to submit your files. Give yourself enough time to check that your submittal is correct.

If you don't submit a project correctly, you will not get credit for it. Why throw away all that hard work you did to write the project? Check your submittals. Make sure they work. Do this before the due date.

Documentation for the submit program is on the web at http://www.gl.umbc.edu/submit/. One of the tools provided by the submit program is submitls. It lists the names of the files you have submitted.

Additionally, there are two programs for use only by CMSC-341 students (not part of the UCS submit program). They are in the directory
/afs/umbc.edu/users/d/e/dennis/pub/CMSC341/ and are named submitmake and submitrun. You can use these programs to make or run your submitted projects.

The syntax is similar to that for submit:

submitmake <class> <project>

Example:  submitmake cs341 Proj5

This makes the project, and shows you the report from the make utility. It cleans up the directory after making the project (removes .o files), but leaves the executable in place.

submitrun <class> <project> [command-line args]

Example:  submitrun cs341 Proj5 test.dat

This runs the project, assuming there is an executable (i.e. submitmake was run successfully).

Grading and Academic Integrity

Your project will be tested using a variety of command lines, some of which will be invalid.
Your project will also be tested using a variety of command files which will test various conditions which your code should handle.

Project grading is described in the Project Policy handout.

Your answers to 341-Fall02-proj5_questions.txt are worth 10% of your project grade.

Cheating in any form will not be tolerated. Please re-read the Project Policy handout for further details on honesty in doing projects for this course.

Remember, the due date is firm. Submittals made after midnight of the due date will not be accepted. Do not submit any files after that time.