# Traversing Reverse Edges

Reverse Edges are a concept from the Ford-Fulkerson method. Their purpose is to take flow that was previously assigned to one path, and redirect it to another path. These redirections are used to find a larger total flow.

Berblom builds on this concept and extends it to be applicable to the Web of Trust graph search problem.

*Note that in this section we only discuss how Berblom's BFS search algorithm **uses** reverse edges. Generation of reverse edges is discussed in more detail in the document ["Creation of Reverse Edges"].*

## Singular Reverse Edges

![Traversing Reverse Edges](../Diagrams/figures/BFS/Traversing-Reverse-Edges_simple.svg)

During pathfinding, reverse edges that were introduced in previous steps of the **Flow Computation** algorithm may be used.

Consider the graph above. The first path `P1` that will be found by [our regular BFS search](./001_BFS.md) algorithm is: `P1: Target -> CB5 -> CM1 -> CT1 -> TA1`

As Berblom finds this path, four reverse edges are created. The new residual net then looks as follows, with the reverse edges marked as dotted red lines (and flow capacity subtracted from forward edges that are used in `P1`):

![Traversing Reverse Edges - Path](../Diagrams/figures/BFS/Traversing-Reverse-Edges-simple_path.svg)

To explain the behavior in detail, let's walk through the path finding step-by-step.
For brevity's sake, the target binding `Target, target@foo.example` will be referred to as `Binding`

- Start of algorithm at `Target, target@foo.example` (`Binding`).
    - Check all certifications on `Binding`:
        - `Target -> Binding`
            - `Target` is pushed into queue
- 1st hop to `Target`.
    - `path_length = 1`
    - Check edges to `Target`:
        - `CB5 -> Target`
            - flow capacity is exhausted -> Ignored
        - `CT4 -> Target`
            - has trust of 60 left
            - Trust depth of `1`.
            - `path_length <= 1` -> Trust depth is fulfilled.
            - `CT4` is pushed into queue
- 2nd hop to `CT4`.
    - `path_length = 2`
    - Check edges to `CT4`:
        - `CT3 -> CT4`
            - has trust of 60 left
            - Trust depth of `2`.
            - `path_length <= 2` -> Trust depth is fulfilled.
            - `CT3` is pushed into queue
- 3rd Hop to `CT3` - Same pattern as CT4
- 4th Hop to `CT2` - Same pattern as CT4
- 5th Hop to `CT1`
    - `path_length = 5`
    - Check edges to `CT1`
        - No usable forward edges (the edge `TA -> CT1` has been exhausted by `P1`)
        - Reverse edge `CM1 ~~> CT1`
            - has trust of 60 left
            - Trust depth of `5` on reverse edge.
            - `path_length <= 5` -> Trust depth is fulfilled.
            - `CM1` is pushed into queue
- 6th Hop to `CM1`. This is where the special handling happens.
    - `path_length = 3`
      Whenever a reverse edge is taken, we effectively simulate the scenario of "what would happen if we were to reroute some flow?".
      In this specific case, we simulate redirecting flow from `TA1 -> CT1` via `CT2` towards `Binding`.
      At the moment we cross the reverse edge `CT1 -> CM1`, we act as if we were doing the following:
        - Split `P1: Binding -> Target -> CB5 -> CM1 -> CT1 -> TA1` at `CT1 -> CM1`, resulting in `Binding -> Target -> CB5 -> CM1` and `CT1 -> TA1`.
        - Consider the current path (before the reverse edge) prepended to `CT1 -> TA1`, resulting in `Binding -> Target -> CT4 -> CT3 -> CT2 -> CT1 -> TA1`.
      This now allows us to perform path finding as if we walked the first part of `P1: Binding -> Target -> CB5 -> CM1`.
      Since that path only has two hops plus the certification, we set the `path_length` to `3`, completely ignoring the path length before the reverse edge.
    - Check edges to `CM1`
        - `CB5 -> CM1`
            - has trust of 60 left
            - Trust depth of `3` on reverse edge.
            - `path_length <= 3` -> Trust depth is fulfilled.
            - `CB5` is pushed into queue
            - The resulting path length on `CB5` is **4**, as we're taking another forward edge!
        - Reverse edge `CB5 ~~> CM1`
            - has trust of 60 left
            - Trust depth of `3`.
            - `path_length <= 3` -> Trust depth is fulfilled.
            - The resulting `path_length` of `CB5` would be **2** as we're taking a reverse edge once more.
              The shorter path length means that the previously found path to `CB5` via the forward edge will be overruled and the reverse edge will be taken instead.
              Having the path length as our primary criteria for choosing nodes, enables us to prefer successive reverse edges over forward edges when walking backwards an existing path.
              This property is extremely important to prevent fragmented paths that cannot be consolidated.
- 7th Hop to `CB5`.
    - `path_length = 2`
      Once more, we set the `path_length` to the now remaining path length of `P1`.
    - Check edges to `CB5`
      From here on, we simply explore all nodes until `TA2` is hit.

At this point, we have effectively updated the first path to `P1: Binding -> Target -> CT4 -> CT3 -> CT2 -> CT1 -> TA1` and found an additional second path `P2: Binding -> Target -> CB5 -> CB4 -> CB3 -> CB2 -> CB1 -> TA2`.
However, to actually calculate this result, we still need to work through the next documentation chapters. In particular [**Path_Consolidation**](../003_Path_Consolidation/001_Path_Consolidation.md).

## Handling reverse-edges from multiple Path Finding runs

There can be scenarios where multiple reverse-edges are available between two nodes.
In these scenarios it can be crucial to pick the correct reverse edge.

Consider the following graph:

![Traversing Reverse Edges Multiple Reverse Edges](../Diagrams/figures/BFS/Traversing-Reverse-Edges-multi.svg)

The first two paths that will be found by our **Path Finding** algorithm are (each with a flow amount of 30):

- `P1: Binding -> Target -> CB5 -> CM1 -> TA2`
- `P2: Binding -> Target -> CB5 -> CM1 -> CT1 -> TA1`

As a byproduct of finding these paths, Berblom creates seven reverse edges (one for each forward traversal of a delegation edge).
The residual net now looks as follows, with the reverse edges marked in red (and flow capacity reduced in forward edges, as used by `P1` and `P2`):

![Traversing Reverse Edges Multiple Reverse Edges - path](../Diagrams/figures/BFS/Traversing-Reverse-Edges-multi_path.svg)

To explain the behavior in detail, let's walk through the path finding step-by-step.
For brevity's sake, the binding `Target, target@foo.example` will be referred to as `Binding`.
For the steps between `Target` and `CT1` take a look at the example in the [previous section](#singular-reverse-edges), which works identically, even though the graphs differ a bit.

- In the first 4 hops, we find the path `Binding -> Target -> CT4 -> CT3 -> CT2`, just like above.
- 5th Hop to `CT1`
    - `path_length = 5`
    - Check edges to `CT1`
        - Forward edge `CT1 -> CM1`
            - has trust of 30 left
            - Trust depth of `5` on reverse edge.
            - `path_length <= 5` -> Trust depth is fulfilled.
            - `CM1` is pushed into queue
            - The resulting path length on `CM1` would be `6`.
        - Reverse edge `CM1 ~~> CT1`
            - has trust of 60 left
            - Trust depth of `5` on reverse edge.
            - `path_length <= 5` -> Trust depth is fulfilled.
            - `CM1` is pushed into queue
            - The resulting path length on `CM1` would be `3` and thereby overrules the forward path.
- 6th Hop to `CM1`. This is where we need to take special care
    - Since we traversed a reverse edge to get here, we must remember what path that reverse edge is associated with.
      In our case, this is `P2` from `TA1` towards `Binding`.
    - `path_length = 3`
    - Check edges to `CM1`
      As you can see, at this point we have **two** valid reverse edges.
      However, in the previous step we chose to walk backwards along `P2`, so at this node we may only pick the reverse edge that's associated with `P2`.
      This results in the following rule:
      After traversing a reverse edge belonging to a Path `P` and if there are multiple reverse edges towards the same node `N`, one must pick a successive reverse edge that belongs to same path `P`, if a successive reverse edge exists towards the node `N`.
        - Reverse edge `CB5 ~~> CM1` that belongs to `P1`.
            - has trust of 30 left
            - Trust depth of `7` on reverse edge.
            - `path_length <= 3` -> Trust depth is fulfilled.
            - `CB5` is pushed into queue
        - Reverse edge `CB5 ~~> CM1` that belongs to `P2`.
            - has trust of 30 left
            - Trust depth of `3` on reverse edge.
            - `path_length <= 3` -> Trust depth is fulfilled.
            - Since this reverse edge also belongs to `P2`, it overrules other edge of `P1` towards `CB5`.
- 7th Hop to `CB5`.
    - `path_length = 2`
      Once more, we set the `path_length` to the now remaining path length of `P1` (`Binding -> Target -> CB5`).
    - Check edges to `CB5`
      From here on, we simply explore all reachable nodes starting with `CB4` until `TA3` is hit.

After this Path Finding step, we have effectively rerouted the flow that previously passed along `P2: Binding -> Target -> CB5 -> CM1 -> CT1 -> TA1`, and instead added these two new paths to our set: `Binding -> Target -> CT4 -> CT3 -> CT2 -> CT1 -> TA1` (with a flow of 30) and `Binding -> Target -> CB5 -> CB4 -> CB3 -> CB2 -> CB1 -> TA3` (also with a flow of 30).

(However, as above, we'll need the material from the following documentation chapters to actually calculate this result.)

["Creation of Reverse Edges"]: ../002_Flow_Computation/002_Creation_of_Reverse_Edges.md
