READING

Read the text, chapter 8 for explanations of how the the MST (Prim) and_x000D_
the SSSP (Dijkstra) algorithms are based on priority queues._x000D_
Be sure to read 8.2.5 and 8.3.3.  The table in Fig. 8.5 is transposed_x000D_
compared to how it is shown in lecture and should be printed for the_x000D_
assignment._x000D_
_x000D_
Several online Unix tutorials are mentioned on the class web page._x000D_
Some tutorials are gdb_tutorial.txt and valgrind.txt ._x000D_
_x000D_
==========================================================================_x000D_
_x000D_
INFORMATION SOURCES_x000D_
_x000D_
Same as ho04.txt, the 1st program assignment._x000D_
_x000D_
adjWgtVec.h and minPQ.h are provided in the class locker and in Handouts_x000D_
directories off the class locker and the class web page._x000D_
_x000D_
These files are for the ADTs AdjWgtVec and MinPQ.  You will implement_x000D_
adjWgtVec.c and minPQ.c for pa04.  Your adjWgtVec.o and minPQ.o should be_x000D_
usable by other students and your greedy04 should be able to use theirs._x000D_
_x000D_
Your pa02 assignment has a lot of the code needed for pa04, if it was_x000D_
fully implemented.  pa03 also should have much of this code._x000D_
==========================================================================_x000D_
_x000D_
ADT OVERVIEW_x000D_
_x000D_
This assignment has an AdjWgtVec ADT that carries over from pa02 and pa03._x000D_
It has a new ADT MinPQ that is more substantial as an ADT than AdjWgtVec_x000D_
because it maintains state and has manipulation procedures.  Yet, in the_x000D_
interest of easy reporting, the information is not hidden._x000D_
_x000D_
The IntVec ADT is not used in pa04 (at least it is not required; you_x000D_
might find a use in some subroutine, but that is your choice.)_x000D_
_x000D_
==========================================================================_x000D_
_x000D_
PROGRAM REQUIREMENTS_x000D_
_x000D_
You will implement Prim's Minimum Spanning Tree algorithm (MST)_x000D_
as explained in the text, Ch. 8._x000D_
It will also be able to execute Dijkstra's Shortest-Path algorithm (SSSP),_x000D_
based on a command-line option._x000D_
The only differences between the algorithms is the function to calculate_x000D_
priority and whether the graph is undirected or directed._x000D_
_x000D_
graph01.c, LoadGraph.c, etc., can be used right from your pa01,_x000D_
except that input edges are treated as UNDIRECTED for MST and have weights_x000D_
in all cases._x000D_
Alternatively, use graph02.c or scc03.c from pa02 or pa03 as a starter._x000D_
In either case,_x000D_
_x000D_
NAME YOUR MAIN PROGRAM greedy04.c AND COMPILE IT INTO THE EXECUTABLE greedy04._x000D_
_x000D_
The "main" procedure will be changed to do different things_x000D_
after the graph is loaded._x000D_
Procedures in this file will allocate the arrays filled by greedyTree():_x000D_
status, fringeWgt, parent._x000D_
_x000D_
greedyTree() is our name for the function that runs either MST or SSSP._x000D_
SEE pp. 397-402 FOR JAVA PSEUDOCODE._x000D_
SEE pp. 397-402 FOR JAVA PSEUDOCODE._x000D_
SEE pp. 397-402 FOR JAVA PSEUDOCODE._x000D_
Note that primMST() in the text allocates "status" because it is not_x000D_
referenced by the caller of primMST(), whereas fringeWgt and parent are_x000D_
used by the caller, so they are allocated earlier and passed in._x000D_
However, this program outputs status, as well as fringeWgt and parent,_x000D_
so you should allocate all three arrays in one place (probably main())_x000D_
and pass them all in to greedyTree()._x000D_
The prototype for greedyTree() will change accordingly._x000D_
_x000D_
We'll follow the C convention of lowercase file names, but type names_x000D_
will remain capitalized.  The correspondences follow the same pattern_x000D_
as earlier programs._x000D_
==========================================================================_x000D_
_x000D_
INPUT FORMAT_x000D_
_x000D_
Input consists of a sequence of lines read from the file_x000D_
that was given as a command-line argument.  The string "-" as a filename_x000D_
stands for ``standard input'', as usual._x000D_
Standard input is called System.in for java and stdin for C._x000D_
We will use stdin to denote either case._x000D_
_x000D_
End-of-file signals the end of input, and is typed on the keyboard_x000D_
as cntl-D in Unix (maybe cntl-Z in DOS, Windows, etc.)._x000D_
_x000D_
Lines will have the format expected by graph01.c, WITH weights._x000D_
One int on the first line to tell us the value of "n"._x000D_
Two ints and a double per line for each edge after that._x000D_
Set up your calls to sscanf to look for these formats._x000D_
Use " %d %d %lf" to assume correct input or " %d %d %lf %c" to check_x000D_
for extra junk._x000D_
_x000D_
Print an informative error message if the input contains a bad vertex_x000D_
number, outside 1,...,n, or has the wrong number of words on a line._x000D_
This is for your own good; not a grading issue._x000D_
_x000D_
Example input:_x000D_
3_x000D_
1 2 4.5_x000D_
2 3 1.5_x000D_
1 3 2.5_x000D_
3 2 1.0_x000D_
The above is just an example of the format._x000D_
It is NOT suggested as a good test file._x000D_
_x000D_
Remember that graphs want to start on index 1, not index 0._x000D_
So allocate 1 extra space in the array and start loading at 1._x000D_
_x000D_
You should make some test files that properly test the algorithms._x000D_
Extensive testing for syntax errors in the input is unnecessary._x000D_
See the examples in the text, and especially those in the homework_x000D_
exercises and practice midterm.  The above is just an example of the format._x000D_
_x000D_
Whether the input is treated as undirected or directed depends on a_x000D_
command-line argument, as described next._x000D_
If the graph is considered undirected, create an edge in each direction_x000D_
from one edge in the input file.  In the above example, for an_x000D_
undirected graph "1 2 4.5" should result in edges (1,2) and (2,1),_x000D_
both with weight 4.5._x000D_
_x000D_
Do not worry if edges are not unique.  MST will work anyway._x000D_
In the above example, you would get parallel edges (2,3) with weights_x000D_
1.5 and 1.0 for the undirected graph, as well as edges (3,2) with weights_x000D_
1.5 and 1.0._x000D_
_x000D_
==========================================================================_x000D_
_x000D_
COMMAND-LINE ARGUMENTS_x000D_
_x000D_
If your program receives no command-line arguments, it should print_x000D_
a usage message and exit._x000D_
Your program must receive at least three command-line arguments to_x000D_
define its task._x000D_
_x000D_
Initial command-line arguments of the form "-something" provide_x000D_
the means for varying what the program does.  One such argument MUST be_x000D_
present, to choose among Prim (-P) and Dijkstra (-D)._x000D_
Depending on this argument, the program sets a variable_x000D_
named "task" and passes it to other functions to vary their computations_x000D_
slightly according to which algorithm is being run._x000D_
Set the value of "task" to 'P' or 'D' according to what is in_x000D_
the command line.  pay attention to single vs. double quotes._x000D_
_x000D_
The second-to-last command-line argument is an integer that gives the_x000D_
START VERTEX for the algorithm to use._x000D_
The final command-line argument is the name of the input file_x000D_
containing the weighted graph._x000D_
This name will not begin with a "-" unless it is "-" by itself,_x000D_
in which case the ``file'' is stdin._x000D_
_x000D_
Examples (in C);_x000D_
_x000D_
Prim MST starting at vertex 7_x000D_
	greedy04 -P 7 graph1.txt_x000D_
_x000D_
Dijkstra SSSP starting at vertex 1_x000D_
	greedy04 -D 1 graph1.txt_x000D_
_x000D_
Notice that the command-line format is an extension of pa02 and pa03._x000D_
_x000D_
==========================================================================_x000D_
_x000D_
OUTPUT_x000D_
_x000D_
Print information on stdout._x000D_
Essentially, output the arrays filled by the algorithm.  Show columns_x000D_
for vertex number, status, priority (cost, depending on which task), parent._x000D_
Print a heading that states which algorithm was run and what the_x000D_
start vertex is._x000D_
_x000D_
DEBUGGING HINT: Let your printArrays() procedure/function/method return_x000D_
an int, so it looks like a function.  It may always return 0._x000D_
This allows you run it from gdb in the middle of your program,_x000D_
by typing "p printArrays()", assuming it takes no parameters._x000D_
_x000D_
When running the program on a large input file remember to use ">"_x000D_
to redirect the stdout to a file._x000D_
==========================================================================_x000D_
_x000D_
HOW TO PROCEED_x000D_
_x000D_
Make a new directory to work in.  Do this first._x000D_
_x000D_
Copy graph02.c to a new name, say greedy04.c._x000D_
Copy intVec.c and intVec.h and Makefile from pa02 into this directory._x000D_
Confirm that graph02 compiles and works._x000D_
From now on graph02.c, intVec.c and intVec.h are not used, except_x000D_
as a reference to be sure you did not change anything by accident._x000D_
DON'T SUBMIT graph02.c, intVec.c and intVec.h._x000D_
_x000D_
If pa02 was not working use pa03 files for your starters,_x000D_
whichever was working best.  Copy them into this directory._x000D_
Then do the above steps on them._x000D_
_x000D_
Now you are ready to start building the MST/SSSP procedures.  Refer to code_x000D_
from your earlier programs if they were working.  Use working code_x000D_
for a starter on new code whenever possible._x000D_
_x000D_
One difference in loadGraph.c from pa03 is that pa03 reads undirected or_x000D_
directed edges, always unweighted,  and now you need undirected weighted or_x000D_
directed weighted edges, depending on the task._x000D_
Also the AdjWgt vectors are weighted, which is different from IntVec._x000D_
Use loadGraph.{c,h} as starters for loadWgtGraph.{c,h} and make changes_x000D_
in the new files._x000D_
_x000D_
Use adjWgtVec.h in the course locker as your starter and add your comments_x000D_
that answer the questions in that file.  DO NOT CHANGE SPELLING._x000D_
_x000D_
Keep life simple and make a function to compute the priority_x000D_
that takes a parameter named "task" to vary how priority_x000D_
is computed.  Set the value of "task" to 'P' or 'D' according_x000D_
to what is in the command line._x000D_
_x000D_
==========================================================================_x000D_
_x000D_
Implementation plan for MST/SSSP in C_x000D_
_x000D_
File            Module         Important Public Fields and Functions_x000D_
_x000D_
greedy04.{c,h}  greedy04       main()_x000D_
                               greedyTree() as in text as MST or SSSP_x000D_
                                   See pp. 397-402._x000D_
                               updateFringe()  as in text, but calls ..._x000D_
			       calcPriority() to calculate the priority._x000D_
                               printOutput()_x000D_
_x000D_
                               int n               // number of vertices_x000D_
                               AdjWgtVec * adjInfo  (instead of adjVertices)._x000D_
_x000D_
                               int task            // 'P' or 'D'_x000D_
_x000D_
                               int s               // start vertex_x000D_
                               int * status_x000D_
                               int * parent_x000D_
                               double * fringeWgt_x000D_
_x000D_
loadWgtGraph.{c,h} LoadWgtGraph  parseN(), initAdjInfo(), loadAdjInfo(), etc.,_x000D_
                                   mostly as in the Appendix, but_x000D_
                                   adjInfo is an array of AdjWgtVec now,_x000D_
                                   not IntVec.  Also, task should be passed_x000D_
                                   in to tell whether to treat the graph as_x000D_
                                   undirected._x000D_
_x000D_
minPQ.{c,h}     MinPQ          (ADT) mostly as in text, pp. 400-402._x000D_
                                     minPQ.h starter is in course locker._x000D_
                                     DO NOT CHANGE PROTOTYPES; add comments_x000D_
_x000D_
                                     As discussed in the text, this_x000D_
                                     Priority Queue ADT should be faithful_x000D_
                                     to the specifications of the_x000D_
                                     operations.  However, the arrays_x000D_
                                     are not private, like they should_x000D_
                                     be for a ``pure'' ADT.  Therefore,_x000D_
                                     the main() procedure can access info_x000D_
                                     about a vertex directly, without_x000D_
                                     going through access functions,_x000D_
                                     for printing purposes, mainly._x000D_
_x000D_
adjWgtVec.{c,h}  AdjWgtVec     (ADT) adjWgtMakeEmptyVec(), adjWgtTop(),_x000D_
                                     adjWgtData(),_x000D_
                                     adjWgtSize(), adjWgtCapacity(),_x000D_
                                     adjWgtVecPush(), adjWgtVecPop()_x000D_
                                     vector of elements of type AdjWgt._x000D_
                                     adjWgtVec.h starter is in course locker._x000D_
                                     DO NOT CHANGE PROTOTYPES; add comments_x000D_
_x000D_
adjWgtVec.h      AdjWgt       (NON-ADT) struct and typedef: to, wgt._x000D_
_x000D_
intVec.{c,h}   IntVec         (ADT) (a starter for adjWgtVec.{c,h}, but_x000D_
                                     not used in the final program) and_x000D_
                                     NOT SUBMITTED._x000D_
_x000D_
==========================================================================_x000D_
_x000D_
A few technical notes:_x000D_
_x000D_
All uses of "float" in the text are changed to "double" here._x000D_
_x000D_
The appendix code had no global variables, but your 3rd program_x000D_
might have.  pa04 should have no extern variables shared across files._x000D_
However, the static constant adjWgtInitCap occurs._x000D_
_x000D_
Although you should not use global variables that are shared across files,_x000D_
you can define "static" variables for important "public" variables,_x000D_
such as n, task, s, in greedy04.c._x000D_
Outside of any function put something like this:_x000D_
_x000D_
static int n;_x000D_
static int task;_x000D_
static int s;_x000D_
_x000D_
minPQ.c should have static variables too, initialized by createPQ()._x000D_
_x000D_
minPQ.h defines the values for the status as:_x000D_
#define UNSEEN ('u')_x000D_
#define FRINGE ('f')_x000D_
#define INTREE ('t')_x000D_
Note that single characters can be type int._x000D_
==========================================================================_x000D_
_x000D_
AdjWgtVec ADT_x000D_
_x000D_
Notice that adjWgtVec.h contains all the details of the AdjWgt struct,_x000D_
but does not show details of the AdjWgtVecNode struct._x000D_
This gives flexibility in how that list is implemented._x000D_
_x000D_
Essentially the type "AdjWgt" replaces the type "int" as the data type_x000D_
for this kind of vector.  It would not be of much use if the clients_x000D_
did not know the details of AdjWgt._x000D_
_x000D_
==========================================================================_x000D_
_x000D_
SUBMITTING_x000D_
_x000D_
The assignment name is pa04.  An example (incomplete) submit command is:_x000D_
_x000D_
  submit cmps101-avg.s17 pa04  greedy04.c  adjWgtVec.c adjWgtVec.h   Makefile_x000D_
_x000D_
You can list as many files as you want to submit.  If you update files,_x000D_
just submit them again.  Don't resubmit unchanged files needlessly._x000D_
_x000D_
DO NOT SUBMIT LARGE INPUT FILES OR LARGE OUTPUT FILES._x000D_
_x000D_
If you submit irrelevant junk, you will lose a fast 20 points._x000D_
It's a good policy to explain in your README any file that is not_x000D_
obviously part of your program._x000D_
_x000D_
You have to put your documentation in your .h files, for data and_x000D_
functions shared by multiple files, as described in adt-c.pdf._x000D_
_x000D_
Submit a README that briefly describes your program with a few sentences,_x000D_
mainly to tell the reader how to run it, what test inputs and outputs_x000D_
you supplied, what they show, and any known bugs._x000D_
If the purpose of some files might be mysterious, here is the place to_x000D_
explain them._x000D_
_x000D_
==========================================================================_x000D_
_x000D_
All code to be graded should follow good style practices including_x000D_
appropriate indentation, descriptive names, consistent capitalization,_x000D_
and useful comments.  Comments should indicate the purpose, preconditions,_x000D_
and postconditions of important procedures.  Avoid comments of_x000D_
self-explanatory code.  The reader may grade your program low_x000D_
if it is sloppily done, making it hard to understand or follow._x000D_
RESPECT THE READER'S TIME.

Do you need a similar assignment done for you from scratch? We have qualified writers to help you. We assure you an A+ quality paper that is free from plagiarism. Order now for an Amazing Discount!
Use Discount Code "Newclient" for a 15% Discount!

NB: We do not resell papers. Upon ordering, we do an original paper exclusively for you.