C代写:CMPS101 Minimum Spanning Tree

代写Graph相关的算法作业,需要编写Minimum Spanning Tree算法。

Reading

Read the text, chapter 8 for explanations of how the the MST (Prim) and the SSSP (Dijkstra) algorithms are based on priority queues.
Be sure to read 8.2.5 and 8.3.3. The table in Fig. 8.5 is transposed compared to how it is shown in lecture and should be printed for the assignment.

Several online Unix tutorials are mentioned on the class web page. Some gdb tutorials are mentioned in the message list.

Information sources

Same as ho04.txt, the 1st program assignment.

edgeVec.h and minPQ.h are provided in the class locker and in Handouts directories off the class locker and the class web page.

These files are for the ADTs EdgeVec and MinPQ. You will implement edgeVec.c and minPQ.c for pa04. Your edgeVec.o and minPQ.o should be usable by other students and your greedy04 should be able to use theirs.

Your pa02 assignment has a lot of the code needed for pa04, if it was fully implemented. pa03 also should have much of this code.

ADT overview

This assignment has an EdgeVec ADT that carries over from pa02 and pa03. It has a new ADT MinPQ that is more substantial as an ADT than EdgeVec because it maintains state and has manipulation procedures. Yet, in the interest of easy reporting, the information is not hidden.

The IntVec ADT is not used in pa04 (at least it is not required; you might find a use in some subroutine, but that is your choice.)

Program requirements

You will implement Prim’s Minimum Spanning Tree algorithm (MST) as explained in the text, Ch. 8.
It will also be able to execute Dijkstra’s Shortest-Path algorithm (SSSP), based on a command-line option.
The only differences between the algorithms is the function to calculate priority and whether the graph is undirected or directed.

graph01.c, LoadGraph.c, etc., can be used right from your pa01, except that input edges are treated as UNDIRECTED for MST and have weights in all cases.
Alternatively, use dfs02.c or scc03.c from pa02 or pa03 as a starter.

The “main” procedure will be changed to do different things after the graph is loaded.
Procedures in this file will allocate the arrays filled by greedyTree(): status, fringeWgt, parent.

greedyTree() is our name for the function that runs either MST or SSSP.
Note that primMST() in the text allocates “status” because it is not referenced by the caller of primMST(), whereas fringeWgt and parent are used by the caller, so they are allocated earlier and passed in.
However, this program outputs status, as well as fringeWgt and parent, so you should allocate all three arrays in one place (probably main()) and pass them all in to greedyTree().
The prototype for greedyTree() will change accordingly.

We’ll follow the C convention of lowercase file names, but type names will remain capitalized. The correspondences follow the same pattern as earlier programs.

Input format

Input consists of a sequence of lines read from the file that was given as a command-line argument. The string “-“ as a filename
stands for ``standard input’’, as usual. Standard input is called System.in for java and stdin for C. We will use stdin to denote either case.

End-of-file signals the end of input, and is typed on the keyboard as cntl-D in Unix (maybe cntl-Z in DOS, Windows, etc.).

Lines will have the format expected by graph01.c, WITH weights. One int on the first line to tell us the value of “n”.
Two ints and a double per line for each edge after that. Set up your calls to sscanf to look for these formats.

Print an informative error message if the input contains a bad vertex number, outside 1,…,n, or has the wrong number of words on a line. This is for your own good; not a grading issue.

Example input:

3
1 2 4.5
2 3 1.5
1 3 2.5
3 2 1.0

The above is just an example of the format. It is NOT suggested as a good test file.

Remember that graphs want to start on index 1, not index 0. So allocate 1 extra space in the array and start loading at 1.

You should make some test files that properly test the algorithms. Extensive testing for syntax errors in the input is unnecessary.
See the examples in the text, and especially those in the homework exercises and practice midterm. The above is just an example of the format.

Whether the input is treated as undirected or directed depends on a command-line argument, as described next. If the graph is considered undirected, create an edge in each direction from one edge in the input file. In the above example, for an undirected graph “1 2 4.5” should result in edges (1,2) and (2,1), both with weight 4.5.

Do not worry if edges are not unique. MST will work anyway. In the above example, you would get parallel edges (2,3) with weights 1.5 and 1.0 for the undirected graph, as well as edges (3,2) with weights 1.5 and 1.0.

Command-line arguments

If your program receives no command-line arguments, it should print a usage message and exit.
Your program must receive at least three command-line arguments to define its task.

Initial command-line arguments of the form “-something” provide the means for varying what the program does. One such argument MUST be present, to choose among Prim (-P) and Dijkstra (-D). Depending on this argument, the program sets a variable named “task” and passes it to other functions to vary their computations slightly according to which algorithm is being run.
Set the value of “task” to ‘P’ or ‘D’ according to what is in the command line.

The second-to-last command-line argument is an integer that gives the start vertex for the algorithm to use.
The final command-line argument is the name of the input file containing the weighted graph.
This name will not begin with a “-“ unless it is “-“ by itself, in which case the ``file’’ is stdin.

Prim MST starting at vertex 7

greedy04 -P 7 graph1.txt

Dijkstra SSSP starting at vertex 1

greedy04 -D 1 graph1.txt

Notice that the command-line format is an extension of pa02.

Output

Print information on stdout. Essentially, output the arrays filled by the algorithm. Show columns for vertex number, status, priority (cost, depending on which task), parent. Print a heading that states which algorithm was run and what the start vertex is.

Debugging hint: Let your printArrays() procedure/function/method return an int, so it looks like a function. It may always return 0.
This allows you run it from gdb in the middle of your program, by typing “p printArrays()”, assuming it takes no parameters.

How to proceed

Make a new directory to work in. Do this first.

Copy graph02.c to a new name, say greedy04.c.
Copy intVec.c and intVec.h and Makefile from pa02 into this directory.
Confirm that graph02 compiles and works.
From now on graph02.c, intVec.c and intVec.h are not used, except as a reference to be sure you did not change anything by accident.
DON’T SUBMIT graph02.c, intVec.c and intVec.h.

If pa02 was not working use pa03 files for your starters, whichever was working best. Copy them into this directory.
Then do the above steps on them.

Now you are ready to start building the MST/SSSP procedures. Refer to code from your earlier programs if they were working. Use working code for a starter on new code whenever possible.

One difference in loadGraph.c from pa03 is that pa03 reads undirected or directed edges, always unweighted, and now you need undirected weighted or directed weighted edges, depending on the task.
Also the edge vectors are weighted, which is different. Use loadGraph.{c,h} as starters for loadWgtGraph.{c,h} and make changes in the new files.

Use edgeVec.h in the course locker as your starter and add your comments that answer the questions in that file. DO NOT CHANGE SPELLING.

Keep life simple and make a function to compute the priority that takes a parameter named “task” to vary how priority is computed. Set the value of “task” to ‘P’ or ‘D’ according to what is in the command line.

A few technical notes

All uses of “float” in the text are changed to “double” here.

The appendix code had no global variables, but your 3rd program might have. pa04 should have no extern variables shared across files. However, the static constant edgeInitCap occurs.

Although you should not use global variables that are shared across files, you can define “static” variables for important “public” variables, such as n, task, s, in greedy04.c.

EdgeVec ADT

Notice that edgeVec.h contains all the details of the EdgeInfo struct, but does not show details of the EdgeVecNode struct. This gives flexibility in how that list is implemented.

Essentially the type “EdgeInfo” replaces the type “int” as the data type for this kind of vector. It would not be of much use if the clients did not know the details of EdgeInfo.