---
# System prepended metadata

title: Week 12 - Graphs

---

# 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");
```
![](https://i.imgur.com/NUACmca.png)

```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");
```
![](https://i.imgur.com/QANtelA.png)


### Activity 3: Finding a path

![](https://i.imgur.com/3Urm4S3.png)

- 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?