CMSC-341, Spring 1999, Sections 101 and 201

Project 5


Assigned  19 April 1999            Due  10 May 1999 - No late projects accepted

Background

This project will expose you to some of the basic issues in programming graphs. You will choose a suitable implementation for a directed graph and read data for the graph from a file. You will then determine a topological sorting for the graph.

The graph will represent a prerequisite structure for CMSC courses (close to but not exactly the real prerequisite structure). It will be a directed graph G = (V,E) in which the values stored at the vertices are course names. There is a directed edge (u,v) just when course v is a prerequisite for course u. Here's an example for some of the courses in the CMSC program. It shows, for example, that CMSC-201 is a pre-requisite for both CMSC-202 and for CMSC-331. As another example, MATH-150 has no pre-requisites.



The graph can be used to answer questions about the order in which courses must be taken, and about optimal ways to schedule courses for earliest graduation.

Description

Write C++ code to implement a graph. Write a main function to produce the output described below.

You are free to use your own designs for any classes in this project. You may name your files anything you wish with the two restrictions that the executable must be named Proj5 and there must be a makefile named either makefile or Makefile. The executable must take one argument on the command line, the name of the file from which to read the courses and their prerequisites.

Please think a bit about your design for this project. Design for clarity, extendability, and performance. The type of value stored at a vertex should be given by the template class. You may assume that each vertex in the graph has a unique value (no duplicates). You may also assume that the graph is directed. It is possible that the graph may be cyclic and you should detect this and report it.

Input data is to be in a file such as prereqs.txt or prereqs-cycle.txt, below. Each line in a data file is a space-separated list of course names. The first course on each line is a prerequisite for each of the other courses on that line.

In case the file describes a cyclic graph, the output is to indicate the existence of a cycle and not do any other output.

Summary of Tasks

Here are your tasks:
  1. Design and implement a graph data structure.
  2. Implement a topological sort operation or function.
  3. Write a main function that does the work indicated in the output described below.

Grading

Project grading is described on the Project Policy page.

Academic Integrity

Please re-read the Project Policy page for details on honesty in doing projects for this course.

Sample Output

Here are two runs that show the expected results and format. The first run is from a valid (non-cyclical) graph. The second run is from a graph that has a cycle.

Important: Note that the courses are listed five to a line and that they are comma-separated except at the end of the line.

There is one command line argument, the file from which to read the data.

This run is on a valid graph. 

umbc9: Proj5 prereqs.txt

A feasible schedule is:

MATH-150,MATH-151,CMSC-201,CMSC-101,CMSC-106
CMSC-103,CMSC-203,CMSC-104,CMSC-331,CMSC-102
CMSC-202,CMSC-109,CMSC-211,CMSC-341,CMSC-311
CMSC-411,CMSC-412,CMSC-421,CMSC-422

This run is on a cyclical graph. 

umbc9: Proj5 prereqs-cycle.txt

Cycle in graph.

Data File prereqs.txt

MATH-150 CMSC-201 CMSC-101 CMSC-106
MATH-151 CMSC-102 CMSC-103 CMSC-202 CMSC-203 CMSC-104
CMSC-101 CMSC-102
CMSC-103 CMSC-109
CMSC-104 CMSC-109
CMSC-106 CMSC-202
CMSC-201 CMSC-202 CMSC-331
CMSC-202 CMSC-211 CMSC-341
CMSC-203 CMSC-341
CMSC-211 CMSC-311
CMSC-311 CMSC-411 CMSC-412
CMSC-331 CMSC-412 CMSC-421
CMSC-341 CMSC-421
CMSC-421 CMSC-422

Data File prereqs-cycle.txt

MATH-150 CMSC-201 CMSC-101 CMSC-106
MATH-151 CMSC-102 CMSC-103 CMSC-202 CMSC-203 CMSC-104
CMSC-101 CMSC-102
CMSC-103 CMSC-109
CMSC-104 CMSC-109
CMSC-106 CMSC-202
CMSC-201 CMSC-202 CMSC-331
CMSC-202 CMSC-211 CMSC-341
CMSC-203 CMSC-341
CMSC-211 CMSC-311
CMSC-311 CMSC-411 CMSC-412
CMSC-331 CMSC-412 CMSC-421
CMSC-341 CMSC-421
CMSC-421 CMSC-422
CMSC-411 CMSC-311
Last modified on Sunday April 18, 1999 (21:39:08 EDT) by Alan Baumgarten
email: abaumg1@cs.umbc.edu

Back up to Spring 1999 CMSC-341 Section 1 and 2 Homepage