[SOLVED] Csci 2270 – data structures assignment 9

OverviewIn this assignment, you will implement an ADT graph and run Breadth-First Search and Depth-First Search algorithms. Graphs are versatile data structures that model relationships between things, so a generic graph data structure has nodes connected by edges. Adjacency matrices and adjacency lists are common ways to implement a graph. This week’s video lectures cover various ways to implement graphs, design decisions regarding storing metadata, and common graph algorithms.## Objectives* Implement an adjacency list ADT graph* Utilize coupled metadata* Implement key graph algorithms including BFS and DFS## Where to StartAfter having accepted your assignment in GitHub Classroom, _clone_ your private repository to your development environment.  We recommend that you use JupyterHub as your coding environment.You will need to run “`cmake“` from within the _build_ directory to create the rules for making the applications.  Next, run “`make“` to use those rules to actually build the executable from the source code.There will be a local executable created that will localay run the same tests that will be used to grade your assignment.Modify the given source code to provide the features described both in the document below and within the code.# GraphIn this assignment you will implement Graph, Edge, and Node classes.Project has following folder tree“`.├── CMakeLists.txt├── CMakeLists.txt.in├── README.md├── app│   └── main.cpp├── build├── code│   ├── Edge.cpp│   ├── Edge.h│   ├── Node.cpp│   ├── Node.h│   ├── Graphs.cpp│   └── Graphs.h└── tests    └── test_Graphs.cpp“`| File | Description ||—|—|| CMakeLists.txt      | Ignore this file – rules to build the Makefile for this project (used by cmake)|| CMakeLists.txt.in   | Ignore this file – more rules to build the Makefile for this project (used by cmake) || __README.md__           | __Readme file you are viewing here__ || app                | Application folder__main.cpp__            | __Application main file for your personal tests. you can use this executable to debug your own classes.__  || build              | Build folder to build the project. your executables are gonna be here eventually.  || code               | all your code should be in this folder.| __Node.cpp__  | __Node class source file__  || __Node.h__    | __Node class header file__  || __Edge.cpp__  | __Edge class source file__  || __Edge.h__    | __Edge class header file__  || __Graphs.cpp__  | __Graph class source file__  || __Graphs.h__    | __Graph class header file__  || tests              | Tests folder  || __test_Graphs.cpp__ | __Tests implemented for you / your personal tests__  |You will make changes to the Graphs.cpp, Node.cpp, and Edge.cpp files. Any other changes in other folders will be ignored in grading process but feel free to change them if you want to test/debug something.## About This homeworkCheck Graphs.h, Edge.h, and Node.h file comments for detailed information for each function.In this assignment, you’ll implement a graph data structure, BFS, and DFS.Here’s a summary of the **Edge class**:* **void setType(int edge_type)** – set the edge type to the given value (see edge type #define statements)- this should only be one line long.Here’s a summary of the **Graph class**:* **void clear()** – resets nodes to WHITE, discovery, finish times, and rank to -1, edges to UNDISCOVERED_EDGE, graph clock to 0.* **void dfs(shared_ptr<node> start)** – runs a depth-first search from indicated start node, exploring all reachable nodes.* **void bfs(shared_ptr<node> start)** – runs a breadth-first search starting from given node, exploring all reachable nodes.* **void bfs(shared_ptr<node> start, shared_ptr<node> finish)** – runs a breadth-first search like other version of BFS; this version stops when the target node is reached.Here’s a summary of the **Node class**:* **void clear()** – sets private variables to a default state.* **void setColor(int search_color, int time)** – sets the ‘color’ of a node according to its discovery state; be sure to set the appropriate time variable based on the new color. White is not(yet) discovered. Grey is discovered but not(yet) finished. Black is finished.* **void getDiscoveryInformation(int& thecolor, int& disco_time, int& finish_time, int& bfs_rank)** – uses four pass-by-reference variables for you to set to appropriate values. Technically returns void but used to access four state variables at one time.* **bool isAncestor(shared_ptr<node> other)** – gives information about the spanning tree formed during a DFS; an ancestor is a predecessor or any of our predecessor’s predecessors.* **void setPredecessor(shared_ptr<node> other)** – gives informaation about the spanning tree formed during a DFS; the predecessor is the node we were on when our node was discovered.## Useful TipsThis assignment is very detail-oriented, so refer to the lecture videos and slides as needed.### Go in orderIt is recommended that you implement the functions in the same order thatthey appear in the test file.### PseudocodeThis is the pseudocode to get you going. You’ll need to augment it(e.g. by setting ancestors, incrementing the clock, classifying edges,and so on).“`bfs(start):  clear graph  mark start gray  Q = empty queue  add start to Q  while Q has stuff in it:    v = popped element from Q    mark v black    visit v    for each unmarked neighbor w        mark w gray        add w to Q“`“`# clear graph before initial calldfs(node):  mark node gray  visit node  E = edges related to node  for all edges e in E:    a = end of e that isn’t node    if a is white:      dfs(a)  mark node black“`### Two versions of bfsThere are two signatures for bfs. If you implement the two-arg version fully, then you can have the one-arg version simply call the two-arg version with a target that doesn’t exist in the graph.Remember: laziness is one of the three virtues of a great programmer.### Use a queue, maybeThe header file includes vectors to store nodes and edges during asearch. You can use these if you like, or ignore them and usesomething else instead.One possible implementation: an iterative BFS using a queue (so,`#include <queue>` atop implementation file), and a recursive DFSusing the `getAdjacentEdges` set.### The auto keywordThe `auto` keyword can make life easier when iterating through acollection. It leverages the compiler to ‘figure out’ what type would beassigned for you (this only works for assignment, you cannot use `auto` forexample in function parameters). Also note that it is NOT like Python’s dynamictypes, the type must still be known at compile time.You can use `auto` to cleanly iterate over C++ collections:“`cppfor (auto n : nodes) {  // N right here will be a single node, one at a time.}“`A more correct way to handle iteration (which forces const and that the value isiterated by reference resulting in zero-copy):“`cppfor (const auto& n : nodes) {  // N right here will be a single node, one at a time.}“`### Use `make_dot`Check out the `tick` and `make_dot` functions provided for youin the implementation file. If you call `tick` after each interestingevent (start, end, and every time you increment the clock) you can usethis to watch the progress of your dfs or bfs.### Make helper functionsYou’ll likely want to create and use helper functions. The details areup to you. For example, I made an `otherEnd` function that returned thestart/end of an edge that wasn’t the node I was looking at.Helpers aren’t strictly necessary but they will make your life easierand reduce the volume of code where bugs can lurk.# Completing the Assignment1. After running the application, determine what is being tested for this assignment See the test cases in the code.2. Make a modification to the code to __Pass__ the test.   * Each time you make changes to the code, be sure to save your edits to the code   * “`make“` the application with the newly saved code   * Test the resulting application3. We suggest that you save your save the version of your code each time you get a test to pass. Make sure to save it both locally and on the GitHub server.4. Once you have solved one of the tests, _push_ your code to the server and access the Moodle page for the assignment.  Place your repository path into the field and sumbit to the Inginious auto-grader.