CSCI 3510 Programming Assignment 3

A word to the wise

Get something done for the first pass. Make it as good as you can.

Preliminaries

A weighted graph is a graph in which each edge has a number attached to it, called the weight of the edge. Here is a picture of a weighted graph.

A spanning tree of a graph is obtained by deleting as many edges as possible, without making it impossible to get from any vertex to any other by following a sequence of edges. For example, the following is a spanning tree of the above weighted graph.

The weight of a spanning tree is the sum of the weights of its edges. For example, the weight of the above spanning tree is 59. Here is another spanning tree for the same graph. Its weight is 48.

Obviously, some spanning trees have smaller weight than others. A minimal spanning tree is a spanning tree with the smallest possible weight.

Suppose that we have a collection of towns, and we must build railroad tracks so that it is possible for a train to get from any town to any other town. Our budget for building tracks is small, so we choose to build as little track as possible. One approach to deciding which tracks to build is to construct a weighted graph, where the weight of the edge from town A to town B is the length of the railroad track that would need to be built to connect towns A and B directly. Then a minimal spanning tree of that graph would be a good choice for connecting the towns, since it is the cheapest way to connect all of the towns using railroad tracks between towns.

A similar problem occurs when a house is being wired for electricity. All of the outlets on a given circuit need to be connected to the circuit panel, and to each other. To connect them with a minimum amount of wire, you might build a graph showing the wiring distances between outlets, and get a minimal spanning tree for the graph.

(A minimal spanning tree is not always the best solution to either of these problems. You can often do better by introducing new railroad track junctions or wiring junctions, called Steiner points. For example, if you have three towns in a triangle, you can connect them together by sending tracks to a point in the middle of the triangle. The middle point is a Steiner point. But good placement of Steiner points is difficult to find, so a minimal spanning tree is a reasonable compromise.)

The Assignment

The input starts with a line that tells how many vertices the graph has. If there are five vertices, then those vertices have numbers 1, 2, 3, 4 and 5. In general, if there are n vertices, then they are numbered 1...n. Following the first line are the edges, one per line. Each edge line has three integers on it. Line

2 4 50

might look like this.

5
1 2  9
1 3 12
2 4 18
2 3  6
2 5 20
3 5 15
0 0 0

The input graph has 5 vertices, and its edges are as follows.

  vertices    weight
  1   2            9
  1   3           12
  2   4           18
  2   3            6
  2   5           20
  3   5           15
  
A minimal spanning tree uses the following edges.

  vertices    weight
  2   3            6
  1   2            9
  3   5           15
  2   4           18

The total weight of the spanning tree is 48.

Data Structures

Choosing an open data structure allows all parts of the program that use the data structure to see the exact representation, and to manipulate that representation directly. This has the advantage that you do not need to introduce any special functions to manipulate the data structure, and you have a lot of flexibility in how to use it. This approach has the disadvantage of making the form of data structure nearly impossible to change. The code is also typically less readable than if you use a closed approach. Also, you often end up writing the same code to manipulate the data in more than one place in your program.

When you choose a closed representation, you are creating an abstract data type. Choosing a closed data structure involves hiding the representation inside a class, and only allowing the data to be accessed through public functions of the class. This typically involves more initial work, but makes your program easier to modify and often makes it easier to write in the long run.

Representing a Weighted Graph

Create a type Graph. You can store a graph as an array of edges, where each member of the array is a triple giving two vertex numbers and a weight. Of course, you must also store the number of edges and the number of vertices.

You may presume that there will be a maximum of 100 edges in the graph, but you must design your program so that it is very easy to change the maximum number of edges to some other number.

An Abstract Data Type

The tool is an abstract data type for managing connectedness. Initially, a connection manager CM starts with no connections at all. That is, nothing is connected to anything else.

The connection manager allows you to place connections between certain vertices, and to ask if two vertices are connected. If you connect A to B, and then connect B to C, then A and C become connected automatically. It is not necessary to tell the connection manager that A and C are connected.

The tool must be implemented as a class. The operations are as follows.

A constructor with a single integer parameter n.

The constructor builds a connection manager that can handle up to n vertices, numbered 1,...,n.

CM.connect(m,n)

This tells connection manager CM to make a connection between vertices m and n. Here, m and n are positive integers, up to the size that this connection manager can handle.

CM.connected(m,n)

This returns true if m and n are connected, and false if they are not.

Here is how to implement these operations. The idea is to have a representative of each group of connected vertices. For example, if vertices 3, 5 and 8 are connected together, then they might decide that 5 represents all of them. Write a function representative(k) that returns the representative of vertex k. In the example, representative(3) would be 5, and representative(5) would also be 5. (Vertex 5 represents itself.) To find out whether two vertices are connected, just check whether they have the same representative.

To implement function representative, keep an array PseudoRep of integers. PseudoRep[k] is called the pseudo-representative of k. Ideally, the pseudo-representative of k is the representative of k. Sometimes, however, the pseudo-representative of a vertex is not its representative. Suppose that r = Pseudo-Rep[k]. It might turn out that r is not a representative at all --- it does not represent itself. Instead, you must take its pseudo-representative. You continue doing this until you find a vertex that represents itself. That vertex is the true representative of the group. So to find the representative of k, you would do the following.

  r = k;
  while(PseudoRep[r] != r) r = PseudoRep[r];

When you are told to make a connection between two vertices m and n, what you need to do is

1. Find the representative r of m and the representative s of n.

2. Force r to be the representative of s, by making PseudoRep[s] = r.

Now s no longer represents itself. All vertices that used to have s as their pseudo-representative now automatically have r as their representative, since the loop will not stop at s any more. It is very important that you only change the pseudo-representative of a number that is currently its own representative, or the method will not work.

Keep as much private in the class as possible. There should be no public data. Do not make a function public unless you need to, because it is one of the operations provided by the abstract data type.

Computing Minimal Spanning Trees

1. Sort the array of edges by their weights, with smaller weights earlier in the array. (You can use function qsort, described below, to do this.)

2. Create a new connection manager. Initially, there are no connections, so every vertex represents itself. Also create a count, initially 0, of the total weight. Create an array that will end up holding the edges of the spanning tree. (It should have the type Graph, since a spanning tree is a graph.) Initially, it has no edges in it, but you gradually add more edges.

3. Scan through the array in increasing order of weight. (That is, do the following in a loop.) When you see edge (i,j), with weight w, ask the connection manager whether vertices i and j are already connected. If they are connected, then just skip this edge, and go to the next edge. If they are not connected then add edge (i,j) to the spanning tree, add w to the total weight of the tree, and tell the connection manager that i and j are connected. Then do the next edge.

Using qsort

The prototype for qsort is as follows.

     void qsort(void *base, 
                size_t nel, 
                size_t width,
                int (*compar) (const void *, const void *));

Parameter nel is the number of elements in the array, and parameter width is the number of bytes occupied by each element. (Type size_t is typically the same as int, and is used for values that describe the size of an array.)

Parameter compar is a function. It is responsible for telling qsort the order in which you want the array sorted. qsort will sort into ascending order, according to what function compar says is ascending order. Function compar takes two parameters, which will be pointers to particular members of the array. compar(A,B) should return

-1	if A < B
0	if A = B
1	If A > B

according to the order in which you want your array to be sorted.

For example, suppose that you want to sort an array of long integers into descending order. You write a comparison function.

int compareLongInts(const long* A, const long* B)
{
  if(*A < *B) return 1;
  else if(*A > *B) return -1;
  else return 0;
}

There is an obvious problem, however. The prototype for function compareLongInts says that its parameters have type const long*. But qsort wants to be passed a function whose parameters have type const void*. To fix this, you can us a cast. A cast is a way of telling the compiler to treat something as if it has a different type. Create a type QSORT_COMPARE_TYPE that you want to cast to, as follows.

   typedef int (*QSORT_COMPARE_TYPE)(const void*, const void*);

To sort an array Arr of n long integers, you use

   qsort((void*)Arr, n, sizeof(long), (QSORT_COMPARE_TYPE)compareLongInts);

Casts are, in general, very dangerous. They are a way of pulling the wool over the eyes of the compiler. This particular kind of cast is safe, and you can use it, but become sloppy with casts at your peril.

You will need to write a comparison function that is appropriate for sorting an array of edges into ascending order according to weight.

Implementing the Program

1. Implement the connection manager ADT. Test it.

2. Implement the part of the program that reads in and prints out the input graph. Test it.

3. Implement the beginnings of the minimal spanning tree algorithm by sorting the edges and printing them after sorting. (It looks like printing a graph is something you might want to do in more than one place. What does that tell you?)

4. Implement the rest of the minimal spanning tree algorithm. Test it.

5. Make the program's output look nice, if necessary.

Improving the Efficiency

After the representative function scans through a chain to find the representative of a vertex, it goes back through the chain and puts the genuine representatives in the PseudoRep array, for every vertex that was looked at in the chain. That way, subsequent representative computations will go much more quickly. For example, if the PseudoRep array contains

  PseudoRep[1] = 2
  PseudoRep[2] = 4
  PseudoRep[3] = 3
  PseudoRep[4] = 6
  PseudoRep[5] = 3
  PseudoRep[6] = 6
  PseudoRep[7] = 4
  PseudoRep[8] = 5

  PseudoRep[1] = 6
  PseudoRep[2] = 6
  PseudoRep[3] = 3
  PseudoRep[4] = 6
  PseudoRep[5] = 3
  PseudoRep[6] = 6
  PseudoRep[7] = 4
  PseudoRep[8] = 5

Implement this improvement. But only do this after everything is working in the basic solution.

What to turn in

When you mail me your solution, clearly label the subject line

   3510 assn3 pass 1 your name