berblom 0.1.0

A novel web-of-trust algorithm for trust calculation.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

# Cycle Detection

Using reverse edges during the BFS can result in some counter-intuitive behavior.

Consider the following graph:

![Cycle Detection - Step 1](../Diagrams/figures/BFS/Cycle-Detection-step1.svg)

As you can see, no cycle exists **yet**, and at this point, the graph is directed and acyclic.

![Cycle Detection - Step 1 Path](../Diagrams/figures/BFS/Cycle-Detection-step1_path.svg)

However, after the first path (`Target -> C4 -> C2 -> C1 -> TA`) has been found, reverse edges are introduced between C2 and C4, which result in a cycle with not just two nodes, but three nodes (`C4 ~~> C2 -> C3 -> C4`).

Let's start the path finding for the next path.

![Cycle Detection - Step 2](../Diagrams/figures/BFS/Cycle-Detection-step2.svg)

We stop at the point where the path `Target -> C4 -> C3 -> C2` has been found.

Now, the algorithm checks the edges towards C2.

It finds a forward delegation from `C1`, which is valid and pushes `C1` into the queue.

**But** it now also finds a reverse delegation from `C4`.
That reverse delegation was from the previous path and has thereby a shorter remaining path length towards the target, as that path was able to take a shorter route.
Without cycle detection, this would be a valid edge to take and the BFS would now explore `C4` and override the information of the current path.

In the next step, `C1` would reach `TA` and path creation together with adjustment of the residual network begins.

After traversing through `TA -> C1 -> C2 -> C3 -> C4`, the graph would look as follows:

![Cycle Detection - Partial Step 3](../Diagrams/figures/BFS/Cycle-Detection-step3_partial.svg)

Now, when adjusting the next edge from C4, things would break.
Due to `C2 -> C4` being valid, `C4` has the previous node set to `C2` instead of `Target`, with the used edge being the reverse edge between `C2 -> C4`.
So instead of following the certification towards `Target`, the algorithm would then proceed and follow the reverse edge.
This means decreasing that reverse edge's trust amount by `80`, as that's the found trust on this path. This is, however, both an invalid operation (`80` > `40`) and wrong as this isn't part of the path.


## Conclusion

Cycle detection is necessary to handle cases:

- Where two paths have the same starting point.
- Where a shared path segment's trust is exhausted, forcing the second path to take a different and longer route.
- And the longer path eventually comes back onto the same path as the first one.