Computer Science homework help

Coding Assignment 3
CSE2320
Name your program Code3_xxxxxxxxxx.c where xxxxxxxxxx is your student id (not netid). My file would be named
Code3_1000074079.c.
Please place the following files in a zip file with a name of Code3_xxxxxxxxxx.zip and submit the zip file.
Code3_xxxxxxxxxx.c
Graph.txt
A zip file is used to avoid Canvas’s file renaming convention.
Reminder – ANY compiler warning(s) or error(s) when compiled on Omega will result in an automatic 0. This apply no matter
what the warning/error is. You will need to code so that your final program will compile cleanly and run on both the VM and
Omega.
For example, if the GTA compiles your code on Omega and sees
[frenchdm@omega CA1]$ gcc Code3_1000074079.c
Code3_1000074079.c:44:2: warning: no newline at end of file
you will receive a 0 on the assignment.
The Program
You are creating a program that can read a file of graph information and run Dijkstra’s Algorithm on the graph and produce the
path and the length/weight of the path between the starting Vertex and any other Vertex in the graph.
Let’s say we start with this graph.
To translate graph to file, we’ll first start by numbering the vertices. The number we assign to a vertex will be that vertex’s
index number in the Vertex Array. Just for convenience, I am going to start with A and number it 0 and go alphabetically from
there. This is not a necessary order. You could start with Vertex E and 0 and mark Vertex C as 1, etc. Just pick one to be index
0 and number from there.
Now we can translate this graph to our file format. Our file format assumes that each line in the file represents a vertex and all
of its edges and weights. If the file has 5 lines, then the graph has 5 vertices.
The format of a line in the file is
VertexLabel, Adjacent Vertex Index, Weight of Edge
where “Adjacent Vertex Index, Weight of Edge” can be repeated. The first line in our file would be
A,1,3,3,6
This shows that Vertex A (which is at index 0) has an edge between itself and Vertex B (which is at index 1) and that edge has a
weight of 3. Vertex A also has an edge between itself and Vertex D (index 3) and that edge has a weight of 6.
The file for this graph will be
A,1,3,3,6
B,0,3,5,4
C,4,4
D,2,5,4,3
E,2,4,5,5
F,1,4,4,5
The ordering of the vertex,edge pairs does not matter – 0,3,5,4 is the same as 5,4,0,3. You need to create a file that
represents a graph you have created – it should be different than the graph shown in the assignment. Name the file
Graph.txt and submit it with your assignment. Your program will be tested with various files/graphs.
IMPORTANT : make NO assumptions about the ordering or the labeling of the vertices in the graph. The VertexLabel could be
up to 5 characters and the vertices can be listed in any order in the file.
Getting Started
Create a define that will be set the to maximum size of your graph – the maximum number of vertices that your program will
load and process. Create your Vertex Array and your Adjacency Matrix using that define. Initialize the Adjacency Matrix to -1.
See File Handling for details on how to populate the Vertex array and the Adjacency Matrix. Prompt for the starting vertex.
Your program should be able to use any vertex in the graph as the starting vertex.
File Handling
As in the previous assignments, open the file from the command line using argv[1]. While using fgets() to read through
the file, use strtok() to parse each line into its parts. Use the parts to
add vertices to the Vertex Array and edges to the Adjacency Matrix.
Conditional Compile
Add a conditional compile statement PRINTIT to print out the Adjacency
Matrix after you have populated it (using values from the file). So, if your
code is compiled as
gcc Code3_xxxxxxxxxx.c -D PRINTIT
then your adjacency matrix will be printed to the screen.
-1 3 -1 6 -1
3 -1 -1 -1 -1
-1 -1 -1 -1 4
-1 -1 5 -1 3
-1 -1 4 -1 -1
The PRINTIT conditional compile should also be used to print out your Vertex Array after running Dijkstra.
I L D P V
0 A 0 -1 1
1 B 3 0 1
2 C 11 3 1
3 D 6 0 1
4 E 9 3 1
I = Index, L = Label, D = Distance, P = Previous, V = Visited
This feature will be used to grade your program. The printing should be controlled with the compiler directive (not by
commenting or uncommenting code). The output of your adjacency matrix and vertex array must have these formats.
Printing and Prompts
The adjacency matrix must be printed AFTER being populated from the file and the vertex array must be printed AFTER running
Dijkstra’s Algorithm. The print outs must be after prompting for the starting vertex. The prompting for the end vertex and
printing of the path may be before or after the print but must be after running Dijkstra’s Algorithm on the data. The path
MUST be printed in order starting with the start vertex and ending with the end/destination vertex. The path should not print
from ending to starting – it must be in order.
Dijkstra’s Algorithm
I suggest you use the Dijkstra code shown in class. It closely mirrors the manual method we learned. If you so choose to use
the Internet as your source, be sure you are getting the C version of Dijkstra (and not some other graph traversal/variation of
Dijkstra). Your Dijkstra code, regardless of where you source it, MUST use an adjacency matrix and a vertex array so that you
can create the required output for grading.
Program Input/Output
student@cse1325:/media/sf_VM2320$ gcc Code3_1000074079.c -g -D PRINTIT
student@cse1325:/media/sf_VM2320$ ./a.out Graph.txt
-1 3 -1 6 -1 -1
3 -1 -1 -1 -1 4
-1 -1 -1 -1 4 -1
-1 -1 5 -1 3 -1
-1 -1 4 -1 -1 5
-1 4 -1 -1 5 -1
What is the starting vertex? A
I L D P V
0 A 0 -1 1
1 B 3 0 1
2 C 11 3 1
3 D 6 0 1
4 E 9 3 1
5 F 7 1 1
What is the destination vertex? E
The path from A to E is A->D->E and has a length of 9
student@cse1325:/media/sf_VM2320$ gcc Code3_1000074079.c -g
student@cse1325:/media/sf_VM2320$ ./a.out Graph.txt
What is the starting vertex? E
What is the destination vertex? A
The path from E to A is E->F->B->A and has a length of 12