# Week 12 - Graphs

## Team

Team name:Error
Date:6/6/2022

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

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

Undirected graphs:

Ex1: A map of streets in a neighborhood. This graph different streets in the area and those streets is connected to each other. The name of the street is the vertices and the edge shows the correlation between those streets. The edge is undirected because no direction must be indicated in this case and each edge can be traversed in both directions

Ex2: The graph of a social network like Facebook. The vertices represent people and the edges illustrate the relationship between people. Those relationship have both ways. So the edge is undirected.

Directed graph

Ex3: Workflow of a coffee shop. Each stage is the vertices and link between each stage is the edge of the graph. Customer can start ordering coffee. Then wait for the barista to make their drink. Finally, they can pickup their order. The edge between each step has direction so it’s a directed edge

Ex4: A map to show a postman’s route in a neighborhood. This graph represent the route that a postman need to follow to deliver his stuffs. The name is each street is the vertices and the edge shows the direction to travel through each street. The edge is directed because it must show the direction to follow

Ex5: Cake recipe graph. Each vertex represent a different steps to make a cake and the edges shows the direction between those steps. We can just put the cake to the oven after mixing it. So, mixing is the prior step, then baking in the oven. Hence, the edge is direct

### Activity 2: Visualizing graphs
Figure 1

int main() { 
graph g{false}; // create an undirected graph g.add_edge("a", "c"); 
g.add_edge("b", "c"); 
g.add_edge("b", "d"); 
g.add_edge("c", "d"); 
g.add_edge("c", "f"); 
g.add_edge("d", "e"); 
g.add_edge("f", "g"); 
g.to_dot("simple.dot"); 
return 0; 
}


Figure 2

int main() { 
    graph g{true}; // create an undirected graph
    g.add_edge("a", "b");
    g.add_edge("b", "d");
    g.add_edge("c", "a");
    g.add_edge("d", "c");
    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

int main() { 
    auto g = graph::load("act3.graph");
    visitor vis{g};
    auto found = vis.find_recursive("a", "h");
    for (auto& v : vis.pre_order()) g.colour_vertex(v, colour::red);
    g.to_dot("simple.dot");
    auto value = vis.visitor::num_visits("d");
    printf("%d", value);
 
}

Answer:
1. The value of variable found is false
2. 3 times

### Activity 4: Positive reports

bool visitor::find_recursive(const std::string &start_vertex, const string &goal) {
    // FIXME Activity 4 - return correct result
    // FIXME Activity 5 - avoid cycles

    // append start_vertex to pre order
    pre_visit(start_vertex);
    bool res=false;//Fix for Activity 4
    if (goal == start_vertex) return true;

    // 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(!is_visited(edge.target())){//Fix for Act 5, it will check that if the vertex is visited or not
            //to avoid stuck in the cycle
            res|=find_recursive(edge.target(), goal);//Fix for Act 4: the res will be updated
        }

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

    return res;
}

}

### Activity 5: Getting lost

bool visitor::find_recursive(const std::string &start_vertex, const string &goal) {
    // FIXME Activity 4 - return correct result
    // FIXME Activity 5 - avoid cycles

    // append start_vertex to pre order
    pre_visit(start_vertex);
    bool res=false;//Fix for Activity 4
    if (goal == start_vertex) return true;

    // 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(!is_visited(edge.target())){//Fix for Act 5, it will check that if the vertex is visited or not
            //to avoid stuck in the cycle
            res|=find_recursive(edge.target(), goal);//Fix for Act 4: the res will be updated
        }

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

    return res;
}

### Activity 6: The limits of recursion
After scanning 1000000 times, it crashed

### Activity 7: Iterative traversal

// FIXME Activity 7 - complete the implementation
    // FIXME Activity 8 - make visit order consistent with recursive version
    // FIXME Activity 11 - keep track of the path
    // FIXME Activity 12 & 12 - detect cycles
    plan_vertex_visit(start_vertex);
    while (visits_planned()) {
        auto& v = peek_next_visit();

        if (v == goal) {
            pre_visit(v);
            return true;
        }
        auto time_visited = num_visits(v);
        if (time_visited == 0) {
            pre_visit(v);

            for (auto iter =  m_graph[v].edges().rbegin(); iter != m_graph[v].edges().rend(); ++iter) {
                // detect loop
                plan_vertex_visit(iter->target());
            }

        }
        else if (time_visited == 1) {
            pop_next_visit();
            if((std::find(m_planned_visits.begin(),m_planned_visits.end(),v)!=m_planned_visits.end())){
                cycle_detected(v);
            }else if(std::find(post_order().begin(),post_order().end(),v)==post_order().end())
            post_visit(v);
        }
    }
    return false;
}

### Activity 8: Depth-first search

// FIXME Activity 7 - complete the implementation
    // FIXME Activity 8 - make visit order consistent with recursive version
    // FIXME Activity 11 - keep track of the path
    // FIXME Activity 12 & 12 - detect cycles
    plan_vertex_visit(start_vertex);
    while (visits_planned()) {
        auto& v = peek_next_visit();

        if (v == goal) {
            pre_visit(v);
            return true;
        }
        auto time_visited = num_visits(v);
        if (time_visited == 0) {
            pre_visit(v);

            for (auto iter =  m_graph[v].edges().rbegin(); iter != m_graph[v].edges().rend(); ++iter) {
                // detect loop
                plan_vertex_visit(iter->target());
            }

        }
        else if (time_visited == 1) {
            pop_next_visit();
            if((std::find(m_planned_visits.begin(),m_planned_visits.end(),v)!=m_planned_visits.end())){
                cycle_detected(v);
            }else if(std::find(post_order().begin(),post_order().end(),v)==post_order().end())
            post_visit(v);
        }
    }
    return false;

void label_pre_order(graph& g, const visitor& vis) {
    for (int i = 0; i < vis.pre_order().size(); i++) {
        std::cout << vis.pre_order()[i] << " ";
        g.label_vertex(vis.pre_order()[i], i); 
    } 
    std::cout << "\n";
}

### Activity 9: Breadth-first search

void visitor::plan_vertex_visit(const string &to_vertex) {
if(m_traversal_type==traversal_t::depth_first)
    m_planned_visits.push_back(to_vertex);
else m_planned_visits.push_front(to_vertex);
}
void label_visit_order(graph &g, visitor &vis) {
for (int i = 0; i < vis.pre_order().size(); i++) {
    std::cout << vis.pre_order()[i] << " "; 
    g.label_vertex(vis.pre_order()[i], i); 
} 
std::cout << "\n"; 
}

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

bool visitor::find_iterative(const string &start_vertex, const string &goal) {
    // FIXME Activity 7 - complete the implementation
    // FIXME Activity 8 - make visit order consistent with recursive version
    // FIXME Activity 10 - keep track of the path
    // FIXME Activity 12 & 12 - detect cycles
    plan_vertex_visit(start_vertex);
    while (visits_planned()) {
        auto& v = peek_next_visit();

        if (v == goal) {
            pre_visit(v);
            return true;
        }
        auto time_visited = num_visits(v);
        if (time_visited == 0) {
            pre_visit(v);

            for (auto iter =  m_graph[v].edges().rbegin(); iter != m_graph[v].edges().rend(); ++iter) {
                // detect loop
                plan_vertex_visit(iter->target());
            }

        }
        else if (time_visited == 1) {
            pop_next_visit();
            if((std::find(m_planned_visits.begin(),m_planned_visits.end(),v)!=m_planned_visits.end())){
                cycle_detected(v);
            }else if(std::find(post_order().begin(),post_order().end(),v)==post_order().end())
            post_visit(v);
        }
    }
    return false;
}

### Activity 11: Detecting cycles

bool visitor::find_iterative(const string &start_vertex, const string &goal) {
    // FIXME Activity 7 - complete the implementation
    // FIXME Activity 8 - make visit order consistent with recursive version
    // FIXME Activity 10 - keep track of the path
    // FIXME Activity 12 & 12 - detect cycles
    plan_vertex_visit(start_vertex);
    while (visits_planned()) {
        auto& v = peek_next_visit();

        if (v == goal) {
            pre_visit(v);
            return true;
        }
        auto time_visited = num_visits(v);
        if (time_visited == 0) {
            pre_visit(v);

            for (auto iter =  m_graph[v].edges().rbegin(); iter != m_graph[v].edges().rend(); ++iter) {
                // detect loop
                plan_vertex_visit(iter->target());
            }

        }
        else if (time_visited == 1) {
            pop_next_visit();
            if((std::find(m_planned_visits.begin(),m_planned_visits.end(),v)!=m_planned_visits.end())){
                cycle_detected(v);
            }else if(std::find(post_order().begin(),post_order().end(),v)==post_order().end())
            post_visit(v);
        }
    }
    return false;
}

### Activity 12: Colouring cycles

void visitor::cycle_detected(const std::string& vertex)() { 
 m_cycle_found = true;
    m_cycle.clear();    // if we've visited a cycle before, clear it
    (void) vertex;
    for(auto i=std::find(m_pre_order.begin(),m_pre_order.end(),vertex);i!=m_pre_order.end();i++)
        m_cycle.insert(*i);
}  

## Looking back

### What we've learnt

* About directed and undirected graphs
* The differences between depth-first and breadth-first search
* Understand how cycles can be detected in a graph

### What were the surprises

Nothing

### What problems we've encountered

Nothing

### What was or still is unclear

Nothing

### How did the group perform?

As good as always