# Path Consolidation

After running the Berblom algorithm to compute maximum trust in a Web of Trust, the resulting set of paths may contain *reverse edges*.
These reverse edges are artifacts of the Ford-Fulkerson-style flow computation, representing "backtracking" or rerouting of trust through the residual network.
However, in a real trust network, only forward delegations are valid.
Therefore, a final *path consolidation* step is required to transform all paths into valid, non-overlapping trust paths that use only forward edges.

## Consolidation Process

The consolidation algorithm works as follows:

- Create a queue with path ids and enqueue every found path checking.
- Until the queue is empty, pop a path id and perform the following steps:
    - Go through every node in the path and check if it's a reverse edge.
      - If the path is clean, mark the path as clean and continue with the next path.
      - If there is a reverse edge, continue with the next step.
    - Save the position of this reverse edge in the path, this is the start of our reverse segment.
    - Extract the forward path id that is responsible for creating this reverse edge.
      That forward path contains the exact matching forward edge that should be used for consolidation.
    - Check if there are any successive reverse edges that belong to that same path.
        - If so, also save the position of the **last** successive reverse edge, which is the end of the reverse segment.
        - If not, the reverse segment consists of a single element, meaning that start/stop are the same position.
    - Load the forward path and search for the matching forward segment.
        The forward segment is the backwards equivalent of the reverse segment.
        This means that simply go through all nodes along the forward path and search for the first delegation:
        - whose target is the issuer of the **last** reverse edge in the reverse path.
        - whose issuer is the target of the **last** reverse edge in the reverse path.
    - Before any splicing is performed, check if the forward path has a higher trust amount than the reverse path.
      - If so, create a copy of the forward path and set its trust amount to the remainder of the forward path after consolidating the reverse path.
        Example: A forward path `A` with trust amount `80` exists.
        Path `B` with trust amount `60` uses one of the reverse edges.
        Create a Path `A'` with a trust amount of `20` and adjust the trust amount of Path `A` to `60`.
    - To now consolidate the paths:
        - Splice the start of the reverse path with the end of the forward path, omitting the middle segment that they both share.
        - Splice the start of the forward path with the end of the reverse path, omitting the middle segment that they both share.
    - Enqueue both paths for checking again, as any trailing reverse edges might have been introduced in either path due to the splicing.


## Example

The [Complex Example Search](../../complex_example_search.md) provides both a good visualization, and detailed generated output on how the path consolidation process works in practice.

The generated output looks as follows, with `N6 ┄⇢ N1` being a reverse edge:

```
Checking Path: S2 → N4 → N5 → N6 ┄⇢ N1 → N2 → N3 → T ⇒ (T, <target@target.example>)
→ Found segments with indices: [3]
→ Looking for matching segment in associated path: S1 → N1 → N6 → T ⇒ (T, <target@target.example>)
→ Found matching segment at index 1
→ Trust of forward path (80) exceeds reverse path (40)
→ Pushing copy of forward path with remaining trust 40
→ Splicing start of reverse path
  S2 → N4 → N5 → N6
  with end of forward path
  N6 → T ⇒ (T, <target@target.example>)
→ Splicing start of forward path
  S1 → N1
  with end of reverse path
  N1 → N2 → N3 → T ⇒ (T, <target@target.example>)
→ Resulting reverse path: S2 → N4 → N5 → N6 → T ⇒ (T, <target@target.example>)
→ Resulting forward path: S1 → N1 → N2 → N3 → T ⇒ (T, <target@target.example>)

Checking Path: S1 → N1 → N6 → T ⇒ (T, <target@target.example>)

Checking Path: S1 → N1 → N2 → N3 → T ⇒ (T, <target@target.example>)
```
