Skip to main content

hopr_transport/path/
selector.rs

1use std::{cmp::Ordering, sync::Arc};
2
3use hopr_api::{
4    OffchainPublicKey,
5    graph::{
6        NetworkGraphTraverse, NetworkGraphView,
7        function::{BasicValueFn, EdgeValueFn},
8        traits::{
9            EdgeImmediateProtocolObservable, EdgeLinkObservable, EdgeObservableRead, EdgeProtocolObservable, ValueFn,
10        },
11    },
12    types::internal::errors::PathError,
13};
14
15use super::{
16    errors::{PathPlannerError, Result},
17    traits::{PathSelector, PathWithMetrics},
18};
19use crate::observer::{PathDirection, PhaseCounts, TransportEvent, TransportObserver};
20
21/// Accumulated path cost and quality aggregates, folded edge-by-edge during DFS.
22///
23/// `PartialOrd` / `PartialEq` compare only the `cost` field so the DFS
24/// pruning threshold (`min_cost`) operates on the same scalar as before.
25#[derive(Clone, Debug)]
26struct PathCostWithMetrics {
27    cost: f64,
28    total_latency_ms: Option<u32>,
29    min_probe_success_rate: Option<f64>,
30    min_ack_rate: Option<f64>,
31    fundable_tickets_floor: Option<u128>,
32}
33
34impl PartialOrd for PathCostWithMetrics {
35    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
36        self.cost.partial_cmp(&other.cost)
37    }
38}
39
40impl PartialEq for PathCostWithMetrics {
41    fn eq(&self, other: &Self) -> bool {
42        self.cost == other.cost
43    }
44}
45
46impl From<(PathCostWithMetrics, Vec<OffchainPublicKey>)> for PathWithMetrics {
47    fn from((metrics, path): (PathCostWithMetrics, Vec<OffchainPublicKey>)) -> Self {
48        PathWithMetrics {
49            path,
50            cost: metrics.cost,
51            total_latency_ms: metrics.total_latency_ms,
52            min_probe_success_rate: metrics.min_probe_success_rate,
53            min_ack_rate: metrics.min_ack_rate,
54            fundable_tickets_floor: metrics.fundable_tickets_floor,
55        }
56    }
57}
58
59/// Returns the minimum of two `Option<T>` values, preferring `Some` over `None`.
60fn opt_min<T: PartialOrd>(a: Option<T>, b: Option<T>) -> Option<T> {
61    match (a, b) {
62        (Some(x), Some(y)) => Some(if x <= y { x } else { y }),
63        (x, y) => x.or(y),
64    }
65}
66
67/// Wraps an `EdgeValueFn<f64, W>` as a `ValueFn` whose `Value` type carries
68/// both the cost and per-path quality aggregates.
69///
70/// All cost semantics are delegated to the inner `EdgeValueFn`; the wrapper
71/// only adds the aggregate fold on the same `&Weight` reference already
72/// available during DFS, so no extra graph lookups are needed.
73struct MetricsValueFn<W: EdgeObservableRead> {
74    inner: EdgeValueFn<f64, W>,
75    /// Face value used to express each edge's balance as a count of single-hop tickets.
76    ///
77    /// Read once per query rather than stored on any edge: deriving a count at query time is
78    /// safe, whereas deriving it at edge-update time is what made a price change stale the
79    /// whole graph.
80    ticket_face_value: Option<hopr_api::graph::traits::Balance>,
81}
82
83impl<W> ValueFn for MetricsValueFn<W>
84where
85    W: EdgeObservableRead + Send + 'static,
86{
87    type Value = PathCostWithMetrics;
88    type Weight = W;
89
90    fn initial_value(&self) -> Self::Value {
91        PathCostWithMetrics {
92            cost: self.inner.initial_value(),
93            total_latency_ms: Some(0),
94            min_probe_success_rate: None,
95            min_ack_rate: None,
96            fundable_tickets_floor: None,
97        }
98    }
99
100    fn min_value(&self) -> Option<Self::Value> {
101        self.inner.min_value().map(|c| PathCostWithMetrics {
102            cost: c,
103            total_latency_ms: None,
104            min_probe_success_rate: None,
105            min_ack_rate: None,
106            fundable_tickets_floor: None,
107        })
108    }
109
110    fn into_value_fn(self) -> BasicValueFn<Self::Value, Self::Weight> {
111        let inner = self.inner.into_value_fn();
112        let ticket_face_value = self.ticket_face_value;
113        Arc::new(move |prev: PathCostWithMetrics, observed: &W, idx: usize| {
114            let cost = inner(prev.cost, observed, idx);
115
116            let edge_lat = observed
117                .immediate_qos()
118                .and_then(|m| m.average_latency())
119                .or_else(|| observed.intermediate_qos().and_then(|m| m.average_latency()));
120            let total_latency_ms = match (prev.total_latency_ms, edge_lat) {
121                (Some(acc), Some(lat)) => Some(((acc as u128 + lat.as_millis()).min(u32::MAX as u128)) as u32),
122                _ => None,
123            };
124
125            // Probe rate: taking the min of immediate and intermediate guards against nodes that
126            // look good on direct probes but degrade under multi-hop load.
127            // `and_then`, not `map`: a stream with no observations contributes nothing to the min
128            // rather than contributing a zero it never measured.
129            let edge_probe = observed
130                .immediate_qos()
131                .and_then(|m| m.average_probe_rate())
132                .into_iter()
133                .chain(observed.intermediate_qos().and_then(|m| m.average_probe_rate()))
134                .reduce(f64::min);
135            let min_probe_success_rate = opt_min(prev.min_probe_success_rate, edge_probe);
136
137            let edge_ack = observed.immediate_qos().and_then(|m| m.ack_rate());
138            let min_ack_rate = opt_min(prev.min_ack_rate, edge_ack);
139
140            // Expressed in single-hop tickets, not base units: the weighting factor below is a
141            // log ratio, and a base-unit balance would compress every realistic channel into a
142            // sliver of its output range.
143            //
144            // `zip`, not a fallback: an absent face value means the price is unknown, not that it
145            // is one. Dividing a base-unit balance by `1` yields a ticket count that saturates to
146            // `u128::MAX` and reads downstream as unlimited capacity — the opposite of what not
147            // knowing should imply. Contribute nothing to the floor until pricing arrives.
148            let edge_tickets = observed
149                .intermediate_qos()
150                .and_then(|m| m.balance())
151                .zip(ticket_face_value)
152                .map(|(balance, face_value)| {
153                    let tickets = if face_value.is_zero() {
154                        hopr_api::graph::traits::Balance::zero()
155                    } else {
156                        balance / face_value
157                    };
158                    if tickets > hopr_api::graph::traits::Balance::from(u128::MAX) {
159                        u128::MAX
160                    } else {
161                        tickets.low_u128()
162                    }
163                });
164            let fundable_tickets_floor = opt_min(prev.fundable_tickets_floor, edge_tickets);
165
166            PathCostWithMetrics {
167                cost,
168                total_latency_ms,
169                min_probe_success_rate,
170                min_ack_rate,
171                fundable_tickets_floor,
172            }
173        })
174    }
175}
176
177/// Trim the candidate set to lower median latency and minimise variance while
178/// preserving an anonymity floor and relayer diversity in every position.
179///
180/// Behaviour:
181/// - If `candidates.len() <= floor`, returns all candidates unchanged (`min(found_count, floor)` semantics — the floor
182///   is never a minimum to fabricate).
183/// - Sorts candidates with a known `total_latency_ms` ascending.
184/// - Keeps `floor` of them preferring distinct first relayers and bounding how often a relayer recurs in each later
185///   position (see `take_relayer_diverse` and `MIDDLE_HOP_SHARE`), lowest latency first within those rules.
186/// - If still over the floor with no populated candidates left, drops unpopulated candidates from the input-order tail.
187///
188/// A path is "fully measured" — and therefore preferred over unmeasured alternatives —
189/// when `total_latency_ms` is known AND either `hops == 0` (direct path, no channel
190/// expected) OR `fundable_tickets_floor` is also known.  This prevents 0-hop direct paths from
191/// being demoted simply because they carry no channel-capacity data.
192pub fn prune_for_consistency(candidates: Vec<PathWithMetrics>, floor: usize, hops: usize) -> Vec<PathWithMetrics> {
193    // floor == 0 means "no pruning" — caller opts out entirely.
194    if floor == 0 || candidates.len() <= floor {
195        return candidates;
196    }
197
198    let fully_measured =
199        |p: &PathWithMetrics| p.total_latency_ms.is_some() && (hops == 0 || p.fundable_tickets_floor.is_some());
200
201    let (mut populated, unpopulated): (Vec<_>, Vec<_>) = candidates.into_iter().partition(|p| fully_measured(p));
202
203    // Sort populated ascending by latency (lowest first → drop from the end).
204    populated.sort_by_key(|p| p.total_latency_ms.unwrap_or(u32::MAX));
205
206    // Prefer measured paths: keep as many populated paths as fit within the floor,
207    // then fill the remaining slots with unpopulated paths.  This ensures that
208    // latency-measured candidates are never discarded when unprobed paths alone
209    // would satisfy the floor.
210    let target_populated = populated.len().min(floor);
211    let populated = take_relayer_diverse(populated, target_populated);
212    let remaining = floor - target_populated;
213
214    let mut result = populated;
215    result.extend(unpopulated.into_iter().take(remaining));
216
217    result
218}
219
220/// A relayer may sit past the first position in at most `n.div_ceil(MIDDLE_HOP_SHARE)` of the `n`
221/// candidates `take_relayer_diverse` keeps, while the pool allows it, counted over every position past
222/// the first together: a relayer in the second position of some paths and the third of others costs
223/// as many paths when it dies as one in either alone.
224///
225/// Distinct first relayers alone leave every other position free to collapse: the best path from
226/// each first relayer often runs through the same second hop, so one relayer sat in the middle of
227/// every forward candidate, and when it died the whole forward direction went dark at once, with
228/// nothing left to corroborate a verdict against (measured: the busiest relay of a 2-hop session
229/// carried 29 % of all relayed packets; killed, the session never recovered). A third bounds what
230/// one relayer's death costs to about a third of the draws before the weights are even looked at.
231const MIDDLE_HOP_SHARE: usize = 3;
232
233/// Takes `n` candidates from `sorted`, preferring not-yet-represented first relayers and bounding
234/// how often any relayer recurs past the first position.
235///
236/// Plain truncation keeps the `n` lowest-latency paths, which in a well-connected network are often
237/// the *same* few relayers reached by different routes; every downstream draw then inherits that
238/// concentration. Relative order is preserved, so each pass stays latency-ordered. Four passes:
239/// paths with a new first relayer whose later relayers are all under the `MIDDLE_HOP_SHARE` cap;
240/// then any path under the cap; then, over the cap, paths with a new first relayer, so a pool whose
241/// every path shares a later relayer still keeps as many first relayers as it offers; then the best
242/// of the rest, so a thin pool still fills the floor.
243fn take_relayer_diverse(sorted: Vec<PathWithMetrics>, n: usize) -> Vec<PathWithMetrics> {
244    if sorted.len() <= n {
245        return sorted;
246    }
247
248    let cap = n.div_ceil(MIDDLE_HOP_SHARE).max(1);
249    let mut seen: Vec<OffchainPublicKey> = Vec::with_capacity(n);
250    let mut per_relayer: std::collections::HashMap<OffchainPublicKey, usize> = Default::default();
251    let mut taken = vec![false; sorted.len()];
252    let mut count = 0;
253
254    // The relayers of `path` past the first: `path` ends with the destination, which is no relayer.
255    let later_relayers = |p: &PathWithMetrics| {
256        p.path
257            .iter()
258            .skip(1)
259            .take(p.path.len().saturating_sub(2))
260            .copied()
261            .collect::<Vec<_>>()
262    };
263
264    let take = |i: usize,
265                p: &PathWithMetrics,
266                taken: &mut Vec<bool>,
267                per_relayer: &mut std::collections::HashMap<OffchainPublicKey, usize>| {
268        taken[i] = true;
269        for relayer in later_relayers(p) {
270            *per_relayer.entry(relayer).or_default() += 1;
271        }
272    };
273
274    // First pass: one path per distinct first relayer, best (lowest-latency) first, with every
275    // later relayer under the cap.
276    for (i, p) in sorted.iter().enumerate() {
277        if count == n {
278            break;
279        }
280        let Some(first) = p.path.first() else { continue };
281        let under_cap = later_relayers(p)
282            .into_iter()
283            .all(|relayer| per_relayer.get(&relayer).copied().unwrap_or(0) < cap);
284        if !seen.contains(first) && under_cap {
285            seen.push(*first);
286            take(i, p, &mut taken, &mut per_relayer);
287            count += 1;
288        }
289    }
290
291    // Second pass: any path whose later relayers are still under the cap, best first.
292    for (i, p) in sorted.iter().enumerate() {
293        if count == n {
294            break;
295        }
296        if taken[i] {
297            continue;
298        }
299        let under_cap = later_relayers(p)
300            .into_iter()
301            .all(|relayer| per_relayer.get(&relayer).copied().unwrap_or(0) < cap);
302        if under_cap {
303            if let Some(first) = p.path.first()
304                && !seen.contains(first)
305            {
306                seen.push(*first);
307            }
308            take(i, p, &mut taken, &mut per_relayer);
309            count += 1;
310        }
311    }
312
313    // Third pass: over the cap, a first relayer not yet represented still comes before a second path
314    // from one that is. Losing a later relayer then costs what the cap could not bound, but losing a
315    // first relayer costs no more than its own share.
316    for (i, p) in sorted.iter().enumerate() {
317        if count == n {
318            break;
319        }
320        if taken[i] {
321            continue;
322        }
323        let Some(first) = p.path.first() else { continue };
324        if !seen.contains(first) {
325            seen.push(*first);
326            take(i, p, &mut taken, &mut per_relayer);
327            count += 1;
328        }
329    }
330
331    // Fourth pass: fill any remaining slots with the best of the rest.
332    for slot in taken.iter_mut() {
333        if count == n {
334            break;
335        }
336        if !*slot {
337            *slot = true;
338            count += 1;
339        }
340    }
341
342    sorted
343        .into_iter()
344        .zip(taken)
345        .filter_map(|(p, keep)| keep.then_some(p))
346        .collect()
347}
348
349/// Number of distinct first relayers across `paths`.
350///
351/// The first relayer is the only node the destination gets to pick when it uses a SURB, so this is
352/// the count that decides whether the return-path degradation detector has a sibling to corroborate
353/// against: a value of 1 is the blind spot where a dead relayer is indistinguishable from a quiet
354/// peer. Paths with no hops (`path` empty) contribute nothing — a 0-hop return has no relayer.
355pub(crate) fn distinct_first_relayers(paths: &[PathWithMetrics]) -> usize {
356    paths
357        .iter()
358        .filter_map(|p| p.path.first())
359        .collect::<std::collections::HashSet<_>>()
360        .len()
361}
362
363/// Compute candidate paths from `src` to `dest` through `graph`.
364///
365/// `length` is the number of edges to traverse (= intermediate hops + 1).
366/// `take` caps the number of candidate paths returned.
367/// The graph crate returns only the intermediate nodes (both `src` and `dest` stripped);
368/// this function re-appends `dest` so callers receive `([intermediates..., dest], cost)`.
369fn compute_paths<G, W>(
370    graph: &G,
371    src: &OffchainPublicKey,
372    dest: &OffchainPublicKey,
373    length: std::num::NonZeroUsize,
374    take: usize,
375    value_fn: MetricsValueFn<W>,
376) -> (Vec<PathWithMetrics>, usize)
377where
378    G: NetworkGraphTraverse<NodeId = OffchainPublicKey, Observed = W>,
379    W: EdgeObservableRead + Send + 'static,
380{
381    let raw = graph.simple_paths(src, dest, length.get(), Some(take), value_fn);
382
383    let returned = raw.len();
384    let paths = raw
385        .into_iter()
386        .filter_map(|(path, _, metrics)| {
387            tracing::trace!(?path, cost = metrics.cost, "evaluating candidate path");
388            if metrics.cost > 0.0 {
389                let mut path = path;
390                path.push(*dest);
391                Some(PathWithMetrics::from((metrics, path)))
392            } else {
393                None
394            }
395        })
396        .collect();
397    (paths, returned)
398}
399
400/// Continues a fold that an earlier traversal started: it starts from `initial` and hands the
401/// wrapped function each edge's index shifted by `offset`.
402///
403/// A traversal from a path's second node, continued from the value after its first edge with an
404/// offset of one, costs every edge exactly as one traversal from the first node would: the value
405/// functions read an edge's position in the whole path, and that is what they are given.
406struct ContinuedValueFn<V, W> {
407    value_fn: BasicValueFn<V, W>,
408    initial: V,
409    min: Option<V>,
410    offset: usize,
411}
412
413impl<V, W> ValueFn for ContinuedValueFn<V, W>
414where
415    V: Clone + PartialOrd + Send + Sync + 'static,
416    W: EdgeObservableRead + Send + 'static,
417{
418    type Value = V;
419    type Weight = W;
420
421    fn initial_value(&self) -> Self::Value {
422        self.initial.clone()
423    }
424
425    fn min_value(&self) -> Option<Self::Value> {
426        self.min.clone()
427    }
428
429    fn into_value_fn(self) -> BasicValueFn<Self::Value, Self::Weight> {
430        let (value_fn, offset) = (self.value_fn, self.offset);
431        Arc::new(move |value, observed, index| value_fn(value, observed, index + offset))
432    }
433}
434
435/// How many times [`search_share`] searches one first relayer's continuations at most.
436///
437/// Each search asks for twice as many as the last, so the last asks for eight times the share,
438/// and all of them together find fewer paths than twice the last.
439const SHARE_SEARCHES: u32 = 4;
440
441/// One first relayer's continuations for its share of the pool.
442///
443/// Some continuations are unusable and dropped from the share: those of no value, and those that
444/// run through the source, which the single traversal from the source never returns but one that
445/// starts past it can. They must not take the places of usable ones, so while too few of the paths
446/// a search found are usable, the search is asked again for twice as many. The traversal shuffles
447/// each node's edges, so every search is a fresh draw that keeps what it found first.
448///
449/// Returns the paths of the first search that found `share` usable, or every continuation there
450/// is, or else those of the last of [`SHARE_SEARCHES`] searches. Doubling bounds the work where
451/// nearly every continuation is unusable, as in a subtree that reaches the destination only past
452/// the source: such a share stays short rather than paying a search per continuation.
453fn search_share<P>(share: usize, unusable: impl Fn(&P) -> bool, mut search: impl FnMut(usize) -> Vec<P>) -> Vec<P> {
454    let mut limit = share;
455    let mut searches = 1;
456    loop {
457        let found = search(limit);
458        let usable = found.iter().filter(|path| !unusable(path)).count();
459        if found.len() < limit || usable >= share {
460            return found;
461        }
462        if searches == SHARE_SEARCHES {
463            tracing::debug!(share, limit, usable, "share left short: most continuations unusable");
464            return found;
465        }
466        searches += 1;
467        limit = limit.saturating_mul(2);
468    }
469}
470
471/// Candidate paths from `src` to `dest`, spread evenly over `src`'s first relayers.
472///
473/// The traversal is depth-first and `take` keeps the paths it finds first, so a single traversal
474/// returns the whole subtree of one first relayer before it reaches the next. Over seven relayers
475/// a three-hop subtree holds 30 paths, so 50 candidates named one or two first relayers, and
476/// every path drawn until the next refresh went through them. Pruning for distinct first relayers
477/// cannot restore what the pool never held: a return pool of one first relayer put a Session's
478/// whole SURB stock behind it, and when that relayer died nothing the Exit sent got home.
479///
480/// So the first edges are found once, and each first relayer's continuations are searched
481/// separately within an even share of `take`, continued from the value after the first edge so
482/// that each path costs exactly what the single traversal would have made it cost. The shares
483/// are interleaved, so a pool cut short at `take` still keeps every first relayer.
484/// Returns the pool and the total number of continuations returned by all searches, including
485/// retries, before filtering and limiting each share or the pool.
486fn compute_paths_spread<G, W>(
487    graph: &G,
488    src: &OffchainPublicKey,
489    dest: &OffchainPublicKey,
490    length: std::num::NonZeroUsize,
491    take: usize,
492    value_fn: MetricsValueFn<W>,
493) -> (Vec<PathWithMetrics>, usize)
494where
495    G: NetworkGraphTraverse<NodeId = OffchainPublicKey, Observed = W>,
496    W: EdgeObservableRead + Send + 'static,
497{
498    // A direct path has no relayer to spread over.
499    if length.get() < 2 {
500        return compute_paths(graph, src, dest, length, take, value_fn);
501    }
502
503    let initial = value_fn.initial_value();
504    let min = value_fn.min_value();
505    let value_fn = value_fn.into_value_fn();
506
507    // Every first edge the full traversal would take, with the value after it: the minimum
508    // prunes here exactly as it does there.
509    let firsts = graph
510        .simple_paths_from(
511            src,
512            1,
513            None,
514            ContinuedValueFn {
515                value_fn: value_fn.clone(),
516                initial,
517                min: min.clone(),
518                offset: 0,
519            },
520        )
521        .into_iter()
522        .filter_map(|(nodes, _, after_first)| match nodes.as_slice() {
523            [first] if first != dest && first != src => Some((*first, after_first)),
524            _ => None,
525        })
526        .collect::<Vec<_>>();
527
528    if firsts.is_empty() {
529        return (Vec::new(), 0);
530    }
531
532    let share = take.div_ceil(firsts.len()).max(1);
533    let mut returned = 0;
534    let mut per_first = firsts
535        .into_iter()
536        .map(|(first, after_first)| {
537            let continuations = |limit| {
538                let found = graph.simple_paths(
539                    &first,
540                    dest,
541                    length.get() - 1,
542                    Some(limit),
543                    ContinuedValueFn {
544                        value_fn: value_fn.clone(),
545                        initial: after_first.clone(),
546                        min: min.clone(),
547                        offset: 1,
548                    },
549                );
550                returned += found.len();
551                found
552            };
553            // The continuations of no value or through `src`: `search_share` does not count them toward the
554            // share, and the pool drops them. One predicate for both, so the two cannot disagree.
555            let unusable = |(rest, _, metrics): &(Vec<OffchainPublicKey>, _, PathCostWithMetrics)| {
556                metrics.cost <= 0.0 || rest.contains(src)
557            };
558            search_share(share, unusable, continuations)
559                .into_iter()
560                .filter_map(move |continuation| {
561                    if unusable(&continuation) {
562                        return None;
563                    }
564                    let (rest, _, metrics) = continuation;
565                    let mut path = Vec::with_capacity(rest.len() + 2);
566                    path.push(first);
567                    path.extend(rest);
568                    path.push(*dest);
569                    tracing::trace!(?path, cost = metrics.cost, "evaluating candidate path");
570                    Some(PathWithMetrics::from((metrics, path)))
571                })
572                .take(share)
573                .collect::<Vec<_>>()
574                .into_iter()
575        })
576        .collect::<Vec<_>>();
577
578    // Sized by what the searches found: `take` is a configured bound, not a size.
579    let found = per_first.iter().map(|paths| paths.len()).sum::<usize>();
580    let mut spread = Vec::with_capacity(take.min(found));
581    while spread.len() < take {
582        let before = spread.len();
583        for paths in per_first.iter_mut() {
584            if spread.len() == take {
585                break;
586            }
587            spread.extend(paths.next());
588        }
589        if spread.len() == before {
590            break;
591        }
592    }
593    (spread, returned)
594}
595
596/// A lightweight graph-backed path selector.
597///
598/// Returns all candidate paths for a `(src, dest, hops)` query directly from
599/// the network graph — no caching is performed here.  The caller (typically
600/// [`crate::path::planner::PathPlanner`]) is responsible for caching, TTL management,
601/// background refresh, and final path selection.
602///
603/// Stores the planner's own identity (`me`) so that it can choose the
604/// appropriate cost function:
605/// - forward path (`src == me`): [`EdgeValueFn::forward`]
606/// - return path (`dest == me`): [`EdgeValueFn::returning`]
607#[derive(Clone)]
608pub struct HoprGraphPathSelector<G> {
609    me: OffchainPublicKey,
610    graph: G,
611    max_paths: usize,
612    edge_penalty: f64,
613    min_ack_rate: f64,
614    anonymity_floor: usize,
615    observer: Option<TransportObserver>,
616}
617
618impl<G> HoprGraphPathSelector<G>
619where
620    G: NetworkGraphTraverse<NodeId = OffchainPublicKey>
621        + NetworkGraphView<NodeId = OffchainPublicKey>
622        + Clone
623        + Send
624        + Sync
625        + 'static,
626    <G as NetworkGraphTraverse>::Observed: EdgeObservableRead + Send + 'static,
627{
628    /// Create a new selector.
629    ///
630    /// * `me` – the planner's own offchain public key, used to determine path direction.
631    /// * `graph` – the network graph to query.
632    /// * `max_paths` – maximum number of candidate paths to return per query.
633    /// * `edge_penalty` – penalty multiplier for edges lacking probe-based quality observations.
634    /// * `min_ack_rate` – minimum acceptable message acknowledgment rate for path selection.
635    /// * `anonymity_floor` – minimum candidate count below which no latency-based pruning occurs.
636    pub fn new(
637        me: OffchainPublicKey,
638        graph: G,
639        max_paths: usize,
640        edge_penalty: f64,
641        min_ack_rate: f64,
642        anonymity_floor: usize,
643    ) -> Self {
644        Self {
645            me,
646            graph,
647            max_paths,
648            edge_penalty,
649            min_ack_rate,
650            anonymity_floor,
651            observer: None,
652        }
653    }
654
655    /// Report graph searches to `observer`. Attach it before the selector is shared.
656    pub fn with_observer(mut self, observer: TransportObserver) -> Self {
657        self.observer = Some(observer);
658        self
659    }
660
661    /// Extended forward path search: find shorter paths using
662    /// [`EdgeValueFn::forward_without_self_loopback`] and append `dest` to each one.
663    ///
664    /// This handles the case where the last edge (relay -> dest) has no graph edge
665    /// (e.g. no payment channel) but the path planner can still assume the last hop
666    /// is reachable. Paths already found by Phase 1 are excluded via `existing`.
667    ///
668    /// The cost from the shorter traversal is preserved as-is — the missing last
669    /// edge contributes a neutral `1.0` multiplier (no quality data available).
670    fn compute_extended_forward_paths(
671        &self,
672        src: &OffchainPublicKey,
673        dest: &OffchainPublicKey,
674        shorter_length: std::num::NonZeroUsize,
675        take: usize,
676        existing: &[PathWithMetrics],
677        // The caller's snapshot, so both phases of one query cost against the same face value.
678        ticket_face_value: Option<hopr_api::graph::traits::Balance>,
679    ) -> (Vec<PathWithMetrics>, usize) {
680        // `forward_without_self_loopback` counts the *finished* path length — the one that includes
681        // the `dest` edge appended below — not the shorter traversal depth. Passing the search depth
682        // understates it by one: for a 1-hop path it collapses `length` to 1, so the first
683        // (monetized) edge is funding-checked with zero remaining hops, waiving the check and
684        // selecting a channel that cannot fund the first-hop ticket (GNO-805). Search `shorter_length`
685        // edges, but cost them against the finished length.
686        let finished_length = shorter_length.saturating_add(1);
687        let value_fn = MetricsValueFn {
688            inner: EdgeValueFn::forward_without_self_loopback(
689                finished_length,
690                self.edge_penalty,
691                self.min_ack_rate,
692                ticket_face_value,
693            ),
694            ticket_face_value,
695        };
696        let raw = self
697            .graph
698            .simple_paths_from(src, shorter_length.get(), Some(take), value_fn);
699
700        let returned = raw.len();
701        let paths = raw
702            .into_iter()
703            .filter_map(|(path, _, metrics)| {
704                if metrics.cost <= 0.0 {
705                    return None;
706                }
707
708                // The graph crate already strips `src`; `path` is [intermediates…, terminator].
709                // Guard: if dest already appears as an intermediate or terminator, appending it
710                // would produce a non-adjacent duplicate that ValidatedPath::new rejects — skip early.
711                if path.contains(dest) {
712                    return None;
713                }
714                let mut candidate = path;
715                candidate.push(*dest);
716
717                // The missing last edge is assumed reachable only while the graph has no word on it. An
718                // edge it has measured dead (a score of exactly 0, which is how it reads a starved edge)
719                // is not missing, and adding the relay back would fill the floor with a path that
720                // delivers nothing, at a better cost than the healthy ones.
721                if let [.., relay, _] = candidate.as_slice()
722                    && self.graph.edge(relay, dest).and_then(|obs| obs.score()) == Some(0.0)
723                {
724                    return None;
725                }
726
727                if existing.iter().any(|pwm| pwm.path == candidate) {
728                    return None;
729                }
730
731                tracing::trace!(?candidate, cost = metrics.cost, "extended forward path candidate");
732                Some(PathWithMetrics::from((metrics, candidate)))
733            })
734            .take(take)
735            .collect();
736        (paths, returned)
737    }
738}
739
740impl<G> PathSelector for HoprGraphPathSelector<G>
741where
742    G: NetworkGraphTraverse<NodeId = OffchainPublicKey>
743        + NetworkGraphView<NodeId = OffchainPublicKey>
744        + Clone
745        + Send
746        + Sync
747        + 'static,
748    <G as NetworkGraphTraverse>::Observed: EdgeObservableRead + Send + 'static,
749{
750    /// Return all candidate paths from `src` to `dest` via `hops` relays.
751    ///
752    /// Each returned tuple contains a path `Vec<OffchainPublicKey>` of length
753    /// `hops + 1` (`[intermediates..., dest]`; `src` excluded) paired with its
754    /// accumulated traversal cost and per-path quality aggregates.
755    ///
756    /// Returns `Err(PathNotFound)` when the graph yields no positive-cost paths.
757    ///
758    /// The function has a potential to run expensive operations, it should be benchmarked
759    /// in a production environment and possibly guarded (e.g. by offloading the long execution
760    /// in an async executor to avoid blocking the caller).
761    #[tracing::instrument(
762        name = "selector.select_paths", level = "trace", skip_all,
763        fields(src = %src, dest = %dest, hops = hops, direction = if src == self.me { "forward" } else { "return" }),
764        ret, err(level = "trace")
765    )]
766    fn select_path(
767        &self,
768        src: OffchainPublicKey,
769        dest: OffchainPublicKey,
770        hops: usize,
771    ) -> Result<Vec<PathWithMetrics>> {
772        let direction = if src == self.me { "forward" } else { "return" };
773        tracing::trace!(%src, %dest, hops, direction, "computing paths from graph");
774
775        let length = std::num::NonZeroUsize::new(hops + 1)
776            .expect("can never fail, it is physically at least 1 after the addition");
777
778        // One read for the whole query. A concurrent `set_ticket_face_value` between two reads
779        // would let the traversal cost and the fundable-ticket floor come from different snapshots
780        // of the same graph, so `composite_weight` would rank a candidate against itself.
781        let ticket_face_value = self.graph.ticket_face_value();
782
783        let phase1;
784        let mut phase2 = None;
785        let paths = if src == self.me {
786            // Phase 1: search for full-length forward paths to dest.
787            let (mut found, returned) = compute_paths_spread(
788                &self.graph,
789                &src,
790                &dest,
791                length,
792                self.max_paths,
793                MetricsValueFn {
794                    inner: EdgeValueFn::forward(length, self.edge_penalty, self.min_ack_rate, ticket_face_value),
795                    ticket_face_value,
796                },
797            );
798            phase1 = PhaseCounts {
799                returned: returned as u64,
800                eligible: found.len() as u64,
801            };
802            tracing::trace!(
803                direction,
804                phase = 1,
805                count = found.len(),
806                "[forward] phase 1 candidates"
807            );
808
809            // Phase 2: if not enough paths, do an extended search with EdgeValueFn::forward_without_self_loopback
810            // for (length - 1) edges and assume the last hop can be done by anybody.
811            if found.len() < self.max_paths
812                && let Some(shorter) = std::num::NonZeroUsize::new(length.get() - 1)
813            {
814                let remaining = self.max_paths - found.len();
815                let (extended, returned) =
816                    self.compute_extended_forward_paths(&src, &dest, shorter, remaining, &found, ticket_face_value);
817                phase2 = Some(PhaseCounts {
818                    returned: returned as u64,
819                    eligible: extended.len() as u64,
820                });
821                tracing::trace!(
822                    direction,
823                    phase = 2,
824                    count = extended.len(),
825                    "[forward] phase 2 extended candidates"
826                );
827                found.extend(extended);
828            }
829
830            found
831        } else {
832            let (found, returned) = compute_paths_spread(
833                &self.graph,
834                &src,
835                &dest,
836                length,
837                self.max_paths,
838                MetricsValueFn {
839                    inner: EdgeValueFn::returning(length, self.edge_penalty, self.min_ack_rate, ticket_face_value),
840                    ticket_face_value,
841                },
842            );
843            phase1 = PhaseCounts {
844                returned: returned as u64,
845                eligible: found.len() as u64,
846            };
847            tracing::trace!(direction, count = found.len(), "[return] candidates");
848            found
849        };
850
851        for (i, pwm) in paths.iter().enumerate() {
852            tracing::trace!(
853                direction,
854                index = i,
855                path = ?pwm.path,
856                cost = pwm.cost,
857                total_latency_ms = ?pwm.total_latency_ms,
858                "[{direction}] candidate path"
859            );
860        }
861
862        let pruned = prune_for_consistency(paths, self.anonymity_floor, hops);
863        if let Some(observer) = &self.observer {
864            let (direction, destination) = if src == self.me {
865                (PathDirection::Forward, dest)
866            } else {
867                (PathDirection::Return, src)
868            };
869            observer(TransportEvent::PathSearched {
870                direction,
871                destination: hopr_api::types::internal::NodeId::Offchain(destination),
872                phase1,
873                phase2,
874                retained: pruned.len() as u64,
875            });
876        }
877        if pruned.is_empty() {
878            return Err(PathPlannerError::Path(PathError::PathNotFound(
879                hops,
880                src.to_string(),
881                dest.to_string(),
882            )));
883        }
884        if tracing::enabled!(tracing::Level::TRACE) {
885            let relayer_set = pruned
886                .iter()
887                .filter_map(|p| p.path.first())
888                .collect::<std::collections::HashSet<_>>();
889            tracing::trace!(
890                %src,
891                %dest,
892                hops,
893                direction,
894                survived = pruned.len(),
895                distinct_relayers = relayer_set.len(),
896                first_relayers = ?relayer_set,
897                "pruned candidate paths",
898            );
899        }
900        Ok(pruned)
901    }
902}
903
904#[cfg(test)]
905mod tests {
906    use std::time::Duration;
907
908    use anyhow::Context;
909    use hex_literal::hex;
910    use hopr_api::{
911        graph::{
912            NetworkGraphUpdate, NetworkGraphWrite,
913            traits::{EdgeObservableWrite, EdgeWeightType},
914        },
915        types::{
916            crypto::prelude::{Keypair, OffchainKeypair},
917            internal::routing::RoutingOptions,
918        },
919    };
920    use hopr_network_graph::ChannelGraph;
921
922    use super::*;
923    use crate::path::{PathPlannerConfig, traits::PathSelector};
924
925    fn test_selector(
926        me: OffchainPublicKey,
927        graph: ChannelGraph,
928        max_paths: usize,
929    ) -> HoprGraphPathSelector<ChannelGraph> {
930        let cfg = PathPlannerConfig::default();
931        HoprGraphPathSelector::new(
932            me,
933            graph,
934            max_paths,
935            cfg.edge_penalty,
936            cfg.min_ack_rate,
937            cfg.min_paths_anonymity_floor,
938        )
939    }
940
941    const SECRET_0: [u8; 32] = hex!("60741b83b99e36aa0c1331578156e16b8e21166d01834abb6c64b103f885734d");
942    const SECRET_1: [u8; 32] = hex!("71bf1f42ebbfcd89c3e197a3fd7cda79b92499e509b6fefa0fe44d02821d146a");
943    const SECRET_2: [u8; 32] = hex!("c24bd833704dd2abdae3933fcc9962c2ac404f84132224c474147382d4db2299");
944    const SECRET_3: [u8; 32] = hex!("e0bf93e9c916104da00b1850adc4608bd7e9087bbd3f805451f4556aa6b3fd6e");
945    const SECRET_4: [u8; 32] = hex!("cfc66f718ec66fb822391775d749d7a0d66b690927673634816b63339bc12a3c");
946
947    const MAX_PATHS: usize = 4;
948
949    fn pubkey(secret: &[u8; 32]) -> OffchainPublicKey {
950        *OffchainKeypair::from_secret(secret).expect("valid secret").public()
951    }
952
953    /// Mark an edge as fully ready for intermediate routing.
954    fn mark_edge_full(graph: &ChannelGraph, src: &OffchainPublicKey, dst: &OffchainPublicKey) {
955        graph.upsert_edge(src, dst, |obs| {
956            obs.record(EdgeWeightType::Connected(true));
957            obs.record(EdgeWeightType::Immediate(Ok(Duration::from_millis(50))));
958            obs.record(EdgeWeightType::Intermediate(Ok(Duration::from_millis(50))));
959            obs.record(EdgeWeightType::Balance(Some(hopr_api::graph::traits::Balance::from(
960                1000u64,
961            ))));
962        });
963    }
964
965    /// An edge that pings and has a funded channel, with no loopback evidence yet.
966    fn mark_edge_unlooped(graph: &ChannelGraph, src: &OffchainPublicKey, dst: &OffchainPublicKey) {
967        graph.upsert_edge(src, dst, |obs| {
968            obs.record(EdgeWeightType::Connected(true));
969            obs.record(EdgeWeightType::Immediate(Ok(Duration::from_millis(50))));
970            obs.record(EdgeWeightType::Balance(Some(hopr_api::graph::traits::Balance::from(
971                1000u64,
972            ))));
973        });
974    }
975
976    // Helper: build a bidirectional 2-hop graph: me ↔ hop ↔ dest.
977    fn two_hop_graph() -> (OffchainPublicKey, OffchainPublicKey, OffchainPublicKey, ChannelGraph) {
978        let me = pubkey(&SECRET_0);
979        let hop = pubkey(&SECRET_1);
980        let dest = pubkey(&SECRET_2);
981        let graph = ChannelGraph::new(me);
982        graph.add_node(hop);
983        graph.add_node(dest);
984        // Forward: me → hop → dest
985        graph.add_edge(&me, &hop).unwrap();
986        graph.add_edge(&hop, &dest).unwrap();
987        mark_edge_full(&graph, &me, &hop);
988        mark_edge_full(&graph, &hop, &dest);
989        // Reverse: dest → hop → me
990        graph.add_edge(&dest, &hop).unwrap();
991        graph.add_edge(&hop, &me).unwrap();
992        mark_edge_full(&graph, &dest, &hop);
993        mark_edge_full(&graph, &hop, &me);
994        (me, hop, dest, graph)
995    }
996
997    /// The extended search that fills up the anonymity floor appends the destination to each relay it
998    /// finds without looking at the edge into it. A relay whose edge into the destination the graph has
999    /// judged dead must not come back through it: the floor is never a minimum to fabricate.
1000    #[tokio::test]
1001    async fn the_floor_should_not_bring_back_a_relay_whose_edge_into_the_destination_is_dead() -> anyhow::Result<()> {
1002        let me = pubkey(&SECRET_0);
1003        let good = pubkey(&SECRET_1);
1004        let bad1 = pubkey(&SECRET_2);
1005        let bad2 = pubkey(&SECRET_3);
1006        let dest = pubkey(&hex!(
1007            "b1c3ec2e9a3b1d5b7f0b5c3a8f3e0d6c4a2b1e0f9d8c7b6a59483726150f4e3d"
1008        ));
1009
1010        let graph = ChannelGraph::new(me);
1011        for node in [good, bad1, bad2, dest] {
1012            graph.add_node(node);
1013        }
1014        graph.set_ticket_face_value(hopr_api::graph::traits::Balance::one());
1015        for relay in [good, bad1, bad2] {
1016            graph.add_edge(&me, &relay)?;
1017            mark_edge_full(&graph, &me, &relay);
1018            graph.add_edge(&relay, &dest)?;
1019        }
1020        mark_edge_full(&graph, &good, &dest);
1021        for bad in [bad1, bad2] {
1022            mark_edge_unlooped(&graph, &bad, &dest);
1023        }
1024        // Loops over the edge into the destination: they return for `good`, never for the others.
1025        for _ in 0..5 {
1026            graph.upsert_edge(&good, &dest, |obs| {
1027                obs.record(EdgeWeightType::Intermediate(Ok(Duration::from_millis(30))));
1028            });
1029            for bad in [bad1, bad2] {
1030                graph.upsert_edge(&bad, &dest, |obs| {
1031                    obs.record(EdgeWeightType::Intermediate(Err(())));
1032                });
1033            }
1034        }
1035
1036        // Fewer routable candidates than the floor, so the extended search runs.
1037        let selector = test_selector(me, graph.clone(), 8);
1038        let paths = selector.select_path(me, dest, 1).context("forward path")?;
1039
1040        assert!(
1041            paths.iter().any(|pwm| pwm.path.contains(&good)),
1042            "the healthy relay must stay a candidate"
1043        );
1044        assert!(
1045            !paths
1046                .iter()
1047                .any(|pwm| pwm.path.contains(&bad1) || pwm.path.contains(&bad2)),
1048            "a relay whose edge into the destination is dead must not be added to fill the floor, got {} candidates",
1049            paths.len()
1050        );
1051        Ok(())
1052    }
1053
1054    /// A relay that rejects our packets still answers pings and acks, so the first edge to it reads
1055    /// healthy everywhere except in the loopbacks routed through it, none of which return.
1056    #[tokio::test]
1057    async fn a_first_relay_whose_loopbacks_never_return_should_be_excluded_for_one_to_three_hops() -> anyhow::Result<()>
1058    {
1059        let me = pubkey(&SECRET_0);
1060        let good = pubkey(&SECRET_1);
1061        let bad = pubkey(&SECRET_2);
1062        let m1 = pubkey(&SECRET_3);
1063        let m2 = pubkey(&SECRET_4);
1064        let dest = pubkey(&hex!(
1065            "b1c3ec2e9a3b1d5b7f0b5c3a8f3e0d6c4a2b1e0f9d8c7b6a59483726150f4e3d"
1066        ));
1067
1068        let graph = ChannelGraph::new(me);
1069        for node in [good, bad, m1, m2, dest] {
1070            graph.add_node(node);
1071        }
1072        // me → good|bad → dest (1 hop), → m1 → dest (2 hops), → m1 → m2 → dest (3 hops)
1073        for (src, dst) in [
1074            (good, dest),
1075            (bad, dest),
1076            (good, m1),
1077            (bad, m1),
1078            (m1, dest),
1079            (m1, m2),
1080            (m2, dest),
1081            (me, good),
1082        ] {
1083            graph.add_edge(&src, &dst)?;
1084            mark_edge_full(&graph, &src, &dst);
1085        }
1086        graph.add_edge(&me, &bad)?;
1087        mark_edge_unlooped(&graph, &me, &bad);
1088
1089        let selector = test_selector(me, graph.clone(), 50);
1090        let costs = |hops: usize| -> anyhow::Result<(Vec<f64>, Vec<f64>)> {
1091            let paths = selector.select_path(me, dest, hops).context("forward path")?;
1092            let (through, around): (Vec<_>, Vec<_>) = paths.into_iter().partition(|pwm| pwm.path.contains(&bad));
1093            Ok((
1094                through.into_iter().map(|pwm| pwm.cost).collect(),
1095                around.into_iter().map(|pwm| pwm.cost).collect(),
1096            ))
1097        };
1098
1099        for hops in 1..=3 {
1100            let (through, around) = costs(hops)?;
1101            assert!(
1102                !through.is_empty() && !around.is_empty(),
1103                "{hops} hop(s): both relays must be candidates before any loop is seen"
1104            );
1105        }
1106
1107        // 5 loops through the first relay, none returned.
1108        graph.upsert_edge(&me, &bad, |obs| {
1109            for _ in 0..5 {
1110                obs.record(EdgeWeightType::Intermediate(Err(())));
1111            }
1112        });
1113
1114        // Excluded from routing (RFC-0010 4.2.3, the active tier); probing still reaches it.
1115        for hops in 1..=3 {
1116            let (through, around) = costs(hops)?;
1117            assert!(
1118                through.is_empty(),
1119                "{hops} hop(s): a relay whose loops never return must not be a candidate, got {through:?}"
1120            );
1121            assert!(
1122                !around.is_empty() && around.iter().all(|cost| *cost > 0.0),
1123                "{hops} hop(s): the honest relay must stay routable"
1124            );
1125        }
1126        Ok(())
1127    }
1128
1129    /// On a return path `dest → relay → me`, the edge into the relay is judged and the edge into `me`
1130    /// is not: a relay that rejects packets shows it on the first, and the last leads to the receiver.
1131    #[tokio::test]
1132    async fn a_return_relay_should_be_excluded_when_loopbacks_fail_on_the_edge_into_it() -> anyhow::Result<()> {
1133        let me = pubkey(&SECRET_0);
1134        let good = pubkey(&SECRET_1);
1135        let bad = pubkey(&SECRET_2);
1136        let dest = pubkey(&hex!(
1137            "b1c3ec2e9a3b1d5b7f0b5c3a8f3e0d6c4a2b1e0f9d8c7b6a59483726150f4e3d"
1138        ));
1139
1140        // Costs of the return paths through `bad` and around it, after loops failed over one edge of `bad`.
1141        let costs = |failed: (OffchainPublicKey, OffchainPublicKey)| -> anyhow::Result<(Vec<f64>, Vec<f64>)> {
1142            let graph = ChannelGraph::new(me);
1143            for node in [good, bad, dest] {
1144                graph.add_node(node);
1145            }
1146            for (src, dst) in [(dest, good), (good, me), (dest, bad), (bad, me)] {
1147                graph.add_edge(&src, &dst)?;
1148                if (src, dst) == failed {
1149                    // No loop returned over the edge, so the 5 below are all it has seen.
1150                    mark_edge_unlooped(&graph, &src, &dst);
1151                } else {
1152                    mark_edge_full(&graph, &src, &dst);
1153                }
1154            }
1155            graph.upsert_edge(&failed.0, &failed.1, |obs| {
1156                for _ in 0..5 {
1157                    obs.record(EdgeWeightType::Intermediate(Err(())));
1158                }
1159            });
1160            let paths = test_selector(me, graph, 50)
1161                .select_path(dest, me, 1)
1162                .context("return path")?;
1163            let (through, around): (Vec<_>, Vec<_>) = paths.into_iter().partition(|pwm| pwm.path.contains(&bad));
1164            Ok((
1165                through.into_iter().map(|pwm| pwm.cost).collect(),
1166                around.into_iter().map(|pwm| pwm.cost).collect(),
1167            ))
1168        };
1169
1170        // A loop that fails blames the edge into the relay, and that is what excludes it.
1171        let (through, around) = costs((dest, bad))?;
1172        assert!(
1173            through.is_empty(),
1174            "a failed edge into the relay must exclude it, got {through:?}"
1175        );
1176        assert!(
1177            !around.is_empty() && around.iter().all(|cost| *cost > 0.0),
1178            "the honest relay must stay routable"
1179        );
1180        Ok(())
1181    }
1182
1183    /// A relay that rejects our packets answers fast, so after the value function starves it, a latency-ordered
1184    /// pruning must not hand its slots to the starved paths. Layered graph of three relays per layer, every layer
1185    /// pair connected, and the dead relay in layer `position` being the one the failed loopbacks are on.
1186    /// Healthy paths outnumber the anonymity floor, so none of the kept paths may go through the dead relay.
1187    #[tokio::test]
1188    async fn a_fast_dead_relay_should_not_keep_a_slot_after_pruning_for_zero_to_three_hops_in_both_directions()
1189    -> anyhow::Result<()> {
1190        const FLOOR: usize = 2;
1191        let me = pubkey(&[1; 32]);
1192        let dest = pubkey(&[2; 32]);
1193        let relay = |layer: usize, index: usize| pubkey(&[10 + (layer * 3 + index) as u8; 32]);
1194
1195        // 0 hops has no relay to judge: the direct route stays.
1196        for direction in ["forward", "return"] {
1197            let graph = ChannelGraph::new(me);
1198            graph.add_node(dest);
1199            let (src, dst) = if direction == "forward" { (me, dest) } else { (dest, me) };
1200            graph.add_edge(&src, &dst)?;
1201            mark_edge_full(&graph, &src, &dst);
1202            let paths = test_selector(me, graph, 50)
1203                .select_path(src, dst, 0)
1204                .context("direct path")?;
1205            assert_eq!(paths.len(), 1, "{direction}, 0 hops: the direct route must stay");
1206        }
1207
1208        let mut failures = Vec::new();
1209        for direction in ["forward", "return"] {
1210            for hops in 1..=3usize {
1211                for position in 1..=hops {
1212                    let graph = ChannelGraph::new(me);
1213                    // A node always knows the ticket price, and without it no path counts as fully measured.
1214                    graph.set_ticket_face_value(hopr_api::graph::traits::Balance::one());
1215                    graph.add_node(dest);
1216                    for layer in 1..=hops {
1217                        for index in 0..3 {
1218                            graph.add_node(relay(layer, index));
1219                        }
1220                    }
1221                    // Layer 0 is the sender, layer `hops + 1` the receiver.
1222                    let (sender, receiver) = if direction == "forward" { (me, dest) } else { (dest, me) };
1223                    let dead = relay(position, 0);
1224                    let node = |layer: usize, index: usize| match layer {
1225                        0 => sender,
1226                        l if l == hops + 1 => receiver,
1227                        l => relay(l, index),
1228                    };
1229                    for layer in 0..=hops {
1230                        for from in 0..if layer == 0 { 1 } else { 3 } {
1231                            for to in 0..if layer == hops { 1 } else { 3 } {
1232                                let (src, dst) = (node(layer, from), node(layer + 1, to));
1233                                graph.add_edge(&src, &dst)?;
1234                                if dst == dead {
1235                                    mark_edge_unlooped(&graph, &src, &dst);
1236                                } else {
1237                                    mark_edge_full(&graph, &src, &dst);
1238                                }
1239                            }
1240                        }
1241                    }
1242                    // The dead relay answers faster than the healthy ones, and none of its loops return.
1243                    for from in 0..if position == 1 { 1 } else { 3 } {
1244                        graph.upsert_edge(&node(position - 1, from), &dead, |obs| {
1245                            obs.record(EdgeWeightType::Immediate(Ok(Duration::from_millis(5))));
1246                            for _ in 0..5 {
1247                                obs.record(EdgeWeightType::Intermediate(Err(())));
1248                            }
1249                        });
1250                    }
1251
1252                    let selector = HoprGraphPathSelector::new(
1253                        me,
1254                        graph,
1255                        50,
1256                        PathPlannerConfig::default().edge_penalty,
1257                        PathPlannerConfig::default().min_ack_rate,
1258                        FLOOR,
1259                    );
1260                    let kept = selector.select_path(sender, receiver, hops).context("pruned paths")?;
1261                    let through_dead = kept.iter().filter(|pwm| pwm.path.contains(&dead)).count();
1262                    if kept.is_empty() || through_dead > 0 {
1263                        failures.push(format!(
1264                            "{direction}, {hops} hop(s), dead relay in position {position}: {through_dead} of {} kept \
1265                             paths run through the dead relay",
1266                            kept.len()
1267                        ));
1268                    }
1269                }
1270            }
1271        }
1272        assert!(failures.is_empty(), "{}", failures.join("\n"));
1273        Ok(())
1274    }
1275
1276    #[tokio::test]
1277    async fn unreachable_dest_should_return_error() -> anyhow::Result<()> {
1278        let me = pubkey(&SECRET_0);
1279        let unreachable = pubkey(&SECRET_1);
1280        let graph = ChannelGraph::new(me);
1281        // No edges at all — neither direction has a path.
1282        let selector = test_selector(me, graph, MAX_PATHS);
1283
1284        let fwd = selector.select_path(me, unreachable, 1);
1285        assert!(fwd.is_err(), "forward: should error when destination is unreachable");
1286        assert!(matches!(
1287            fwd.unwrap_err(),
1288            PathPlannerError::Path(PathError::PathNotFound(..))
1289        ));
1290
1291        let rev = selector.select_path(unreachable, me, 1);
1292        assert!(rev.is_err(), "reverse: should error when destination is unreachable");
1293        assert!(matches!(
1294            rev.unwrap_err(),
1295            PathPlannerError::Path(PathError::PathNotFound(..))
1296        ));
1297
1298        Ok(())
1299    }
1300
1301    #[tokio::test]
1302    async fn path_should_exclude_source() -> anyhow::Result<()> {
1303        let (me, _hop, dest, graph) = two_hop_graph();
1304        let selector = test_selector(me, graph, MAX_PATHS);
1305
1306        let fwd = selector.select_path(me, dest, 1).context("forward path")?;
1307        assert!(!fwd.is_empty());
1308        for pwm in &fwd {
1309            assert!(!pwm.path.contains(&me), "forward path must not contain the source");
1310            assert!(pwm.cost > 0.0, "cost must be positive");
1311        }
1312
1313        let rev = selector.select_path(dest, me, 1).context("reverse path")?;
1314        assert!(!rev.is_empty());
1315        for pwm in &rev {
1316            assert!(!pwm.path.contains(&dest), "reverse path must not contain the source");
1317            assert!(pwm.cost > 0.0, "cost must be positive");
1318        }
1319
1320        Ok(())
1321    }
1322
1323    #[tokio::test]
1324    async fn multi_hop_path_should_have_correct_length() -> anyhow::Result<()> {
1325        // Bidirectional: me ↔ A ↔ B ↔ dest  (2 intermediate hops each way)
1326        let me = pubkey(&SECRET_0);
1327        let a = pubkey(&SECRET_1);
1328        let b = pubkey(&SECRET_2);
1329        let dest = pubkey(&SECRET_3);
1330        let graph = ChannelGraph::new(me);
1331        for n in [a, b, dest] {
1332            graph.add_node(n);
1333        }
1334        // Forward: me → A → B → dest
1335        graph.add_edge(&me, &a).unwrap();
1336        graph.add_edge(&a, &b).unwrap();
1337        graph.add_edge(&b, &dest).unwrap();
1338        mark_edge_full(&graph, &me, &a);
1339        mark_edge_full(&graph, &a, &b);
1340        mark_edge_full(&graph, &b, &dest);
1341        // Reverse: dest → B → A → me
1342        graph.add_edge(&dest, &b).unwrap();
1343        graph.add_edge(&b, &a).unwrap();
1344        graph.add_edge(&a, &me).unwrap();
1345        mark_edge_full(&graph, &dest, &b);
1346        mark_edge_full(&graph, &b, &a);
1347        mark_edge_full(&graph, &a, &me);
1348
1349        let selector = test_selector(me, graph, MAX_PATHS);
1350
1351        let fwd = selector.select_path(me, dest, 2).context("forward 2-hop path")?;
1352        assert!(!fwd.is_empty());
1353        for pwm in &fwd {
1354            assert_eq!(pwm.path.len(), 3, "forward 2-hop path: [A, B, dest]");
1355            assert_eq!(pwm.path.last(), Some(&dest));
1356        }
1357
1358        let rev = selector.select_path(dest, me, 2).context("reverse 2-hop path")?;
1359        assert!(!rev.is_empty());
1360        for pwm in &rev {
1361            assert_eq!(pwm.path.len(), 3, "reverse 2-hop path: [B, A, me]");
1362            assert_eq!(pwm.path.last(), Some(&me));
1363        }
1364
1365        Ok(())
1366    }
1367
1368    #[tokio::test]
1369    async fn one_hop_path_should_include_relay_and_destination() -> anyhow::Result<()> {
1370        // Bidirectional: me ↔ relay ↔ dest
1371        let (me, relay, dest, graph) = two_hop_graph();
1372        let selector = test_selector(me, graph, MAX_PATHS);
1373
1374        let fwd = selector.select_path(me, dest, 1).context("forward 1-hop path")?;
1375        assert!(!fwd.is_empty());
1376        for pwm in &fwd {
1377            assert_eq!(pwm.path.len(), 2, "forward: [relay, dest]");
1378            assert_eq!(pwm.path.last(), Some(&dest));
1379            assert!(!pwm.path.contains(&me));
1380        }
1381
1382        let rev = selector.select_path(dest, me, 1).context("reverse 1-hop path")?;
1383        assert!(!rev.is_empty());
1384        for pwm in &rev {
1385            assert_eq!(pwm.path.len(), 2, "reverse: [relay, me]");
1386            assert_eq!(pwm.path.last(), Some(&me));
1387            assert!(!pwm.path.contains(&dest));
1388        }
1389
1390        let _ = relay;
1391        Ok(())
1392    }
1393
1394    #[tokio::test]
1395    async fn diamond_topology_should_return_multiple_paths() -> anyhow::Result<()> {
1396        // Bidirectional diamond: me ↔ a ↔ dest and me ↔ b ↔ dest
1397        let me = pubkey(&SECRET_0);
1398        let a = pubkey(&SECRET_1);
1399        let b = pubkey(&SECRET_2);
1400        let dest = pubkey(&SECRET_3);
1401        let graph = ChannelGraph::new(me);
1402        for n in [a, b, dest] {
1403            graph.add_node(n);
1404        }
1405        // Forward: me → a → dest,  me → b → dest
1406        graph.add_edge(&me, &a).unwrap();
1407        graph.add_edge(&me, &b).unwrap();
1408        graph.add_edge(&a, &dest).unwrap();
1409        graph.add_edge(&b, &dest).unwrap();
1410        mark_edge_full(&graph, &me, &a);
1411        mark_edge_full(&graph, &me, &b);
1412        mark_edge_full(&graph, &a, &dest);
1413        mark_edge_full(&graph, &b, &dest);
1414        // Reverse: dest → a → me,  dest → b → me
1415        graph.add_edge(&dest, &a).unwrap();
1416        graph.add_edge(&dest, &b).unwrap();
1417        graph.add_edge(&a, &me).unwrap();
1418        graph.add_edge(&b, &me).unwrap();
1419        mark_edge_full(&graph, &dest, &a);
1420        mark_edge_full(&graph, &dest, &b);
1421        mark_edge_full(&graph, &a, &me);
1422        mark_edge_full(&graph, &b, &me);
1423
1424        let selector = test_selector(me, graph, MAX_PATHS);
1425
1426        let fwd = selector.select_path(me, dest, 1).context("forward path")?;
1427        assert_eq!(fwd.len(), 2, "forward: both paths via a and b should be returned");
1428        for pwm in &fwd {
1429            assert_eq!(pwm.path.last(), Some(&dest));
1430        }
1431
1432        let rev = selector.select_path(dest, me, 1).context("reverse path")?;
1433        assert_eq!(rev.len(), 2, "reverse: both paths via a and b should be returned");
1434        for pwm in &rev {
1435            assert_eq!(pwm.path.last(), Some(&me));
1436        }
1437
1438        Ok(())
1439    }
1440
1441    #[tokio::test]
1442    async fn zero_cost_paths_should_return_error() -> anyhow::Result<()> {
1443        // Graph has edges in both directions but no observations → all costs zero → pruned.
1444        let me = pubkey(&SECRET_0);
1445        let dest = pubkey(&SECRET_1);
1446        let graph = ChannelGraph::new(me);
1447        graph.add_node(dest);
1448        graph.add_edge(&me, &dest).unwrap();
1449        graph.add_edge(&dest, &me).unwrap();
1450        // No observations → cost function will return non-positive cost → pruned.
1451
1452        let selector = test_selector(me, graph, MAX_PATHS);
1453        assert!(
1454            selector.select_path(me, dest, 1).is_err(),
1455            "forward: edge with no observations should produce no valid path"
1456        );
1457        assert!(
1458            selector.select_path(dest, me, 1).is_err(),
1459            "reverse: edge with no observations should produce no valid path"
1460        );
1461        Ok(())
1462    }
1463
1464    #[tokio::test]
1465    async fn no_path_at_requested_hop_count_should_return_error() -> anyhow::Result<()> {
1466        // Graph has direct edges both ways; requesting 2 hops should fail in both directions.
1467        let me = pubkey(&SECRET_0);
1468        let dest = pubkey(&SECRET_1);
1469        let graph = ChannelGraph::new(me);
1470        graph.add_node(dest);
1471        graph.add_edge(&me, &dest).unwrap();
1472        graph.add_edge(&dest, &me).unwrap();
1473        mark_edge_full(&graph, &me, &dest);
1474        mark_edge_full(&graph, &dest, &me);
1475
1476        let selector = test_selector(me, graph, MAX_PATHS);
1477        assert!(
1478            selector.select_path(me, dest, 2).is_err(),
1479            "forward: no 2-hop path should exist for a direct edge"
1480        );
1481        assert!(
1482            selector.select_path(dest, me, 2).is_err(),
1483            "reverse: no 2-hop path should exist for a direct edge"
1484        );
1485        Ok(())
1486    }
1487
1488    #[tokio::test]
1489    async fn forward_path_should_work_without_last_edge() -> anyhow::Result<()> {
1490        // In the real network, the last edge (relay → dest) may not have a
1491        // payment channel. The graph has me → relay but NO relay → dest edge.
1492        // The virtual last hop fallback should still find the forward path.
1493        let me = pubkey(&SECRET_0);
1494        let relay = pubkey(&SECRET_1);
1495        let dest = pubkey(&SECRET_2);
1496        let graph = ChannelGraph::new(me);
1497        graph.add_node(relay);
1498        graph.add_node(dest);
1499        // Forward: me → relay (fully observed). NO relay → dest edge.
1500        graph.add_edge(&me, &relay).unwrap();
1501        mark_edge_full(&graph, &me, &relay);
1502        // Reverse: dest → relay → me (both edges exist for the return path).
1503        graph.add_edge(&dest, &relay).unwrap();
1504        graph.add_edge(&relay, &me).unwrap();
1505        mark_edge_full(&graph, &dest, &relay);
1506        mark_edge_full(&graph, &relay, &me);
1507
1508        let selector = test_selector(me, graph, MAX_PATHS);
1509
1510        // Forward path should work via virtual last hop
1511        let fwd = selector
1512            .select_path(me, dest, 1)
1513            .context("forward path with virtual last hop")?;
1514        assert!(!fwd.is_empty(), "forward path should find at least one route");
1515        for pwm in &fwd {
1516            assert_eq!(pwm.path.len(), 2, "forward: [relay, dest]");
1517            assert_eq!(pwm.path[0], relay);
1518            assert_eq!(pwm.path[1], dest);
1519        }
1520
1521        // Return path should work normally (both edges exist)
1522        let rev = selector.select_path(dest, me, 1).context("return path")?;
1523        assert!(!rev.is_empty(), "return path should find at least one route");
1524        for pwm in &rev {
1525            assert_eq!(pwm.path.len(), 2, "return: [relay, me]");
1526            assert_eq!(pwm.path.last(), Some(&me));
1527        }
1528
1529        Ok(())
1530    }
1531
1532    #[tokio::test]
1533    async fn five_node_chain_should_support_max_hops() -> anyhow::Result<()> {
1534        // Bidirectional: me ↔ a ↔ b ↔ c ↔ dest  (3 intermediate hops each way)
1535        let me = pubkey(&SECRET_0);
1536        let a = pubkey(&SECRET_1);
1537        let b = pubkey(&SECRET_2);
1538        let c = pubkey(&SECRET_3);
1539        let dest = pubkey(&SECRET_4);
1540        let graph = ChannelGraph::new(me);
1541        for n in [a, b, c, dest] {
1542            graph.add_node(n);
1543        }
1544        // Forward: me → a → b → c → dest
1545        graph.add_edge(&me, &a).unwrap();
1546        graph.add_edge(&a, &b).unwrap();
1547        graph.add_edge(&b, &c).unwrap();
1548        graph.add_edge(&c, &dest).unwrap();
1549        mark_edge_full(&graph, &me, &a);
1550        mark_edge_full(&graph, &a, &b);
1551        mark_edge_full(&graph, &b, &c);
1552        mark_edge_full(&graph, &c, &dest);
1553        // Reverse: dest → c → b → a → me
1554        graph.add_edge(&dest, &c).unwrap();
1555        graph.add_edge(&c, &b).unwrap();
1556        graph.add_edge(&b, &a).unwrap();
1557        graph.add_edge(&a, &me).unwrap();
1558        mark_edge_full(&graph, &dest, &c);
1559        mark_edge_full(&graph, &c, &b);
1560        mark_edge_full(&graph, &b, &a);
1561        mark_edge_full(&graph, &a, &me);
1562
1563        let selector = test_selector(me, graph, MAX_PATHS);
1564
1565        let fwd = selector
1566            .select_path(me, dest, RoutingOptions::MAX_INTERMEDIATE_HOPS)
1567            .context("forward 3-hop path")?;
1568        assert!(!fwd.is_empty());
1569        for pwm in &fwd {
1570            assert_eq!(pwm.path.len(), 4, "forward: [a, b, c, dest]");
1571            assert_eq!(pwm.path.last(), Some(&dest));
1572            assert!(!pwm.path.contains(&me));
1573        }
1574
1575        let rev = selector
1576            .select_path(dest, me, RoutingOptions::MAX_INTERMEDIATE_HOPS)
1577            .context("reverse 3-hop path")?;
1578        assert!(!rev.is_empty());
1579        for pwm in &rev {
1580            assert_eq!(pwm.path.len(), 4, "reverse: [c, b, a, me]");
1581            assert_eq!(pwm.path.last(), Some(&me));
1582            assert!(!pwm.path.contains(&dest));
1583        }
1584
1585        Ok(())
1586    }
1587
1588    #[tokio::test]
1589    async fn selector_should_reject_extended_path_containing_destination() -> anyhow::Result<()> {
1590        // If me has a direct edge to dest (e.g. an edge node with a channel to its
1591        // exit server), Phase 2 must not emit [dest, dest] — appending dest to a
1592        // candidate that already ends in dest forms a loop that ValidatedPath::new
1593        // would catch anyway, but we want the guard to skip it cleanly.
1594        let me = pubkey(&SECRET_0);
1595        let relay = pubkey(&SECRET_1);
1596        let dest = pubkey(&SECRET_2);
1597        let graph = ChannelGraph::new(me);
1598        graph.add_node(relay);
1599        graph.add_node(dest);
1600        // me → dest: direct channel (this is what the own_chain_addr fix exposes)
1601        graph.add_edge(&me, &dest).unwrap();
1602        mark_edge_full(&graph, &me, &dest);
1603        // me → relay: for 1-hop via relay
1604        graph.add_edge(&me, &relay).unwrap();
1605        mark_edge_full(&graph, &me, &relay);
1606        // Return path
1607        graph.add_edge(&dest, &relay).unwrap();
1608        graph.add_edge(&relay, &me).unwrap();
1609        mark_edge_full(&graph, &dest, &relay);
1610        mark_edge_full(&graph, &relay, &me);
1611
1612        let selector = test_selector(me, graph, MAX_PATHS);
1613
1614        let fwd = selector
1615            .select_path(me, dest, 1)
1616            .context("forward path with dest as direct neighbor")?;
1617        assert!(!fwd.is_empty(), "should find at least one path via relay");
1618        for pwm in &fwd {
1619            assert_eq!(pwm.path.len(), 2, "path must be [relay, dest]");
1620            assert_eq!(pwm.path[0], relay, "first node must be relay, not dest");
1621            assert_eq!(pwm.path[1], dest);
1622        }
1623        Ok(())
1624    }
1625
1626    #[tokio::test]
1627    async fn selector_should_reject_one_hop_path_where_relay_equals_destination() -> anyhow::Result<()> {
1628        // Same as above but without relay→dest edge — only Phase 2 (virtual last hop)
1629        // is in play. The guard must skip the me→dest edge as a relay candidate.
1630        let me = pubkey(&SECRET_0);
1631        let relay = pubkey(&SECRET_1);
1632        let dest = pubkey(&SECRET_2);
1633        let graph = ChannelGraph::new(me);
1634        graph.add_node(relay);
1635        graph.add_node(dest);
1636        // me → dest: direct channel (no relay→dest edge)
1637        graph.add_edge(&me, &dest).unwrap();
1638        mark_edge_full(&graph, &me, &dest);
1639        // me → relay (relay is a valid intermediate; no relay→dest edge needed for Phase 2)
1640        graph.add_edge(&me, &relay).unwrap();
1641        mark_edge_full(&graph, &me, &relay);
1642        // Return path
1643        graph.add_edge(&dest, &relay).unwrap();
1644        graph.add_edge(&relay, &me).unwrap();
1645        mark_edge_full(&graph, &dest, &relay);
1646        mark_edge_full(&graph, &relay, &me);
1647
1648        let selector = test_selector(me, graph, MAX_PATHS);
1649
1650        let fwd = selector
1651            .select_path(me, dest, 1)
1652            .context("forward path — dest is direct neighbor, relay is intermediate")?;
1653        assert!(!fwd.is_empty(), "should find path via relay (virtual last hop)");
1654        for pwm in &fwd {
1655            assert_eq!(pwm.path[0], relay, "intermediate must be relay, not dest");
1656            assert_ne!(pwm.path[0], dest, "dest must not appear as intermediate");
1657        }
1658        Ok(())
1659    }
1660
1661    #[tokio::test]
1662    async fn selector_should_skip_zero_cost_paths() -> anyhow::Result<()> {
1663        // Build graph with edges but NO observations → cost function returns 0.
1664        let me = pubkey(&SECRET_0);
1665        let hop = pubkey(&SECRET_1);
1666        let dest = pubkey(&SECRET_2);
1667        let graph = ChannelGraph::new(me);
1668        graph.add_node(hop);
1669        graph.add_node(dest);
1670        graph.add_edge(&me, &hop).context("adding edge me -> hop")?;
1671        graph.add_edge(&hop, &dest).context("adding edge hop -> dest")?;
1672        // No mark_edge_full/mark_edge_last → observations are empty → cost = 0
1673
1674        let selector = test_selector(me, graph, MAX_PATHS);
1675
1676        let err = selector
1677            .select_path(me, dest, 1)
1678            .expect_err("zero-cost paths should be filtered out");
1679        anyhow::ensure!(
1680            matches!(err, PathPlannerError::Path(PathError::PathNotFound(..))),
1681            "expected PathNotFound, got: {err}"
1682        );
1683        Ok(())
1684    }
1685
1686    // ── pruning tests ─────────────────────────────────────────────────────────
1687
1688    fn make_path_with_latency(latency_ms: Option<u32>) -> PathWithMetrics {
1689        PathWithMetrics {
1690            path: vec![],
1691            cost: 1.0,
1692            total_latency_ms: latency_ms,
1693            min_probe_success_rate: None,
1694            min_ack_rate: None,
1695            fundable_tickets_floor: None,
1696        }
1697    }
1698
1699    fn make_path_with_tickets(latency_ms: Option<u32>, fundable_tickets_floor: Option<u128>) -> PathWithMetrics {
1700        PathWithMetrics {
1701            path: vec![],
1702            cost: 1.0,
1703            total_latency_ms: latency_ms,
1704            min_probe_success_rate: None,
1705            min_ack_rate: None,
1706            fundable_tickets_floor,
1707        }
1708    }
1709
1710    /// A candidate whose first hop is relayer `relayer_idx`, with the given latency.
1711    fn make_path_via(relayer_idx: u8, latency_ms: u32) -> PathWithMetrics {
1712        let mut secret = [1u8; 32];
1713        secret[0] = relayer_idx.max(1);
1714        let relayer = *OffchainKeypair::from_secret(&secret).expect("valid secret").public();
1715        PathWithMetrics {
1716            path: vec![relayer],
1717            cost: 1.0,
1718            total_latency_ms: Some(latency_ms),
1719            min_probe_success_rate: None,
1720            min_ack_rate: None,
1721            fundable_tickets_floor: Some(1000),
1722        }
1723    }
1724
1725    #[test]
1726    fn prune_should_prefer_distinct_first_relayers_over_pure_latency_order() {
1727        // The four lowest-latency paths all leave via relayer 1; relayers 2..4 are slower. A pure
1728        // latency truncation to 3 would keep only relayer 1, collapsing all downstream diversity.
1729        let candidates = vec![
1730            make_path_via(1, 10),
1731            make_path_via(1, 11),
1732            make_path_via(1, 12),
1733            make_path_via(1, 13),
1734            make_path_via(2, 50),
1735            make_path_via(3, 60),
1736            make_path_via(4, 70),
1737        ];
1738
1739        let result = prune_for_consistency(candidates, 3, 1);
1740        assert_eq!(3, result.len());
1741
1742        let relayers: Vec<String> = result
1743            .iter()
1744            .map(|p| hopr_api::types::primitive::traits::ToHex::to_hex(p.path.first().expect("non-empty")))
1745            .collect();
1746        let mut distinct = relayers.clone();
1747        distinct.sort();
1748        distinct.dedup();
1749        assert_eq!(3, distinct.len(), "the floor must be filled with distinct relayers");
1750
1751        // The best path per relayer is the one kept, so latency still drives the choice within
1752        // each relayer.
1753        assert_eq!(Some(10), result[0].total_latency_ms, "still latency-ordered");
1754    }
1755
1756    /// A 2-hop candidate: first relayer `first_idx`, middle relayer `middle_idx`, then the destination.
1757    fn make_path_through(first_idx: u8, middle_idx: u8, latency_ms: u32) -> PathWithMetrics {
1758        let key = |tag: u8, idx: u8| {
1759            let mut secret = [1u8; 32];
1760            secret[0] = idx.max(1);
1761            secret[2] = tag;
1762            *OffchainKeypair::from_secret(&secret).expect("valid secret").public()
1763        };
1764        PathWithMetrics {
1765            path: vec![key(1, first_idx), key(2, middle_idx), key(3, 1)],
1766            cost: 1.0,
1767            total_latency_ms: Some(latency_ms),
1768            min_probe_success_rate: None,
1769            min_ack_rate: None,
1770            fundable_tickets_floor: Some(1000),
1771        }
1772    }
1773
1774    /// Eight first relayers, each with its fastest path through the same middle relayer and a
1775    /// slower one through its own. Distinct first relayers alone would keep the eight fastest paths
1776    /// and put the hub in the middle of every candidate; the cap lets it into at most 3 of the 8.
1777    #[test]
1778    fn prune_should_bound_how_often_a_relayer_recurs_in_a_middle_position() {
1779        let hub = 9u8;
1780        let mut candidates = Vec::new();
1781        for first in 1..=8u8 {
1782            candidates.push(make_path_through(first, hub, 10 + u32::from(first)));
1783            candidates.push(make_path_through(first, first, 50 + u32::from(first)));
1784        }
1785
1786        let result = prune_for_consistency(candidates, 8, 2);
1787        assert_eq!(8, result.len());
1788
1789        let hub_key = make_path_through(1, hub, 0).path[1];
1790        let through_hub = result.iter().filter(|p| p.path[1] == hub_key).count();
1791        assert_eq!(
1792            3, through_hub,
1793            "the hub sits in the middle of at most ceil(8 / 3) candidates"
1794        );
1795
1796        let firsts: std::collections::HashSet<_> = result.iter().map(|p| p.path[0]).collect();
1797        assert_eq!(8, firsts.len(), "every first relayer is still represented");
1798        assert_eq!(
1799            Some(11),
1800            result[0].total_latency_ms,
1801            "the fastest path is still kept, and the order is still by latency"
1802        );
1803    }
1804
1805    /// Over the cap, a new first relayer still comes before a second path from one already kept:
1806    /// every path runs through the same middle relayer, the first pass keeps two, and the floor of
1807    /// four is filled from the two first relayers not yet represented, not from the next-fastest
1808    /// paths of the two that are.
1809    #[test]
1810    fn prune_should_keep_distinct_first_relayers_when_the_cap_runs_out() {
1811        let hub = 9u8;
1812        let candidates = vec![
1813            make_path_through(1, hub, 10),
1814            make_path_through(1, hub, 11),
1815            make_path_through(2, hub, 12),
1816            make_path_through(2, hub, 13),
1817            make_path_through(3, hub, 14),
1818            make_path_through(4, hub, 15),
1819        ];
1820        let result = prune_for_consistency(candidates, 4, 2);
1821        assert_eq!(4, result.len());
1822        let firsts: std::collections::HashSet<_> = result.iter().map(|p| p.path[0]).collect();
1823        assert_eq!(4, firsts.len(), "four first relayers, not two kept twice each");
1824    }
1825
1826    /// A 3-hop candidate over relayers named by index whatever their position, so that one relayer can
1827    /// sit second in some paths and third in others.
1828    fn make_three_hop_path(first: u8, second: u8, third: u8, latency_ms: u32) -> PathWithMetrics {
1829        let relayer = |idx: u8| {
1830            let mut secret = [1u8; 32];
1831            secret[0] = idx.max(1);
1832            secret[2] = 7;
1833            *OffchainKeypair::from_secret(&secret).expect("valid secret").public()
1834        };
1835        let mut destination = [1u8; 32];
1836        destination[2] = 3;
1837        PathWithMetrics {
1838            path: vec![
1839                relayer(first),
1840                relayer(second),
1841                relayer(third),
1842                *OffchainKeypair::from_secret(&destination)
1843                    .expect("valid secret")
1844                    .public(),
1845            ],
1846            cost: 1.0,
1847            total_latency_ms: Some(latency_ms),
1848            min_probe_success_rate: None,
1849            min_ack_rate: None,
1850            fundable_tickets_floor: Some(1000),
1851        }
1852    }
1853
1854    /// The cap counts a relayer over every position past the first together. Six first relayers whose
1855    /// fastest paths put the same relayer second in three of them and third in the other three: counted
1856    /// per position, it could sit in four of the six candidates; counted together, it sits in two.
1857    #[test]
1858    fn prune_should_bound_a_relayer_over_all_later_positions_together() {
1859        let hub = 30u8;
1860        let mut candidates = Vec::new();
1861        for first in 1..=3u8 {
1862            candidates.push(make_three_hop_path(first, hub, 10 + first, u32::from(first)));
1863        }
1864        for first in 4..=6u8 {
1865            candidates.push(make_three_hop_path(first, 10 + first, hub, u32::from(first)));
1866        }
1867        for first in 1..=6u8 {
1868            candidates.push(make_three_hop_path(
1869                first,
1870                20 + first,
1871                40 + first,
1872                100 + u32::from(first),
1873            ));
1874        }
1875
1876        let result = prune_for_consistency(candidates, 6, 3);
1877        assert_eq!(6, result.len());
1878        let hub_key = make_three_hop_path(1, hub, 2, 0).path[1];
1879        let through_hub = result.iter().filter(|p| p.path[1..3].contains(&hub_key)).count();
1880        assert_eq!(
1881            2, through_hub,
1882            "the hub sits past the first position in at most ceil(6 / 3) candidates"
1883        );
1884        let firsts: std::collections::HashSet<_> = result.iter().map(|p| p.path[0]).collect();
1885        assert_eq!(6, firsts.len(), "every first relayer is still represented");
1886    }
1887
1888    /// With the pool too thin to respect the cap, the floor is still filled: the cap bounds, it
1889    /// never starves.
1890    #[test]
1891    fn prune_should_fill_the_floor_through_a_hub_when_nothing_else_is_left() {
1892        let candidates = (1..=6u8)
1893            .map(|first| make_path_through(first, 9, 10 + u32::from(first)))
1894            .collect();
1895        let result = prune_for_consistency(candidates, 4, 2);
1896        assert_eq!(4, result.len(), "four of six through the only middle relayer there is");
1897    }
1898
1899    #[test]
1900    fn distinct_first_relayers_counts_unique_first_hops() {
1901        // Three paths, two of them via the same relayer → two distinct first relayers. Paths with
1902        // no hops contribute nothing.
1903        let paths = vec![
1904            make_path_via(1, 10),
1905            make_path_via(1, 20),
1906            make_path_via(2, 30),
1907            make_path_with_latency(Some(40)), // empty path
1908        ];
1909        assert_eq!(2, distinct_first_relayers(&paths));
1910    }
1911
1912    #[test]
1913    fn floor_zero_keeps_all_distinct_relayers_unlike_a_small_cap() {
1914        // Ten qualifying paths, each via a distinct relayer. This is the "if 10 qualify, use 10"
1915        // case: with the cap disabled (floor = 0) every relayer survives, so the return-path
1916        // degradation detector always has siblings to corroborate against. A small cap (2) throws
1917        // eight good relayers away — the collapse that made the 2026-08-28 outage undetectable.
1918        let candidates: Vec<_> = (1..=10u8).map(|i| make_path_via(i, i as u32 * 10)).collect();
1919
1920        let uncapped = prune_for_consistency(candidates.clone(), 0, 1);
1921        assert_eq!(10, uncapped.len(), "floor = 0 disables pruning: all candidates survive");
1922        assert_eq!(10, distinct_first_relayers(&uncapped), "all ten relayers kept");
1923
1924        let capped = prune_for_consistency(candidates, 2, 1);
1925        assert_eq!(2, capped.len(), "floor = 2 caps survivors at two");
1926        assert_eq!(2, distinct_first_relayers(&capped));
1927    }
1928
1929    #[test]
1930    fn prune_should_fall_back_to_latency_order_once_relayers_are_exhausted() {
1931        // Only two relayers available but a floor of 4: the remaining slots go to the next-best
1932        // paths regardless of relayer.
1933        let candidates = vec![
1934            make_path_via(1, 10),
1935            make_path_via(2, 20),
1936            make_path_via(1, 30),
1937            make_path_via(2, 40),
1938            make_path_via(1, 50),
1939        ];
1940
1941        let result = prune_for_consistency(candidates, 4, 1);
1942        assert_eq!(4, result.len());
1943        assert_eq!(
1944            vec![Some(10), Some(20), Some(30), Some(40)],
1945            result.iter().map(|p| p.total_latency_ms).collect::<Vec<_>>()
1946        );
1947    }
1948
1949    #[test]
1950    fn prune_keeps_all_when_below_floor() {
1951        let candidates: Vec<_> = (0..5).map(|i| make_path_with_latency(Some(i * 10))).collect();
1952        let result = prune_for_consistency(candidates, 8, 1);
1953        assert_eq!(result.len(), 5, "below floor: nothing should be dropped");
1954    }
1955
1956    #[test]
1957    fn prune_drops_high_latency_first() {
1958        // 30 paths with strictly increasing latency, floor=8 → keep lowest 8
1959        let candidates: Vec<_> = (0..30u32)
1960            .map(|i| make_path_with_tickets(Some(i * 10), Some(1_000_000)))
1961            .collect();
1962        let result = prune_for_consistency(candidates, 8, 1);
1963        assert_eq!(result.len(), 8);
1964        for p in &result {
1965            assert!(p.total_latency_ms.unwrap() < 80, "only the 8 lowest should survive");
1966        }
1967    }
1968
1969    #[test]
1970    fn prune_preserves_populated_paths_over_unpopulated() {
1971        // 3 populated + 6 unpopulated, floor=8
1972        // total=9 > floor=8: all 3 populated are kept (populated always preferred),
1973        // then 5 unpopulated fill the remaining slots.
1974        let mut candidates: Vec<_> = vec![
1975            make_path_with_tickets(Some(10), Some(1_000)),
1976            make_path_with_tickets(Some(30), Some(1_000)),
1977            make_path_with_tickets(Some(20), Some(1_000)),
1978        ];
1979        candidates.extend((0..6).map(|_| make_path_with_latency(None)));
1980        let result = prune_for_consistency(candidates, 8, 1);
1981        assert_eq!(result.len(), 8);
1982        // All 3 populated paths survive; 1 unpopulated is trimmed.
1983        let populated: Vec<_> = result.iter().filter(|p| p.total_latency_ms.is_some()).collect();
1984        assert_eq!(populated.len(), 3);
1985        assert!(populated.iter().any(|p| p.total_latency_ms == Some(10)));
1986        assert!(populated.iter().any(|p| p.total_latency_ms == Some(20)));
1987        assert!(populated.iter().any(|p| p.total_latency_ms == Some(30)));
1988    }
1989
1990    #[test]
1991    fn prune_drops_unpopulated_when_all_populated_exhausted() {
1992        // 0 populated, 20 unpopulated, floor=8 → keep first 8
1993        let candidates: Vec<_> = (0..20).map(|_| make_path_with_latency(None)).collect();
1994        let result = prune_for_consistency(candidates, 8, 1);
1995        assert_eq!(result.len(), 8);
1996    }
1997
1998    #[test]
1999    fn prune_keeps_populated_when_unpopulated_exceeds_floor() {
2000        // Regression: 2 populated + 10 unpopulated, floor=8.
2001        // Old formula: target_populated = 8.saturating_sub(10) = 0 → both populated dropped.
2002        // Correct: keep up to 8 populated (only 2 exist), fill 6 remaining with unpopulated.
2003        let mut candidates: Vec<_> = vec![
2004            make_path_with_tickets(Some(10), Some(1_000)),
2005            make_path_with_tickets(Some(20), Some(1_000)),
2006        ];
2007        candidates.extend((0..10).map(|_| make_path_with_latency(None)));
2008        let result = prune_for_consistency(candidates, 8, 1);
2009        assert_eq!(result.len(), 8);
2010        let populated: Vec<_> = result.iter().filter(|p| p.total_latency_ms.is_some()).collect();
2011        assert_eq!(populated.len(), 2, "both measured paths must survive");
2012        assert!(populated.iter().any(|p| p.total_latency_ms == Some(10)));
2013        assert!(populated.iter().any(|p| p.total_latency_ms == Some(20)));
2014    }
2015
2016    #[test]
2017    fn prune_exact_floor_is_unchanged() {
2018        let candidates: Vec<_> = (0..8)
2019            .map(|i| make_path_with_tickets(Some(i * 10), Some(1_000)))
2020            .collect();
2021        let result = prune_for_consistency(candidates, 8, 1);
2022        assert_eq!(result.len(), 8);
2023    }
2024
2025    #[test]
2026    fn prune_0_hop_with_measured_latency_and_no_capacity_is_populated() {
2027        // 0-hop: fundable_tickets_floor = None is expected; path should be treated as "fully measured"
2028        // if latency is known.
2029        let mut candidates: Vec<_> = vec![
2030            make_path_with_tickets(Some(50), None), // 0-hop: no capacity, latency known
2031        ];
2032        candidates.extend((0..10).map(|_| make_path_with_latency(None)));
2033        let result = prune_for_consistency(candidates, 8, 0);
2034        assert_eq!(result.len(), 8);
2035        // The 0-hop path must be in the populated bucket and survive.
2036        let has_0_hop = result.iter().any(|p| p.total_latency_ms == Some(50));
2037        assert!(has_0_hop, "0-hop path with measured latency must survive pruning");
2038    }
2039
2040    #[test]
2041    fn prune_multi_hop_without_fundable_tickets_floor_is_unpopulated() {
2042        // A 1-hop path with measured latency but NO capacity is unmeasured (unpopulated).
2043        // It should be demoted below paths that have both latency and capacity.
2044        let candidates: Vec<_> = vec![
2045            make_path_with_tickets(Some(50), Some(1_000)), // fully measured
2046            make_path_with_tickets(Some(50), Some(1_000)), // fully measured
2047            make_path_with_tickets(Some(50), Some(1_000)), // fully measured
2048            make_path_with_tickets(Some(50), Some(1_000)), // fully measured
2049            make_path_with_tickets(Some(50), Some(1_000)), // fully measured
2050            make_path_with_tickets(Some(50), Some(1_000)), // fully measured
2051            make_path_with_tickets(Some(50), Some(1_000)), // fully measured
2052            make_path_with_tickets(Some(50), Some(1_000)), // fully measured
2053            make_path_with_tickets(Some(40), None),        // missing capacity → unpopulated
2054        ];
2055        let result = prune_for_consistency(candidates, 8, 1);
2056        assert_eq!(result.len(), 8);
2057        // The path with missing capacity should not survive when all 8 slots are filled
2058        // by fully measured paths.
2059        let has_missing_balance = result.iter().any(|p| p.fundable_tickets_floor.is_none());
2060        assert!(
2061            !has_missing_balance,
2062            "path without capacity floor must be pruned when fully-measured paths fill the floor"
2063        );
2064    }
2065
2066    #[test]
2067    fn prune_for_consistency_floor_zero_returns_all() {
2068        // floor == 0 must be treated as "no pruning" — all candidates survive unchanged.
2069        let candidates = vec![
2070            make_path_with_tickets(Some(10), Some(1_000)),
2071            make_path_with_tickets(Some(20), None),
2072            make_path_with_tickets(None, None),
2073        ];
2074        let result = prune_for_consistency(candidates, 0, 1);
2075        assert_eq!(result.len(), 3, "floor=0 must return all candidates");
2076    }
2077
2078    // ── path metrics aggregation tests ────────────────────────────────────────
2079
2080    #[tokio::test]
2081    async fn path_metrics_aggregate_latency_correctly() -> anyhow::Result<()> {
2082        // 3-hop path: me → A (30ms) → B (40ms) → dest (50ms)
2083        // Total latency accumulated during DFS should be ~120ms.
2084        let me = pubkey(&SECRET_0);
2085        let a = pubkey(&SECRET_1);
2086        let b = pubkey(&SECRET_2);
2087        let dest = pubkey(&SECRET_3);
2088        let graph = ChannelGraph::new(me);
2089        for n in [a, b, dest] {
2090            graph.add_node(n);
2091        }
2092
2093        let make_edge = |src: &OffchainPublicKey, dst: &OffchainPublicKey, lat_ms: u64| {
2094            graph.upsert_edge(src, dst, |obs| {
2095                obs.record(EdgeWeightType::Connected(true));
2096                obs.record(EdgeWeightType::Immediate(Ok(Duration::from_millis(lat_ms))));
2097                obs.record(EdgeWeightType::Balance(Some(hopr_api::graph::traits::Balance::from(
2098                    1000u64,
2099                ))));
2100            });
2101        };
2102
2103        // Drive EMA to convergence with many samples at the target value.
2104        for _ in 0..20 {
2105            make_edge(&me, &a, 30);
2106            make_edge(&a, &b, 40);
2107            make_edge(&b, &dest, 50);
2108        }
2109
2110        // Edges only in the forward direction (me → a → b → dest)
2111        graph.add_edge(&me, &a).unwrap();
2112        graph.add_edge(&a, &b).unwrap();
2113        graph.add_edge(&b, &dest).unwrap();
2114
2115        let selector = test_selector(me, graph, MAX_PATHS);
2116        let paths = selector.select_path(me, dest, 2).context("forward 2-hop path")?;
2117        assert!(!paths.is_empty());
2118
2119        let total = paths[0].total_latency_ms.expect("latency must be Some");
2120        assert!(
2121            (100..=130).contains(&total),
2122            "expected ~120ms total latency, got {total}ms"
2123        );
2124        Ok(())
2125    }
2126
2127    #[tokio::test]
2128    async fn path_metrics_fundable_tickets_floor_is_min() -> anyhow::Result<()> {
2129        let me = pubkey(&SECRET_0);
2130        let hop = pubkey(&SECRET_1);
2131        let dest = pubkey(&SECRET_2);
2132        let graph = ChannelGraph::new(me);
2133        graph.add_node(hop);
2134        graph.add_node(dest);
2135
2136        // Stated, not assumed. A face value of one makes the ticket count equal the balance, which
2137        // is what keeps the numbers below readable — but it has to be pushed, because without a
2138        // price the floor is now `None` rather than silently dividing by one.
2139        graph.set_ticket_face_value(hopr_api::graph::traits::Balance::one());
2140
2141        graph.upsert_edge(&me, &hop, |obs| {
2142            obs.record(EdgeWeightType::Connected(true));
2143            obs.record(EdgeWeightType::Intermediate(Ok(Duration::from_millis(50))));
2144            obs.record(EdgeWeightType::Balance(Some(hopr_api::graph::traits::Balance::from(
2145                500u64,
2146            ))));
2147        });
2148        graph.upsert_edge(&hop, &dest, |obs| {
2149            obs.record(EdgeWeightType::Connected(true));
2150            obs.record(EdgeWeightType::Intermediate(Ok(Duration::from_millis(50))));
2151            obs.record(EdgeWeightType::Balance(Some(hopr_api::graph::traits::Balance::from(
2152                200u64,
2153            ))));
2154        });
2155        graph.add_edge(&me, &hop).unwrap();
2156        graph.add_edge(&hop, &dest).unwrap();
2157
2158        let selector = test_selector(me, graph, MAX_PATHS);
2159        let paths = selector.select_path(me, dest, 1).context("1-hop path")?;
2160        assert!(!paths.is_empty());
2161        assert_eq!(
2162            paths[0].fundable_tickets_floor,
2163            Some(200),
2164            "floor must be the smaller of 500 and 200"
2165        );
2166        Ok(())
2167    }
2168
2169    #[tokio::test]
2170    async fn starved_first_hop_channel_must_not_be_selected() -> anyhow::Result<()> {
2171        // GNO-805: the client's own outgoing channel — the first, monetized hop — drains below one
2172        // ticket face value. The first-hop ticket can then no longer be created (hopr-ticket-manager
2173        // rejects it with "balance of channel is too low"), so path selection must not hand out that
2174        // route at all. Phase 1 (`forward`) rejects it correctly; the regression is Phase 2
2175        // (`forward_without_self_loopback`), which for a 1-hop target searches a single edge with
2176        // `length = 1` and so checks `balance_suffices(balance, 0, face)` — zero remaining hops
2177        // waives the funding check and re-admits the drained hop.
2178        let me = pubkey(&SECRET_0);
2179        let relay = pubkey(&SECRET_1);
2180        let dest = pubkey(&SECRET_2);
2181
2182        // Face value 100; a monetized first edge needs >= one full-path winning ticket = 100.
2183        let face = hopr_api::graph::traits::Balance::from(100u64);
2184
2185        let build = |first_hop_balance: u64| {
2186            let graph = ChannelGraph::new(me);
2187            graph.add_node(relay);
2188            graph.add_node(dest);
2189            graph.set_ticket_face_value(face);
2190            // me -> relay: the monetized first hop, drained or funded per the argument.
2191            graph.upsert_edge(&me, &relay, |obs| {
2192                obs.record(EdgeWeightType::Connected(true));
2193                obs.record(EdgeWeightType::Immediate(Ok(Duration::from_millis(50))));
2194                obs.record(EdgeWeightType::Intermediate(Ok(Duration::from_millis(50))));
2195                obs.record(EdgeWeightType::Balance(Some(hopr_api::graph::traits::Balance::from(
2196                    first_hop_balance,
2197                ))));
2198            });
2199            // relay -> dest: healthy; the final hop is not monetized regardless.
2200            mark_edge_full(&graph, &relay, &dest);
2201            graph.add_edge(&me, &relay).unwrap();
2202            graph.add_edge(&relay, &dest).unwrap();
2203            graph
2204        };
2205
2206        // Control: a funded first hop yields a usable path, proving the topology is otherwise valid
2207        // and that a later PathNotFound is caused by the drain, not a missing route.
2208        let funded = test_selector(me, build(10_000), MAX_PATHS);
2209        let healthy = funded.select_path(me, dest, 1).context("funded first hop must route")?;
2210        assert!(!healthy.is_empty(), "a funded first hop must be selectable");
2211        assert_eq!(healthy[0].path.first(), Some(&relay), "route must go via the relay");
2212
2213        // The bug: first hop drained to 50 — below one face value (100), so it cannot fund a ticket.
2214        let starved = test_selector(me, build(50), MAX_PATHS);
2215        let result = starved.select_path(me, dest, 1);
2216        assert!(
2217            matches!(result, Err(PathPlannerError::Path(PathError::PathNotFound(..)))),
2218            "a first hop that cannot fund a single ticket must not be selected, got: {result:?}"
2219        );
2220        Ok(())
2221    }
2222
2223    #[tokio::test]
2224    async fn first_hop_funded_for_one_ticket_is_selectable() -> anyhow::Result<()> {
2225        // Regression for the removed balance headroom (hopr-api#144): the selector used to require a
2226        // first edge to hold twice the path's ticket cost (`MIN_BALANCE_HEADROOM = 2`), so a channel
2227        // with enough for one winning ticket but less than two was pruned despite being fundable. The
2228        // planner now requires only one full-path winning ticket, so such a channel must route.
2229        let me = pubkey(&SECRET_0);
2230        let relay = pubkey(&SECRET_1);
2231        let dest = pubkey(&SECRET_2);
2232
2233        // Face value 100; first hop at 150 — above one winning ticket (100), below the old 2x = 200
2234        // headroom. Selectable now, pruned before.
2235        let face = hopr_api::graph::traits::Balance::from(100u64);
2236        let graph = ChannelGraph::new(me);
2237        graph.add_node(relay);
2238        graph.add_node(dest);
2239        graph.set_ticket_face_value(face);
2240        graph.upsert_edge(&me, &relay, |obs| {
2241            obs.record(EdgeWeightType::Connected(true));
2242            obs.record(EdgeWeightType::Immediate(Ok(Duration::from_millis(50))));
2243            obs.record(EdgeWeightType::Intermediate(Ok(Duration::from_millis(50))));
2244            obs.record(EdgeWeightType::Balance(Some(hopr_api::graph::traits::Balance::from(
2245                150u64,
2246            ))));
2247        });
2248        mark_edge_full(&graph, &relay, &dest);
2249        graph.add_edge(&me, &relay).unwrap();
2250        graph.add_edge(&relay, &dest).unwrap();
2251
2252        let selector = test_selector(me, graph, MAX_PATHS);
2253        let paths = selector
2254            .select_path(me, dest, 1)
2255            .context("a first hop funded for one winning ticket must route")?;
2256        assert!(
2257            !paths.is_empty(),
2258            "a first hop funded for one winning ticket must be selectable"
2259        );
2260        assert_eq!(paths[0].path.first(), Some(&relay), "route must go via the relay");
2261        Ok(())
2262    }
2263
2264    #[tokio::test]
2265    async fn starved_intermediate_hop_via_extended_search_must_not_be_selected() -> anyhow::Result<()> {
2266        // Same off-by-one, one hop deeper. With no relay -> dest channel, a 2-hop request falls to
2267        // the Phase 2 extended search (me -> a -> b, dest appended). `b` is the last *searched*
2268        // edge but still a monetized hop. The understated length waived its funding via the
2269        // intermediate `require_funding` branch collapsing to zero remaining hops; costing against
2270        // the finished length keeps the check at one ticket.
2271        let me = pubkey(&SECRET_0);
2272        let a = pubkey(&SECRET_1);
2273        let b = pubkey(&SECRET_2);
2274        let dest = pubkey(&SECRET_3);
2275
2276        let face = hopr_api::graph::traits::Balance::from(100u64);
2277
2278        let build = |second_hop_balance: u64| {
2279            let graph = ChannelGraph::new(me);
2280            for n in [a, b, dest] {
2281                graph.add_node(n);
2282            }
2283            graph.set_ticket_face_value(face);
2284            // me -> a: healthy and well funded.
2285            graph.upsert_edge(&me, &a, |obs| {
2286                obs.record(EdgeWeightType::Connected(true));
2287                obs.record(EdgeWeightType::Immediate(Ok(Duration::from_millis(50))));
2288                obs.record(EdgeWeightType::Intermediate(Ok(Duration::from_millis(50))));
2289                obs.record(EdgeWeightType::Balance(Some(hopr_api::graph::traits::Balance::from(
2290                    10_000u64,
2291                ))));
2292            });
2293            // a -> b: the monetized hop under test.
2294            graph.upsert_edge(&a, &b, |obs| {
2295                obs.record(EdgeWeightType::Connected(true));
2296                obs.record(EdgeWeightType::Immediate(Ok(Duration::from_millis(50))));
2297                obs.record(EdgeWeightType::Intermediate(Ok(Duration::from_millis(50))));
2298                obs.record(EdgeWeightType::Balance(Some(hopr_api::graph::traits::Balance::from(
2299                    second_hop_balance,
2300                ))));
2301            });
2302            // No b -> dest edge: forces the Phase 2 extended search (last hop assumed by anybody).
2303            graph.add_edge(&me, &a).unwrap();
2304            graph.add_edge(&a, &b).unwrap();
2305            graph
2306        };
2307
2308        // Control: a funded second hop routes via the extended search.
2309        let funded = test_selector(me, build(10_000), MAX_PATHS);
2310        let healthy = funded
2311            .select_path(me, dest, 2)
2312            .context("funded second hop must route")?;
2313        assert!(!healthy.is_empty(), "a funded second hop must be selectable");
2314        assert_eq!(healthy[0].path.first(), Some(&a), "route must start at the first relay");
2315
2316        // The bug: second hop drained to 50 — below one face value (100).
2317        let starved = test_selector(me, build(50), MAX_PATHS);
2318        let result = starved.select_path(me, dest, 2);
2319        assert!(
2320            matches!(result, Err(PathPlannerError::Path(PathError::PathNotFound(..)))),
2321            "a monetized intermediate hop that cannot fund a ticket must not be selected, got: {result:?}"
2322        );
2323        Ok(())
2324    }
2325
2326    // NOTE: a test for fundable_tickets_floor=None is omitted intentionally.
2327    // The forward cost function requires a funding balance on all non-last edges, so
2328    // every path the selector returns has capacity data on at least one edge, making
2329    // fundable_tickets_floor always Some for reachable paths.
2330    #[test]
2331    /// Keep path ordering and equality based on cost regardless of diagnostic quality metadata.
2332    fn path_cost_equality_ignores_quality_metadata() {
2333        let cost = PathCostWithMetrics {
2334            cost: 0.5,
2335            total_latency_ms: None,
2336            min_probe_success_rate: None,
2337            min_ack_rate: None,
2338            fundable_tickets_floor: None,
2339        };
2340        let measured = PathCostWithMetrics {
2341            total_latency_ms: Some(100),
2342            min_probe_success_rate: Some(0.9),
2343            min_ack_rate: Some(0.8),
2344            fundable_tickets_floor: Some(3),
2345            ..cost.clone()
2346        };
2347        assert_eq!(cost, measured);
2348        assert_ne!(cost, PathCostWithMetrics { cost: 0.6, ..measured });
2349    }
2350
2351    #[test]
2352    /// Ensure TRACE-only diagnostics leave the selected candidate paths unchanged.
2353    fn trace_diagnostics_preserve_the_selected_candidates() -> anyhow::Result<()> {
2354        let (me, _, dest, graph) = two_hop_graph();
2355        let selector = test_selector(me, graph, MAX_PATHS);
2356        let expected = selector.select_path(me, dest, 1)?;
2357        let subscriber = test_log::tracing_subscriber::fmt()
2358            .with_max_level(tracing::Level::TRACE)
2359            .with_writer(std::io::sink)
2360            .finish();
2361        let actual = tracing::subscriber::with_default(subscriber, || selector.select_path(me, dest, 1))?;
2362        assert_eq!(actual.len(), expected.len());
2363        assert_eq!(actual[0].path, expected[0].path);
2364        assert_eq!(actual[0].cost, expected[0].cost);
2365        Ok(())
2366    }
2367
2368    #[test]
2369    /// Report actual search phases, retained candidates and empty results to the observer.
2370    fn observer_sees_real_search_phases_and_empty_searches() -> anyhow::Result<()> {
2371        let (me, _, dest, graph) = two_hop_graph();
2372        let events = Arc::new(parking_lot::Mutex::new(Vec::new()));
2373        let selector = HoprGraphPathSelector::new(me, graph, MAX_PATHS, 0.5, 0.5, 0).with_observer(Arc::new({
2374            let events = events.clone();
2375            move |event| events.lock().push(event)
2376        }));
2377        selector.select_path(me, dest, 1)?;
2378        assert!(selector.select_path(pubkey(&SECRET_4), me, 1).is_err());
2379
2380        let events = events.lock();
2381        assert_eq!(events.len(), 2, "one event per search, and no resolve is invented");
2382        let searches: Vec<_> = events
2383            .iter()
2384            .filter_map(|event| match event {
2385                TransportEvent::PathSearched {
2386                    phase1,
2387                    phase2,
2388                    retained,
2389                    ..
2390                } => Some((*phase1, *phase2, *retained)),
2391                _ => None,
2392            })
2393            .collect();
2394        assert_eq!(searches.len(), 2);
2395        assert_eq!(1, searches.iter().filter(|(_, _, retained)| *retained == 0).count());
2396        assert!(searches.iter().any(|(phase1, ..)| phase1.returned > 0));
2397        assert!(searches.iter().any(|(_, phase2, _)| phase2.is_some()));
2398        Ok(())
2399    }
2400
2401    /// `relayers` relayers in a full mesh between `me` and `dest`, every link in both directions.
2402    ///
2403    /// `tickets` gives each link's channel balance in tickets from a scrambled link number, so a
2404    /// test can make an edge's value depend on its position in the path (the tickets a channel
2405    /// must fund are the hops that follow it).
2406    fn mesh_graph(
2407        relayers: usize,
2408        tickets: impl Fn(u64) -> u64,
2409    ) -> (
2410        OffchainPublicKey,
2411        OffchainPublicKey,
2412        Vec<OffchainPublicKey>,
2413        ChannelGraph,
2414    ) {
2415        const FACE_VALUE: u64 = 100;
2416        let me = pubkey(&SECRET_0);
2417        let dest = pubkey(&SECRET_1);
2418        let relays = (0..relayers)
2419            .map(|_| *OffchainKeypair::random().public())
2420            .collect::<Vec<_>>();
2421        let graph = ChannelGraph::new(me);
2422        graph.set_ticket_face_value(hopr_api::graph::traits::Balance::from(FACE_VALUE));
2423        graph.add_node(dest);
2424        relays.iter().for_each(|r| graph.add_node(*r));
2425
2426        let mut n = 0u64;
2427        let mut link = |a: &OffchainPublicKey, b: &OffchainPublicKey| {
2428            n += 1;
2429            graph.add_edge(a, b).unwrap();
2430            graph.upsert_edge(a, b, |obs| {
2431                obs.record(EdgeWeightType::Connected(true));
2432                obs.record(EdgeWeightType::Immediate(Ok(Duration::from_millis(10 + n % 7 * 13))));
2433                obs.record(EdgeWeightType::Intermediate(Ok(Duration::from_millis(20 + n % 5 * 17))));
2434                obs.record(EdgeWeightType::Balance(Some(hopr_api::graph::traits::Balance::from(
2435                    tickets(n.wrapping_mul(2_654_435_761) >> 7) * FACE_VALUE,
2436                ))));
2437            });
2438        };
2439        for r in &relays {
2440            link(&me, r);
2441            link(r, &me);
2442            link(&dest, r);
2443            link(r, &dest);
2444            for s in relays.iter().filter(|s| *s != r) {
2445                link(r, s);
2446            }
2447        }
2448        (me, dest, relays, graph)
2449    }
2450
2451    fn metrics_fn(
2452        graph: &ChannelGraph,
2453        length: std::num::NonZeroUsize,
2454        forward: bool,
2455    ) -> MetricsValueFn<<ChannelGraph as NetworkGraphTraverse>::Observed> {
2456        let cfg = PathPlannerConfig::default();
2457        let face = graph.ticket_face_value();
2458        MetricsValueFn {
2459            inner: if forward {
2460                EdgeValueFn::forward(length, cfg.edge_penalty, cfg.min_ack_rate, face)
2461            } else {
2462                EdgeValueFn::returning(length, cfg.edge_penalty, cfg.min_ack_rate, face)
2463            },
2464            ticket_face_value: face,
2465        }
2466    }
2467
2468    fn first_relayers(paths: &[PathWithMetrics]) -> std::collections::HashSet<OffchainPublicKey> {
2469        paths.iter().filter_map(|p| p.path.first().copied()).collect()
2470    }
2471
2472    /// Diagnostics count all searched continuations even when the spread pool is capped.
2473    #[rstest::rstest]
2474    #[case::forward(true)]
2475    #[case::returning(false)]
2476    fn observer_counts_spread_candidates_before_the_pool_limit(#[case] forward: bool) -> anyhow::Result<()> {
2477        let (me, dest, relays, graph) = mesh_graph(7, |_| 1000);
2478        let (src, dst) = if forward { (me, dest) } else { (dest, me) };
2479        let events = Arc::new(parking_lot::Mutex::new(Vec::new()));
2480        let cfg = PathPlannerConfig::default();
2481        let selector =
2482            HoprGraphPathSelector::new(me, graph, 4, cfg.edge_penalty, cfg.min_ack_rate, 0).with_observer(Arc::new({
2483                let events = events.clone();
2484                move |event| events.lock().push(event)
2485            }));
2486
2487        let paths = selector.select_path(src, dst, 1)?;
2488        assert_eq!(paths.len(), 4);
2489        assert_eq!(distinct_first_relayers(&paths), 4);
2490        let events = events.lock();
2491        assert_eq!(events.len(), 1);
2492        let TransportEvent::PathSearched {
2493            direction,
2494            phase1,
2495            phase2,
2496            retained,
2497            ..
2498        } = &events[0]
2499        else {
2500            anyhow::bail!("expected a path search event");
2501        };
2502        assert_eq!(
2503            *direction,
2504            if forward {
2505                PathDirection::Forward
2506            } else {
2507                PathDirection::Return
2508            }
2509        );
2510        assert_eq!(phase1.returned, relays.len() as u64);
2511        assert_eq!(phase1.eligible, paths.len() as u64);
2512        assert!(phase2.is_none());
2513        assert_eq!(*retained, paths.len() as u64);
2514        Ok(())
2515    }
2516
2517    /// The defect: a three-hop search over seven relayers kept 50 paths that named two first
2518    /// relayers, the depth-first order filling the pool with whole subtrees.
2519    #[rstest::rstest]
2520    #[case::forward(true)]
2521    #[case::returning(false)]
2522    fn a_spread_pool_should_name_every_first_relayer_where_one_traversal_named_two(
2523        #[case] forward: bool,
2524    ) -> anyhow::Result<()> {
2525        let (me, dest, relays, graph) = mesh_graph(7, |_| 1000);
2526        let (src, dst) = if forward { (me, dest) } else { (dest, me) };
2527        let length = std::num::NonZeroUsize::new(4).context("non-zero")?;
2528
2529        let (single, _) = compute_paths(&graph, &src, &dst, length, 50, metrics_fn(&graph, length, forward));
2530        assert!(
2531            first_relayers(&single).len() <= 2,
2532            "30 paths per first relayer, cut at 50"
2533        );
2534
2535        let (spread, _) = compute_paths_spread(&graph, &src, &dst, length, 50, metrics_fn(&graph, length, forward));
2536        assert!(spread.len() <= 50);
2537        assert_eq!(relays.len(), first_relayers(&spread).len());
2538        for p in &spread {
2539            assert_eq!(4, p.path.len());
2540            assert_eq!(Some(&dst), p.path.last());
2541            assert!(
2542                !p.path.contains(&src),
2543                "a path must not run back through its source: {:?}",
2544                p.path
2545            );
2546            let distinct = p.path.iter().collect::<std::collections::HashSet<_>>();
2547            assert_eq!(p.path.len(), distinct.len(), "a path must be simple: {:?}", p.path);
2548        }
2549        Ok(())
2550    }
2551
2552    /// Every path the spread search returns is one the single traversal returns, valued the same:
2553    /// a channel must fund the hops after it, so an edge valued at the wrong position would pass
2554    /// or fail the funding check differently, and the two sets would differ.
2555    #[rstest::rstest]
2556    #[case::forward(true)]
2557    #[case::returning(false)]
2558    fn a_spread_pool_should_value_each_path_as_one_traversal_does(#[case] forward: bool) -> anyhow::Result<()> {
2559        let (me, dest, _, graph) = mesh_graph(5, |n| 1 + n % 4);
2560        let (src, dst) = if forward { (me, dest) } else { (dest, me) };
2561
2562        for hops in 1..=3 {
2563            let length = std::num::NonZeroUsize::new(hops + 1).context("non-zero")?;
2564            let key = |p: &PathWithMetrics| {
2565                format!(
2566                    "{:?} {} {:?} {:?} {:?} {:?}",
2567                    p.path,
2568                    p.cost,
2569                    p.total_latency_ms,
2570                    p.min_probe_success_rate,
2571                    p.min_ack_rate,
2572                    p.fundable_tickets_floor
2573                )
2574            };
2575            let mut all = compute_paths(
2576                &graph,
2577                &src,
2578                &dst,
2579                length,
2580                usize::MAX,
2581                metrics_fn(&graph, length, forward),
2582            )
2583            .0
2584            .iter()
2585            .map(key)
2586            .collect::<Vec<_>>();
2587            let mut spread =
2588                compute_paths_spread(&graph, &src, &dst, length, 10_000, metrics_fn(&graph, length, forward))
2589                    .0
2590                    .iter()
2591                    .map(key)
2592                    .collect::<Vec<_>>();
2593            all.sort();
2594            spread.sort();
2595            assert!(!all.is_empty(), "{hops} hops: the mesh must route");
2596            // From two hops on, the first channel must fund more tickets than some channels hold.
2597            let simple_paths = (5 - hops + 1..=5).product::<usize>();
2598            if hops > 1 {
2599                assert!(all.len() < simple_paths, "{hops} hops: funding must reject some paths");
2600            }
2601            assert_eq!(all, spread, "{hops} hops");
2602        }
2603        Ok(())
2604    }
2605
2606    /// Fewer candidates than first relayers still take one path from each relayer they can.
2607    #[test]
2608    fn a_spread_pool_cut_short_should_keep_distinct_first_relayers() -> anyhow::Result<()> {
2609        let (me, dest, _, graph) = mesh_graph(7, |_| 1000);
2610        let length = std::num::NonZeroUsize::new(3).context("non-zero")?;
2611
2612        let (spread, _) = compute_paths_spread(&graph, &dest, &me, length, 4, metrics_fn(&graph, length, false));
2613        assert_eq!(4, spread.len());
2614        assert_eq!(4, first_relayers(&spread).len());
2615        Ok(())
2616    }
2617
2618    /// A first relayer's continuations can run back through the source, which the single traversal
2619    /// never returns, and they must not take the place of those that do not. Every relayer here links
2620    /// back to the source, so each first relayer's three-hop subtree holds 6 continuations through it
2621    /// beside its 30 good ones; each share is smaller than either.
2622    #[rstest::rstest]
2623    #[case::forward(true)]
2624    #[case::returning(false)]
2625    fn a_spread_pool_should_fill_each_share_with_paths_that_avoid_the_source(
2626        #[case] forward: bool,
2627    ) -> anyhow::Result<()> {
2628        let (me, dest, relays, graph) = mesh_graph(7, |_| 1000);
2629        let (src, dst) = if forward { (me, dest) } else { (dest, me) };
2630        let length = std::num::NonZeroUsize::new(4).context("non-zero")?;
2631
2632        let per_relayer = 2;
2633        let take = per_relayer * relays.len();
2634        let (spread, _) = compute_paths_spread(&graph, &src, &dst, length, take, metrics_fn(&graph, length, forward));
2635        assert!(
2636            spread.iter().all(|p| !p.path.contains(&src)),
2637            "a path must not run back through its source"
2638        );
2639        assert_eq!(
2640            take,
2641            spread.len(),
2642            "every share filled with paths that avoid the source"
2643        );
2644        for relayer in &relays {
2645            assert_eq!(
2646                per_relayer,
2647                spread.iter().filter(|p| p.path.first() == Some(relayer)).count(),
2648                "each first relayer keeps its whole share"
2649            );
2650        }
2651
2652        // Fewer candidates than first relayers: one from each relayer the pool has room for.
2653        let (cut_short, _) = compute_paths_spread(&graph, &src, &dst, length, 4, metrics_fn(&graph, length, forward));
2654        assert_eq!(4, cut_short.len());
2655        assert_eq!(4, first_relayers(&cut_short).len());
2656        Ok(())
2657    }
2658
2659    /// A subtree whose every continuation is unusable, however large: four searches, each for twice
2660    /// as many as the last, and the share stays empty.
2661    #[test]
2662    fn a_share_search_should_stop_after_its_last_doubling() {
2663        let mut limits = Vec::new();
2664        let found = search_share(
2665            3,
2666            |unusable: &bool| *unusable,
2667            |limit| {
2668                limits.push(limit);
2669                vec![true; limit]
2670            },
2671        );
2672        assert_eq!(vec![3, 6, 12, 24], limits);
2673        assert!(found.iter().all(|unusable| *unusable), "nothing to keep");
2674    }
2675
2676    /// The search stops at the first that found enough usable continuations, and at one that found
2677    /// every continuation there is.
2678    #[test]
2679    fn a_share_search_should_stop_once_enough_are_usable_or_the_subtree_runs_out() {
2680        // Every other continuation is unusable: 2 of 4 are usable, then 4 of 8.
2681        let mut limits = Vec::new();
2682        let found = search_share(
2683            4,
2684            |unusable: &bool| *unusable,
2685            |limit| {
2686                limits.push(limit);
2687                (0..limit).map(|i| i % 2 == 0).collect()
2688            },
2689        );
2690        assert_eq!(vec![4, 8], limits);
2691        assert_eq!(4, found.iter().filter(|unusable| !**unusable).count());
2692
2693        // Five continuations, three unusable: the second search finds all five.
2694        let subtree = [true, false, true, false, true];
2695        let mut limits = Vec::new();
2696        let found = search_share(
2697            4,
2698            |unusable: &bool| *unusable,
2699            |limit| {
2700                limits.push(limit);
2701                subtree.iter().copied().take(limit).collect()
2702            },
2703        );
2704        assert_eq!(vec![4, 8], limits);
2705        assert_eq!(subtree.to_vec(), found);
2706    }
2707
2708    /// A zero edge penalty leaves a path of no value where it applies without a floor: a last hop
2709    /// with nothing observed on it, forward, or with no ack rate, on return. Such a path is dropped
2710    /// and must not take the place of one of value. Every first relayer here reaches the destination
2711    /// over 6 probed relayers and 6 relayers whose last hop is like that, so half its continuations
2712    /// are of no value, and each share is as large as the other half.
2713    #[rstest::rstest]
2714    #[case::forward(true)]
2715    #[case::returning(false)]
2716    fn a_spread_pool_should_fill_each_share_with_paths_of_value(#[case] forward: bool) -> anyhow::Result<()> {
2717        let (me, dest, relays, graph) = mesh_graph(7, |_| 1000);
2718        // Ack rates where the value functions apply them, on the edge from me forward and on the
2719        // edge to me on return: without one, a zero penalty leaves every path of no value.
2720        for r in &relays {
2721            for (a, b) in [(me, *r), (*r, me)] {
2722                graph.upsert_edge(&a, &b, |obs| {
2723                    obs.record(EdgeWeightType::ImmediateProtocolConformance {
2724                        num_packets: 100,
2725                        num_acks: 100,
2726                    });
2727                });
2728            }
2729        }
2730        for _ in 0..6 {
2731            let unprobed = *OffchainKeypair::random().public();
2732            graph.add_node(unprobed);
2733            // Funded from every probed relayer, so these continuations are found.
2734            for r in &relays {
2735                graph.add_edge(r, &unprobed)?;
2736                graph.upsert_edge(r, &unprobed, |obs| {
2737                    obs.record(EdgeWeightType::Connected(true));
2738                    obs.record(EdgeWeightType::Balance(Some(hopr_api::graph::traits::Balance::from(
2739                        1000 * 100,
2740                    ))));
2741                });
2742            }
2743            // On to the destination with nothing observed, and to me connected with no ack rate.
2744            graph.add_edge(&unprobed, &dest)?;
2745            graph.add_edge(&unprobed, &me)?;
2746            graph.upsert_edge(&unprobed, &me, |obs| obs.record(EdgeWeightType::Connected(true)));
2747        }
2748        let (src, dst) = if forward { (me, dest) } else { (dest, me) };
2749        let length = std::num::NonZeroUsize::new(3).context("non-zero")?;
2750        let no_penalty = || {
2751            let (cfg, face) = (PathPlannerConfig::default(), graph.ticket_face_value());
2752            MetricsValueFn {
2753                inner: if forward {
2754                    EdgeValueFn::forward(length, 0.0, cfg.min_ack_rate, face)
2755                } else {
2756                    EdgeValueFn::returning(length, 0.0, cfg.min_ack_rate, face)
2757                },
2758                ticket_face_value: face,
2759            }
2760        };
2761        let take = 6 * relays.len();
2762        let (of_value, of_no_value): (Vec<_>, Vec<_>) = graph
2763            .simple_paths(&src, &dst, length.get(), None, no_penalty())
2764            .into_iter()
2765            .partition(|(.., metrics)| metrics.cost > 0.0);
2766        assert_eq!(
2767            take,
2768            of_value.len(),
2769            "the probed relayers carry 6 paths of value per first relayer"
2770        );
2771        assert_eq!(
2772            take,
2773            of_no_value.len(),
2774            "the unprobed relayers carry as many of no value"
2775        );
2776
2777        let (spread, returned) = compute_paths_spread(&graph, &src, &dst, length, take, no_penalty());
2778        assert!(spread.iter().all(|p| p.cost > 0.0), "a path of no value is dropped");
2779        assert_eq!(take, spread.len(), "every share filled with paths of value");
2780        assert!(returned > spread.len(), "diagnostics also count unusable continuations");
2781        Ok(())
2782    }
2783
2784    /// The selector searches both directions spread over first relayers (pruning off, so the
2785    /// candidates it found are what it returns).
2786    #[tokio::test]
2787    async fn a_three_hop_pool_should_name_every_first_relayer_in_both_directions() -> anyhow::Result<()> {
2788        let (me, dest, relays, graph) = mesh_graph(7, |_| 1000);
2789        let cfg = PathPlannerConfig::default();
2790        let selector =
2791            HoprGraphPathSelector::new(me, graph, cfg.max_cached_paths, cfg.edge_penalty, cfg.min_ack_rate, 0);
2792
2793        let forward = selector.select_path(me, dest, 3).context("forward pool")?;
2794        assert_eq!(relays.len(), distinct_first_relayers(&forward));
2795        let returning = selector.select_path(dest, me, 3).context("return pool")?;
2796        assert_eq!(relays.len(), distinct_first_relayers(&returning));
2797        Ok(())
2798    }
2799}