# Week 12 - Graph traversals

## Team

Team name:
Date: 3-6-2021

Members
Anton Vorderman
Nian Luisman
Thom Kistemaker

| 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

### Activity 1: Application of graphs

#### 5 Voorbeelden:

1. Facebook
1. Connecties tussen personen
2. Vertices zijn Personen, edges zijn vriendschap
3. Undirected. De vriendschap is wederzijds of nietbestaand (geen edge).
2. Twitter
1. Connecties tussen accounts
2. Vertices zijn accounts, edges geven een 'volg' aan.
3. Directed. Account A kan account B volgen, zonder dat B ook A volgt
3. blockchain
1. connectes van computers en transacties
2. Vertices zijn de computers, edges zijn de acties handelingen die uigevoedt moeten worden.
3. Directed. alles is aan elkaar toegewezen.
4. Google maps
1. Locaties en de wegen er tussen
2. Vertices zijn de locaties en de edges zijn de wegen
3. Directed.
5. LinkedIn
1. Connecties tussen personen
2. Vertices zijn personen, edges zijn connecties
3. Undirected. Een connectie op LinkedIn is wederzijds

### Activity 2: Representing graphs

1. Adjacency List: An Adjacency list is an array consisting of the address of all the linked lists. The first node of the linked list represents the vertex and the remaining lists connected to this node represents the vertices to which this node is connected. This representation can also be used to represent a weighted graph. The linked list can slightly be changed to even store the weight of the edge.
2. Adjacency Matrix: Adjacency Matrix is a 2D array of size V x V where V is the number of vertices in a graph. Let the 2D array be adj[][], a slot adj[i][j] = 1 indicates that there is an edge from vertex i to vertex j. Adjacency matrix for undirected graph is always symmetric. Adjacency Matrix is also used to represent weighted graphs. If adj[i][j] = w, then there is an edge from vertex i to vertex j with weight w.

### Activity 3: Graph construction

if (run_activity_3) {
        // activity 3
        // build an undirected graph that matches the graph of Figure 1
        graph undirected{false};
        // TODO: add edges
        for (auto& label : {"a", "b", "c", "d", "e", "f", "g"})
            undirected.add_vertex(label);
        undirected.add_edge("a", "c");
        undirected.add_edge("c", "b");
        undirected.add_edge("c", "d");
        undirected.add_edge("b", "d");
        undirected.add_edge("d", "e");
        undirected.add_edge("c", "f");
        undirected.add_edge("f", "g");
        undirected.to_dot("act3-undirected.dot");

        // build a directed graph that matches the graph of Figure 2
        graph directed{true};
        for (auto& label : {"a", "b", "c", "d", "e", "f", "g"})
            directed.add_vertex(label);
        directed.add_edge("a", "b");
        directed.add_edge("c", "a");
        directed.add_edge("b", "d");
        directed.add_edge("d", "c");
        directed.add_edge("d", "e");
        directed.add_edge("e", "f");
        directed.add_edge("f", "g");
        directed.add_edge("g", "e");
        directed.to_dot("act3-directed.dot");
    }

### Activity 4: A first traversal

if (run_activity_4) {
    // implement the function "traverse_rec" as given in the PDF
    // create the two graphs
    graph left = activity_4_left();
    graph right = activity_4_right();

    left.to_dot("act4-left.dot");
    right.to_dot("act4-left.dot");

    // TODO: uncomment functions and see what happens
    traverse_rec(left.find_vertex("a"));
    //traverse_rec(right.find_vertex("a"));
}
graph activity_4_left() {
    graph g{true};
    for (auto& label : {"a", "b", "c", "d", "e", "f", "g", "h"})
        g.add_vertex(label);

    g.add_edge("a", "b");
    g.add_edge("a", "e");
    g.add_edge("b", "c");
    g.add_edge("c", "d");
    g.add_edge("e", "f");
    g.add_edge("e", "g");
    g.add_edge("f", "d");
    g.add_edge("g", "h");
    g.add_edge("h", "d");

    return g;
}

graph activity_4_right() {
    graph g{true};
    for (auto& label : {"a", "b", "c", "d", "e", "f", "g"})
        g.add_vertex(label);

    g.add_edge("a", "b");
    g.add_edge("b", "c");
    g.add_edge("c", "d");
    g.add_edge("d", "e");
    g.add_edge("d", "f");
    g.add_edge("f", "b");
    g.add_edge("c", "g");

    return g;
}

De linker graph heeft geen probleem met het aanroepen van de recursive functie. De graph wordt van bovenaan als eerst doorlopen, en werkt zijn weg naar beneden indien de bovenliggende route aan een einde is gekomen.
Vertex D is 3 keer gepasseerd

De rechter graph heeft een oneindige loop in de graph zitten. De error die we krijgen is "recursing too deeply", oftwel hij crasht doordat er geen einde aan de functie komt.

### Activity 5: Find all reachable vertices

if (run_activity_5) {
    // change the definition of the traverse_rec function, so that
    // an unordered set can be passed
    graph directed{true};
    for (auto& label : {"a", "b", "c", "d", "e", "f", "g"})
        directed.add_vertex(label);
    directed.add_edge("a", "b");
    directed.add_edge("c", "a");
    directed.add_edge("b", "d");
    directed.add_edge("d", "c");
    directed.add_edge("d", "e");
    directed.add_edge("e", "f");
    directed.add_edge("f", "g");
    directed.add_edge("g", "e");
    // TODO: add some vertices and edges

    // run the function and colour reachable nodes
    lookup reachable;
    traverse_rec(directed.find_vertex("a"), reachable);
    traverse_rec(directed.find_vertex("b"), reachable);
    traverse_rec(directed.find_vertex("c"), reachable);

    for (auto& label : reachable)
        directed.colour_vertex(label, colour::red);
    directed.to_dot("reachable.dot");
}
    
void traverse_rec(const graph::vertex& v, lookup& visited) {
    // you need this function in activities 5 and 11
    std::cout << "Visiting " << v.label() << std::endl;
    visited.insert(v.label());
    for (const auto& edge : v.edges()) {
        if(visited.find(edge.target().label()) == visited.end()){
            traverse_rec(edge.target(), visited);
        }
        else{
            return;
        }
    }
}

### Activity 6: Recursion overhead

if (run_activity_6) {
        graph g{true};
        const int size = 100000;
        for (int i = 0; i < size; i++)
            g.add_vertex("a" + std::to_string(i));

        for (int i = 1; i < size; i++)
            g.add_edge("a" + std::to_string(i - 1), "a" + std::to_string(i));

        lookup reachable;
        traverse_rec(g["a0"], reachable);
    }

bij a16156 stopte hij al. Dit gebeurt consistent.

### Activity 7: Iterative traversal

        graph g{true};
        const int size = 100000;
        for (int i = 0; i < size; i++)
            g.add_vertex("a" + std::to_string(i));

        for (int i = 1; i < size; i++)
            g.add_edge("a" + std::to_string(i - 1), "a" + std::to_string(i));

        lookup reachable;
        traverse(g["a0"]);

De Graph wordt nu wel succesvol geprocessed

### Activity 8: Breadth-first search

Push_back:
Visited a
Visited b
Visited c
Visited g
Visited d
Visited f
Visited e
Push_front
Visited a
Visited b
Visited c
Visited d
Visited g
Visited e
Visited f

Bij ```push_back()``` gaat hij van onder naar boven door de lijst van edges zodra er een optie is. Bij ```push_front()``` gaat hij van boven naar onder door de lijst van edges zodra er een optie is.
Bijvoorbeeld bij C heeft hij 2 opties: d & g
Bij het toevoegen van de edges wordt eerst d toegevoegd en daarna g. Dit is dus ook de volgorde die hij aanhoudt bij ```push_front()```, terwijl hij het andersom doet bij ```push_back()```

Volgorde van de edges:

g.add_edge("a", "b");
g.add_edge("b", "c");
g.add_edge("c", "d");
g.add_edge("d", "e");
g.add_edge("d", "f");
g.add_edge("f", "b");
g.add_edge("c", "g");

### Activity 9: Comparison

bool find_goal(const graph::vertex& start, const std::string& goal) {

    std::deque<graph::vertex> queue = { start };
    std::unordered_set<std::string> visited;
    queue.push_back(start);
    while (!queue.empty()) {
        auto v = queue.back(); // v is the next vertex to visit
        queue.pop_back(); // remove v from queue

        if (visited.find(v.label()) == visited.end()) { // was v visited before?

            if(v.label() == goal){
                return true;
            }

            std::cout << "Visited " << v.label() << std::endl;
            visited.insert(v.label()); // no, mark v as visited
            // add all vertices adjacent to v to the queue
            for (auto& edge : v.edges() )
                queue.push_front(edge.target());
        }
    }
    return false;
}

Volgens ons is er niet veel verschil tussen depth first en breadth first. Ligt er maar net aan waar de te zoeken goal zit.

### Activity 10: Cycles and visited nodes

Er wordt geen rekening gehouden met eenrichtingsverkeer. Zodra de vertice bezocht is en hij hem nog een keer tegen komt gaat hij er van uit dat het een cycle is.

### Activity 11: Understanding the recursion

Visiting a
Visiting b
Visiting c
Visiting d
Visiting e
Backtracking from e
Backtracking from d
Backtracking from c
Visiting f
Backtracking from f
Backtracking from b
Backtracking from a

De "Backtracking" lines worden in reverse geprint.

### Activity 12: Understanding the iteration

Visiting a
Visiting b
Visiting f
Visiting d
Visiting e
Backtracking from e
Backtracking from d
Backtracking from f
Visiting c
Backtracking from c
Backtracking from b
Backtracking from a

Hij gaat nu eerst bovenlangs via f in plaats van via c bij de vorige opgave

### Activity 13: Cycle detection

## Look back

### What we've learnt

Fill in...

### What were the surprises

Fill in...

### What problems we've encountered

Activity 7: in de main functie stonden een aantal graphs vooraf ingevuld. 3 van de 4 werkten niet. Toen we zelf de hele lange graph toevoegden werkte hij wel gewoon.

Bij activities 11 en 12 moesten we figuur 3a gebruiken, maar doordat die figuur een loop heeft ging dat mis bij activity 11. Daarom hebben we maar 3b gebruikt.

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