# 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
### Activity 3: Finding a path
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);
}
```
## 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.
Sign in with Wallet
Connect another wallet