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

## 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
examples of how graphs might be used
- social networks
- contact tracing for infectious diseases
- relationships between entities

Graph representations:
- Adjacency Matrix(Let the 2D array be adj[][], a slot adj[i][j] = 1 indicates that there is an undirected edge from vertex i to vertex j.)
- Incidence Matrix(matrix of size= Total number of vertices by total number of edges.This matrix is filled with either 0 or 1 or -1. Where, 0 is used to represent row edge which is not connected to column vertex. 1 is used to represent row edge which is connected as outgoing edge to column vertex.-1 is used to represent row edge which is connected as incoming edge to column vertex.)
- Adjacency List(An array of lists is used. The size of the array is equal to the number of vertices. Let the array be an array[]. An entry array[i] represents the list of vertices adjacent to the ith vertex.)

### Activity 2: Visualizing graphs
graph1
graph2

### Activity 3: Finding a path

What is the value of the variable found in the program? 0
How many times is vertex d visited by the function find_recursive? 6

### Activity 4: Positive reports

bool visitor::find_recursive(const string &start_vertex, const string &goal) {
    if(start_vertex==goal)
        return true;
    pre_visit(start_vertex);
    auto& vertex = m_graph[start_vertex];
    for (auto& edge : vertex.edges()) {
        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) {
    if(start_vertex==goal)
        return true;
    pre_visit(start_vertex);
    auto& vertex = m_graph[start_vertex];
    for (auto& edge : vertex.edges()) {
        if (!is_visited(edge.target()))
            find_recursive(edge.target(), goal);
    }
    post_visit(start_vertex);
    return false;
}

### Activity 6: The limits of recursion

87350
### Activity 7: Iterative traversal

bool visitor::find_iterative(const string &start_vertex, const string &goal) {
    (void) goal;
    plan_vertex_visit(start_vertex);
    while (visits_planned()) {
        auto peak = peek_next_visit();
        if(peek_next_visit()==goal) return true;
        pre_visit(peak);
        pop_next_visit();
}

### Activity 8: Depth-first search

bool visitor::find_iterative(const string &start_vertex, const string &goal) {
    (void) goal;
    plan_vertex_visit(start_vertex);
    while (visits_planned()) {
        auto peak = peek_next_visit();
        pop_next_visit();
        if (!is_visited(peak)) {
            pre_visit(peak);
            if (peak == goal) return true;
            auto &vertex = m_graph[peak];
            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;
}

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

### Activity 9: Breadth-first search

bool visitor::find_iterative(const string &start_vertex, const string &goal) {
    (void) goal;
    plan_vertex_visit(start_vertex);
    while (visits_planned()) {
        if (m_traversal_type == traversal_t::depth_first) {
            auto peak = peek_next_visit();
            pop_next_visit();
            if (!is_visited(peak)) {
                pre_visit(peak);
                if (peak == goal) return true;
                auto &vertex = m_graph[peak];
                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());
                    }
                }
            }
        } else {
            auto peak = peek_first_visit();
            pop_first_visit();
            if (!is_visited(peak)) {
                pre_visit(peak);
                if (peak == goal) return true;
                auto &vertex = m_graph[peak];
                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)

Record your answer here

### Activity 11: Detecting cycles

void visitor::find_iterative(const string &start_vertex, const string &goal) {  
 (void) goal;
    plan_vertex_visit(start_vertex);
    while (visits_planned()) {
        if (m_traversal_type == traversal_t::depth_first) {
            auto peak = peek_next_visit();
            pop_next_visit();
            if (!is_visited(peak)) {
                pre_visit(peak);
                if (peak == goal) return true;
                auto &vertex = m_graph[peak];
                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());
                    } 
                    else {
                        cycle_detected(edge.target());
                    }
                }
            }
        } else {
            auto peak = peek_first_visit();
            pop_first_visit();
            if (!is_visited(peak)) {
                pre_visit(peak);
                if (peak == goal) return true;
                auto &vertex = m_graph[peak];
                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());
                    }
                    else {
                        cycle_detected(edge.target());
                    }
                }
            }
        }
    }
    return false;
}

### Activity 12: Colouring cycles

void visitor::cycle_detected(const std::string& vertex)() { 
    m_cycle_found = true;
    m_cycle.insert(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?