# Week 12 - [Graph] Traversals
## Team
Team name: **Group [497441]**
Date: 05/30/2021
Members: Max Thielen
| Role | Name |
| - | - |
| **Facilitator** keeps track of time, assigns tasks and makes sure all the group members are heard and that decisions are agreed upon. | Max Thielen |
| **Spokesperson** communicates group’s questions and problems to the teacher and talks to other teams; presents the group’s findings. | Max Thielen |
| **Reflector** observes and assesses the interactions and performance among team members. Provides positive feedback and intervenes with suggestions to improve groups’ processes. | Max Thielen |
| **Recorder** guides consensus building in the group by recording answers to questions. Collects important information and data. | Max Thielen |
## Activities
### Activity 1: Application of graphs
* Navigation Application
* The graph represents the area the map covers (i.e. town, city, country, world).
* The nodes represent intersection and the edges represent streets. Due to the structure of the graph, the traversal is able to find the fastest route from A to B.
* The edges are **undirected** since roads/edges can be traversed both ways.
* Search Engine
* The graph represents collection of webpages and their connections.
* The nodes represent web pages and the edges represent links.
* The edges are **directed** since links/edges go one way.
* Social Network
* The graph represents collection of users and their connections.
* The nodes represent users and the edges represent follows.
* The edges are **undirected** since follows/edges are considered bidirectional.
* Cryptocurrency (DAG)
* The graph represents users transaction history.
* The nodes represent a transaction and the edges connect the transaction adding valididty to them.
* The edges are **directed** since the edges point foward in time.
* Product Recommendation
* The graph represents connections between goods sold by a business.
* The nodes represent the goods and the edges represent related goods bought by other users.
* The edges are **undirected** since the relation between goods/edges goes both ways.
### Activity 2: Representing graphs
* Adjacency Matrix
An adjeceny matrix is a 2 dimensional array storing all verticies on one axis and the vertecies' connections on the other.
* Adjacency List
An adjeceny list is an array storing lists storing a 'route' through the graph. The array then contains all of the routes and therefor every vertex.
In this case the given code is built on a vertix storing every vertex while a map stores the vertecies' connections, making it an adjecency list.
### Activity 3: Graph construction
* **Undirected:**
```c=
graph undirected{false};
for(auto& v:{"a","b","c","d","e","f","g"}){
undirected.add_vertex(v);
}
undirected.add_edge("a","c");
undirected.add_edge("b","c");
undirected.add_edge("c","d");
undirected.add_edge("b","d");
undirected.add_edge("c","f");
undirected.add_edge("d","e");
undirected.add_edge("f","g");
```
* **Directed:**
```c=
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("e","f");
directed.add_edge("f","g");
directed.add_edge("g","e");
```
### Activity 4: A first traversal
```c=
graph left{true};
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("e","f");
left.add_edge("e","g");
left.add_edge("c","d");
left.add_edge("f","d");
left.add_edge("g","h");
left.add_edge("h","d");
graph right{true};
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("c","d");
right.add_edge("d","f");
right.add_edge("f","b");
right.add_edge("c","g");
right.add_edge("d","e");
```
There is really no need to use the debugger since by only reading the traversial function console output, it becomes apparent that in the **right graph** verticies **b,c,d,f** are visited over an over again with no end. Due to the recursive element to the function and the loop within the right graph the traversal function can not end due to a lacking proper exit statement.
For the left graph, it is quite interesting that vertex a is only visited once. The first path is found from a to d but then the second path starts at e and ends at d. The last path then starts g showing that the next path will always pick up at the earliest fork. All paths end at d therefor it is visited 3 times.
### Activity 5: Find all reachable vertices
```c=
void traverse_rec(const graph::vertex& v, lookup& visited) {
std::cout << "Visiting " << v.label() << std::endl;
visited.insert(v.label());
for (const auto& edge : v.edges()) {
if(visited.find(edge.target().label())==visited.end()) {
traverse_rec(edge.target(), visited);
}
}
}
```
```c=
digraph undirected {
rankdir = LR; node[shape=oval style=filled];
a[label="a", fillcolor="red"];
b[label="b", fillcolor="red"];
c[label="c", fillcolor="red"];
d[label="d", fillcolor="red"];
e[label="e", fillcolor="red"];
f[label="f", fillcolor="red"];
g[label="g", fillcolor="red"];
edge[dir = none];
a -> c;
b -> c;
b -> d;
c -> d;
c -> f;
d -> e;
f -> g;
}
```
```c=
digraph directed {
rankdir = LR; node[shape=oval style=filled];
a[label="a", fillcolor="red"];
b[label="b", fillcolor="red"];
c[label="c", fillcolor="red"];
d[label="d", fillcolor="red"];
e[label="e", fillcolor="red"];
f[label="f", fillcolor="red"];
g[label="g", fillcolor="red"];
edge[dir = forward];
a -> b;
b -> d;
c -> a;
d -> c;
d -> e;
e -> f;
f -> g;
g -> e;
}
```
**By the way,** I would like to say that giving us this code is pure evil. I know it should not have taken me as long as it did see this (especially cause it was correctly given in the assignment pdf) but that was the last place I though too look for a mistake. Good one.
```c=
for (auto& label : reachable)
directed.colour_vertex("a", colour::red);
directed.to_dot("reachable.dot");
```
### Activity 6: Recursion overhead
The recursive function caps at size: 16,136.
### Activity 7: Iterative traversal
```c=
void traverse_depth(const graph::vertex& start) {
std::deque<graph::vertex> queue = {start};
std::unordered_set<std::string> visited;
queue.push_back(start);
while(!queue.empty()){
auto v = queue.back();
queue.pop_back();
if(visited.find(v.label()) == visited.end()){
std::cout << "Visiting " << v.label() << std::endl;
visited.insert(v.label());
for(auto& edge : v.edges()){
queue.push_back(edge.target());
}
}
}
}
```
This method can take on graph sizes more than 10x the size the recusive method could so it is safe to say it works.
Line 13 and 15 were quite tricky! But how am I supposed to believe these are not on purpose?
### Activity 8: Breadth-first search
```c=
void traverse_breadth(const graph::vertex& start) {
std::deque<graph::vertex> queue = {start};
std::unordered_set<std::string> visited;
queue.push_back(start);
while(!queue.empty()){
auto& v = queue.back();
if(visited.find(v.label()) == visited.end()){
std::cout << "Visiting " << v.label() << std::endl;
visited.insert(v.label());
for(auto& edge : v.edges()){
queue.push_front(edge.target());
}
}
queue.pop_back();
}
}
```
The depth first method used in activity 7 follows one path through the graph to the end until traversing the next, while the breadth first method in activity 8 uses a 'sweeping motion' across the graph visiting each node at each level.
### Activity 9: Comparison
```c=
bool find_goal_d(const graph::vertex& start, const std::string& goal) {
std::deque<graph::vertex> queue = {start};
std::unordered_set<std::string> visited;
queue.push_back(start);
while(!queue.empty()){
auto v = queue.back();
queue.pop_back();
if(v.label()==goal){
std::cout << "Found " << v.label() << std::endl;
return true;
}
else if(visited.find(v.label()) == visited.end()){
std::cout << "Visiting " << v.label() << std::endl;
visited.insert(v.label());
for(auto& edge : v.edges()){
queue.push_back(edge.target());
}
}
}
return false;
}
bool find_goal_b(const graph::vertex& start, const std::string& goal) {
// 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();
if(v.label()==goal){
std::cout << "Found " << v.label() << std::endl;
return true;
}
else if(visited.find(v.label()) == visited.end()){
std::cout << "Visiting " << v.label() << std::endl;
visited.insert(v.label());
for(auto& edge : v.edges()){
queue.push_front(edge.target());
}
}
queue.pop_back();
}
return false;
}
```
<!-- 
 -->
When looking for vertex g in the right graph depth first will find the goal quicker than breadth first. However, when looking for vertex d breadth first will beat depth first by one move.
The same can be observed in the left graph. When searching for vertex h depth first wins but when searching for vertex c breadth first wins by a big margin.
Depending on the edges and location of the vertex either method can be faster.
### Activity 10: Cycles and visited nodes
With the code displayed above, the cycle is found an figgure a, but it also falsely detects a cycle in figgure b. This is because the code relies on traversing over already visited vertecies in order to discover a cycle, the problem is that in figgure b vertex d is traversed over twice since two vertecies point towards it.
### Activity 11: Understanding the recursion
Since this recurive traversal function uses the depth first method, the graph is traversed till vertex e where there are no more edges connecteding to a new vertex. Then the function backtracks to node d to search for any missed edges. Upon finding vertex f the function can back track all the way to a enusuring all of the vertecies are accounted for.
### Activity 12: Understanding the iteration
```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());
}
}
}
```
The only difference in traversal from the recusive function is that in this case vertex f is visited before vertex e. The stems from the way the queue is set up, when adding new vertecies connected to the current vertex they are added to the back of the queue (holding all univisted vertecies). Then, when pulling the next current vertex it gets pulled from the back of the vertex so the last vertex added in the previous step comes first.
### Activity 13: Cycle detection
```c=
std::unordered_set<std::string> traverse(const graph::vertex& start) {
std::unordered_set<std::string> visited;
std::unordered_set<std::string> cycle;
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());
else {
cycle.insert(v.label());
auto temp_v = edge.target();
while(temp_v.label()!=v.label()){
cycle.insert(temp_v.label());
temp_v = temp_v.edges().back().target();
}
}
}
}
return cycle;
}
```
## Look back
### What we've learnt
Graph traversal(depth first vs. breadth first and recursive vs iterative) as well as cycle detection.
### What were the surprises
Recursion is not pratical in large graphs
### What problems we've encountered
Bugs
### What was or still is unclear
N/A
### How did the group perform?
Well
Sign in with Wallet
Connect another wallet