# Week 12 - Graphs

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

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

LinkedIn
Connecties
Edges representeren connecties
Undirected

instagram
Edges -> volgers
Directed.

Facebook
Edges -> vrienden
Undirected

Vliegroutes op vliegveld
Edges -> routes om te vliegen
directed

Playstation network
Edges -> Vrienden
undirected

### Activity 2: Visualizing graphs

1 
2 

### Activity 3: Finding a path

Vraag 1:
False
vraag 2:
3x


### Activity 4: Positive reports

bool visitor::find_recursive(const string &start_vertex, const string &goal) {
}

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

    pre_visit(start_vertex);

    auto& vertex = m_graph[start_vertex];

    for (auto& edge : vertex.edges()) {
        if (m_visited.contains(goal)){
            return true;
        }
        
    find_recursive(edge.target(), goal);
    post_visit(start_vertex);
        
    return false;
}

### Activity 5: Getting lost

bool visitor::find_recursive(const string &start_vertex, const string &goal) {
}

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

    pre_visit(start_vertex);

    if (start_vertex == goal) 
    {
        return true;
    }

    auto &vertex = m_graph[start_vertex];

    for (auto &edge: vertex.edges()) {

        if (!is_visited(edge.target())) {
            if (find_recursive(edge.target(), goal)){
                return true;
            }
        }
    }
    post_visit(start_vertex);
    return false;
}

### Activity 6: The limits of recursion

83438

### Activity 7: Iterative traversal

bool visitor::find_iterative(const string &start_vertex, const string &goal) {
}

bool visitor::find_iterative(const string &start_vertex, const string &goal) {
    (void) goal;

    plan_vertex_visit(start_vertex);
    while (visits_planned()) {
        auto v = peek_next_visit();
        auto &vertex = m_graph[v];
        if(!is_visited(goal) ){
            pre_visit(v);
            if (v == goal)
                return true;
        }
        bool planned = false;
        for (auto &edge: vertex.edges()) {
            if (!is_visited(edge.target())) {
                plan_vertex_visit(edge.target());
                planned = true;
                break;
            } else if (num_visits(edge.target())== 1) cycle_detected(edge.target());
            
        }
        if(!planned) {
            post_visit(v);
            pop_next_visit();
        }
    }
    return false;
}

### Activity 8: Depth-first search

bool visitor::find_iterative(const string &start_vertex, const string &goal) {
}

void label_pre_order(graph& g, const visitor& vis) {

}

### Activity 9: Breadth-first search

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

Record your answer here

### Activity 11: Detecting cycles

void visitor::find_iterative(const string &start_vertex, const string &goal) {   
}

### Activity 12: Colouring cycles

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?