Many real-life problems can be modelled with graphs. For example, cities could be nodes in a graph and flights between them could be edges (with flight-duration or flight-price as potential edge weights); so, finding the shortest or cheapest flight between two cities will translate to finding the shortest path between two nodes in the graph.
In this lab we will see how a graph can be read from file and how traversal algorithms DFS and BFS can be used to retrieve paths between two nodes.
Sometimes we make a graph based on some logic (like when we built a game tree (that is a rooted directed graph) in assignment 3). But more often, we receive the structure of the graph in a file. Assuming that no node is completely isolated, a graph is identified by its edge set or by its adjacency matrix.
To get used to the notation, verify that the edge set and the adjacency matrix given below both describe the same graph.
edge set: 0 1 0 3 1 2 2 4 2 3 adjacency matrix: 0 1 0 1 0 1 0 1 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0
Looking at the function "readGreaph" in graphTraversal.cpp from lecture 26, we can see that the graph is read from a file that describes the graph in edge set format and is saved in an unordered_map<string,vector<string>> G. In other words, the graph is stored as an adjacency list where each node is mapped to a vector of its neighbors.
In this lab, we will get and store the graphs in the same manner.
In this lab, we will take the graphTraversal.cpp from Lecture 26 and change it so we can find some path from a vertex u to a vertex v in a simple connected graph.
As discussed in class, we can use DFS or BFS to find a path from a node u to a node v. The key idea is to start DFS or BFS from u and stop when we visit v while keeping track of what node leads us to what other node (a.k.a keeping track of parents). Then, to retrieve the path, we start from v and follow the parents until we get to u. You can download the folder for this lab from here.
graphFindPath.cpp is similar to graphTraversal.cpp except in graphFindPath.cpp there is an unoredered_map<string,string> called parent, a line in the DFS function that saves the parent for a node as soon as it's visited, and a function get_reverse_path that starts from v and keeps following the parents until it reaches u.
Verify that compiling and running the program will give you the path that DFS finds from u to v:
g++ --std=c++0x -o graphFindPath.o graphFindPath.cpp ./graphFindPath.o graph.txt a d Path found by DFS: a b d Path found by BFS:The program falls in an infinite loop when trying to get the path from BFS because BFS doesn't save parents yet (it's your job to change that). In order to stop the program you can use Ctrl+c.
Change function BFS so that it saves the parents for each vertex. If you do this correctly, you should get the following results when compiling and running graphFindPath.cpp:
g++ --std=c++0x -o graphFindPath.o graphFindPath.cpp ./graphFindPath.o graph.txt a d Path found by DFS: a b d Path found by BFS: a d All done!
At this stage, if you compile and run graphFindPath.cpp as follows, it will fall in an infinite loop.
./graphFindPath.o graph2.txt a h Path found by DFS:
You would need to stop the program using Ctrl+c again. This is because in graph2.txt, the nodes a and h are in two different connected components and there is no path between them.
Change function get_reverse_path in a way that it works even if there was no path between u and v (If they were in different connected components). If you complete this step correctly, the program will finish printing an empty line instead of getting stuck in an infinite loop:
g++ --std=c++0x -o graphFindPath.o graphFindPath.cpp ./graphFindPath.o graph2.txt a h Path found by DFS: Path found by BFS: All done!