---
# System prepended metadata

title: Week 12 - Graphs- ***IULIAN***

---

# Week 12 - Graphs- ***IULIAN***

## Team

Team name:
Date:

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.                                             |  Taimour    |
| **Spokesperson** communicates group’s questions and problems to the teacher and talks to other teams; presents the group’s findings.                                              |   Iulian   |
| **Reflector** observes and assesses the interactions and performance among team members. Provides positive feedback and intervenes with suggestions to improve groups’ processes. |    Hugo  |
| **Recorder** guides consensus building in the group by recording answers to questions. Collects important information and data.                                                   |   Arturo   |

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

data organisation
pathfinding
algorithms
computer networks
modeling of structures (ex. atoms)

### Activity 2: Visualizing graphs

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


### Activity 3: Finding a path

![](https://i.imgur.com/dP0qgH9.png)
The value of found is false because find_recursive is not implemented.
The amount of times passed through d is 3 times (according to the function)

### Activity 4: Positive reports

```c++
bool visitor::find_recursive(const std::string &start_vertex, const string &goal) {

    // append start_vertex to pre order
    pre_visit(start_vertex);

    // get vertex ref from name
    auto& vertex = m_graph[start_vertex];

    // go over the outgoing edges of the vertex
    for (auto& edge : vertex.edges()) {
        // continue traversal from the neighbour
        if (start_vertex == goal) return true;
        if (find_recursive(edge.target(), goal)) return true;

    }
    // append start_vertex to post order
    post_visit(start_vertex);

    return false;
}
```

### Activity 5: Getting lost

```c++
bool visitor::find_recursive(const std::string &start_vertex, const string &goal) {
    // new line for ativity 5
    if (is_visited(start_vertex)) return false;
    
    // append start_vertex to pre order
    pre_visit(start_vertex);

    // get vertex ref from name
    auto& vertex = m_graph[start_vertex];

    // go over the outgoing edges of the vertex
    for (auto& edge : vertex.edges()) {
        // continue traversal from the neighbour
        if (start_vertex == goal) return true;
        if (find_recursive(edge.target(), goal)) return true;

    }
    // append start_vertex to post order
    post_visit(start_vertex);

    return false;
}
```

### Activity 6: The limits of recursion

The smallest chain at which the prgram crashes is 21650.

### Activity 7: Iterative traversal

```c++
bool visitor::find_iterative(const string &start_vertex, const string &goal) {
    // FIXME Activity 7 - complete the implementation - done :)
    // FIXME Activity 8 - make visit order consistent with recursive version
    // FIXME Activity 11 - keep track of the path
    // FIXME Activity 12 & 12 - detect cycles
    (void) goal;
    plan_vertex_visit(start_vertex);
    while (visits_planned()) {
        auto v = peek_next_visit();
        pop_next_visit();
        if (!is_visited(v)) {
            pre_visit(v);
            if (v == goal) return true;
            auto &vertex = m_graph[v];
            for (int i = vertex.edges().size()-1; i  >= 0; i--) {
                auto& edge = vertex.edges().at(i);
                if (!is_visited(edge.target())) {
                    plan_vertex_visit(edge.target());
                }
            }
        }
    }
    return false;
}
```

### Activity 8: Depth-first search

```c++
bool visitor::find_iterative(const string &start_vertex, const string &goal) {
    // FIXME Activity 7 - complete the implementation - done :)
    // FIXME Activity 8 - make visit order consistent with recursive version - done :)
    // FIXME Activity 11 - keep track of the path
    // FIXME Activity 12 & 12 - detect cycles
    (void) goal;
    plan_vertex_visit(start_vertex);
    while (visits_planned()) {
        auto v = peek_next_visit();
        pop_next_visit();
        if (!is_visited(v)) {
            pre_visit(v);
            if (v == goal) return true;
            auto &vertex = m_graph[v];
            for (int i = vertex.edges().size()-1; i  >= 0; i--) {
                auto& edge = vertex.edges().at(i);
                if (!is_visited(edge.target())) {
                    plan_vertex_visit(edge.target());
                }
            }
        }
    }
    return false;
}
```

```c++
void label_pre_order(graph& g, const visitor& vis) {
    for (size_t i = 0; i < vis.pre_order().size(); i++) {
        g.label_vertex(vis.pre_order().at(i), i+1);
    }
}
```

### Activity 9: Breadth-first search

```c++
bool visitor::find_iterative(const string &start_vertex, const string &goal) {
    // FIXME Activity 7 - complete the implementation - done :)
    // FIXME Activity 8 - make visit order consistent with recursive version - done :)
    // FIXME Activity 11 - keep track of the path 
    // FIXME Activity 12 & 12 - detect cycles
    (void) goal;
    plan_vertex_visit(start_vertex);
    while (visits_planned()) {
        if (m_traversal_type == traversal_t::depth_first) {


            auto v = peek_next_visit();
            pop_next_visit();
            if (!is_visited(v)) {
                pre_visit(v);
                if (v == goal) return true;
                auto &vertex = m_graph[v];
                for (int i = vertex.edges().size() - 1; i >= 0; i--) {
                    auto &edge = vertex.edges().at(i);
                    if (!is_visited(edge.target())) {
                        plan_vertex_visit(edge.target());
                    }
                }
            }
            
            
            // HEREEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE
            // breadth first below in the else
            
            
        } else {
            auto v = peek_first_visit();
            pop_first_visit();
            if (!is_visited(v)) {
                pre_visit(v);
                if (v == goal) return true;
                auto &vertex = m_graph[v];
                for (int i = vertex.edges().size() - 1; i >= 0; i--) {
                    auto &edge = vertex.edges().at(i);
                    if (!is_visited(edge.target())) {
                        plan_vertex_visit(edge.target());
                    }
                }
            }
        }
    }
    return false;
}

const string &visitor::peek_first_visit() const {
    return m_planned_visits.front();
}

void visitor::pop_first_visit() {
    if (m_planned_visits.empty()) throw std::logic_error("pop_first_visit: there is no planned visit to cancel");
    m_planned_visits.pop_front();
}
```

### Activity 10: Keeping track of the path (post-visits)

post_visit is already implemented in a more efficient way in my find_iterative function and works correctly there, so i don't need to call the function.

### Activity 11: Detecting cycles

```c++
bool visitor::find_iterative(const string &start_vertex, const string &goal) {
    // FIXME Activity 7 - complete the implementation - done :)
    // FIXME Activity 8 - make visit order consistent with recursive version - done :)
    // FIXME Activity 11 - keep track of the path - done B)
    // FIXME Activity 12 & 12 - detect cycles
    (void) goal;
    plan_vertex_visit(start_vertex);
    while (visits_planned()) {
        if (m_traversal_type == traversal_t::depth_first) {
            auto v = peek_next_visit();
            pop_next_visit();
            if (!is_visited(v)) {
                pre_visit(v);
                if (v == goal) return true;
                auto &vertex = m_graph[v];
                for (int i = vertex.edges().size() - 1; i >= 0; i--) {
                    auto &edge = vertex.edges().at(i);
                    if (!is_visited(edge.target())) {
                        plan_vertex_visit(edge.target());
                    } 
                    
                    
                    // new code here
                    else {
                        cycle_detected(edge.target());
                    }
                }
            }
        } else {
            auto v = peek_first_visit();
            pop_first_visit();
            if (!is_visited(v)) {
                pre_visit(v);
                if (v == goal) return true;
                auto &vertex = m_graph[v];
                for (int i = vertex.edges().size() - 1; i >= 0; i--) {
                    auto &edge = vertex.edges().at(i);
                    if (!is_visited(edge.target())) {
                        plan_vertex_visit(edge.target());
                    }
                    
                    
                    // new code here
                    else {
                        cycle_detected(edge.target());
                    }
                }
            }
        }
    }
    return false;
}
```


### Activity 12: Colouring cycles

```c++
void visitor::cycle_detected(const string &vertex) {
    m_cycle_found = true;
    m_cycle.insert(vertex);
}
```
![](https://i.imgur.com/RJHCV8c.png)


## Looking back

### What we've learnt

We learned how to use graphs and how they function.

### What were the surprises

Graphs are really fun and easy to work with.

### What problems we've encountered

None, graphs are cool.

### What was or still is unclear

Graphs are a very clear concept and we feel we grasped the full idea of them.

### How did the group perform?

We speed run through this assignment together and co-operated in such a way that everyone understood what is going on.





