Description
Please follow the instructions in the A3 pdf and don’t use any out side sources
Unformatted Attachment Preview
CSS343 Data Structures, Algorithms, and Discrete Mathematics II
Assignment 3: Graph Program
Implement a Graph class on the template below and test your class for depth-first search, breadth-first search
and in djikstra’s shortest path.
All the public functions for Vertex, Edge and Graph have to be implemented. You can change the private
variables and functions as needed. Your program should compile and run against assignment3.cpp provided.
You should write your own expanded version of assignment3.
vertex.h, vertex.cpp, edge.h, edge.cpp, graph.h, graph.cpp, assignment3.cpp
Graph file format
The format of the graph files is: an integer indicating the number of edges, followed by a series of lines of the
from “fromVertex toVertex edgeEweight”. fromVertex and toVertex are strings, edgeWeight is an integer. All
the edges are directed and have 0 or larger weights.
Sample graph files: graph0.txt, graph1.txt, graph2.txt
Pseudocode
graph2.txt as provided
AdjacencyList for the vertex is sorted alphabetically (map already does this for us), so the edge from S to T
gets processed before the edge from S to U. getNextNeighbor returns T before U
Depth-first search
Can be done recursively or iteratively.
Recursive version:
Mark all nodes as unvisited
call dfsHelper with startVertex
dfsHelper: vertex
visit vertex
for each neighbour, getNextNeighbor of vertex as n
if n is not visited
call dfsHelper with n
Iterative version:
Mark all nodes as unvisited
push v onto stack
while stack is not empty
if there is a neighbor for the vertex on top of the stack that has not been
visited
push neighbor onto stack
visit neighbor
else
no unvisited neighbor
pop stack
Starting from O gives the following visiting order:
O P R S T U Q
Breadth-first search
Mark all nodes as unvisited
enqueue startVertex to queue
mark startVertex as visited
while queue is not empty
w = dequeue
for each unvisited neighbor u of w
visit u
enqueue u
Starting from O gives the following visiting order:
O P Q R S T U
Djikstra’s shortest path
create a priority queue, pq to keep total cost to vertex
for all neighbors u of startVertex
weight[u] = weight of edge from startVertex to u
previous[u] = startVertex // all neighbors have startVertex as previous
pq add (u, weight[u])
add startVertex to vertexSet
while pq is not empty
v = get vertex with lowest weight from pq
if v is not in vertexSet
for each neighbor u of v
v2ucost = get edge cost to go from v to u
if there is no weight[u]
// we could not get to u before
// this is the only path
weight[u] = weight[v] + v2ucost;
previous[u] = v; // new previous added
pq add (u, weight[u])
else
// we could get to to u before
// is going via v better?
if (weight[u] > weight[v] + v2ucost)
// yes
weight[u] = weight[v] + v2ucost;
previous[u] = v; // new previous added
pq add (u, weight[u])
else
// no, previous route was better
// do nothing
Starting from O
weight[P] = 5, weight[Q] = 2
vertexSet = {O}
processing pq { (Q, 2), (P, 5) }
v = Q
vertexSet is now {O, Q}
pq is now { (P, 5) }
looking at Q’s neighbors
u = R
weight[R] = 3
previous[R] = Q
pq add (R, 3)
processing pq { (R, 3), (P, 5) }
v = R
vertexSet is now {O, Q, R}
looking at R’s neighbors
u = O is visited, skip it
u = S
weight[S] = weight[R] + 3 = 6
previous[S] = R
pq add (S, 6)
processing pq { (P, 5), (S, 6)}
v = P
u = R is visited, skip it
u = S
vertexSet is now {O, Q, R, S}
looking at S’s neighbors
u = T
weight[T] = weight[S] + 2
previous[S] = T
pq add (T, 8)
// next neighbor
u = U
weight[U] = weight[S] + 3
previous[U] = T
pq add (U, 9)
processing pq { (T, 8), (U, 9) }
v = T
…
Submission
As always expected when programming, comment clearly and thoroughly. Clearly state any
assumptions you make in the beginning comment block of the appropriate place, e.g., the class
definition. Comments in the class definition file should describe the ADT, all functionality, and
assumptions so someone could use the class and understand behavior and restrictions. Pre and post
conditions are fine, but not required. See the example on Assignments page for a well-documented
program.
You do NOT need to handle data type errors due to bad input.
I will run my own main to test your code. The main function provided doesn’t test your program fully,
so you need to supplement it.
Write one function at a time. Test it before moving on to the next function. I suggest starting with add
Use valgrind to check for memory leaks as you develop the program. Much easier to fix things early
on.
Submit a single zip file, assignment3.zip with the following files:
Class names start with capital letters, but file names are all lowercase for compatibility
vertex.h, vertex.cpp, edge.h, edge.cpp, graph.h, graph.cpp
assignment3.cpp – your own testing functions and main
output.txt – the script file.
README.txt (or PDF) – your comments. Includes several bits of information about your
implementation, any assignments you made, and any compiler instructions.
Grading Rubric
Multiple criteria. -5 for partially correct, -10 for not working or missing
1. depth-first search
2. breadth-first search
3. djikstra’s shortest path
4. Vertex functions, especially getNextNeighbor
6. Graph destructor
7. Graph functions not mentioned above, especially ~Graph
8. efficiency and complexity
9. In-code comments
10. Coding style + assignment3.zip constructed properly – all lines less than 80
characters, some exceptions are OK…
Purchase answer to see full
attachment
