In this Project, we have provided an API of a Graph class that you need to implement. This class will be used to
represent undirected graphs. In the starter code, we have provided 4 code files (Graph.h, Graph.cpp,
GraphTest.cpp, and Makefile) as well as 2 example graph files (small.csv and hiv.csv).
Graph.h
This file contains the basic declarations of the (undirected) Graph class that you need to implement. We have
declared a series of function signatures that you will need to implement. You are free to modify Graph.h however
you wish (e.g. adding instance variables to the Graph class, adding any helper functions you'd like, etc.). Our only
requirement is that the function signatures we have declared remain unchanged (though you are welcome to
overload them if you wish).
Please be sure to thoroughly read the header comments in Graph.h to be sure you understand the
functionality, input(s), and output(s) of each function in the Graph class.
Graph.cpp
This file contains the skeleton of implementing the functions we have declared in the (undirected) Graph class.
Your task is to fill in the function bodies. You are welcome to add any variables, functions, classes, etc. you wish.
GraphTest.cpp
This file contains a tester program to help you run and test your code. We will be using this program to grade your
code. You are welcome to modify GraphTest.cpp for testing purposes however you wish: we will simply ignore
any changes you have made to GraphTest.cpp when we grade your code. The GraphTest executable that is
created from GraphTest.cpp can be run as follows:
./GraphTest
Edge List
The argument is the filename of an edge list representing an undirected graph with non-negative
edge weights in the CSV format: each line represents an undirected edge between nodes u and v with weight w
in the following format: u,v,w
For example, imagine we want to represent the following graph:
We could represent it using the following edge list CSV (note that the order of the rows is arbitrary):
A,B,0.1
A,C,0.5
B,C,0.1
B,0,0.1
F,G,0.5/n In this Project, we have provided an API of a Graph class that you need to implement. This class will be used to
represent undirected graphs. In the starter code, we have provided 4 code files (Graph.h, Graph.cpp,
GraphTest.cpp, and Makefile) as well as 2 example graph files (small.csv and hiv.csv).
Graph.h
This file contains the basic declarations of the (undirected) Graph class that you need to implement. We have
declared a series of function signatures that you will need to implement. You are free to modify Graph.h however
you wish (e.g. adding instance variables to the Graph class, adding any helper functions you'd like, etc.). Our only
requirement is that the function signatures we have declared remain unchanged (though you are welcome to
overload them if you wish).
Please be sure to thoroughly read the header comments in Graph.h to be sure you understand the
functionality, input(s), and output(s) of each function in the Graph class.
Graph.cpp
This file contains the skeleton of implementing the functions we have declared in the (undirected) Graph class.
Your task is to fill in the function bodies. You are welcome to add any variables, functions, classes, etc. you wish.
GraphTest.cpp
This file contains a tester program to help you run and test your code. We will be using this program to grade your
code. You are welcome to modify GraphTest.cpp for testing purposes however you wish: we will simply ignore
any changes you have made to GraphTest.cpp when we grade your code. The GraphTest executable that is
created from GraphTest.cpp can be run as follows:
./GraphTest
Edge List
The argument is the filename of an edge list representing an undirected graph with non-negative
edge weights in the CSV format: each line represents an undirected edge between nodes u and ✓ with weight w
in the following format: u,v,w
For example, imagine we want to represent the following graph:
We could represent it using the following edge list CSV (note that the order of the rows is arbitrary):
A,B,0.1
A,C,0.5
B,C,0.1
B,D, 0.1
E,F,0.4
F,G,0.5 Here is an image of the same graph:
B
0.1
D
F
0.1
O
A
-0.1-
0.4
0.5
0.5
C
E
G Here are some things you can expect about the edge list CSVs you will be given:
• You are guaranteed that edge weights will be non-negative (i.e., they will be 20)
• You are guaranteed there will not be any self-edges (e.g. u,u,?)
• You are guaranteed that you will not be given a multigraph, meaning you are guaranteed that there will not
exist multiple edges between nodes u and v in the provided edge list
• Further, because the edges are undirected, if you see an edge from u to v (e.g. u,v,?), you are guaranteed
that you will not see an edge from v to u (e.g. v,u,?) later in the file
o Remember: an edge from u to v is bidirectional and is thus also an edge from v to u
• You are not guaranteed that the edges in the CSV will be sorted in any particular order
Test
The argument denotes which of the GraphTest tests you want to run. The tests are as follows:
graph_properties: Test building a Graph object and checking its basic properties
• shortest_unweighted: Test the Graph::shortest_path_unweighted function
shortest_weighted : Test the Graph::shortest_path_weighted function
• connected_components: Test the Graph::connected_components function
• smallest_threshold: Test the Graph::smallest_connecting_threshold function
Feel free to investigate the code within GraphTest.cpp to see how exactly it works.
Makefile
npile your code using the make command. If you choose to cre
This file will help you
any additional code
files, you are welcome to do so: our only requirement is that, given the original version of GraphTest.cpp, we
should be able to run your code using the make command, which should create an executable called GraphTest
that can be run as described above. Potential Development Process
Step 1: Reading the Header Comments
Before you do anything, please read all of the header comments in Graph.h thoroughly to make sure you
understand what exactly each function is supposed to do. You should consider the following questions as you
investigate each function declared Graph.h:
• What are the parameters of this function? What do they mean? How are they formatted?
• Given the parameters, what is this function supposed to actually do? What data structure(s) and algorithm(s)
would be relevant to achieve this functionality?
What is the output of this function? What does it mean? How is it formatted?
Step 2: Designing Your Graph
Before you write even a single line of code, completely map out how exactly you want to implement the graph
ADT. You should consider the following questions as you think about your unique design:
• What are the graph operations you will need to support?
• What data structure(s) will you use to represent nodes?
• What data structure(s) will you use to represent edges between nodes?
• Are there any helper variables, functions, classes, etc. that you will want to add?
• What are the time complexities of various standard graph operations if you use the data structure(s) you've
chosen? Can you modify your choices to speed things up?
I want you to literally write out every data structure you can use to represent the graph, along with each data
structure's worst-case Big-O time and space complexities, and map the functionality of these data structures to
the properties of a graph. This design step is by far the most important step, as proper design will make your Step 3: Writing the Constructor
The first nontrivial code you should write will likely be the Graph constructor. You will need to populate the Graph
using the edges contained within the given edge list CSV file. You should think about the following questions as
you implement your constructor:
• How should you initialize each of the instance variables you added to the Graph class?
• Do you want to add any helper functions (or perhaps an overloaded constructor) to help you initialize your
graph from the given CSV file?
Step 4: Implementing Basic Graph Operations
Once you are confident that your Graph constructor is correct, write the functions that access basic properties of
a graph: num_nodes (), nodes (), num_edges (), edge_weight(), num_neighbors (), and neighbors (). You
should think about the following questions as you implement these functions:
• How can you use the instance variables you've added to the Graph class to perform these operations? What
would be the worst-case time complexity of each operation?
• Are there any optimizations you can make by adding even more instance variables to the Graph class to
quickly look up certain values instead of computing them from scratch each time, but without blowing up in
memory consumption?
Once you have implemented all of these functions, you should be able to use the graph_properties test in
GraphTest. Once you have these basic properties working, the remaining functions can be implemented in any
order (they will likely be independent of one another), so feel free to deviate from our recommended order if you
prefer.
However, all of the following steps require your basic graph functionality to work completely correctly. Thus, do
not continue until you are able to get the basic graph functionality completely working!/n Read through the project instructions pdf file attached. The "Potentional Development Process"
must be followed when implementing the code. You need to implement all functions according to
requirement in project instructions. There is a test file called "GraphTest.cpp" provided to test the
code and the example file provided in the "example" folder. Also, very important, make sure there is
no memory leaks in the implementation.
the proj files explains how and what to implement. in the attached files, only Graph.cpp needs to be
edited, rest other code files are supporting files and file to test the implementation
and the files in the "example" folder is to be used for testing/n/n/n
