# Week 12 - Graph traversals

## Team

Team name: Zahir Josefina
Len Bauer
Sebastian Wojciechowski

Date: 04/06/2021

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

## Activities

### Activity 1: Application of graphs
Examples:

1. Router Network connections:
a. Wifi connections between individua devices on the network.
b. the verticies represent the individual devices on the network and the edges represent the connections between said devices.
c. they edges are directional as the devices are usually conected to the reouter and not the router to the device.

2. Intagram Followers:
a. It represent the following between account on instagram.
b. The verticies represent the individual account on the website and the edges the following/relations between them.
c. The edges are Directed because when you follow a new account, that new account does not automatically follow you back.

3. Facebook Friends:
a. It represents the relation between facebook friends
b The vertices represent individual accounts, while edges represent relations between them.
c.The edges are undirected because adding an account as a friend by one person changes the connection status between them for both users.

4. Google Maps:
a. It represents the map of possible routes
b. The vertices represent the the individual places you can go through your journey, while the edges represent paths between them.
c. The edges are undirectes beacuse you can travel between the points in both directions.

5. Resource Allocation Graph In Operating System:
a. Different resource allocations of the opperating system.
b. Each process and resources are considered to be vertices.Edges are drawn from resources to the allocated process, or from requesting processes to the requested resource.
c. The edges are directed becausethey are pointing from the recources to the allocated process.

### Activity 2: Representing graphs

- Adjacency Matrix: In the adjacency matrix representation, a graph is represented in the form of a two-dimensional array. The size of the array is V x V, where V is the set of vertices.

- In the adjacency list representation, a graph is represented as an array of linked list. The index of the array represents a vertex and each element in its linked list represents the vertices that form an edge with the vertex.

Adjacency Matrix:

- Uses O(n^2) memory
- It is fast to lookup and check for presence or absence of a specific edge between any two nodes O(1)
- It is slow to iterate over all edges
- It is slow to add/delete a node; a complex operation O(n^2)
- It is fast to add a new edge O(1)

Adjacency List

- Memory usage depends more on the number of edges (and less on the number of nodes), which might save a lot of memory if the adjacency matrix is sparse
- Finding the presence or absence of specific edge between any two nodes is slightly slower than with the matrix O(k); where k is the number of neighbors nodes
- It is fast to iterate over all edges because you can access any node neighbors directly
- It is fast to add/delete a node; easier than the matrix representation
- It fast to add a new edge O(1)

The method of storing its vertices and edges is a one that uses an
adjacency list

### Activity 3: Graph construction

Undirected:

      graph undirected{false};
        for (auto& v : {"a", "b", "c", "d", "e", "f", "g"})
        undirected.add_vertex(v);
        undirected.add_edge("a", "c");
        undirected.add_edge("c", "b");
        undirected.add_edge("c", "d");
        undirected.add_edge("c", "f");
        undirected.add_edge("f", "g");
        undirected.add_edge("b", "d");
        undirected.add_edge("d", "e");
        undirected.to_dot("example.dot");
        undirected.to_dot("act3-undirected.dot");


Directed:

   graph directed{true};
        for (auto& v : {"a", "b", "c", "d", "e", "f", "g"})
        directed.add_vertex(v);
        directed.add_edge("a", "b");
        directed.add_edge("b", "d");
        directed.add_edge("d", "c");
        directed.add_edge("c", "a");
        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

Left:
- the vertices are vistited in the same order as they are added to the graph. When it reaches the end of a route, it goes back until it finds a new branch.
- Vertex D was visited 3 times.

Right:
- It result in an error because of the loop of (b -> c -> d -> f -> b)

### Activity 5: Find all reachable vertices

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);
        }
    }
}

- Directed:

digraph g {
	rankdir = LR;	node[shape=oval style=filled];
	a[label="a", fillcolor="red"];
	b[label="b", fillcolor="red"];
	c[label="c", fillcolor="red"];
	d[label="d", fillcolor="red"];
	e[label="e", fillcolor="red"];
	f[label="f", fillcolor="red"];
	g[label="g", fillcolor="red"];

	edge[dir = forward];
	a -> b;
	b -> d;
	c -> a;
	d -> c;
	d -> e;
	e -> f;
	f -> g;
	g -> e;
}

- Undirected:

digraph g {
	rankdir = LR;	node[shape=oval style=filled];
	a[label="a", fillcolor="red"];
	b[label="b", fillcolor="red"];
	c[label="c", fillcolor="red"];
	d[label="d", fillcolor="red"];
	e[label="e", fillcolor="red"];
	f[label="f", fillcolor="red"];
	g[label="g", fillcolor="red"];

	edge[dir = none];
	a -> c;
	b -> c;
	b -> d;
	c -> d;
	c -> f;
	d -> e;
	f -> g;
}

### Activity 6: Recursion overhead

The max recursion the program can handle is 16141 but it seems that it can change depending on a machine that compiles the program

### Activity 7: Iterative traversal

The iterative version can indeed process the graphs.

### Activity 8: Breadth-first search
The main chane is that, with the Push_Back function it does a Breadth first search function. While with Push_Front it does Depth first search function

### 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(); 
		queue.pop_back(); 

		if (visited.find(v.label()) == visited.end()) { 
			std::cout << "Visited " << v.label() << std::endl;
			visited.insert(v.label()); 
			for (auto &edge : v.edges())
				queue.push_front(edge.target());

			for(auto &vertex : queue)
				std::cout << vertex.label() << "\n";
		}

	}
	return visited.contains(goal);
}

### Activity 10: Cycles and visited nodes

It doesn't work because it returns true when an edge is visited twice. This does not automatically mean that it is a cycle.

### Activity 11: Understanding the recursion

The line visiting will be printed in the right order. The line Backtracking however, will be printed in reverse.

### Activity 12: Understanding the iteration

### Activity 13: Cycle detection

## Look back

### What we've learnt

- This week we learned about graphs. Most notably Directed and UnDirected graphs.
- We also learned about depth and breadth search

### What were the surprises

- There weren't many surprises this week aside from a couple of bug in the code. From what I see they were fixed in the pdf later on but without an announcement we feel like this can mess some people up.

### What problems we've encountered

- As said before we encounter some problem with some bugs in activity 5 and 7.
- Due to project system we had some trouble working on algorithm.

### What was or still is unclear

- Activity 12 and 13 are still unclear mostly because we didn't have enough time to make them.

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

- The collaboration of our group was pretty good as always but similair to last week project system took a lot of time out of us.