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.
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.
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.
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.
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
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