Assigned: | Monday, October 3 |
Due: | Monday, October 24, 11:59pm |
This assignment gives you experience using structures and arrays and writing a program with two modules.
It is important to follow the design. Do not make up a different design.
An undirected graph (or simply a graph) is a collection of vertices connected by a collection of edges. An edge connects exactly two different vertices to one another. You can draw a picture of a graph by showing the vertices as circles and the edges as lines connecting them. Here is an example.
A path from vertex v1 to vertex vk is a sequence of vertices (v1, v2, …, vk) such that there is an edge between vi and vi+1, for i = 1, …, n − 1.
We will only be concerned with connected graphs. A graph is connected if there is a path from every vertex to every other vertex. For example, in the above graph, there is a path from 3 to 4 that goes (3, 1, 2, 4). There are other paths from 3 to 4 as well. For any two vertices u and v, there is a path from u to v.
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 the graph so that it is no longer connected. That is, we still need to have a path from each vertex to each other vertex. For example, the following is a spanning tree of the above weighted graph.
If graph G has n vertices then every spanning tree of G has exactly n−1 edges.
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.
There is a well-known algorithm, called Kruskal's algorithm, for computing a minimal spanning tree of a weighted graph. It goes as follows.
Sort the edges from small weight to larger weight. Call the sorted list of edges e0, …, em−1. So, for example, e0 is the edge with the smallest weight.
Start with an empty graph K. It has all of the vertices, but no edges yet. Edges will be added to it until, at the end, it is the minimal spanning tree.
For i = 0, …, m−1 do
When the algorithm is done, K is a minimal spanning tree of your graph. See below for an argument that Kruskal's algorithm works.
Kruskal's algorithm is an example of a greedy algorithm, which is an algorithm that tries to optimize on a large scale by optimizing on a small scale. When Kruskal's algorithm chooses an edge to connect two groups of vertices, it chooses the edge with the smallest weight that does the job (because it looks at the edges in increasing order of weight). There is no thought about whether that decision will be a good one in the long run. It turns out that Kruskal's algorithm works, and always finds a minimal weight spanning tree. Watch out, though. Many greedy algorithms for other problems appear to be reasonable but fail to produce a correct result on some inputs.
Write a program that reads a description of a weighted graph with integer weights, in the input format shown below. Then the program should print the original graph and the edges that are part of a minimal spanning tree of that graph, in a clear and readable format. It should also print the total weight of the minimal spanning tree. 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.
The input must be read from the standard input and the output must be written to the standard output.
You can put test inputs into files, and I strongly recommend that you do that. Just redirect the standard input to a file. Command
./mst <graph1.txtruns executable file mst with its standard input coming from file graph1.txt.
Start from the standard template. Call your program mst.cpp.
Your program must follow the outline in the next section, "design and implementation plan." It can have additional functions, but it must have at least the functions indicated in the design.
As always, your program must follow the coding standards.
Development plan |
---|
1. Representing a Weighted GraphStart by defining two structure types. All structure types must be documented by saying (1) what a value of this structure represents and (2) what each field represents.
You can assume that there are no more than 100 edges, but that number must be easy to change. To increase this to 200, for example, should only require changing one line of your program. To achieve that, create a named constant that is the maximum number of edges. For example, const int maxEdges = 100;defines constant maxEdges with a value of 100. Any time you need to refer to the maximum number of edges, use maxEdges, not 100. |
2. Installing an EdgeDefine a function insertEdge(u, v, w, g) that adds an edge between u and v of weight w to graph g. If the array is full, it should refuse to add the edge. Here is a suitable contract for insertEdge. Not its similarity to the preceing 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. |
3. Input and Input FormatDefine a function readGraph() that takes no parameters and reads a graph from the standard input. It must return the graph. First, write a contract. It should be short, simple and clear. 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 50indicates 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. 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 Function readAGraph will need to build a graph and install edges in it. It must use insertEdge to install each edge. |
4. Output and Output FormatDefine 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. |
5. MainDefine a main function that just reads a graph and writes it. Test it. Do not move on until this works. |
6. Sorting an Array of EdgesDefine and document a function sortEdges(g) that sorts the array of edges in graph g. 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 implements a variant of the Quicksort algorithm. You should include header file <cstdlib> to use qsort. Qsort needs information about the array and how to sort it. It also needs for you to perform some 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
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. Warning. Function qsort is part of the C standard library, and C is an old language designed for experts. Some things are done in clumsy ways. Your function, compareEdges, does not have type QSORT_COMPARE_TYPE, since compareEdges takes two parameters of type const Edge*, and qsort says that it should take two parameters of type void*. But you can tell the compiler to ignore this, and to let you pass your compareEdges function to qsort, by doing a cast, which tells the compiler to treat a value of one type as if it is a value of a different type. In most cases, this is a very dangerous thing to do, but you have to do it to use qsort. |
7. Building a Minimal Spanning TreeDefine and document a function minimalSpanningTree(g) that will take a graph g as a parameter and return a minimal spanning tree of g (also of type graph). 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. Modify main so that it computes the minimal spanning tree and prints it. Test this, keeping in mind that minimalSpanningTree currently just sorts the edges. Are the edges sorted correctly? |
8. Performing Kruskal's AlgorithmNow modify your minimalSpanningTree function definition so that it uses Kruskal's algorithm to compute a minimal spanning tree. Create a new graph K without any edges. Look at each edge in g and decide whether to add it to K. If so, then add it to K. You already have a function that adds an edge to a graph. 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. See the next item, "determining connections," to see how to decide whether to add an edge to the minimal spanning tree. |
9. Determining ConnectionsFor 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 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, 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! |
10. Getting the Total WeightDefine 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. |
Do not modify equiv.h or equiv.cpp, unless you are only fixing errors. No minimal-spanning-tree code should find its way into equiv.h or equiv.cpp.
In the past, many students have become lax about contracts in this assignment, and it has cost them a lot of points. Pay attention to contracts. Proofread them. Do they explain how every parameter affects what the function accomplishes? Do they refer to parameter by name? Do they explain what the returned value means, if there is a returned value?
Be sure to document your structure type definitions. Say what the structure represents and what information each field holds.
Ensure that you are implementing Kruskal's algorithm correctly. Test your program on more than one graph. Check the output. Is it right?
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.
Choose sensible variable names.
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. Any bugs that result from ignoring this advise are on you.
Your mst.cpp file must not make use of the fact that type ER is a pointer or an array. Just use the functions defined in equiv.cpp on ER objects. You can expect to lose a lot of points if you ignore this.
Each function can have at most one loop in its body. Do not use one loop to simulate two nested loops by manipulating the loop parameters.
A function body must not change the value of a call-by-value parameter.
Make sure that each function does its whole job., not just part of it job. Make sure that a function does not have undocumented requirements.
Avoid code duplication and duplicate calls.
A Makefile is provided for you. If you put it in the directory that you have created for assignment 4, then you can use the following.
To turn in your work, log into the Linux system, change your
directory for the one for assignment 4,
use the following command.
~abrahamsonk/2530/bin/submit 4 mst.cpp equiv.cpp equiv.h
After submitting, you should receive confirmation that the
submission was successful. If you do not receive confirmation,
assume that the submission did not work.
Command
~abrahamsonk/2530/bin/submit 4
will show you what you have submitted for
assignment 4.
You can do repeated submissions. New submissions will replace old ones.
Late submissions will be accepted for 24 hours after the due date. If you miss a late submission deadline by a microsecond, your work will not be accepted.