Notice:

Project 5 is due either at 12:00 midnight of the last day of class. There are no resubmissions or late submissions for Project 5; however, projects which achieve a grade less than 60 will be examined to determine if they deserve a grade great than what was actually received (to a maximum of 60).

40 % of this project will be graded based on how many standard deviations you are from average class speed on this algorithm.

You may use all standard libraries available on ecelinux. This includes the Standard Template Library (STL), cstring, etc.

Requirements

In this sub-project, you will implement one class:

1. A weighted graph: Weighted_graph

This is a graph that has positive real weights for edges (double). Note that there are no templates used in this project.

Description

This class allows the user to create and destroy an undirected weighted graph. You will be able to find a minimum spanning tree using Kruskal's algorithm. The vertices are numbered 0 through n − 1 where n is the argument to the constructor.

In a nutshell, Kruskal's algorithm runs as follows:

• Start with an empty minimum spanning tree and mark each edge as unvisited,
• While there are edges not yet visited or while the minimum spanning tree does not have n − 1 edges:
• Find the edge with minimum weight that has not yet been visited.
• Mark that edge as visited.
• If adding that edge does not create a cycle (that is, the two vertices are not already connected), add that edge to the minimum spanning tree.

Note that there are numerous mechanisms of simplifying this problem. It's up to you to consider the test case and to determine any optimizations you should make. While the description above is absolutely correct, there are more efficient mechanisms of, for example, determining whether or not two vertices are connected in the partially built minimum spanning tree.

Grading scheme

Three quarters of the weight of the project will be to ensure that the project works. For those students who achieved a grade of 70, they will be entered into a competition with their classmates. Teaching assistants, the instructor and laboratory instructor are all welcomed to attempt to compete in this problem.

Contest

The instructor and perhaps some of the instructional support staff will be implementing the projects, as well. Anyone (including instructors and teaching assistants) whose run time is better than that of the instructor will be awarded $20 with a maximum payout of $100 to the top five. In addition, the top three student (regardless of whether they are faster than the instructor's project) will be invited to dinner at AM Africa as a reward.

Member Variables

The design of the class is up to you: you may use any data structure you see fit.

Member Functions

Constructors

The constructor takes an argument n which defines a graph with vertices numbered from 0 through n − 1. The vertex i is given an initial priority of i. The default value of n is 10.

Destructor

The destructor frees up any memory allocated by the constructor.

Copy Constructor

No copy constructor is required.

Assignment Operator =

No assignment operator is required.

Accessors

This class has five accessors:

int degree( int i ) const

Returns the in degree of the given vertex i. If i is outside the range 0, ..., n − 1, throw an illegal argument exception.

int edge_count() const

Returns the number of edges in the graph.

std::pair<double, int> minimum_spanning_tree() const

Use Kruskal's algorithm to find the minimum spanning tree. You will return the weight of the minimum spanning tree and the number of edges that were tested for insertion into the minimum spanning tree.

An example of Kruskal's algorithm is shown in the following figures. To find the minimum spanning tree on the graph in Figure 1, we begin by examining the edges with least weight: the edges with weights 1.3 and 1.4 can be safely inserted, but the edge with weight 1.5 cannot, as it creates a cycle. After this, the edge with weight 1.6 can be inserted. The minimum spanning tree up to this point is shown in red in Figure 2. We proceed by inserting the edge with weight 1.7, but we cannot insert the edge with weight 1.8, as this causes a cycle. We conclude by adding the edge of weight 1.9. The weight of the minimum spanning tree is 7.9 and we visited seven nodes to find this.

Figure 1. A weighted graph.

Figure 2. The partial minimum spanning tree after the first four edges were checked.

Mutators

This class has three mutators:

bool insert_edge( int i, int j, double w )

If i equals j and are in the graph, return false. Otherwise, either insert a new edge from vertex i to vertex j or, if the edge already exists, update the weight and return true. Recall that the graph is undirected. If i or j are outside the range 0, ..., n − 1 or if the weight w is less than or equal to zero, throw an illegal argument exception.

bool erase_edge( int i, int j )

If an edge between nodes i and j exists, remove the edge. In this case or if i equals j return true. Otherwise, if no edge exists, return false. If i or j are outside the range 0, ..., n − 1, throw an illegal argument exception.

void clear_edges()

Removes all the edges from the graph.

Friends

The class has no friends.

Testing

Consider testing your code with something like:

#include <iostream>
#include "Weighted_graph.h"

using namespace std;

int main() {
	Weighted_graph graph(4);

	graph.insert_edge( 0, 1, 7.2 ); 
	graph.insert_edge( 0, 2, 7.5 ); 
	graph.insert_edge( 0, 3, 7.3 );
	graph.insert_edge( 1, 2, 7.6 );
	graph.insert_edge( 1, 3, 7.4 );
	graph.insert_edge( 2, 3, 7.7 );
	cout << graph.minimum_spanning_tree().first << endl;   // returns the minimum spanning tree weight: 22
	cout << graph.minimum_spanning_tree().second << endl;  // returns the number of nodes inspected: 4
	graph.insert_edge( 0, 2, 7.5 );   // returns true
	graph.insert_edge( 0, 2, 7.8 );   // returns true
	cout << graph.minimum_spanning_tree().first << endl;   // returns the minimum spanning tree weight: 22.1
	cout << graph.minimum_spanning_tree().second << endl;  // returns the number of nodes inspected: 4

	return 0;
}

Common Issues

Recall that the order in which member variables are assigned in the copy constructor is the same order in which the member variables are declared in the class definition. Thus, the following would fail:

class Faulty {
	private:
		int *array;
		int towers;

	public:
		Fault( int );
		Fault( Fault const & );
};

// 'array' is assigned before 'towers' even though it looks like
// 'towers' is assigned the value of the argument first.
Fault::Fault( int n ):
towers( n ),
array( new int[towers] ) {
	// empty
}

// Similarly, 'array' is assigned before 'towers' even though it looks like
// 'towers' is assigned the value of 'faulty.towers' first.
Fault::Fault( int n ):
Fault::Fault( Fault const &faulty ):
towers( faulty.towers ),
array( new int[towers] ) {
	for ( int i = 0; i < towers; ++i ) {
		array[i] = faulty.array[i];
	}
}

Tools you can use

You are welcome to use a sorting algorithm written by someone else, so long as you acknowledge that author or organization. You can also use the implementation of sort in the Standard Template Library (STL), which you can view some commentary on here. You will, however, have to sort a triplet, where two member variables are the vertices, and one is the weight.

class Edge {
	public:
		int v1;
		int v2;
		double weight;
};

or

typedef struct {
	int v1;
	int v2;
	double weight;
} edge_t;

You can then sort a vector of these using the algorithm sort function.

You will also require a disjoint set data structure. You are welcome to use Disjoint_set as implemented in these course notes. You may use all standard libraries available on ecelinux. This includes the Standard Template Library (STL), cstring, etc.