A graph is a collection of vertices connected by a collection of edges. An edge connects exactly two vertices to one another. You can draw a picture of a graph by showing the vertices and the edges connecting them. Here is an example. The vertices are shown as circles with numbers in them and the edges are lines connecting the vertices.
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 vertices are the towns, and 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 having a vertex for each outlet and for the circuit panel, with the weight between two vertices being the wiring distance between those vertices. Then 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 placements of Steiner points are difficult to find, so a minimal spanning tree is a reasonable compromise.)
For this assignment, you will write a program that reads a description of a weighted graph, and prints the edges that are part of a minimal spanning tree of that graph, and also prints the total weight of the minimal spanning tree.
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 50indicates that there is an edge between vertices 2 and 4, and that its weight is 50. The end of the input is signaled by a line that contains just a 0. An input describing graph
might look like this.
5 1 2 9 1 3 12 2 4 18 2 3 6 2 5 20 3 5 15 0
Please note that the first number is the number of vertices, not the number of edges. The output of your program for this input might look like this.
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.
When designing a program, you need to decide how to represent your data. Typically, you draw diagrams showing arrays, structures, pointers, etc. to understand the data representation.
Once you have decided on a representation, you need to decide whether you want the data structure to be open or closed in your program.
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 or module, and only allowing the data to be accessed through public functions of the class or module. This typically involves more initial work, but makes your program easier to modify and often makes it easier to write in the long run.
For this program I will have mercy on you and allow you to use an open representation for graphs. You will find this a little simpler.
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.
Here is a simple algorithm, called Kruskall's Algorithm, for computing a minimal spanning tree of a weighted graph. It uses the Merge-together abstract data type fromyour second assignment.
If the array of edges of the graph is called G.edges, then sort the edges in G.edges by their weights, with smaller weights earlier in the array. (You can use function qsort, described below, to do this.)
Create a new merge-together object with a value for each vertex. Say that two vertices are connected if they are in the same set. Initially, there are no connections, so every vertex is in a singleton set.
Create an array that will end up holding the edges of the spanning tree. Initially, it has no edges in it, but you gradually add more edges. Also create a count, initially 0, of the total weight of the edges in the spanning tree array.
Scan through the array G.edges in increasing order of weight. (That is, do the following in a loop.) When you see edge (i,j), with weight w, ask the merge-together object 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 merge-together object that i and j are connected. Then do the next edge.
When you are finished, you will have created an array holding the edges of a minimal spanning tree of the original graph, and you will have computed the total weight. Print them all.
There is a standard library function called qsort that implements a variant of the quicksort algorithm for sorting arrays. You should include header file stdlib.h or cstdlib to use qsort. This function is designed to be able to sort any kind of array into any desired order. In order to achieve this degree of generality, qsort needs information about the array and how to sort it.
The prototype for qsort is as follows.
void qsort(void *base,
size_t nel,
size_t width,
int (*compar) (const void *, const void *));
Parameter base is a pointer to the array that you want to sort.
Notice that its type is void*. That just means that qsort knows that
it is a pointer, but does not know what type of thing it points to.
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
| a negative number | if A < B | |
| 0 | if A = B | |
| a positive number | if A > B |
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)
{
return *B - *A;
}
Notice that compareLongInts returns a positive number when A < B.
This is because you
want to sort into descending order, but qsort wants to sort into
what it thinks is ascending order. So you tell qsort that 30 < 10.
Also notice that the parameters to compareLongInts are pointers.
qsort will call this function, and will pass it pointers to the
members that qsort wants to compare. qsort will call the
comparison function many times.
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);We have passed qsort the array to sort, the number of elements, the number of bytes occupied by each element (given by sizeof(long), since each element has type long) and the comparison function, cast to the appropriate type.
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. Function compareLongInts is only an example, and cannot be used to compare edges. An edge is not an integer. Write a function to compare two edges.
Here is a suggestion for how to implement this program. This is a refinement plan. It tells how to produce more and more of the program, gradually refining it until eventually it does the whole job. It is critical that a refinement plan have tests along the way, so that the part written so far is known to work. That way, if you get an error, it is almost always in the part of the program that was most recently written, and finding bugs is relatively easy.
Implement the part of the program that reads in and prints out the input graph. Test it. It is a good idea to use functions. You will need to print other graphs later.
Implement the beginnings of the minimal spanning tree algorithm by sorting the edges and printing them after sorting. Be sure that this is working.
Implement the rest of the minimal spanning tree algorithm. Test it.
Make the program's output look nice, if necessary. Test it.
When you do a test, if things don't work, then use the debugger or add some prints to see what is going on. Do not try to work in the dark. Before you try to fix the problem, understand what is wrong. After you have diagnosed the problem, fix it. Do not move on until everything that you have written so far is working.
Turn in all of your source files, including the ones from assignment 2 that you are using here. You are allowed to turn in a version of your assignment 2 program that does not implement the efficiency improvements, and will not be graded down for that in this assignment. There should be, at a minimum, two files for the merge-together data type (a header file and an implementation file) and one file for the minimal spanning tree program. There might be more, depending on how you implement this program.
The merge-together abstract data type must be in a separate file from the minimal spanning tree finder. Your program should be well documented, well indented and easy to read. Keep it that way during development. Do not try to work on a sloppy, poorly documented program, unless you have time to burn.