# Week 12 - Graphs
## Team
Team name: Academy Award Winning, Choccy Milk Drinking, Argonian Maid Reading, PP Entitled Chair-menning, Cross Dressing SIMPS In Yugoslavia With Honda Accords On The Quest For Feet
Date: 23/05/2022
yes(66%)
Members
Mihnea: Mihnea Bastea (514541)
Vlad: Vladislav Serafimov (509761)
Steve: Stephen Cruz Wright (521476)
| Role | Name |
| ------------------------------------------------------------------------------------------------------------------------------------- | ------ |
| **Facilitator** keeps track of time, assigns tasks and makes sure all the group members are heard and that decisions are agreed upon. | Vlad |
| **Spokesperson** communicates group’s questions and problems to the teacher and talks to other teams; presents the group’s findings. | Steve |
| **Recorder** guides consensus building in the group by recording answers to questions. Collects important information and data. | Mihnea |
## Activities
Make sure to have the activities signed off regularly to ensure progress is tracked.
Download the provided project and open it in CLion. **NOTE**: in this week you will have to reuse the code of last week. Follow the instructions given in the `main.cpp` file.
### Activity 1: Applications of graphs
1. **Social networks**
- What does the graph represent? - A network of different people who interact with each other
- What do the vertices and edges represent? - The verticies are representations of people and the edges can be who interacts with who (but it's largely arbitrary)
- Are the edges directed or undirected? Why? - No, because the interactions go both ways
2. **Neural networks**
- What does the graph represent? - A network that modells a simple brain
- What do the vertices and edges represent? - The verticies are different weights and the edges are their relations
- Are the edges directed or undirected? Why? - Yes, because the data has to go from starting point to the end
3. **Maps**
- What does the graph represent? - A network of roads
- What do the vertices and edges represent? - The verticies are different starting points and the edges are the roads
- Are the edges directed or undirected? Why? - No, because the the roads can be traversed both ways (for the most part)
4. **Electrical connections**
- What does the graph represent? - A network of wires
- What do the vertices and edges represent? - The verticies are whatever means of interaction with clients is used and the edges are the wires
- Are the edges directed or undirected? Why? - No, because the data can flow both ways
5. **Family trees**
- What does the graph represent? - A family and the relationships between its members
- What do the vertices and edges represent? - The verticies are the family members and the edges are their relationships
- Are the edges directed or undirected? Why? - Yes, because of the parent-child dynamic
### Activity 2: Visualizing graphs
```cpp=
///figure 1 code
graph g{false}; // create an undirected graph
g.add_edge("a", "c");
g.add_edge("b", "c");
g.add_edge("c", "d");
g.add_edge("d", "b");
g.add_edge("d", "e");
g.add_edge("c", "f");
g.add_edge("f", "g");
g.to_dot("simple.dot");
```
```cpp=
///figure 2 code
graph g{true}; // create an undirected graph
g.add_edge("a", "b");
g.add_edge("b", "d");
g.add_edge("d", "c");
g.add_edge("c", "a");
g.add_edge("d", "e");
g.add_edge("e", "f");
g.add_edge("f", "g");
g.add_edge("g", "e");
g.to_dot("simple.dot");
```
### Activity 3: Finding a path
- The function find_recursive always returns a false so the value of found is always false.
- Vertex "d" is visited 3 times.
### Activity 4: Positive reports
```c++=
bool visitor::find_recursive(const std::string &start_vertex, const string &goal) {
if(start_vertex==goal) {
pre_visit(goal);
return true;
}
pre_visit(start_vertex);
auto& vertex = m_graph[start_vertex];
for (auto& edge : vertex.edges()) {
find_recursive(edge.target(), goal);
const std::string & test = edge.target();
if (test==goal){
return true;
}
auto& visited = pre_order();
if (1 == std::count(visited.begin(), visited.end(), goal))
return true;
}
post_visit(start_vertex);
return false;
}
```
### Activity 5: Getting lost
```c++=
bool visitor::find_recursive(const std::string &start_vertex, const string &goal) {
if(start_vertex==goal) {
pre_visit(goal);
return true;
}
pre_visit(start_vertex);
auto& vertex = m_graph[start_vertex];
for (auto& edge : vertex.edges()) {
auto& visited = pre_order();
if (1 != std::count(visited.begin(), visited.end(), edge.target().name())){
cycle_found();
find_recursive(edge.target(), goal);
}
const std::string & test = edge.target();
if (test==goal){
return true;
}
if (1 == std::count(visited.begin(), visited.end(), goal))
return true;
}
post_visit(start_vertex);
return false;
}
```
### Activity 6: The limits of recursion
>Weirdly enough I got to 40 000 and clion was using 8gb of ram it could probably go higher but it would take ages to compute.
### Activity 7: Iterative traversal
```c++=
bool visitor::find_iterative(const string &start_vertex, const string &goal) {
(void) goal;
plan_vertex_visit(start_vertex);
string v;
while (visits_planned()) {
v = peek_next_visit();
pre_visit(v);
pop_next_visit();
}
auto check = pre_order();
for (auto i = 0u; i <m_graph.num_vertices()-1; ++i) {
if (m_graph.vertices().at(i).name()==goal)
return true;
if (std::count(check.begin(), check.end(), m_graph.vertices().at(i).name())!=1){
pre_visit(m_graph.vertices().at(i).name());
}
}
return false;
}
```
### Activity 8: Depth-first search
```c++
bool visitor::find_iterative(const string &start_vertex, const string &goal) {
}
```
```c++
void label_pre_order(graph& g, const visitor& vis){
for (auto i = 0u; i <vis.pre_order().size() ; ++i) {
g.label_vertex(vis.pre_order().at(i),i);
}
}
```
### Activity 9: Breadth-first search
```c++
```
### Activity 10: Keeping track of the path (post-visits)
Record your answer here
### Activity 11: Detecting cycles
```c++
void visitor::find_iterative(const string &start_vertex, const string &goal) {
}
```
### Activity 12: Colouring cycles
```c++
void visitor::cycle_detected(const std::string& vertex)() {
}
```
## Looking back
### What we've learnt
Formulate at least one lesson learned.
### 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
