Project Workflow
As mentioned in the overview, as long as (1) you implement all of the functions we declared in Graph.h, (2) we can compile the original starter GraphTest.cpp via make, and (3) we can run GraphTest as described, you are absolutely free to implement the project any way you think is best. However, here are some suggestions just in case you feel a bit lost.
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 coding much easier and will make your code much faster. Be sure to refer to the "Summaries of Data Structures" section of the Data Structures Stepik text to help you brainstorm.
Once you have decided on a design for your graph implementation, you will want to add any instance variables your design will need to the Graph class.
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 first few tests in GraphTest, as well as the autograder. 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!
Step 5: Finding a Weighted Shortest Path
In the shortest_path_weighted() function, you will be finding the shortest weighted path from a given start node to a given end node. You will want to implement this using Dijkstra's Algorithm. Be sure to map out how exactly the algorithm will operate with the specific graph design you have chosen. You should think about the following questions as you implement this:
What data structure(s) will help you implement Dijkstra's Algorithm, and do they have built-in C++ implementations?
How will you use the properties of your graph design to facilitate Dijkstra's Algorithm?
What is the worst-case time complexity of your approach? Are there any optimizations you can make to speed things up?
Be sure to refer to the "Dijkstra's Algorithm" section of the Data Structures Stepik text for more information about Dijkstra's algorithm.
Step 6: Finding the Smallest Connecting Threshold
In HIV transmission clustering, a natural question is the following: Given two individuals u and v, what is the smallest threshold d such that, if we were to only include edges with weight less than or equal to d, there would exist a path connecting u and v?
In the smallest_connecting_threshold() function, you will be finding the smallest connecting threshold between a given pair of nodes u and v. We will have time constraints on this, so you will need to implement an optimal solution. As a hint, you will probably want to make use of a Disjoint Set to make your code as fast as possible. Be sure to refer to the "Disjoint Sets" section of the Data Structures Stepik text for more information about Disjoint Sets.
Design Notes
Before you write even a single line of code, it's important to properly design the various components of your Graph class. Here, we will discuss some aspects of the design that you should be sure to think about.
Parsing a CSV File
The edge list your Graph constructor needs to read will be a CSV file, such as the following CSV file with 3 columns:
Niema,Moshiri,100 Ryan,Micallef,95 Felix,Garcia,95
In C++, you can parse a CSV file as follows (note that first, second, and third are all string objects):
C++12345678910ifstreammy_file(filename);//openthefilestringline;//helpervartostorecurrentlinewhile(getline(my_file,line)){//readonelinefromthefileistringstreamss(line);//createistringstreamofcurrentlinestringfirst,second,third;//helpervarsgetline(ss,first,',');//storefirstcolumnin"first"getline(ss,second,',');//storesecondcolumnin"second"getline(ss,third,'\n');//storethirdcolumncolumnin"third"}my_file.close();//closefilewhendone
Using the C++ tuple Class
In order to represent the mathematical concept of a tuple, C++ provides a tuple class. Be sure to thoroughly read the C++ tuple documentation, but the following code example will hopefully show you how to use it:
RunC XXXXXXXXXX#includeiostream>//loadcout#includestring>//loadstringclass#includetuple>//loadtupleclassusingnamespacestd;intmain(){tuplestring,string,int>prof=make_tuple("Niema","Moshiri",1993);cout"FirstName:"get0>(prof)endl;cout"LastName:"get1>(prof)endl;cout"BirthYear:"get2>(prof)endl;}
You may or may not want to use tuple objects in your underlying Graph design, but you will likely want to use them as you implement the member functions of the Graph class (e.g. as you implement a graph traversal algorithm). Pro-tip: if you try to sort a vector that contains tuple objects using std::sort, the tuple objects will be sorted based on the first element.
Using the C++ pair Class
Much like the tuple class, C++ provides the pair class that can be used to represent a pair of objects. Be sure to thoroughly read the C++ pair documentation, but the following code example will hopefully show you how to use it:
RunC XXXXXXXXXX#includeiostream>//loadcout#includestring>//loadstringclass#includeutility>//loadpairclassusingnamespacestd;intmain(){pairstring,string>prof=make_pair("Niema","Moshiri");cout"FirstName:"prof.firstendl;cout"LastName:"prof.secondendl;}
Creating a C++ struct
When examining your data types, you may find yourself adding many properties to your tuple objects, or may want increased readability by creating custom types. C++ provides the ability to define a struct, which is essentially a simple class that can be used to bundle together elements. Be sure to thoroughly read the C++ struct documentation, but the following code example will hopefully show you how to use it:
RunC++1 XXXXXXXXXX#includeiostream>//loadcout#includestring>//loadstringclassusingnamespacestd;//definestructstructperson{stringfirst;stringlast;unsignedintyear;};intmain(){//createstructobjectonstackpersonprof={.first="Niema",
Using a Custom Comparison Class with priority_queue
When you implement Dijkstra's Algorithm, you will likely want to store tuple objects representing (total path weight, from, to) tuples to keep track of your graph traversal. In C++, you can create a priority_queue with a custom comparison class. You may want to create a custom comparison class to compare these tuples in a way that uses the priority_queue as a min-heap with respect to total path weight. Be sure to read the C++ priority_queue documentation thoroughly to see how to define a custom comparison class and use it with a priority_queue object.
Modifying the Makefile
As you design your Graph class, you may feel as though you want to create additional code files for any helper classes you may potentially create. Note that you don't have to: you can complete this project without creating any additional files. However, if you do choose to do so, you will find that you will want to modify the Makefile in order to properly compile your executable. Feel free to make any modifications you wish, and you may want to refer to this guide to help you.