# Week 12 - Graph traversals
## Team
Team name: Group N/A
Date: 30-05-2021
Members
| Role | Name |
|-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|------|
| **Facilitator** keeps track of time, assigns tasks and makes sure all the group members are heard and that decisions are agreed upon. |Hlib |
| **Spokesperson** communicates group’s questions and problems to the teacher and talks to other teams; presents the group’s findings. |Cas |
| **Reflector** observes and assesses the interactions and performance among team members. Provides positive feedback and intervenes with suggestions to improve groups’ processes. |Jenny |
| **Recorder** guides consensus building in the group by recording answers to questions. Collects important information and data. |Yordan |
## Activities
### Activity 1: Application of graphs
**Graph representation 1: Social graphs (Facebook)**
**• What does the graph represent?**
Social graphs draw edges between you and the people, places and things you interact with online.
**• What do the vertices and edges represent?**
On The Graph API, everything is a vertice or node. This are entities such as Users, Pages, Places, Groups, Comments, Photos, Photo Albums, Stories, Videos, Notes, Events and so forth. Anything that has properties that store data is a vertice.
**• Are the edges directed or undirected? Why?**
The edges are undirected because every person can come in contact with any other person.
**Graph representation 2: Google's Knowledge Graph**
**• What does the graph represent?**
The knowledge Graph represents associated links that are shown to you when you look up a word or sentence.
**• What do the vertices and edges represent?**
The the graph, webpages are the nodes. The edges are the links shown by the algorithm when looking up a word or sentece.
**• Are the edges directed or undirected? Why?**
Google uses the PageRank algorithm, which models webpages and links in them as a directed graph.
**Graph representation 3: Flight Networks**
**• What does the graph represent?**
In flight network, graph data strutures are used to compute shortest paths and fuel usage in route planning, often in a multi-modal context.
**• What do the vertices and edges represent?**
The vertices in flight networks are places of departure and destination, airports, aircrafts, cargo weights.
The flight trajectories between airports are the edges. Turns out it's very feasible to fit graph data structures in route optimizations because of precompiled full distance tables between all airports.
**• Are the edges directed or undirected? Why?**
The edges undirected so that every airport can communicate with every plane in order to create a map to see the GPS locations of the planes in order to avoid collisions and calculate fuel usage.
**Graph representation 4:**
**• What does the graph represent?**
**• What do the vertices and edges represent?**
**• Are the edges directed or undirected? Why?**
**Graph representation 5:**
**• What does the graph represent?**
**• What do the vertices and edges represent?**
**• Are the edges directed or undirected? Why?**
### Activity 2: Representing graphs
**Adjacency List:** An Adjacency list is an array consisting of the address of all the linked lists. The first node of the linked list represents the vertex and the remaining lists connected to this node represents the vertices to which this node is connected. This representation can also be used to represent a weighted graph. The linked list can slightly be changed to even store the weight of the edge.
**Adjacency Matrix:** Adjacency Matrix is a 2D array of size V x V where V is the number of vertices in a graph. Let the 2D array be adj[][], a slot adj[i][j] = 1 indicates that there is an edge from vertex i to vertex j. Adjacency matrix for undirected graph is always symmetric. Adjacency Matrix is also used to represent weighted graphs. If adj[i][j] = w, then there is an edge from vertex i to vertex j with weight w.
**Describe how the graph class stores its vertices and edges - does it use the concept of an adjacency list, or of an adjacency matrix?**
*Answer: It uses the concept of a adjency list because it stores it's vertices and edges by finding the label of the adjacent vertex. When using a matrix, you would have to copy the whole matrix first, which doesn't happen.*
### Activity 3: Graph construction
```c=
if (run_activity_3) {
// activity 3
// build an undirected graph that matches the graph of Figure 1
graph g{false};
// TODO: add edges
for (auto& v : {"a", "b", "c", "d", "e", "f", "g"})
g.add_vertex(v);
g.add_edge("a", "c");
g.add_edge("b", "c");
g.add_edge("b", "d");
g.add_edge("c", "d");
g.add_edge("c", "f");
g.add_edge("d", "e");
g.add_edge("f", "g");
// ....
g.to_dot("act3-undirected.dot");
// build a directed graph that matches the graph of Figure 2
graph directed{true};
for (auto& v : {"a", "b", "c", "d", "e", "f", "g"})
directed.add_vertex(v);
directed.add_edge("a", "b");
directed.add_edge("c", "a");
directed.add_edge("b", "d");
directed.add_edge("d", "c");
directed.add_edge("d", "e");
directed.add_edge("g", "e");
directed.add_edge("e", "f");
directed.add_edge("f", "g");
directed.to_dot("act3-directed.dot");
}
```
Undirected
Directed
### Activity 4: A first traversal
```c=
if (run_activity_4) {
// implement the function "traverse_rec" as given in the PDF
// create the two graphs
graph left{true};
graph right{true};
// TODO: add edges to left and right
for (auto& v : {"a", "b", "c", "d", "e", "f", "g", "h"})
left.add_vertex(v);
left.add_edge("a", "b");
left.add_edge("a", "e");
left.add_edge("b", "c");
left.add_edge("c", "d");
left.add_edge("e", "f");
left.add_edge("e", "g");
left.add_edge("f", "d");
left.add_edge("g", "h");
left.add_edge("h", "d");
for (auto& v : {"a", "b", "c", "d", "e", "f", "g"})
right.add_vertex(v);
right.add_edge("a", "b");
right.add_edge("b", "c");
right.add_edge("f", "b");
right.add_edge("c", "g");
right.add_edge("c", "d");
right.add_edge("d", "e");
right.add_edge("d", "f");
left.to_dot("act4-left.dot");
right.to_dot("act4-right.dot");
// TODO: uncomment functions and see what happens
traverse_rec(left.find_vertex("a"));
traverse_rec(right.find_vertex("a"));
}
```
**• Explain why your program results in an error.**
*Explanation: In the right graph there is no end/termination point.*
**• how would you describe the order in which vertices are visited?**
*Asnwer: Perfect*
**• How many times is vertex d visited?**
*Answer: 3 times*
### Activity 5: Find all reachable vertices
Main Function Code
```c=
if (run_activity_5) {
auto directed = activity_4_left();
// run the function and colour reachable nodes
lookup reachable;
traverse_rec(directed.find_vertex("a"), reachable);
traverse_rec(directed.find_vertex("b"), reachable);
traverse_rec(directed.find_vertex("c"), reachable);
for (auto& label : reachable){
directed.colour_vertex(label, colour::red);
}
directed.to_dot("reachable.dot");
}
```
Function Code:
```c=
void traverse_rec(const graph::vertex& v, lookup& visited) {
// you need this function in activities 5 and 11
visited.insert(v.label());
for (const auto& edge : v.edges()){
if (visited.find(edge.target().label()) == visited.end()) {
traverse_rec(edge.target(), visited);
}
}
}
```
Initial Graph Photo:
All The Reachable Vertexes From Dot A:
All The Reachable Vertexes From Dot B:
All The Reachable Vertexes From Dot C:
### Activity 6: Recursion overhead
The maximum size is 18518
### Activity 7: Iterative traversal
Code:
```c=
void traverse(const graph::vertex& start) {
// you need this function in activities 7, 8, 11, and 12
std::deque<graph::vertex> queue = { start };
std::unordered_set<std::string> visited;
queue.push_back(start);
while (!queue.empty()) {
auto v = queue.back(); // v is the next vertex to viist
queue.pop_back(); // remove v from queue
if (visited.find(v.label()) == visited.end()) {
// was v visited before?
std::cout << "Visited " << v.label() << std::endl;
visited.insert(v.label()); // no, mark v as visited
// add all vertices adjacent to v to the queue
for (auto& edge : v.edges()){
queue.push_back(edge.target());
}
}
}
}
```
#### Does the iterative version successfully process the graphs?
Yes
### Activity 8: Breadth-first search
Code:
```c=
void traverse(const graph::vertex& start) {
// you need this function in activities 7, 8, 11, and 12
std::deque<graph::vertex> queue = { start };
std::unordered_set<std::string> visited;
queue.push_back(start);
while (!queue.empty()) {
auto v = queue.back(); // v is the next vertex to viist
queue.pop_back(); // remove v from queue
if (visited.find(v.label()) == visited.end()) {
// was v visited before?
std::cout << "Visited " << v.label() << std::endl;
visited.insert(v.label()); // no, mark v as visited
// add all vertices adjacent to v to the queue
for (auto& edge : v.edges()){
queue.push_front(edge.target());
}
}
}
}
```
#### Describe the impact this relatively small change has on the order in which the vertices are visited by the function:
The program visits the vertexes that are closer to the previous one.
### Activity 9: Comparison
Code:
```c=
bool find_goal(const graph::vertex& start, const std::string& goal) {
// you need this function in activity 9
std::deque<graph::vertex> queue = { start };
std::unordered_set<std::string> visited;
queue.push_back(start);
while (!queue.empty()) {
auto v = queue.back(); // v is the next vertex to viist
queue.pop_back(); // remove v from queue
if (visited.find(v.label()) == visited.end()) {
// was v visited before?
std::cout << "Visited " << v.label() << std::endl;
visited.insert(v.label()); // no, mark v as visited
if (v.label() == goal){
return true;
}
// add all vertices adjacent to v to the queue
for (auto& edge : v.edges()){
queue.push_front(edge.target());
}
}
}
return false;
}
```
### Activity 10: Cycles and visited nodes
Code:
```c=
bool find_cycle(const graph::vertex& start) {
// you'll need this function in activity 10
std::unordered_set<std::string> visited{};
std::deque<graph::vertex> queue = { start };
while (!queue.empty()) {
auto v = queue.back(); // v is next vertex to visit
queue.pop_back(); // remove v from queue
// check if v was visited before
if (visited.find(v.label()) == visited.end()) {
visited.insert(v.label()); // not visited before, mark v as visited
// add all vertices adjacent to v to the queue
for (auto &edge : v.edges()){
queue.push_back(edge.target());
}
} else {
return true; // indicate that a cycle was found
}
}
return false;
}
```
#### Explanation:
if the program sees the same vertex 2 times it doesn't mean that the graph contains the cycle, because the graph is directed.
### Activity 11: Understanding the recursion
CODE:
```c=
void traverse_rec(const graph::vertex& v, lookup& visited) {
// label vertex v
visited.insert(v.label());
std::cout << "Visiting " << v.label() << std::endl;
for (const auto &edge: v.edges()) {
const auto& target = edge.target();
if (visited.find(target.label()) == visited.end()) {
traverse_rec(target, visited);
}
}
std::cout << "Backtracking from " << v.label() << std::endl;
}
```
### Activity 12: Understanding the iteration
CODE:
```c=
void traverse(const graph::vertex& start) {
std::unordered_set<std::string> visited;
std::deque<graph::vertex> queue = { start };
while (!queue.empty()) {
auto& v = queue.back(); // v is next vertex to visit
if (visited.find(v.label()) == visited.end()) {
// was v visited before?
std::cout << "Visiting " << v.label() << std::endl;
visited.insert(v.label()); // no, mark v as visited
} else if (v.edges().empty()){
std::cout << "Backtracking from " << v.label() << std::endl;
queue.pop_back(); // remove v from queue
} else {
// get next adjacent vertex, visit it if not already visited
auto edge = v.edges().back();
v.edges().pop_back();
if (visited.find(edge.target().label()) == visited.end()){
queue.push_back(edge.target());
}
}
}
}
```
#### Order explanation
if there are 2 or more edges, then the program will go reversed order. For example, there are edges to b and c going out from the vertex a. In this case, the program firstly go to vertex c and then to vertex b.
##### It is the only difference between recursion and iteration methods
#### What information does the content of the queue contain?
The queue contains all the vertexes that we didn't come back from
### Activity 13: Cycle detection
Function Code:
```c=
std::deque<graph::vertex> traverse(const graph::vertex& start) {
std::unordered_set<std::string> visited;
std::deque<graph::vertex> queue = { start };
while (!queue.empty()) {
auto& v = queue.back(); // v is next vertex to visit
if (visited.find(v.label()) == visited.end()) {
// was v visited before?
std::cout << "Visiting " << v.label() << std::endl;
visited.insert(v.label()); // no, mark v as visited
} else if (v.edges().empty()){
std::cout << "Backtracking from " << v.label() << std::endl;
queue.pop_back(); // remove v from queue
} else {
// get next adjacent vertex, visit it if not already visited
auto edge = v.edges().back();
v.edges().pop_back();
for (auto i = 0; i < queue.size() - 1; i++){
if (queue[i].label() == edge.target().label()){
for (i; i > 0; i--){
queue.pop_front();
}
return queue;
}
}
if (visited.find(edge.target().label()) == visited.end()){
queue.push_back(edge.target());
}
}
}
return queue;
}
```
Main Function Code:
```c=
if (run_activity_13) {
graph g = figure_3a();
for (auto& v : traverse(g["a"]))
g.colour_vertex(v.label(), colour::azure);
g.to_dot("finding_cycle.dot");
}
```
Graph Photo:
## Look back
### What we've learnt
Fill in...
### What were the surprises
Fill in...
### What problems we've encountered
Fill in...
### What was or still is unclear
Fill in...
### How did the group perform?
How was the collaboration? What were the reasons for hick-ups? What worked well? What can be improved next time?
Google Drive
Gist
Clipboard
Sign in with Wallet
