Topological Sorting Assignment

Some Requirements and Assumptions:

• Assume the names of the nodes are integers from 1 to n where n is the number of vertices in the graph.

• You must design your program to use appropriate classes.

• You must implement your classes using separate declaration files (.h) and implementation files (.cc).

• All coding MUST be properly documented (IMPROPER or INADEQUATE DOCUMENTATION will result in a grade of at most 60%.) Proper documentation includes the following:
  • Your name, date, and a description of the class must be in the header documentation of each class.

  • In the header (.h) file, each function or data member must include a brief comment as to the purpose.

  • Each function must have header documentation in the implementation (.cc) file. The header must include a brief description of what the function does and PRECONDITIONS (a statement describing the state of member data and parameters expected at the beginning of execution of the function) and POSTCONDITIONS (a statement describing the state of member data, parameters, and return values at the end of execution of the function).

  • The main program must include header documentation with your name and the purpose of the program and a description of the format of the input file. There should be appropriate internal documentation (if the main file has functions they should be documented with Pre and Post conditions as above.

• Assume input will come from a file. You may write your program to use either of the following file formats (either read to end of file or use a count).
  • Format 1: The first line contains the number of vertices in the graph. Each of the following lines contains a vertex number followed by a list of vertices that are adjacent to the first vertex. A 0 will mark the end of the list. There is no row for a vertex with an empty adjacency list. You cannot assume the vertices are listed in order by their name (number). For example, a file to represent the graph in #1a in Section 5.3 would be:

        7
        1 2 3 0
        2 5 7 0
        3 6 0
        4 1 2 3 6 7 0
        7 5 6 0
    

    A sample file for a graph using this format is Digraph1Eof.dat.

    NOTE: If inFile is the name of your ifstream object while (!inFile.eof()) can be used to read to the end of the file. End of file isn't detected until it is read so it is a good idea to use a priming read before the loop and then your next read at the end.

  • Format 2: The first line contains the number of vertices in the graph. The next line contains the number of lines that follow (the number of vertices with outgoing edges). Each of the following lines (one for each vertex with outgoing edges) contains the number of the vertex followed by the number of outgoing edges followed by a list of the number for the endpoint of each outgoing edge. The following file would represent the graph in #1a.

        7
        5
        1 2 2 3
        2 2 5 7
        3 1 6
        4 5 1 2 3 6 7 
        7 2 5 6 
    

    A sample file using this format is Digraph1Count.dat.

Hand In