Your objective is to implement a program taht deals with a number graph algorithms, and an application of graphs to processor scheduling..

Here is a high-level description of what you are to do:

// validate all data
// read number of nodes and number of processors
read in n, indicating the number of nodes in a graph
read in m, indicating the number of processors (relevant for last phase)

// read edges and edge weights
while (no more input)
    read a triple (a,b,w_ab), indicating a directed edge from a to b, with edge weight w_ab
    // note a and b are in the range [0..n-1], and w_ab is a positive integer
// you now have an n-node graph with weighted edges
// print out tree description as normal adjacency list (with edge weights)
// can print pretty if you want

// use two depth first searches to determine the strongly connected components
// clearly identify each strongly connected component and its member
// see section 9.6.5 in Weiss

// find the shortest path lengths from node 0 to all others
// use the O(M lgN) version of Dijkstra's shortest path algorithm
// print the lengths of these paths for each node [0..n-1]
// be careful; it's okay to find an infinite path if not connected

// print out nodes topologically sorted based on edge relation
// print out an indication of a cycle if one is found
// else note the graph is acyclic
// print out an indication if this graph is a tree
// else note the graph is not a tree
// Note: a graph is a tree if
//    it has n-1 edges &&
//    no cycles &&
//    a unique root (unique smallest element in top sort)

EXTRA CREDIT
// if the graph is a tree then
//     treating the nodes as unit execution time tasks
//     treating the links as the inverse of precedence (a->b means a waits on b)
//     develop an m-processor schedule that will complete all tasks as quickly as possible
//        note: reverse links are great for assigning priorities
//            but they need to be reversed for assigning processors

Turn in a disk with a directory whose name is the same as yours
    Use the convention <Last Name> <Initial of First Name>
        So my folder would be named "HughesC"
    The contents of the folder will be
        The source file(s) for your program
        Executable files, as appropriate to programming language
        Test Files named Graph1.txt, Graph2.txt, ...
            Include at least 3 files
                One of these must have no cycles
                One must have at least two strongly connected components
                One must be a tree (and thus apply to the extra credit part)
        Text files showing your output for each test data file
            These are named GraphOut1.txt, GraphOut2.txt, ...
        A report entitled Results.doc that makes your output easy to interpret
            Hand draw annotated graphs and trees
            (you do not need to do pretty computer graphics)

Due: Friday, December 3, 1999 at 4:00 PM
Cutoff: No late assignments will be accepted