Your project will create a class for undirected graphs and provide several functions that are associated with a graph. Your program will read graph data from a file and create a Graph object containing the specified nodes and edges. Your program will then read commands from a command file and execute all commands found in the file.
Project Due Dates:
All source code and data files for this project are found in the directory
/afs/umbc.edu/users/d/e/dennis/pub/cs341/proj4
The header file for the graph class (graph.h) is as follows. Feel free to modify it as you see fit.
#include <iostream.h>
typedef char Node;
class Graph
{
public:
Graph ();
~Graph ();
// add an edge -- checks that verticies exist
void addEdge (const Node& v1, const Node& v2, int weight);
// add a Node and retrun it's id
int addNode (const Node& v1);
// perform depth-first search starting from
// specified vertex
void dfs (const Node& v1) const;
// perform breadth-first search starting
// from specified vertex
void bfs (const Node& v1) const;
// generate minimum spanning tree
void mst () const;
// single-source shortest path
void shortpath (const Node& n1, const Node& n2) const;
// output the graph
friend ostream& operator<< (ostream& out, const Graph& g);
// return the number of verticies -- if needed
int getNumNodes() const;
private:
// your graph representation goes here
// isAdjacent -- you probably need this
// determines if 2 nodes in the graph are
// adjacent... returns T/F (1/0)
int isAdjacent (const Node& n1, const Node&n2) const;
// other private data member go here
};
The input file contains the data for an UNDIRECTED graph. An example graph:
The input file that represents this graph is:
5
A
B
C
D
E
8
A B 1
A C 2
B D 4
D E 3
C E 4
B E 1
D C 2
B C 2
The first line provides the number of nodes in the graph (let's call it N). This number is guaranteed to be less than 20.
The next N lines contain single character node designations. This data is stored in the node.
The next (N + 1st) line provides the number of edges, call it E. There is only the theoretical guarantee on the maximum size of E.
The next E lines contain the edge information. Each line consists
of two node designators (single characters) and the edge's weight
(an integer). Note that undirected edges are stored in both directions.
That is, the line
A W 2
implies there is an edge W -- A as well as
an edge A -- W, both with weight = 2.
When nodes designations are read from the file, a Node is creatd and added to the graph via the addNode() member function. When edges are read from the file, they are added to the graph via the addEdge() member function.
The description of the functions that will be supported by the graph datatype are as follows:
The commands file should have either B, D, M, P, S or E in the first column. If there is anything else, you should print an error and immediately exit out.
The explanations of the 6 characters are as follows:
Your program will be tested with two graph data files and two command files. Both graphs will be connected, undirected graphs. The usual 5-point bonus for projects submitted at least 24 hours early are available. The usual 5-point per penalties for the first 2 days late are assessed. No project will be accepted if more than 48 hours late. The stack and queue classes are provided for you. The files Stack.h, Stack.C, Q.h and Q.C are in the project directory. The breakdown of the grades for the different parts of the project are as follows:
For this project, you are to submit ALL source files and
and a makefile. In addition, you are to use the Unix script
facility to run your command. After executing the script command,
run your program twice.
All files are located in
/afs/umbc.edu/users/d/e/dennis/pub/cs341/proj4