20-ECES-228-001 Data Structures Fall 2007

Homework Assignment Number 7A

Using Set Partition Class on Minimum Cost Network

Due: November 26, 2007
Submit solution to xxxxx@email.uc.edu

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.
ClevelandColumbusCincinnatiChicago
Cleveland-12096300
Columbus120-43178
Cincinnati9643-200
Chicago300178200-
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 following two files specify and implement the Cable class:
   // File cable.h - specification of class Cable
   #ifndef _CABLE
   #define _CABLE

   class Cable {
   public:
      short int city1, city2; int cost;
      Cable (short int, short int, int);
   };
   #endif
and
   // File cable.cc - implementation of the class Cable
   #include "cable.h"

   Cable::Cable (short int city1, short int city2, int cost) {
      this->city1 = city1;
      this->city2 = city2;
      this->cost = cost;
   }
Use the following specification for the Supervisor class to implement the solution.
   #ifndef _SUPERVISOR
   #define _SUPERVISOR
   #include <fstream>
   #include <stdlib.h>
   #include "partition.h"
   #include "cable.h"
   using namespace std;

   class Supervisor {
      char *filename;
      size_t pos, size;
      char *buffer; // will hold the entire data file
      int avail;

   public:
      Partition *part;
      Cable **cables, **solution;
      int total, s_count, max_city, ncables;
   
      Supervisor(char*);
      char *getNextNumber();
      void readData();
      void sort();
      void printSolution();
      void solve();
   };
   #endif

Finally, the following 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 valuefunction (void *object) {  return (int)(*(short int*)object);  }

   int main (int argc, char **argv) {
      clock_t t,e,g,h;

      if (argc != 2) {
         cerr << "Usage: " << argv[0] << "  \n";
         exit(0);
      }

      Supervisor *supervisor = new Supervisor(argv[1]);
      t = clock();
      supervisor->readData();
      e = clock();
      supervisor->sort();
      g = clock();
      supervisor->solve();
      h = clock();
      supervisor->printSolution();

      cout << "Time: proc: " << ((double)(h-g))/CLOCKS_PER_SEC
           << " sort: " << ((double)(g-e))/CLOCKS_PER_SEC 
           << " read: " << ((double)(e-t))/CLOCKS_PER_SEC << "\n";
   }

For convenience, you may use the files list.cc, list.h, cell.cc, cell.h, node.cc, node.h, list_funcs.h, cable.h, cable.cc, partition.h, hashtable.h, hw7.cc (contains the main procedure), and the Makefile. You will also need to supply hashtable.cc from homework 5B and partition.cc from homework 6B.

Your task is to produce supervisor.cc which implements the specification of supervisor.h. In particular you should implement the methods readData(), sort(), solve(), and printSolution() 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.