CpSc 241, Section 2
                             Assignment 5 
                             9 March 2001


Due: Thursday, April ?? at 11:59 p.m.

	Not accepted late.

Total point value of assignment:  150 points

Implementation of Kruskal's Algorithm for Minimum Spanning Tree (MST).

Part 1:  Read in the data and store the data in a graph.  Assume the
data contains triples

      city1      city2      distance

representing edges in a graph.  The number of edges and the number of
cities is not known at the beginning of execution of the program.  You
may assume that the number of cities is <= 50.  You may use an
adjacency matrix for representing the graph, although the adjacency list
representation gives an improvement on the growth rate of most algorithms.
You are prohibited from using Weiss' graph class.  You must use your own
graph class.  The graph class you construct should contain the required
hash table and array of references to the city names.

Assume the graph is undirected, so the above triple means that there
is an edge from city1 to city2 and from city2 to city1, both having
the same distance.  (for this particular problem)

Use a hash table to store the city names and the corresponding distinct 
integer assigned to the city.  Use an array (or vector) to access the 
String representation of the city name, as was done in class.  The String
representation of the city name should be stored exactly once, and
is accessed both from the hash table and from the array (or vector).  

Reading the data:  The data should be read from the keyboard in a loop
that asks the user whether or not more data should be read.  In
pseudocode, the loop should be of the form:

      ask the user if more data should be read
      while the answer is yes
      {
          input city1, city2, distance

          if city1 already in hash table
              get num1 associated with city1
          else
              assign num1, place city1 in hash table, place reference 
              to city1 in array position num1, and increment cityCount

          if city2 already in hash table
              get num2 associated with city2
          else
              assign num2, place city2 in hash table, place reference 
              to city2 in array position num2, and increment cityCount

          store distance in adjacency list/matrix

          ask the user if more data should be read
      }

Example 1 data.  Suppose the data read is

          Clemson   Greenville   32
          Clemson   Anderson   11
          Greenville   Anderson   28
          Pendleton   Clemson   6
          Anderson   Pendleton   9

and suppose the array is called cityNames, then the storage would be

          cityNames [1] = "Clemson"
          cityNames [2] = "Greenville"
          cityNames [3] = "Anderson"
          cityNames [4] = "Pendleton"

assuming that the first city is numbered 1.  You will need a method

          public void printCityNames ( )
          // post:  the names of all cities in the graph are printed.

A call to printCityNames with the above graph should print

          1  Clemson    
          2  Greenville
          3  Anderson
          4  Pendleton

You may number the cities from zero, rather than one, if you wish.

Example 2 data.  Suppose the data read is:

          SanFrancisco	LosAngeles	380
          SanFrancisco	SaltLakeCity   745
          LosAngeles	SaltLakeCity	688
          SaltLakeCity	Denver		512
          Denver	KansasCityMO	605
          KansasCityMO	StLouisMO	256
          KansasCityMO	LittleRockAR	389
          LittleRockAR	MemphisTN	137
          MemphisTN		StLouisMO	285
          KansasCityMO	OklahomaCity 	344
          OklahomaCity	AlbuquerqueNM	543
          AlbuquerqueNM		Denver		439
          AlbuquerqueNM		LosAngeles	804
          SaltLakeCity		Boise	339
          Boise		PortlandOR		427
          PortlandOR	Seattle		175
          Boise		Seattle		494
          PortlandOR	SanFrancisco	636
          StLouisMO		NashvilleTN 	313
          MemphisTN		NashvilleTN		210
          StLouisMO		LouisvilleKY	258
          LouisvilleKY	NashvilleTN		175

	
********************************************************************************

Grading rubric:

The following are tested sequentially.  After the first failure,
no further testing is done.  For instance, if your code is
a reasonable attempt to solve the problem, compiles correctly,
handles Example 1 data correctly, but fails on Example 2 data,
you will receive 30 points.  You will not receive credit for
using a hash table or other tests.

Program submitted is a reasonable attempt to solve problem (10 pts.)

Program compiles without error.  (20 pts.)  Remember that every
	class you use must be available from your program.  If you
	are using Weiss' classes, such as hash table, you need to
	import them and place a comment at the beginning of your program
	to be sure the TA knows what classpath is needed.  You must 
	include your own graph class.  If you use modifications to 
	Weiss' classes you must either provide an entire class or an
	extension of Weiss' class containing the modifications.

Program reads Example 1 data without error and prints correctly
	on call to printCityNamesi().  (10 pts.)

Program reads Example 2 data without error and prints correctly
	on call to printCityNames().   (10 pts.)

The MST printed for Example 1 data is correct.  (20 pts.)

The MST printed for Example 2 data is correct.  (20 pts.)

Program uses hash table to store city names.  A hash on the city name
 	should indicate the number associated with the city name or that
	the city name is not present.  (If you change Weiss' hash table,
	you must include the hash table code you are using in your submission.)
	(10 pts.)

Program stores the String representing city name exactly once.
	That is, hash table and array reference the same instance of
	the city name.  (10 pts.)

The program reads a data set provided by the grader without error
and prints correctly on call to printCityNames().  (10 pts.)

The MST printed by this data set is correct.  (30 pts.)

Extra credit:  Adjacency lists, rather than adjacency matrix,
	are used to store the graph.  (10 pts.)




********************************************************************************