Data Structures C++ Project #8 solution

Part I

You are to implement a Graph<Item class for an edge list implementation of a labeled graph with a fixed number of vertices and labels of type Item.




Your class will have an array, vertexlist, which stores data of type Item for each vertex, and an array, edges, which stores a list of target vertices for each vertex (edgelists). The edges array is an array of List<E objects, each List<E object storing edge information for a vertex. (List<E is in the STL library. Reference can be found at www.cplusplus.com)




The instance variables for your class being:

Item vertexlist[MAXIMUM]; //array which stores Vertex labels

List<EdgeNode edges[MAXIMUM]; // array which stores edge lists, one for each vertex

size_t many_vertices; // number of Vertex nodes currently stored

 

MAXIMUM can be defined as 100 in this project.




Your class should be store data as follows:

class EdgeNode{ //a object of this class represents one edge in the graph

private:

int vertex_num; // vertex it is going TO

public:

EdgeNode(int vnum);

void setvnum(int);

int getvnum();

bool operator==(const EdgeNode& obj);

}

 

Your class should provide the following functions (as found in Graph.h on page 738-740):




MEMBER CONSTANTS for the graph<Item template class:

// const size_t MAXIMUM = 100

// graph::MAXIMUM is the maximum number of vertices that a graph can have.

//

// CONSTRUCTOR for the graph<Item template class:

// graph( )

// Postcondition: The graph has been initialized with no vertices and no edges.

//

// MODIFICATION MEMBER FUNCTIONS for the graph<Item template class:

// void add_vertex(const Item& label)

// Precondition: size( ) < MAXIMUM.

// Postcondition: The size of the graph has been increased by adding one new

// vertex. This new vertex has the specified label and no edges.

//

// void add_edge(size_t source, size_t target)

// Precondition: (source < size( )) and (target < size( )).

// Postcondition: The graph has all the edges that it originally had, and it

// also has another edge from the specified source to the specified target.

// (If this edge was already present, then the graph is unchanged.)

//

// void remove_edge(size_t soure, size_t target)

// Precondition: (source < size( )) and (target < size( )).

// Postcondition: The graph has all the edges that it originally had except

// for the edge from the specified source to the specified target. (If this

// edge was not originally present, then the graph is unchanged.)

//

// Item& operator [ ] (size_t vertex)

// Precondition: vertex < size( ).

// Postcondition: The return value is a reference to the label of the

// specified vertex.

//

// CONSTANT MEMBER FUNCTIONS for the graph<Item template class:

// size_t size( ) const

// Postcondition: The return value is the number of vertices in the graph.

//

// bool is_edge(size_t source, size_t target) const

// Precondition: (source < size( )) and (target < size( )).

// Postcondition: The return value is true if the graph has an edge from

// source to target. Otherwise the return value is false.

//

// set<size_t neighbors(size_t vertex) const

// Precondition: (vertex < size( )).

// Postcondition: The return value is a set that contains all the vertex

// numbers of vertices that are the target of an edge whose source is at

// the specified vertex.

//

// Item operator [ ] (size_t vertex) const

// Precondition: vertex < size( ).

// Postcondition: The return value is a reference to the label of the

// specified vertex.

// NOTE: This function differs from the other operator [ ] because its

// return value is simply a copy of the Item (rather than a reference of

// type Item&). Since this function returns only a copy of the Item, it is

// a const member function.




In addition to the functions indicated above, you are to also code

// bool is_path(size_t source, size_t target) const

// Precondition: (source < size( )) and (target < size( )).

// Postcondition: The return value is true if the graph has an path from

// source to target. Otherwise the return value is false.

 

** You are to use the breadthfirst search algorithm for the is_Path method (you will need a queue class for this). Code should be included to which will print (to the console) node data as it is encountered, provided for a trace of the traversal. This will aid you in any necessary debugging, and allow me to ensure that your method is functional and data stored correctly.




Part II The Application

You are to write a course prerequisite application. This application will use a Graph<string object for storing the courses and their relationships (courses are vertices, edges are used to represent the ‘prerequisite’ relationship between one course and another). Your application should allow the user to:




* enter a new course (the course name is provided by the user)

* enter a prerequisite relationship between two courses (two course names are provided by user)

(error message is given if both courses do not exist)

* remove a prerequisite relationship between two courses (course names provided by user)

* report if one course is the immediate prerequisite of another (course names provided by user)

* report if there is a prerequisite path between on course and another (course names provided by user)

* output all courses which can be taken directly after taking that course (course name provided by user)

* outputs all courses which have been entered

 

You are to code an interactive application which allows the user to create a Graph<string class. This application should allow the user to insert vertices, insert and delete edges, and check the existence of edges and paths within your Graph. You are to test thoroughly to ensure that your code works correctly with non-trivial graphs.

 

You are to submit your Graph.h template class file and your application.cpp file. Be sure your code is well tested and provides documentation which includes method effect/pre/post condition information.