Setting up a Graph

Due Tuesday, April 12

Some Requirements and Assumptions:

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

• You must design your program to use the classes described below.

• 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 in the following file format:
  • 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. See the example from the quickhull assignment.

Classes

• A class to represent a graph list node. This will be a basic node with just a number for the vertex number and a link to the next graph list node. It should have basic getter and setter functions.

• A class to represent an unordered list of graph list nodes. The insert function should insert at the beginning of the list. Have a function to print the list and other functions as needed.

• Optional A class to represent a graph node. At this point the node would have a field for the vertex number, for the in-degree of the node, and for the list of adjacent nodes.

• A class to represent a graph. This class will represent the graph using an array. If you create a class to represent a graph node, the array will be an array of graph nodes and all information about each node will be stored in the node. If you do not have a graph node class, then the array will be an array of lists of adjacent nodes and your class will need parallel arrays to store additional graph information. For now, that would be an array to store the in-degree for each node. This class needs to have a function to read the graph data in from a file and set the graph up. Space for the array(s) should be dynamically allocated after the number of vertices has been read in. There should also be a function to calculate the in-degree of each vertex, a function to print the in-degrees and a function to print the graph.

Hand In