Graph Toposorting

Purpose

After completing this assignment, you should be able to:

• store information into a program as a graph
• utilize a topological sort to partially order a graph

Task

Write a program that reads in a file containing course information and prerequisites, and output a degree program using those courses.

Discussion

Graphs (a collection of vertices and edges) are powerful data structures that allow computer scientists to solve a wide variety of problems (concurrency, networking, transportation, etc.) One question that arises in dealing with graphs is how do we "sort" the nodes of a graph?

To do so we utilize a sorting algorithm known as Topological sort (toposort). Toposort operates according to the following algorithm (for directed graphs):

Repeatedly, until there are no more nodes:
- pick the next node with indegree 0
- remove it

If there is more than one node with indegree 0, then the node selection is arbitrary among those nodes.

In this program, you are to utilize toposort to output a recommended degree program for a given series of courses and their prerequisites. You can model each course as a node in a graph, and an edge exists from course A to course B if and only if course A is a prerequisite of course B. Then, conducting a topological sort will give you an ordered listing of courses that can be taken in the correct sequence.

Criteria

The Graph.h file should contain your templated Graph class, and the main.cpp file should implement the solution to the programming problem using your Graph class.

Your program should run as follows:

$ more CS-classes.txt
MATH127
MATH181 => MATH127
CS135 => MATH127
CS202 => CS135
CS302 => CS202, MATH181
...
$ g++ main.cpp
$ ./a.out CS-degree.txt
Recommended CS degree program:
MATH127, CS135, CS202, MATH181, CS302, ...
$