berblom 0.1.0

use std::{
    collections::{HashMap, HashSet},
    io::Write,
};

use priority_queue::PriorityQueue;
use wot_network::{
    Binding,
    Certificate,
    Network,
    TrustDepth,
    search::{Path as WotNetworkPath, Paths, TrustAnchor as WotTrustAnchor, WotSearchTrait},
};

use crate::{
    debug::mermaid_graph,
    internal_prelude::*,
    queue::NodePriority,
    types::{
        certification::Certification,
        edges::{Delegation, PathEdge, ReverseEdge, UsedEdge},
        node::{EdgeSearchInfo, Node, TrustAnchor},
        path::Path,
        target_node::TargetNode,
    },
};

impl WotSearchTrait for FlowGraph {
    fn new(network: Network, anchors: Vec<WotTrustAnchor>, target: Binding) -> Self {
        Self::new(network, anchors, target)
    }

    fn search(&mut self, target_trust_amount: usize) -> Paths {
        FlowGraph::search(self, Some(target_trust_amount))
    }
}

/// Represents a flow network graph for determining the total trust between a target [`Binding`]
/// and a set of [`TrustAnchor`](WotTrustAnchor)s.
#[derive(Debug, Clone)]
pub struct FlowGraph {
    /// The [`Node`]s in the flow graph.
    ///
    /// Each node represents a [`Certificate`] in the network.
    nodes: HashMap<Certificate, Node>,

    trust_anchors: HashMap<Certificate, TrustAnchor>,

    /// The [`TargetNode`] representation.
    ///
    /// Contains runtime data that's relevant for our Ford-Fulkerson variant.
    target_node: TargetNode,

    current_path_id: usize,
}

impl FlowGraph {
    /// Constructs a new [`FlowGraph`] instance.
    ///
    /// The resulting [`FlowGraph`] can be used to detect flow paths from the trust anchors towards
    /// the target binding by calling [`FlowGraph::search`].
    ///
    /// # Parameters
    ///
    /// - `network`: The [`Network`] containing all certificates, delegations, and certifications.
    /// - `trust_anchors`: The set of trust anchors that should be used for this search.
    /// - `target_binding`: The target [`Binding`] for which the trust is to be determined.
    pub fn new(
        mut network: Network,
        trust_anchors: Vec<WotTrustAnchor>,
        target_binding: Binding,
    ) -> Self {
        // Since we're only interested in a single target, we can ignore all certifications except
        // the ones on the target binding.
        let target_certifications = network
            .certifications
            .remove(&target_binding)
            .unwrap_or_default();

        // Transform them from wot_network Certifications into our own representation.
        let certifications = target_certifications
            .into_iter()
            .map(Certification::new)
            .collect();

        let target_node = TargetNode::new(target_binding, certifications);

        // Convert the certificates into `Node`s.
        // Nodes contain additional runtime information used during our Ford-Fulkerson derivative.
        let mut nodes = HashMap::new();
        for (cert, delegations) in network.delegations.into_iter() {
            // Make sure all delegating nodes exist as well.
            for delegation in &delegations {
                let issuer = delegation.issuer().clone();
                nodes
                    .entry(issuer.clone())
                    .or_insert(Node::new(issuer, Vec::new()));
            }

            let node = nodes
                .entry(cert.clone())
                .or_insert(Node::new(cert, Vec::new()));
            node.delegations = delegations.into_iter().map(Delegation::new).collect();
        }

        // Create `Node`s for certifications.
        // Certification issuer nodes may not be part of the remaining network. For the search
        // algorithm to work, a respective Node must exist for every certification issuer.
        for certification in target_node.certifications.iter() {
            if !nodes.contains_key(&certification.inner.issuer) {
                nodes.insert(
                    certification.inner.issuer.clone(),
                    Node::new(certification.inner.issuer.clone(), Vec::new()),
                );
            }
        }

        // A map of trust anchors and their respective trust.
        // Converted into a HashMap for faster lookup.
        let trust_anchors: HashMap<Certificate, TrustAnchor> = trust_anchors
            .into_iter()
            .map(|anchor| (anchor.cert.clone(), TrustAnchor::new(anchor.clone())))
            .collect();

        FlowGraph {
            nodes,
            trust_anchors,
            target_node,
            current_path_id: 0,
        }
    }

    /// Returns a reference to the nodes in the flow graph.
    pub(crate) fn nodes(&self) -> &HashMap<Certificate, Node> {
        &self.nodes
    }

    /// Returns a reference to the trust anchors map.
    pub(crate) fn trust_anchors(&self) -> &HashMap<Certificate, TrustAnchor> {
        &self.trust_anchors
    }

    /// Returns a reference to the target node.
    pub(crate) fn target_node(&self) -> &TargetNode {
        &self.target_node
    }

    /// Performs a full Berblom search on a Web-of-Trust (WoT) network.
    ///
    /// Returns fully-resolved, valid, and non-conflicting trust paths that represent one possible
    /// set of paths achieving the maximum possible trust between the target binding and the
    /// specified trust anchors.
    ///
    /// # Note
    ///
    /// There may exist multiple different sets of paths that achieve the same total trust in the
    /// network. This algorithm only returns a single of these possible sets.
    ///
    /// # Parameters
    ///
    /// - `target_trust_amount`: Without this parameter, the maximum flow will be determined, even
    ///   if it's above `120` or `255`. If you are only interested in figuring out whether a certain
    ///   trust amount can be reached, use this prevent unnecessary path exploration.
    pub fn search(&mut self, target_trust_amount: Option<usize>) -> Paths {
        // The list of paths
        // It is **absolutely crucial** to not re-order this list of paths!!
        // Reverse-edges reference the indices of these paths, which is a necessary relationship to
        // efficiently consolidate paths in the very last step!
        //
        // Path indices must **never** be changed!!!
        let mut paths = Vec::new();

        let mut total_trust: usize = 0;

        debug!("===== Berblom Algorithm =====");
        debug!(
            "→ Search for target binding {} ({})",
            self.target_node.binding.cert, self.target_node.binding.identity
        );
        debug!("→ Trust anchors are: {:#?}", self.trust_anchors);

        while let Some(path) = self.step() {
            let total_trust_after_path = total_trust + path.trust_amount as usize;

            total_trust = total_trust_after_path;
            trace!(
                "Path is '{}' with amount {}",
                path.simple_display(),
                path.trust_amount,
            );
            paths.push(path);

            // Check if we reached the target amount. If so, we may stop early.
            if let Some(target_amount) = target_trust_amount
                && total_trust >= target_amount
            {
                break;
            }
        }

        let paths = Self::consolidate_paths(paths, None::<&mut std::fs::File>).unwrap();

        // Now transform all paths into the [`wot_network::Path`] type.
        let wot_network_paths = paths
            .into_iter()
            .map(|path| {
                (WotNetworkPath {
                start: path.trust_anchor,
                delegations: path
                    .edges
                    .into_iter()
                    .map(|edge| {
                        let PathEdge::ForwardEdge(delegation) = edge else {
                            panic!("Found reverse edge {edge:?} on resolved path. This is a bug!")
                        };
                        delegation.inner
                    })
                    .collect(),
                certification: path.certification.inner,
            }, path.trust_amount)
            })
            .collect();

        Paths::new_with_paths(wot_network_paths)
    }

    /// Call [`Self::search`], whilst creating a debug markdown writer with mermaid
    /// representations of the search process.
    ///
    /// At every step of the Berblom algorithm, the residual graph will be written as a mermaid
    /// graph. If a path can found on that graph, the graph will be written once more, but
    /// with that path being highlighted.
    ///
    /// # Note
    ///
    /// This is a debug tool with limits:
    /// - Mermaid is not capable of keeping a layout between steps. Especially the introduction of
    ///   reverse edges drastically changes the resulting graphs.
    /// - Mermaid does not prevent overlap of edge text. Some edge information may simply not be
    ///   readable.
    /// - For performance reasons, this implementation uses HashMaps, which is why there are no
    ///   guarantees in which order edges are added to the Mermaid diagram. Edge declaration order
    ///   matters in Mermaid and will result in different layouts. This means that graph layouts
    ///   will not be idempotent, despite the input data being identical.
    pub fn search_with_mermaid<W: Write>(
        &mut self,
        target_trust_amount: Option<usize>,
        writer: &mut W,
    ) -> std::io::Result<Paths> {
        // The list of paths
        // It is **absolutely crucial** to not re-order this list of paths!!
        // Reverse-edges reference the indices of these paths, which is a necessary relationship to
        // efficiently consolidate paths in the very last step!
        //
        // Path indices must **never** change!!!
        let mut paths = Vec::new();

        let mut current_step = 1;
        writeln!(writer, "# Step 1")?;
        writeln!(writer, "\n```mermaid")?;
        write!(writer, "{}", &mermaid_graph(self, None))?;
        writeln!(writer, "```\n")?;

        // Save the current graph for the mermaid graph with a found path.
        // Once we get the path in here, the residual graph (self) is already adjusted.
        // But the path needs to be drawn on the original graph.
        let mut previous_graph = self.clone();

        let mut total_trust: usize = 0;

        while let Some(path) = self.step() {
            println!("Path: {}", path.simple_display());

            // Draw the path on the graph before i has been updated.
            writeln!(writer, "## Path for {current_step}")?;
            writeln!(writer, "Path: `{}`\\n", path.simple_display())?;

            writeln!(writer, "\n```mermaid")?;
            write!(writer, "{}", mermaid_graph(&previous_graph, Some(&path)))?;
            writeln!(writer, "```\n")?;

            current_step += 1;
            // Draw the updated graph for the next step.
            writeln!(writer, "# Step {current_step}")?;
            writeln!(writer, "\n```mermaid")?;
            write!(writer, "{}", &mermaid_graph(self, None))?;
            writeln!(writer, "```\n")?;

            // Save the current graph for the next iteration
            previous_graph = self.clone();

            let total_trust_after_path = total_trust + path.trust_amount as usize;

            total_trust = total_trust_after_path;
            trace!(
                "Path is '{}' with amount {}",
                path.simple_display(),
                path.trust_amount,
            );
            paths.push(path);

            // Check if we reached the target amount. If so, we may stop early.
            if let Some(target_amount) = target_trust_amount
                && total_trust >= target_amount
            {
                break;
            }
        }

        let paths = Self::consolidate_paths(paths, Some(writer))?;

        // Now transform all paths into the [`wot_network::Path`] type.
        let wot_network_paths = paths
            .into_iter()
            .map(|path| {
                (WotNetworkPath {
                start: path.trust_anchor,
                delegations: path
                    .edges
                    .into_iter()
                    .map(|edge| {
                        let PathEdge::ForwardEdge(delegation) = edge else {
                            panic!("Found reverse edge {edge:?} on resolved path. This is a bug!")
                        };
                        delegation.inner
                    })
                    .collect(),
                certification: path.certification.inner,
            }, path.trust_amount)
            })
            .collect();

        Ok(Paths::new_with_paths(wot_network_paths))
    }

    /// Performs a single step of the [Ford-Fulkerson] derivative algorithm.
    ///
    /// See the "Flow Computation" chapter to get a high-level overview of what this does.
    pub(crate) fn step(&mut self) -> Option<Path> {
        // Perform a backwards BFS lookup on the internal residual network.
        let trust_anchor_id = self.search_path()?;

        // Assemble the path and adjust the residual network.
        let path = match self.finalize_path(trust_anchor_id) {
            Ok(path) => path,
            Err(message) => {
                error!("Dumping network:\n{self:#?}");
                panic!("{message}");
            }
        };

        // Reset all path search related variables on the whole graph.
        self.reset_search_data();

        // We found a path, increment id for the next path.
        self.current_path_id += 1;

        Some(path)
    }

    /// Searches for a path in the residual trust network.
    ///
    /// Performs a backwards BFS from the target [`Binding`] towards the [`TrustAnchor`]s.
    ///
    /// For more information see the "Path Finding" chapter.
    fn search_path(&mut self) -> Option<Certificate> {
        debug!("===== Starting path search =====");

        // Queue holds (certificate, path_length, current_amount, previous_cert)
        let mut queue: PriorityQueue<Certificate, NodePriority> = PriorityQueue::new();
        // Get a handle to the target binding identity.
        // This is necessary for delegations with regex restrictions against the target binding.
        let target_id = &self.target_node.binding.identity;

        // Populate the discovery queue with the certifications from the TargetNode.
        for (edge_id, certification) in self.target_node.certifications.iter().enumerate() {
            trace!(
                "Checking certification {} → ({}, {})",
                certification.inner.issuer(),
                certification.inner.target_cert(),
                certification.inner.target_id(),
            );

            // Skip the certification if no trust is left.
            if certification.available_amount() == 0 {
                trace!("→ Skip certification no trust is left.");
                continue;
            }

            let Some(issuer) = self.nodes.get_mut(certification.inner.issuer()) else {
                error!(
                    "→ Cannot find certification issuer node: {}",
                    certification.inner.issuer()
                );
                continue;
            };

            // Continue early if the node has no trust left.
            if issuer.available_amount() == 0 {
                trace!("→ Skip delegation as node has no available trust.");
                continue;
            }

            // Calculate next trust amount of the issuer node.
            let issuer_trust_amount = self
                .target_node
                .available_amount()
                .min(certification.available_amount());

            // Create a set of visited nodes to prevent cycling.
            let mut visited_nodes = HashSet::new();
            visited_nodes.insert(issuer.id.clone());

            issuer.path_info = EdgeSearchInfo::Some {
                current_amount: issuer_trust_amount,
                target: self.target_node.binding.cert.clone(),
                used_edge: UsedEdge::Certification(edge_id),
                path_length: 1,
                visited_nodes,
            };

            // At this point, it's possible that we already immediately hit the trust anchor!
            // Check if the certification issuer is in the set of trust anchors and whether that
            // anchor still has some trust left to give.
            if let Some(anchor) = self.trust_anchors.get(certification.inner.issuer())
                && anchor.available_amount() > 0
            {
                trace!(
                    "SUCCESS - found trust anchor {}",
                    certification.inner.issuer()
                );
                return Some(certification.inner.issuer().clone());
            }

            queue.push(issuer.id.clone(), NodePriority::new(1, issuer_trust_amount));
        }

        trace!("Queue after handling certifications: {queue:?}");

        // While searching for a path in the network, we don't just return on the first anchor we
        // find, but rather look for all anchors with the same (or smaller) path length.
        //
        // We then pick the one with the highest trust amount first.
        let mut found_path_length: Option<usize> = None;
        // List of found anchors with the structure of `(trust_anchor_id, trust_amount)`.
        let mut found_anchors: Vec<(Certificate, u8)> = Vec::new();

        // This is where the real BFS starts.
        //
        // Work through the discovery queue one node at a time:
        // - Check if the Node is a TrustAnchor. If so, we can stop, as we found a valid path
        //   towards a TrustAnchor.
        // - For every delegation on the current node:
        //     - Check if the current path length is shorter or equal than the allowed trust depth
        //       on the delegation.
        //     - If there are any regexes on the delegation, make sure that they match the target
        //       binding's `target_id`.
        //     - For every other Node that is then reached by a valid delegation:
        //         - The `used_amount` must not be touched during the search process!
        //         - Ensure that the Node has some trust amount left.
        //         - Make sure that there isn't already a previous_node on the Node with a shorter
        //           `path_length`. If so, ignore this delegation.
        //         - If there's already a previous_node with an equal `path_length`, but a lower
        //           trust amount, this delegation overrules any other previous delegations.
        //         - If the Delegation and Node are valid, adjust the `previous_node`. The
        //           `current_amount` is the minimum((allowed_amount - used_amount),
        //           delegation.trust_amount, previous_node.current_amount).
        //         - Put the discovered Node on top at the end of the discovery queue.
        while let Some((node_id, priority)) = queue.pop() {
            trace!("Current: {node_id}, Priority: {priority:?}");

            let Some(target) = self.nodes.get(&node_id).cloned() else {
                error!("Found a previously registered Node that's now missing: {node_id}");
                continue;
            };

            // Get the current path length.
            let EdgeSearchInfo::Some {
                path_length: target_path_length,
                current_amount: target_current_amount,
                visited_nodes: target_visited_nodes,
                used_edge: target_used_edge,
                ..
            } = target.path_info
            else {
                panic!(
                    "Encountered path in queue without EdgeSearchInfo. This is a bug! Path: {target:#?}"
                );
            };

            // This is one of the exit conditions for finding a path.
            // As soon as we find any trust anchor, we continue to visit all nodes with that same
            // path length, so that we find the best path for that length.
            //
            // We stop exploration, as soon as we visit any node with a longer path.
            if let Some(found_path_length) = found_path_length
                && target_path_length > found_path_length
            {
                break;
            }

            // Check if the node is a TrustAnchor with remaining trust.
            //
            // If so, mark the anchor as one of found anchors for this path length.
            // We will pick (one of) the best found anchors, once all nodes for this path
            // length are explored.
            //
            // Path creation and adjustments of the residual network are done outside of this
            // function
            //
            // If this is not the case, the node is a "normal" node and we need to further explore
            // the graph.
            if let Some(anchor) = self.trust_anchors.get(&node_id)
                && anchor.available_amount() > 0
            {
                trace!("SUCCESS - found trust anchor {node_id}",);

                if found_path_length.is_none() {
                    found_path_length = Some(target_path_length);
                    found_anchors.push((
                        target.id.clone(),
                        target_current_amount.min(anchor.available_amount()),
                    ));
                }
                continue;
            } else if !found_anchors.is_empty() {
                // If we already found an anchor for this path length, we no longer have to explore
                // any further along the graph. We simply look at the remaining nodes for this
                // length and stop afterwards, picking (one of) the best found anchors.
                continue;
            }

            // Start discovery of new nodes via the target's incoming delegations.
            for (edge_id, delegation) in target.delegations.iter().enumerate() {
                trace!(
                    "Checking delegation {} → {}",
                    delegation.issuer(),
                    delegation.target()
                );
                // Only follow the delegation, if there's any trust amount left in the first place.
                if delegation.available_amount() == 0 {
                    trace!("→ Skip delegation with trust 0");
                    continue;
                }

                // Path depth check for the upholding of trust_depth restrictions.
                //
                // The delegation.trust_depth must be bigger or equal than the path length from the
                // current node towards the target binding. If we wouldn't do this, we would allow a
                // longer path than is actually permitted by this delegation.
                if delegation.trust_depth() < target_path_length.min(u8::MAX as usize) as u8 {
                    trace!(
                        "→ Skip delegation as trust_depth ({}) < path_length ({})",
                        delegation.trust_depth(),
                        target_path_length
                    );
                    continue;
                }

                // Some delegations may restrict their forwarded trust towards the target binding
                // via a regular expression.
                //
                // Ensure that the target binding identifier satisfies all delegation regexes.
                if !delegation.regexes().is_empty()
                    && !delegation
                        .regexes()
                        .iter()
                        .any(|regex| regex.matches(target_id))
                {
                    trace!("→ Skip delegation, no matching regex for target binding");
                    continue;
                }

                // Get the issuer of the delegation
                let Some(issuer) = self.nodes.get_mut(delegation.issuer()) else {
                    error!(
                        "→ Found delegation towards '{}' from non-existent node '{}'. Ignoring this delegation!",
                        delegation.target(),
                        delegation.issuer()
                    );
                    continue;
                };

                // Calculate the new trust amount that would be set on the `issuer`, if we would
                // follow this edge.
                //
                // This is the minimum value of:
                // - `target_current_amount`: the max trust amount that can be pushed along the
                //   current path up and including the target.
                // - `delegation.available_amount()` The remaining trust amount that can be pushed
                //   through this specific delegation.
                // - `issuer.available_amount()` The remaining available trust amount that can be
                //   pushed through `issuer`.
                let issuer_trust_amount = target_current_amount
                    .min(delegation.available_amount())
                    .min(issuer.available_amount());

                // Don't add the node, if we don't have any flow.
                if issuer_trust_amount == 0 {
                    continue;
                }

                // Check if the issuer node is already enqueued.
                // If so, we have some guarantees due to the fact that we use a BFS:
                //
                // - All elements that are currently in the queue have either **the same path
                //   length** or **a bigger path length** than `target`.
                // - It follows from that, that no node with a longer path than `target` has reached
                //   the front of the queue.
                //
                // This guarantee allows us to simply modify `issuer` **in case** we manage to
                // find a better path to it, without having to worry about any queue positioning.
                let already_enqueued = issuer.path_info.is_some();

                // Right now, we know that we are allowed to follow this delegation.
                // Now, we need to check whether we already reached the issuer via a different
                // path. If so, we may only proceed if the current path is shorter than the
                // previously discovered path to `issuer`.
                if let EdgeSearchInfo::Some {
                    current_amount: issuer_current_amount,
                    path_length: issuer_path_length,
                    ..
                } = &issuer.path_info
                {
                    trace!("→ Node has already been visited",);

                    // The previously detected path is shorter. Ignore this delegation.
                    if *issuer_path_length < target_path_length + 1 {
                        trace!("→ Skipping - shorter path to {} exists", issuer.id);
                        continue;
                    }

                    trace!(
                        "→ Node would have new trust amount of {issuer_trust_amount} (old {issuer_current_amount})",
                    );

                    // If the paths have the same length, make sure the current trust amount is
                    // bigger than that of the other path. Otherwise, ignore this delegation.
                    //
                    // In case of an equal trust amount, we simply use the existing path and ignore
                    // this delegation.
                    if *issuer_path_length == target_path_length + 1
                        && issuer_current_amount >= &issuer_trust_amount
                    {
                        trace!(
                            "→ Skipping - {} already has a path with equal length and better trust amount {} vs {}",
                            issuer.id, issuer_current_amount, issuer_trust_amount,
                        );
                        continue;
                    }

                    if *issuer_path_length > target_path_length + 1 {
                        trace!("→ SUCCESS - found a shorter path to {}", issuer.id);
                    } else {
                        trace!(
                            "→ SUCCESS - found a path with to {} with more trust {issuer_trust_amount} (old {issuer_current_amount})",
                            issuer.id
                        );
                    }
                } else {
                    trace!("→ SUCCESS - found a new path to {}", issuer.id);
                }

                let mut visited_nodes = target_visited_nodes.clone();
                visited_nodes.insert(issuer.id.clone());

                let path_length = target_path_length + 1;

                // At this point, we have determined that current path is either shorter or has a
                // higher trust value and should therefore be used to reach `issuer`.
                // Update the path info accordingly
                issuer.path_info = EdgeSearchInfo::Some {
                    current_amount: issuer_trust_amount,
                    target: node_id.clone(),
                    used_edge: UsedEdge::Delegation(edge_id),
                    path_length,
                    visited_nodes,
                };

                let priority = NodePriority::new(path_length, issuer_trust_amount);
                if !already_enqueued {
                    trace!(
                        "→ Pushing {} onto queue with priority: {}",
                        issuer.id, &priority
                    );
                } else {
                    trace!(
                        "→ Update {} in queue with priority: {}",
                        issuer.id, &priority
                    );
                }

                // Enqueue/Update the issuer node onto the list.
                queue.push(issuer.id.clone(), priority);
            }

            // Check if we used a reverse edge to get to the current node and if so, to which path
            // it belongs to.
            // If we traverse any successive reverse edges and there are multiple reverse edges to
            // one node, we must favor the one which belongs to the same path.
            // Read the `001_Path_Finding/002_Traversing_Reverse_Edges.md` for more information.
            let previous_reverse_edge_path_id = match target_used_edge {
                UsedEdge::Certification(_) => None,
                UsedEdge::Delegation(_) => None,
                UsedEdge::ReverseEdge { path_id, .. } => Some(path_id),
            };

            // Save if a successive reverse edge for a previous reverse edge has been
            // found.
            // Read the `001_Path_Finding/002_Traversing_Reverse_Edges.md` for more information.
            let mut successive_reverse_node = None;

            // Start discovery of new nodes via the target's incoming reverse_edges.
            //
            // # Note
            //
            // In contrast to delegations, we **do not** have to check regexes on reverse edges:
            // By using a reverse edge, practically cancel out the usage of the associated
            // forward edge. I.e. we remove some usage from the paths.
            // Since we effectively remove/reroute usage, there are no constraints that need to be
            // checked.
            for (edge_id, reverse_edge) in target.reverse_edges.iter().enumerate() {
                // A successive reverse edge has been found towards this reverse edge's issuer.
                // That means that we can not allow any other reverse edges to overrule that path.
                if let Some(node) = &successive_reverse_node
                    && node == &reverse_edge.issuer
                {
                    continue;
                }

                // Make sure that we don't use any reverse edges to nodes that were already visited
                // along the current path! This would result in cycles and is an illegal operation.
                //
                // See chapter Cycle_Detection for more information.
                if target_visited_nodes.contains(&reverse_edge.issuer) {
                    continue;
                }

                trace!(
                    "Checking reverse edge {} → {}",
                    reverse_edge.issuer, reverse_edge.target
                );
                // Only follow the reverse edge, if there's any trust amount left in the first
                // place.
                if reverse_edge.trust_amount == 0 {
                    trace!("→ Skipping - trust amount of edge is 0");
                    continue;
                }

                // Path depth check for the upholding of trust_depth restrictions.
                //
                // The trust_depth must be bigger or equal than the path length from the
                // current node towards the target binding. If we wouldn't do this, we would allow a
                // longer path than is actually permitted by this reverse edge.
                if reverse_edge.trust_depth < target_path_length.min(u8::MAX as usize) as u8 {
                    trace!(
                        "→ Skipping - trust_depth ({}) < path_length ({})",
                        reverse_edge.trust_depth, target_path_length
                    );
                    continue;
                }

                // Get the issuer node.
                let Some(issuer) = self.nodes.get_mut(&reverse_edge.issuer) else {
                    error!(
                        "Found reverse edge towards '{}' from non-existent node '{}'. Ignoring this reverse edge!",
                        target.id, reverse_edge.issuer
                    );
                    continue;
                };

                // Calculate the new trust amount that would be set on the `issuer`, if we would
                // follow this edge.
                //
                // This is the minimum value of:
                // - `target_current_amount`: the max trust amount that can be pushed along the
                //   current path up and including the target.
                // - `delegation.trust_amount` The max trust_amount that can be pushed through this
                //   specific reverse edge.
                // - `issuer.available_amount()` The remaining available trust amount that can be
                //   pushed through `issuer`.
                let new_trust_amount = target_current_amount
                    .min(reverse_edge.trust_amount)
                    .min(issuer.available_amount());

                // Check if this reverse edge is a successive reverse edge on the same path.
                let is_successive = if let Some(prev_path_id) = previous_reverse_edge_path_id
                    && reverse_edge.path_id == prev_path_id
                {
                    true
                } else {
                    false
                };

                // Right now, we know that we are allowed to follow this reverse edge.
                //
                // Next we need to check whether we already reached the issuer node via a different
                // path. If so, we may only proceed if the new path is shorter than the
                // previously discovered path to `issuer`.
                //
                // Since we're traversing a reverse edge, this process involves checking whether the
                // `remaining_path_length` after rerouting the trust along the reverse edge would be
                // shorter than the current path length on the node.
                //
                // See the documentation chapter "Traversing Reverse Edges" for more info.
                if let EdgeSearchInfo::Some {
                    current_amount,
                    path_length,
                    // This `previous_issuer` info is used to prefer traversal along multiple
                    // successive reverse edges that belong to the same path, in case multiple
                    // forward/reverse edges point towards the same node.
                    target: previous_of_issuer,
                    used_edge,
                    ..
                } = &issuer.path_info
                {
                    trace!("→ Node has already been visited",);

                    // Perform the length check
                    if *path_length < reverse_edge.remaining_path_length {
                        trace!("→ Skipping - shorter path to {} exists", issuer.id);
                        continue;
                    }

                    trace!(
                        "→ Node would have new trust amount of {new_trust_amount} (old {current_amount})",
                    );

                    // Make sure we prefer successive reverse edges towards the target node.
                    //
                    // I.e. if another reverse edge from `target` already visited the `issuer`
                    // node, we must overrule that route, even if it's a similar or even better
                    // match.
                    if is_successive
                        && *previous_of_issuer == target.id
                        && used_edge.is_reverse_edge()
                    {
                        successive_reverse_node = Some(reverse_edge.issuer.clone());
                        trace!("→ SUCCESS - found a successive reverse edge to the target node");
                    }
                    // If the paths have the same length, make sure the current trust amount is
                    // bigger than that of the other path. Otherwise, ignore this delegation.
                    //
                    // In case of an equal trust amount, we simply use the existing path and ignore
                    // this reverse edge.
                    else if *path_length == reverse_edge.remaining_path_length
                        && *current_amount >= new_trust_amount
                    {
                        trace!(
                            "→ Skipping - {} already has a path with same length and better or equal trust amount ({} > {})",
                            issuer.id, current_amount, new_trust_amount,
                        );
                        continue;
                    } else if reverse_edge.remaining_path_length < *path_length {
                        trace!(
                            "→ SUCCESS - found a shorter path to {} ({} < {})",
                            issuer.id, reverse_edge.remaining_path_length, path_length,
                        );
                    } else {
                        trace!(
                            "→ SUCCESS - found a path with more trust ({new_trust_amount} > {current_amount}) to {}",
                            issuer.id
                        );
                    }
                } else {
                    trace!("→ SUCCESS - found a new path to the target node");
                }

                let mut visited_nodes = target_visited_nodes.clone();
                visited_nodes.insert(issuer.id.clone());

                // At this point, we have determined that current path can and should be extended
                // towards issuer. Update the path info accordingly.
                issuer.path_info = EdgeSearchInfo::Some {
                    current_amount: new_trust_amount,
                    target: node_id.clone(),
                    used_edge: UsedEdge::ReverseEdge {
                        index: edge_id,
                        path_id: self.current_path_id,
                    },
                    path_length: reverse_edge.remaining_path_length,
                    visited_nodes,
                };

                let priority =
                    NodePriority::new(reverse_edge.remaining_path_length, new_trust_amount);
                if !queue.contains(&issuer.id) {
                    trace!(
                        "→ Pushing {} onto queue with priority: {priority}",
                        issuer.id
                    );
                } else {
                    trace!(
                        "→ Updating {} in queue with priority: {priority}",
                        issuer.id
                    );
                }

                // Enqueue/Update the issuer node onto the list.
                queue.push(issuer.id.clone(), priority);
            }
        }

        // Exit early with `None` if we haven't found any path.
        let _found_path_length = found_path_length?;

        // We expect at least one anchor to be there.
        let mut anchors_iter = found_anchors.into_iter();
        let mut best_anchor = anchors_iter.next().unwrap();

        // Determine (one of) the best anchors.
        for anchor in anchors_iter {
            if anchor.1 > best_anchor.1 {
                best_anchor = anchor
            }
        }

        Some(best_anchor.0)
    }

    /// Called by [`Self::step`] whenever a path has been detected.
    ///
    /// At this point, the internal network is in a state where we can follow
    /// [`Node::path_info`]'s [`EdgeSearchInfo::Some::target`] fields from the node with the given
    /// `trust_anchor_id` until we reach the target binding. At this point, the path is embedded
    /// in the graph and must be converted into a usable form. While traversing the path, this
    /// function also takes care of adjusting the residual network.
    ///
    /// In detail, this means that we perform the (roughly summarized) following steps:
    /// - Traverse the graph by hopping along the [`Node::path_info`]
    ///   [target](`EdgeSearchInfo::Some::target`)s' [edge](`EdgeSearchInfo::Some::used_edge`)s on
    ///   each node
    /// - Build a path representation from those nodes.
    /// - While traversing the path:
    ///   - For every forward edge that has been used:
    ///     - Subtract the used trust amount on the forward edges.
    ///     - Introduce a reverse edge.
    ///        - Consult the Chapter "Creation of Reverse Edges" for more details.
    ///   - If reverse edges have been used:
    ///     - Subtract the used trust amount on the reverse edges.
    ///     - Add the used trust amount on the reverse edge back to the **associated** forward edge!
    ///       Consult the chapter "Traversing Reverse Edges" for more info.
    fn finalize_path(&mut self, trust_anchor_id: Certificate) -> Result<Path, String> {
        debug!("===== Assembling path and adjusting residual network =====");
        // # `Path` related variables
        //
        // A full `Path` can only be created once all of its components are in place.
        // Since this includes the certificate to the target binding, we can only create it at the
        // very end.
        //
        // - `trust_anchor_id`: We already know this, as it's passed in as a parameter. It's the
        //   starting point of the path.
        // - `edges`: A vector of `PathEdge` that is filled with delegations while building the
        //   path. It contains all edges from the trust anchor up to the certificate that holds the
        //   certification of the target binding.
        // - `path_trust_amount`: The trust amount for the full length of this path. This is
        //   equivalent to the `current_amount` on the target anchor node. It's the minimum value of
        //   remaining trust amount of both nodes or edges along the path. This value is very
        //   important, as this is the value that's used to adjust remaining flow on edges, nodes
        //   and the value used when creating reverse edges.
        //
        // # Loop related runtime variables
        //
        // - `target_id` This is the reference to the next target node along in the path. As we loop
        //   and advance through the path, the target will become the issuer in the next iteration.
        // - `used_edge`:  This is a reference to the edge that's used to get from the current
        //   (`issuer`) node to the target node (`target_id`). Since our path finding is backwards,
        //   the edges are counterintuitively saved on the target of an edge instead of the source.

        let (path_trust_amount, mut target_id, mut used_edge) = {
            // Get the trust anchor node.
            let Some(anchor_node) = self.nodes.get_mut(&trust_anchor_id) else {
                return Err(format!(
                    "Missing trust anchor node '{trust_anchor_id}' after path has been found! This is a bug.",
                ));
            };

            let EdgeSearchInfo::Some {
                current_amount: path_trust_amount,
                target,
                used_edge,
                ..
            } = anchor_node.path_info.clone()
            else {
                panic!("Missing path info on trust anchor after successful BFS: {anchor_node:#?}");
            };

            // Get the actual trust anchor info.
            // Nodes may act as both, nodes **and** trust anchors. Both roles may have individual
            // trust amount restrictions. So we need to consider both, the trust amount
            // node, but also on the trust anchor meta information itself.
            let Some(anchor) = self.trust_anchors.get_mut(&trust_anchor_id) else {
                return Err(format!(
                    "Missing trust anchor '{trust_anchor_id}' after path has been found! This is a bug.",
                ));
            };

            // The final limiting factor on the trust amount is the remaining trust on the anchor.
            let path_trust_amount = path_trust_amount.min(anchor.available_amount());

            // Adjust the used amounts of the anchor node.
            let Some(new_amount) = anchor_node.used_amount.checked_add(path_trust_amount) else {
                return Err(format!(
                    "Total amount of used trust ({}) and found trust ({}) on TA node {} in path exceed u8 bound! This is a bug.",
                    anchor_node.used_amount, path_trust_amount, anchor_node.id
                ));
            };
            anchor_node.used_amount = new_amount;

            // Adjust the used amounts of the actual anchor.
            let Some(new_anchor_amount) = anchor.used_amount.checked_add(path_trust_amount) else {
                return Err(format!(
                    "Total amount of used trust ({}) and found trust ({}) on TA {} in path exceed u8 bound! This is a bug.",
                    anchor.used_amount, path_trust_amount, trust_anchor_id
                ));
            };
            anchor.used_amount = new_anchor_amount;

            (path_trust_amount, target, used_edge)
        };

        let mut edges = Vec::new();

        trace!("→ Start path walk");
        // Now that we handled the initial logic, we walk along the path until we hit the final
        // node.
        //
        // This process is a bit weird, as we always have to perform steps somewhat backward, as
        // our BFS operates backward and our edges are thereby also saved "backwards" (on the
        // target).
        //
        // - Get the next node in the path, which we call `issuer`, as it's the issuer for the next
        //   edge to take.
        // - Put the edge used to get to this `issuer` into the `edges` list.
        // - Adjust the used trust amount of both the `issuer` as well as the edge's value
        // - Get the next edge and the id of the next edge's target node.
        let certification_index = loop {
            // At first, check if we hit an exit condition.
            // This means that we reached our target binding id, while also following a
            // certification.
            if target_id == self.target_node.binding.cert
                && let UsedEdge::Certification(index) = used_edge
            {
                break index;
            }

            let Some(issuer) = self.nodes.get_mut(&target_id) else {
                return Err(format!(
                    "Missing Node '{trust_anchor_id}' along path! This is a bug.",
                ));
            };

            // Adjust the used amounts of the node
            let Some(new_amount) = issuer.used_amount.checked_add(path_trust_amount) else {
                return Err(format!(
                    "Total amount of used trust ({}) and found trust ({}) on node {} in path exceed u8 bound! This is a bug.",
                    issuer.used_amount, path_trust_amount, issuer.id,
                ));
            };
            trace!(
                "→ Adjusting used trust amount of {}: {} -> {} (of {})",
                issuer.id, issuer.used_amount, new_amount, issuer.allowed_amount
            );
            issuer.used_amount = new_amount;

            // Push a copy of the used edge to the path, while adjusting the edges on
            // the original edges to shape the residual graph.
            match &used_edge {
                UsedEdge::Delegation(index) => {
                    let Some(delegation) = issuer.delegations.get_mut(*index) else {
                        return Err(format!(
                            "Found invalid delegation index {index} on node {}. This is a bug.",
                            issuer.id
                        ));
                    };

                    // Consume the used trust amount from the delegation.
                    let Some(new_amount) = delegation.used_amount.checked_add(path_trust_amount)
                    else {
                        return Err(format!(
                            "Total amount of used trust ({}) and found trust ({}) on delegation exceeds u8 bound! This is a bug.",
                            path_trust_amount, delegation.used_amount,
                        ));
                    };
                    trace!(
                        "→ Adjust used trust amount of delegation: {} -> {}",
                        delegation.issuer(),
                        delegation.target()
                    );
                    trace!(
                        "  ↳ Trust amount changed from: {} -> {} (of {})",
                        delegation.used_amount,
                        new_amount,
                        delegation.trust_amount()
                    );

                    delegation.used_amount = new_amount;

                    edges.push(PathEdge::ForwardEdge(delegation.clone()))
                }
                UsedEdge::ReverseEdge { index, path_id: _ } => {
                    let Some(reverse_edge) = issuer.reverse_edges.get_mut(*index) else {
                        return Err(format!(
                            "Found invalid reverse edge index {index} on node {}. This is a bug.",
                            issuer.id
                        ));
                    };

                    // Subtract the used trust amount from the edge.
                    let Some(new_amount) = reverse_edge.trust_amount.checked_sub(path_trust_amount)
                    else {
                        return Err(format!(
                            "Total amount of used trust ({}) in reverse edge exceeds available trust ({})! This is a bug.\nReverse edge: {} -> {}",
                            path_trust_amount,
                            reverse_edge.trust_amount,
                            reverse_edge.issuer,
                            reverse_edge.target
                        ));
                    };
                    trace!(
                        "→ Adjust used trust amount of reverse edge: {} -> {}",
                        reverse_edge.issuer, reverse_edge.target
                    );
                    trace!(
                        "  ↳ Trust amount changed from: {} -> {}",
                        reverse_edge.trust_amount, new_amount,
                    );

                    reverse_edge.trust_amount = new_amount;

                    // Push the path
                    edges.push(PathEdge::ReverseEdge(reverse_edge.clone()))
                }
                UsedEdge::Certification(index) => {
                    return Err(format!(
                        "Tried to get certification with index {index} on intermediate node. This is a bug."
                    ));
                }
            }

            // Make sure we have a previous node.
            let EdgeSearchInfo::Some {
                target: next_target_id,
                used_edge: next_used_edge,
                ..
            } = &issuer.path_info
            else {
                panic!("Node in path doesn't have a `path_info`! This is a bug: {issuer:#?}");
            };

            // Set the next node to look at with the used edge to get there.
            target_id = next_target_id.clone();
            used_edge = *next_used_edge;
        };

        // At this point, we hit the target binding and can now build the path.
        let Some(certification) = self.target_node.certifications.get_mut(certification_index)
        else {
            return Err(format!(
                "Found invalid certification index {certification_index} on target binding node. This is a bug.",
            ));
        };

        trace!(
            "→ Reached certification edge {} -> {} ({})",
            certification.inner.issuer(),
            certification.inner.target_cert(),
            certification.inner.target_id(),
        );

        // As a last step, also consume the used trust amount on the certification.
        let Some(new_amount) = certification.used_amount.checked_add(path_trust_amount) else {
            return Err(format!(
                "Total amount of used trust ({}) and found trust ({}) on certification exceeds u8 bound! This is a bug.",
                path_trust_amount, certification.used_amount,
            ));
        };
        certification.used_amount = new_amount;

        let path = Path {
            trust_amount: path_trust_amount,
            trust_anchor: trust_anchor_id,
            edges,
            certification: certification.clone(),
        };

        let path_length = path.len();

        // While traversing the path, we must be able to know the allowed delegation length at
        // each step. The reason for this is that we need to know this value on [`ReverseEdges`]
        // so that we may simulate rerouting the trust flow along another node.
        //
        // To calculate this value, we need to compute the delegation length based on the
        // allowed depth values on each delegation and the length of the path.
        //
        // Consider the following flow. The letters are nodes are the numbers on the arrows are
        // the trust depth.
        //
        // ```
        // A -5-> B -8-> C -2-> D
        // ```
        //
        // - A allows a depth of 5.
        // - When reaching `B`, `B` it effectively "inherits" a depth of 4.
        // - The `min(4, 8)` is used, so `B` delegates with a depth of 4 towards `C`.
        // - Now `C` inherits the depth of `3`.
        // - The `min(3, 2)` is used, so `C` delegates with a depth of 2 towards `D`.
        let mut allowed_delegation_length = TrustDepth::Unlimited;

        trace!("→ Perform reverse edge creation and reverse-forward graph adjustments.");

        for (current_length, edge) in path.edges.iter().enumerate() {
            match edge {
                // As a forward edge (delegation) has been used, we now need to create a respective
                // reverse edge.
                PathEdge::ForwardEdge(delegation) => {
                    let Some(node) = self.nodes.get_mut(delegation.issuer()) else {
                        return Err(format!(
                            "Missing Node '{}' while creating reverse edges! This is a bug.",
                            delegation.issuer()
                        ));
                    };

                    let reverse_edge = ReverseEdge {
                        issuer: delegation.target().clone(),
                        target: delegation.issuer().clone(),
                        trust_amount: path_trust_amount,
                        trust_depth: allowed_delegation_length,
                        remaining_path_length: path_length - (current_length + 1),
                        path_id: self.current_path_id,
                    };

                    trace!("→ Created new reverse edge: {reverse_edge:?}.");

                    node.reverse_edges.push(reverse_edge);

                    // Calculate the new trust depth.
                    allowed_delegation_length = allowed_delegation_length
                        .minus(1)
                        .min(delegation.trust_depth());
                }
                // For every usage of a reverse edge, we need to adjust the respective forward edge
                // as well. I.e. We practically "rerouted" some trust flow along a
                // different path, which means that we freed up some trust along the
                // forward edge.
                PathEdge::ReverseEdge(reverse_edge) => {
                    let Some(node) = self.nodes.get_mut(&reverse_edge.issuer) else {
                        return Err(format!(
                            "Missing Node '{}' while adjusting reverse-forward edges! This is a bug.",
                            reverse_edge.issuer
                        ));
                    };

                    // As we just traversed a reverse edge, we no longer work with the
                    // allowed_delegation_length up until this point, as this is now overwritten by
                    // the reverse_edge's saved value.
                    allowed_delegation_length = reverse_edge.trust_depth;

                    // TODO: We currently don't handle the case that multiple delegations between
                    // the same edges exist!
                    // The current implementation could result in undefined behavior in case:
                    // - Two delegations between A and B exist
                    // - The delegations have different trust levels and/or different trust_amounts.
                    // - One of the delegation edges is used.
                    // - The resulting reverse edge is used as well.
                    //
                    // -> We now need to add the used trust amount on the reverse edge back to the
                    // **original** edge that created this reverse edge. There's however currently
                    // no way to determine which forward edge has been used, so
                    // any of the two could be picked.
                    //
                    // For example, if the forward edge with the higher trust depth is selected
                    // instead of the original edge with a lower trust depth,
                    // trust could be consumed from a more permissive edge, potentially resulting in
                    // a lower overall trust discovered in the network.
                    //
                    // This case is probably very esoteric though.
                    //
                    // To properly handle this, we need to do either of these two things:
                    // - Prune any duplicate edges (not 100% correct, but this is somewhat of an
                    //   esoteric edge-case)
                    // - Save the index of the forward edge on the reverse edge. That way, we can
                    //   reference specific delegations when introducing reverse edges. That allows
                    //   us to differentiate which of the two edges was used for that path, given
                    //   the case that the reverse edge is being used and the original forward edge
                    //   needs to have its `used_amount` adjusted.
                    //
                    // **UPDATE:** This could theoretically already be easily fixable by the
                    // introduction of `UsedEdge`.

                    // Find a delegation that matches the reverse_edge.
                    let Some(delegation) = node.delegations.iter_mut().find(|delegation| {
                        delegation.issuer() == &reverse_edge.target
                            && delegation.target() == &reverse_edge.issuer
                    }) else {
                        return Err(format!(
                            "Couldn't find matching delegation for reverse edge with issuer {} and target {}! This is a bug.",
                            reverse_edge.issuer, reverse_edge.target,
                        ));
                    };

                    trace!(
                        "→ Adjust delegation whose reverse edge was used: {} -> {}",
                        delegation.issuer(),
                        delegation.target()
                    );

                    // Add the freed up trust amount back to the delegation.
                    let Some(new_amount) = delegation.used_amount.checked_sub(path_trust_amount)
                    else {
                        return Err(format!(
                            "Total amount of used trust on delegation ({}) and restored trust ({}) is smaller than 0! This is a bug.",
                            delegation.trust_amount(),
                            path_trust_amount,
                        ));
                    };
                    trace!(
                        "  ↳ Used trust amount changed from: {} -> {} (of {})",
                        delegation.used_amount,
                        new_amount,
                        delegation.trust_amount()
                    );
                    delegation.used_amount = new_amount;
                }
            }
        }

        Ok(path)
    }

    /// Resolves all reverse edges introduced during the max-flow detection algorithm.
    ///
    /// All reverse edge path segments have a corresponding forward path segment in a different
    /// path. In the [`Self::finalize_path`] function, where the residual network is adjusted
    /// and reverse edges are created based on a chosen path, an extra important step is
    /// performed:
    ///
    /// The path id (index) that is responsible for creating a reverse edge is **saved** on
    /// each reverse edges.
    ///
    /// When another path now uses that reverse edge, we know for which exact path we simulate
    /// "rerouting" trust.
    ///
    /// This enables us to directly consolidate reverse edges with perfectly matching paths,
    /// which allows to **skip any trust depth checks**!
    ///
    /// Takes an optional `writer` string to which debug info is added/printed.
    fn consolidate_paths<W: Write>(
        mut paths: Vec<Path>,
        mut writer: Option<&mut W>,
    ) -> std::io::Result<Vec<Path>> {
        #[derive(PartialEq, Debug)]
        enum Segment {
            None,
            Some {
                // The associated path
                path_id: usize,
                // The indices of the segment
                segment_indices: Vec<usize>,
            },
        }

        if let Some(ref mut writer) = writer {
            writeln!(writer, "\n\n# Path Consolidation\n```")?;
        }

        // Create a list of all paths that need to be checked.
        // We will manipulate the paths inside the original path vector.
        let mut path_ids_to_check: Vec<usize> = (0..paths.iter().len()).collect();

        while let Some(path_id) = path_ids_to_check.pop() {
            // Direct access as path ids must reference valid array indices.
            let mut path = paths[path_id].clone();

            if let Some(ref mut writer) = writer {
                write!(writer, "\nChecking Path: {}\n", path.simple_display())?;
            }

            // Save the indices of the reverse edges in a vector.
            let mut segment = Segment::None;

            for (index, edge) in path.edges.iter().enumerate() {
                if let Some(edge) = edge.reverse() {
                    // To keep things simple, we only look at chains of reverse edges that belong to
                    // the same path. This means that if there are multiple reverse edges in a
                    // single path, the path will be checked multiple times.
                    match &mut segment {
                        Segment::None => {
                            // We encountered the first reverse edge.
                            // Lock the path id in.
                            segment = Segment::Some {
                                path_id: edge.path_id,
                                segment_indices: vec![index],
                            }
                        }
                        Segment::Some {
                            segment_indices, ..
                        } => {
                            segment_indices.push(index);
                        }
                    }
                }
            }

            // Only continue if we found a segment.
            let Segment::Some {
                path_id: forward_path_id,
                segment_indices,
            } = segment
            else {
                continue;
            };

            if let Some(ref mut writer) = writer {
                writeln!(writer, "→ Found segments with indices: {segment_indices:?}")?;
            }

            // We now have a segment of reverse edge(s) that belong to the same path, and we also
            // know which exact path we need to consolidate with.
            // Now we just need to figure out the corresponding segment in the forward path.

            // The last segment of the reverse path will be the first segment of the forward path.
            let first_reverse_index = segment_indices.first().unwrap();
            let last_reverse_index = segment_indices.last().unwrap();
            let last_reverse_edge = path
                .edges
                .get(*last_reverse_index)
                .expect("We know this index exists")
                .reverse()
                .expect("We know this is a reverse edge");

            // Now we need to find a forward edge that matches the reverse edge.
            let mut forward_path = paths[forward_path_id].clone();

            if let Some(ref mut writer) = writer {
                writeln!(
                    writer,
                    "→ Looking for matching segment in associated path: {}",
                    forward_path.simple_display()
                )?;
            }

            let mut first_forward_index = None;
            for (index, edge) in forward_path.edges.iter().enumerate() {
                let PathEdge::ForwardEdge(forward_edge) = edge else {
                    continue;
                };

                // The target/issuer don't match, so skip it.
                if forward_edge.issuer() != &last_reverse_edge.target
                    || forward_edge.target() != &last_reverse_edge.issuer
                {
                    continue;
                }

                first_forward_index = Some(index);
            }

            let Some(first_forward_index) = first_forward_index else {
                error!(
                    "Couldn't find matching forward edge for reverse edge segment {segment_indices:?} of path {path:?}"
                );
                error!("Associated forward path is {forward_path:?}");
                panic!("Encountered critical error in path consolidation");
            };

            if let Some(ref mut writer) = writer {
                writeln!(
                    writer,
                    "→ Found matching segment at index {first_forward_index}",
                )?;
            }

            // Calculate the last segment index.
            let last_forward_index = first_forward_index + segment_indices.len() - 1;

            // Before we actually consolidate the paths, we need to handle the case that the
            // reverse edge doesn't consume all of the available amount that's provided by the
            // forward edge.
            //
            // This is effectively a partial reroute of the forward path.
            // To handle this, we make a copy of the forward path with the remaining trust amount.
            // The original path will be updated to the amount of the reverse path.
            if forward_path.trust_amount > path.trust_amount {
                let mut forward_path_clone = forward_path.clone();
                forward_path_clone.trust_amount = forward_path.trust_amount - path.trust_amount;

                if let Some(ref mut writer) = writer {
                    writeln!(
                        writer,
                        "→ Trust of forward path ({}) exceeds reverse path ({})",
                        forward_path.trust_amount, path.trust_amount
                    )?;
                    writeln!(
                        writer,
                        "→ Pushing copy of forward path with remaining trust {}",
                        forward_path_clone.trust_amount
                    )?;
                }

                // Push the cloned paths to be checked.
                paths.push(forward_path_clone);
                path_ids_to_check.push(paths.len() - 1);

                // Update the forward path to match the reverse path.
                forward_path.trust_amount = path.trust_amount;
            }

            // Remove the segments and swap tails between path and forward_path
            //
            // This is effectively this operation:
            // path[0..first_reverse_index] + forward_path[last_forward_index..]
            // forward_path[0..first_forward_index] + path[last_reverse_index..]
            //
            // We create a clone of the tails before mutating anything for better visualization and
            // to make sure that we can safely swap the certifications as well.
            let mut path_tail = path.clone();
            path_tail.edges = path_tail.edges[last_reverse_index + 1..].to_vec();
            let mut forward_path_tail = forward_path.clone();
            forward_path_tail.edges = forward_path_tail.edges[last_forward_index + 1..].to_vec();

            // Truncate to the start of the segment
            path.edges.truncate(*first_reverse_index);
            forward_path.edges.truncate(first_forward_index);

            if let Some(ref mut writer) = writer {
                writeln!(
                    writer,
                    "→ Splicing start of reverse path\n  {}\n  with end of forward path\n  {}",
                    path.simple_display_without_target(),
                    forward_path_tail.simple_display_without_anchor(),
                )?;
                writeln!(
                    writer,
                    "→ Splicing start of forward path\n  {}\n  with end of reverse path\n  {}",
                    forward_path.simple_display_without_target(),
                    path_tail.simple_display_without_anchor(),
                )?;
            }

            // Append the swapped tails and overwrite certifications.
            path.edges.extend(forward_path_tail.edges);
            path.certification = forward_path_tail.certification;

            forward_path.edges.extend(path_tail.edges);
            forward_path.certification = path_tail.certification;

            if let Some(ref mut writer) = writer {
                writeln!(
                    writer,
                    "→ Resulting reverse path: {}",
                    path.simple_display()
                )?;
                writeln!(
                    writer,
                    "→ Resulting forward path: {}",
                    forward_path.simple_display()
                )?;
            }

            paths[path_id] = path;
            paths[forward_path_id] = forward_path;

            // Both path might now contain reverse edges, due to the splicing, so enqueue them both
            // for checking.
            path_ids_to_check.push(path_id);
            path_ids_to_check.push(forward_path_id);
        }

        if let Some(ref mut writer) = writer {
            write!(writer, "\n```")?;
        }

        Ok(paths)
    }

    /// Resets the graph's path finding algorithm related variables.
    /// This is called at the end of each [`Self::step`].
    fn reset_search_data(&mut self) {
        for (_, node) in self.nodes.iter_mut() {
            node.path_info = EdgeSearchInfo::None;
        }
    }
}