Project 3 - CS 462 - Algorithm Analysis

Loyola College in Maryland
CS 462 - Algorithm Analysis Spring 2004

Loyola College > Department of Computer Science > Dr. James Glenn > CS 462 > Programming Projects > Project 3 - Graph

Due

Tuesday, April 13th at 11:59pm. Late projects will be assessed a 20% penalty for each day past the due date. Projects will not be accepted more than four days past the due date.

Objectives

to develop and use a graph class

Assignment

There are two parts to this assignment:

write a Graph class according to the specifications given below; and
write a program that uses your Graph class to process some data.

Your Graph class should model directed, weighted graphs in which the vertices are natural numbers. Your class should have the following constructors and methods.

Graph(), a constructor to create a graph with no vertices and no edges.
~Graph(), a destructor to destroy a graph.
void addVertex(), a method to add a vertex to a graph. The first vertex added should be numbered 0, the second should be numbered 1, and so forth.
int countVertices(), a method that returns the number of vertices that have been added to a graph.
void addEdge(int src, int dest, double weight), a method that adds an edge from the first vertex given to the second. The weight of the new edge is given by the last parameter. If the edge was already added, the new edge replaces the old edge.
bool hasEdge(int src, int dest), a method that determines if an edge exists.
double getWeight(int src, int dest), a method that returns the weight of an edge.
void reverse(), a method that reverses all the edges in a graph.

In addition, your class must have a nested class Edge that models the directed, weighted edges. Edge should have methods

int getSource() to get the index of the source vertex;
int getDestination() to get the index of the destination vertex; and
double getWeight() to get the weight of the edge.

Finally, your class must provide an iterator class called const_edge_iterator that can be used to iterate over the edges that leave any chosen vertex. The Graph methods associated with the iterator class are

const_edge_iterator begin(int src) to get an iterator positioned at the first edge leaving vertex number src and
const_edge_iterator end(int src) to get an iterator positioned at the end of the edges leaving vertex src.

const_edge_iterator must support operators !=, *, and ++, so that the following code would display the indices of all the vertices that are adjacent to vertex number u.

for (Graph::const_edge_iterator v = g.begin(u); v != g.end(u); ++v)
  std::cout << (*v).getDestination() << std::endl;

Input and Output

For the second part of the project, you will read input from standard input and build a graph based on what you read. The input will consist of team names, one name per line. Each pair of lines represents the result of one game. The first team is the winner and the second team is the loser. You must build a graph that contains edges from the winners to the losers. The number of times one team beat another should be recorded as the weight of the corresponding edge.

After all the data has been read, you should write to standard output a summary of the data read. This summary should, for each team, list the team that first team beat, along with the number of times if greater than one. For example, if the input is

Virginia
Maryland
Virginia
Duke
Maryland
Duke
Virginia
Duke

then the output should be

Virginia
  Duke [2x]
  Maryland
Maryland
  Duke
Duke

(the order may be chosen arbitrarily as long as all the teams defeated by one team are grouped together).

Files

input.1 contains the results of NCAA men's basketball games between MAAC teams. The corresponding output is output.1.
input.2 contains the results of all NCAA men's basketball games between Division I teams through Wed March 17th. This is a 117kB file containing 9816 lines of data. The corresponding output is output.2.
input.3 contains 128 copies of input.2. Each copy has a different prefix prepended to the teams names. Over 1 million lines and 19 megabytes. You may want to get this from ~jglenn/public_html/462/S2004/Projects/P3/input.3 instead of copying it to your directory.

Hints

To create the nested Edge class, simply nest the definition of Edge in the definition of Graph. The skeleton of your header file would then be

class Graph
{
  public:
    class Edge
    {
      ...
    };

  ...
};

and the method definitions in the implementation file would look something like

void Graph::Edge::foo()
{
  ...
}

If you use an STL data structure to hold your edge lists then creating the iterators is easy. For example, if you have an array of vectors outgoing to hold the edges leaving each vertex, then your const_edge_iterator is the same as std::vector< Edge >::const_iterator and you can include the line

typedef std::vector< Edge >::const_iterator const_edge_iterator;

in the public section of your class definition. Your begin method could then simply return outgoing[src].begin().

Since your graph uses numbers for vertices and the input file uses strings, you will have to have some additional structures, separate from the graph, that keep track of which vertex numbers correspond to which team names and vice versa.

Grading

For full credit, your code must:

be robust -- if the arguments passed to a method don't make sense then the method must do something reasonable;
have reasonable asymptotic running times; and
not create memory leaks.

A special bonus may be awarded for implementations that are particularly fast.

Submissions

Submit all source code files necessary to build your code in a tar file (preferably compressed).