Rationale:

This is the third of a series of three homeworks. This one uses the Partition class developed in the previous homework to help solve the Minimum Cost Network Problem.

Review of the Minimum Cost Network Problem:

Given a collection of n cities and the cost of routing cable between every pair of cities, find the minimum cost network of cables that allows a person in one city to connect with a person in any other city. Network cost is the sum of the costs of all cables used. Cables must be laid between cities. Cables connect only at cities (splicing of a crossing pair of cables between cities is not allowed). A person in city x can connect with a person in city y only if there is a sequence of distinct cities c1 , c2 , ..., cj , none of which are either x or y, such that cables are laid between x and c1 , between c1 and c2 , ... , between cj and y. Such a sequence is called a path between x and y.

Example:

The following is a table showing fictitious costs of laying cable between pairs of four familiar cities. Cleveland Columbus Cincinnati Chicago Cleveland - 120 96 300 Columbus 120 - 43 178 Cincinnati 96 43 - 200 Chicago 300 178 200 - Note that the costs do not correspond with distances between cities: this mimicks some, but not all, real-life situations (reflecting a natural barrier such as a mountain to cross - thereby increasing cost). For the above example, the minimum spanning network consists of three cables: one connecting Cleveland to Cincinnati, one connecting Cincinnati to Columbus and one connecting Columbus to Chicago, for a total cost of 317. In general, there are n-1 cables in a minimum spanning network connecting n cities.

Method:

input: A collection of cable costs between pairs of cities output: A network of cables of minimum cost 1. Order the cables by increasing cost. 2. Let N represent the network of cables to be output and make it empty. 3. Repeat the following until all the cables are considered. 3a. Choose the next cable c in the ordered list. 3b. Check whether including c in the solution N allows you to trace more than one path between some pair of cities using only cables already placed in N. 3c. If it does, forget c and continue the loop. 3d. Otherwise, include c in N. 4. Return N.

Using redundant and setunion of the Partition class:

Partition all cities into subsets such that any pair of cities in the same subset is connected by cables in N and any pair in different subsets is not connected by cables in N. Initially, since N is empty, each city is in its own subset. Line 3b of the above algorithm is equivalent to invoking redundant of the Partition class on the two end cities of the cable c: if the value of redundant is false then the cable may be placed into N. Line 3d implies applying setunion of the Partition class on the set representatives of the end cities as all cities in each of the two sets are now connected due to the added cable c.

Homework:

Use the Partition class of the previous homework to implement a solution to the Minimum Cost Network problem using the algorithm above. There are two kinds of objects to worry about in this assignment: cables and cities. The files cable.h and cable.cc implement the Cable class: // File cable.h - specification of class Cable #ifndef _CABLE #define _CABLE class Cable { public: int city1, city2, cost; Cable (int, int, int); }; #endif and // File cable.cc - implementation of the class Cable #include "cable.h" Cable::Cable (int city1, int city2, int cost) { this->city1 = city1; this->city2 = city2; this->cost = cost; } The files city.h and city.cc implement the City class. These are shown here: #ifndef _CITY #define _CITY #include "funcs.h" class City { friend class displayC; friend class valueC; friend class compareC; char *name; public: City (char*); }; #endif and #include <iostream> #include <stdlib.h> #include "city.h" using namespace std; City::City (char *name) { this->name = new char[strlen(name)+1]; strcpy(this->name,name); } The City objects will be stored in the inverted tree structure of the Partition class. The Cable objects may be stored in a priority queue - they will be removed from the queue in increasing order of cable cost. A priority queue class, called PQueue, is given in files pqueue.h and pqueue.cc. Use the following specification for the Supervisor class to implement the solution. #ifndef _SUPERVISOR #define _SUPERVISOR #include <fstream> #include <iostream> #include <stdlib.h> #include "pqueue.h" #include "partition.h" #include "cable.h" #include "city.h" #include "funcs_mst.h" using namespace std; class Supervisor { friend ostream &operator<<(ostream&, Supervisor*); char *filename; size_t pos, size; char *buffer; // Will hold the entire data file Partition *part; PQueue *q; // Priority queue for the cables Cable **solution; // Array of cables to hold the solution int total, // For printing the minimum cost s_count, // For printing the number of cables in solution max_city, // Maximum city number ncables; // Number of cables public: Supervisor(char*); void readData(); void solve(); }; ostream &operator<<(ostream&, Supervisor*); #endif Finally, the following, in hw7.cc, shows how to use Supervisor class: // File hw7.cc // Solve the Minimum Spanning Network problem. // Given: A collection of cables, each connecting two cities and having // a cost. // Find: A subset of cables which connects all the cities such that its // total cable cost is minimized. #include <iostream> #include <time.h> #include "supervisor.h" using namespace std; int main (int argc, char **argv) { clock_t t,e,h; if (argc != 2) { cerr << "Usage: " << argv[0] << " \n"; exit(0); } Supervisor *supervisor = new Supervisor(argv[1]); t = clock(); supervisor->readData(); e = clock(); supervisor->solve(); h = clock(); cout << supervisor; cout << "Time: proc: " << ((double)(h-e))/CLOCKS_PER_SEC << " read: " << ((double)(e-t))/CLOCKS_PER_SEC << "\n"; } For convenience, you may use the files list.cc, list.h, node.cc, node.h, pqueue.cc, pqueue.h, funcs.h, cable.h, cable.cc, partition.h, hashtable.h, hw7.cc, and the Makefile. You will also need to supply hashtable.cc from homework 5 and partition.cc from homework 6. Your task is to produce supervisor.cc which implements the specification of supervisor.h. In particular you should implement the methods readData(), and solve(), and overload the << operator in the Supervisor class. The readData method should be able to read cable data from a file containing one triple per line where each triple is a city number, a city number, and an integer cost. For example, the method should be able to read the file net.40.dat.