The Assignment

Write a program that reads, from the standard input, a description of a weighted graph with integer weights, in the input format shown below. Then the program should write, on the standard output:

1. the original graph G;

2. the computed minimal spanning tree T of G;

3. the total weight of T.

To show a graph (or tree), show the number of vertices, the number of edges and a list of all of the edges, with their weights.

Make it clear just what each part of the output is. Don't make a reader guess what he or she is looking at. The output of your program might look like this.

Input graph: There are 5 vertices and 6 edges vertices weight 1 2 9 1 3 12 2 4 18 2 3 6 2 5 20 3 5 15 Minimal spanning tree: There are 5 vertices and 4 edges vertices weight 2 3 6 1 2 9 3 5 15 2 4 18 The total weight of the spanning tree is 48. 

Additional Requirements

Your program must follow the design in the section "A refinement plan." It can have additional functions, but it must have at least the functions indicated in the design. Do not add extra responsibilities to the required functions.

A Refinement Plan

Development plan

1. Create a directory to hold assignment 5.

Copy equiv.h and equiv.cpp from Assignment 4 into that directory. Put all of the files for Assignment 5 in that directory. Get files Makefile, dotest and put them in that directory.

2. Create a file called mst.cpp

Copy and paste the template into it. Edit the file. Add your name and the assignment number. If you will use tabs, say how far apart the tab stops are.

3. Document the program

Write a comment in mst.cpp telling what this program will do when it is finished. Include information to help a reader understand what this program does and how to use it, with:

1. the fact that this program reads a weighted graph g from the standard input and writes a minimal spanning tree of g to the standard output;

2. the input format (below), with an example;

3. a sample input and sample output for that input.

4. Vertex numbers and edge numbers

Do not confuse edges with vertices. Keep track of the number of vertices in a graph separately from the number of edges. Remember that the first number in the input is the number of vertices, not the number of edges.

The vertices are numbered 1, , n. You will need to have an array of edges. It is a good idea to start numbering the edges from 0, not from 1. So put the first edge that you read at index 0 in the array of edges.

5. Representing a weighted graph

Start by defining two structure types, Edge and Graph, in mst.cpp. Be sure to document each.

1. An object of type Edge represents one edge in a graph. It has three fields: two vertex numbers and a weight. Include a parameterless constructor that sets all three fields to 0.

2. An object of type Graph represents a weighted graph. It has four fields:

   • the number of vertices in the graph,
   • the number of edges in the graph,
   • a pointer to an array of Edge structures that holds the edges,
   • the physical size of the array of edges.

   Choose clear and sensible names for the fields.

   Include a constructor Graph(n, e) that yields a graph with n vertices and no edges, but with an array of edges whose physical size is e.

   Do not confuse the physical size of the array with the current number of edges. The physical size is the maximum number of edges allowed. The current number of edges might be less than that.

All structure types must be documented by saying

1. what an object of this structure type represents and
2. what property of the object each field represents.

6. Adding an Edge

In mst.cpp, define a function insertEdge(u, v, w, g) that adds an edge between u and v of weight w to graph g. If the edge array is full, insertEdge must refuse to add the edge.

Here is a suitable contract for insertEdge. Note its similarity to the preceding paragraph.

 // insertEdge(u, v, w, g) inserts an edge of weight w between vertices // u and v into graph g. // // If there is not enough room in g to add the edge, then // insertEdge does nothing. 

Pass g by pointer to insertEdge. Otherwise, insertEdge will modify a (shallow) copy of your graph, which is not what you want. So the type of parameter g should be Graph*.

Here is a suitable heading for insertEdge.

 void insertEdge(int u, int v, int w, Graph* g) 

Make sure that insertEdge does the whole job of inserting an edge. Don't force its caller to do part of the job. Increasing the number of edges is part of the job.

7. Input and Input Format

In mst.cpp, define a function readGraph(e) that reads a description of a graph from the standard input and returns a poiner to that graph. It should create the graph with enough room to hold e edges. The graph will need to be allocated in the heap, since it must persist after readGraph returns.

First, write a heading and a contract for readGraph. Then write the function definition.

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 

indicates that there is an edge of weight 50 between vertices 2 and 4. The weights are integers. The end of the input is signaled by a line that contains just a 0. Input

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

describes graph

ReadGraph must use 'insertEdge' to add each edge to the graph.

8. Output and Output Format

In mst.cpp, define and document a function writeGraph(G) that writes a description of graph G on the standard output. See the sample output above for a reasonable output format. WriteGraph should not say that the graph is "the input graph". It should just show the graph. Naming the graph is the responsibility of whoever calls writeGraph.

9. Main

In mst.cpp, define a main function that just reads a graph and writes it. Test the program. Do not move on until this works. Do not skip testing this!

10. Sorting an Array of Edges

In mst.cpp, define and document a function sortEdges(G) that sorts the array of edges in graph G into nondescending order by weight. Use library function qsort to do this. (Should the contract say that sortEdges uses qsort?)

Function qsort is part of the C Standard Library. It is a general-purpose sorting function that sorts an array using a variant of the Quicksort algorithm. You should include header file to use qsort.

Qsort needs information about the array and how to sort it. It also needs for you to perform some type conversions that, in general, would be questionable, but that work correctly here.

Qsort takes four parameters. Function call

 qsort(base, numElements, elementSize, compare); 

sorts array base, where:

• Parameter base is a pointer to the array that you want to sort. You should convert this pointer to type (void*).

• Parameter numElements is the number of elements in the base array. It is the logical size of the edge array.

• Parameter elementSize is the number of bytes occupied by each element. Since each thing in the array has type Edge, elementSize should be sizeof(Edge). (In general, sizeof(T) is the number of bytes that something of type T occupies.)

• Parameter compare is a function. (C++ allows you to pass a function as a parameter to another function. You do not run the function yourself; qsort will run it for you, many times. You are just lending the tool to qsort, not using the tool yourself.)

  Function compare takes two parameters, which will be pointers to particular members of the array when qsort calls it. compare(A, B) should return

  A negative number

  if *A should come before *B in the sorted array

  A positive number

  if *A should come after *B in the sorted array

  0

  if you do not care what order they are in

  Your comparison function can look as follows, since you want to sort according to the weights of the edges.

   int compareEdges(const Edge* A, const Edge* B) { return A->weight - B->weight; } 

To run qsort, define a new type, QSORT_COMPARE_TYPE, as follows. It is the type of the compare parameter that qsort expects to receive.

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

Now statement

 qsort((void*) Arr, n, sizeof(Edge), (QSORT_COMPARE_TYPE) compareEdges); 

will sort array of n edges Arr according to weights, with smaller weights toward the beginning of the array.

11. Building a Minimal Spanning Tree

In mst.cpp, define and document a function minimalSpanningTree(G) that takes a graph G (passed by pointer) as a parameter and returns a pointer to a minimal spanning tree of G.

Document 'minimalSpanningTree' as it will be when finished. It will return a minimal spanning tree of G.

For now, only make it sort the edges of G and return G. You will write more later.

Modify 'main' so that it computes the minimal spanning tree (by calling 'minimalSpanningTree') and prints that tree. Test this, keeping in mind that 'minimalSpanningTree' currently just sorts the edges. You can use the automated tester. Are the edges sorted correctly? Do not skip testing this!

12. Kruskal's Algorithm

Modify your 'minimalSpanningTree' function definition so that it uses Kruskal's algorithm to compute a minimal spanning tree of G. Create a new graph T (in the heap) without any edges.

Look at each edge in G and decide whether to add it to T. If so, then add it to T. You already have a function that adds an edge to a graph. Use it.

See the next step, "determining connections," to see how to decide whether to add an edge to the minimal spanning tree.

The only modification of G that minimalSpanningTree(G) is allowed to do is to sort the array of edges. You are not allowed to destroy the array of edges in G in order to build the array of edges of the minimal spanning tree! Graph G must be intact after running minimalSpanningTree(G). Making a shallow copy of G won't help. Do not copy G.

13. Determining Connections

For two vertices u and v, say that u~v just when there is a path between u and v. Then ~ is an equivalence relation. (~ is reflexive: the path from u to u has length 0 and is just (u). It should be easy to see that ~ is also symmetric and transitive.)

Use your equivalence relation manager from the previous assignment to keep track of the equivalence classes of ~. Initially, each vertex is in an equivalence class by itself. When Kruskal's algorithm calls for adding an edge between u and v, it must tell the equivalence relation manager to merge u and v. To ask if there is a path between u and v, just ask if u and v are in the same equivalence class.

Do not copy your equivalence manager into your file that implements Kruskal's algorithm. Keep it in separate files equiv.cpp and equiv.h. Just include "equiv.h" in mst.cpp. Do not include equiv.cpp in mst.cpp!

Now test this. Is the minimal spanning tree correct? Try more than one graph! Many students have submitted programs that they thought were correct but that failed some tests.

14. Getting the Total Weight

In mst.cpp, define and document a function to compute the total weight of a graph by adding up the weights of the edges. It should return the weight, and must not write anything.

Add a call to this function in main. Test it.

15. Proofread your program.

Proofread your contracts. Make sure that there are no spelling or grammatical errors. Be sure that each contracts explains how each parameter affects the function, and refer to each parameter by its name.

4 2. 5 2 3 9 3 4 2. 5 2 3 9 3