代写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:
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.