hopr_network_graph/petgraph/
graph.rs

1use std::sync::Arc;
2
3use bimap::BiHashMap;
4use hopr_api::OffchainPublicKey;
5use parking_lot::RwLock;
6use petgraph::graph::{DiGraph, NodeIndex};
7
8use crate::{Observations, errors::ChannelGraphError};
9
10/// Internal mutable state of a [`ChannelGraph`], protected by a lock.
11#[derive(Debug, Clone, Default)]
12pub(crate) struct InnerGraph {
13    pub(crate) graph: DiGraph<OffchainPublicKey, Observations>,
14    pub(crate) indices: BiHashMap<OffchainPublicKey, NodeIndex>,
15}
16
17/// A directed graph representing logical channels between nodes.
18///
19/// The graph is directed, with nodes representing the physical nodes in the network using
20/// their [`OffchainPublicKey`] as identifier and edges representing the logical channels
21/// between them. Each logical channel aggregates different weighted properties, like
22/// channel capacity (calculated from the on-chain channel balance, ticket price and ticket probability)
23/// and evaluated transport network properties between the nodes.
24///
25/// Interior mutability is provided via an internal [`RwLock`] so that all trait
26/// methods (which take `&self`) can safely read and write the graph. In production
27/// code, the graph is expected to be shared behind an `Arc<ChannelGraph>`.
28#[derive(Debug, Clone)]
29pub struct ChannelGraph {
30    pub(crate) me: OffchainPublicKey,
31    pub(crate) edge_penalty: f64,
32    pub(crate) min_ack_rate: f64,
33    pub(crate) inner: Arc<RwLock<InnerGraph>>,
34}
35
36impl ChannelGraph {
37    /// Creates a new channel graph with the given self identity and default edge scoring
38    /// parameters (edge_penalty = 0.5, min_ack_rate = 0.1).
39    ///
40    /// The `me` key represents the local node which is automatically added
41    /// to the graph as the first node.
42    ///
43    /// Production code should prefer [`with_edge_params`](Self::with_edge_params) to
44    /// receive values from `PathPlannerConfig`.
45    pub fn new(me: OffchainPublicKey) -> Self {
46        Self::with_edge_params(me, 0.5, 0.1)
47    }
48
49    /// Creates a new channel graph with custom edge scoring parameters.
50    ///
51    /// * `me` – offchain public key of the local node (added as the first graph node).
52    /// * `edge_penalty` – penalty multiplier for edges lacking probe-based quality observations.
53    /// * `min_ack_rate` – minimum acceptable message acknowledgment rate for path selection.
54    pub fn with_edge_params(me: OffchainPublicKey, edge_penalty: f64, min_ack_rate: f64) -> Self {
55        let mut graph = DiGraph::new();
56        let mut indices = BiHashMap::new();
57
58        let idx = graph.add_node(me);
59        indices.insert(me, idx);
60
61        Self {
62            me,
63            edge_penalty,
64            min_ack_rate,
65            inner: Arc::new(RwLock::new(InnerGraph { graph, indices })),
66        }
67    }
68
69    /// Returns the self-identity key of this graph.
70    pub fn me(&self) -> &OffchainPublicKey {
71        &self.me
72    }
73}
74
75impl hopr_api::graph::NetworkGraphView for ChannelGraph {
76    type NodeId = OffchainPublicKey;
77    type Observed = Observations;
78
79    fn node_count(&self) -> usize {
80        self.inner.read().graph.node_count()
81    }
82
83    fn contains_node(&self, key: &OffchainPublicKey) -> bool {
84        self.inner.read().indices.contains_left(key)
85    }
86
87    fn nodes(&self) -> futures::stream::BoxStream<'static, Self::NodeId> {
88        let keys: Vec<OffchainPublicKey> = {
89            let inner = self.inner.read();
90            inner.indices.left_values().copied().collect()
91        };
92
93        Box::pin(futures::stream::iter(keys))
94    }
95
96    fn has_edge(&self, src: &OffchainPublicKey, dest: &OffchainPublicKey) -> bool {
97        let inner = self.inner.read();
98        let (Some(src_idx), Some(dest_idx)) = (inner.indices.get_by_left(src), inner.indices.get_by_left(dest)) else {
99            return false;
100        };
101        inner.graph.contains_edge(*src_idx, *dest_idx)
102    }
103
104    fn edge(&self, src: &Self::NodeId, dest: &Self::NodeId) -> Option<Self::Observed> {
105        let inner = self.inner.read();
106        let src_idx = inner.indices.get_by_left(src)?;
107        let dest_idx = inner.indices.get_by_left(dest)?;
108        let edge_idx = inner.graph.find_edge(*src_idx, *dest_idx)?;
109        inner.graph.edge_weight(edge_idx).copied()
110    }
111
112    fn identity(&self) -> &OffchainPublicKey {
113        &self.me
114    }
115}
116
117impl hopr_api::graph::NetworkGraphWrite for ChannelGraph {
118    type Error = ChannelGraphError;
119    type NodeId = OffchainPublicKey;
120    type Observed = Observations;
121
122    fn add_node(&self, key: OffchainPublicKey) {
123        let mut inner = self.inner.write();
124        if !inner.indices.contains_left(&key) {
125            let idx = inner.graph.add_node(key);
126            inner.indices.insert(key, idx);
127        }
128    }
129
130    fn remove_node(&self, key: &OffchainPublicKey) {
131        let mut inner = self.inner.write();
132        if let Some((_, idx)) = inner.indices.remove_by_left(key) {
133            inner.graph.remove_node(idx);
134
135            // petgraph swaps the last node into the removed slot,
136            // so we need to update the index mapping for the swapped node.
137            if let Some(swapped_key) = inner.graph.node_weight(idx) {
138                let swapped_key = *swapped_key;
139                inner.indices.insert(swapped_key, idx);
140            }
141        }
142    }
143
144    fn add_edge(&self, src: &OffchainPublicKey, dest: &OffchainPublicKey) -> Result<(), ChannelGraphError> {
145        let mut inner = self.inner.write();
146        let src_idx = inner
147            .indices
148            .get_by_left(src)
149            .copied()
150            .ok_or(ChannelGraphError::PublicKeyNodeNotFound(*src))?;
151        let dest_idx = inner
152            .indices
153            .get_by_left(dest)
154            .copied()
155            .ok_or(ChannelGraphError::PublicKeyNodeNotFound(*dest))?;
156
157        if inner.graph.find_edge(src_idx, dest_idx).is_none() {
158            inner.graph.add_edge(src_idx, dest_idx, Observations::default());
159        }
160
161        Ok(())
162    }
163
164    fn remove_edge(&self, src: &OffchainPublicKey, dest: &OffchainPublicKey) {
165        let mut inner = self.inner.write();
166        if let (Some(src_idx), Some(dest_idx)) = (
167            inner.indices.get_by_left(src).copied(),
168            inner.indices.get_by_left(dest).copied(),
169        ) && let Some(edge_idx) = inner.graph.find_edge(src_idx, dest_idx)
170        {
171            inner.graph.remove_edge(edge_idx);
172        }
173    }
174
175    /// Mutably updates the edge observations between two nodes.
176    ///
177    /// If the edge does not exist, it gets created first.
178    ///
179    /// If the nodes do not exist, they are added as well.
180    #[tracing::instrument(level = "debug", skip(self, f))]
181    fn upsert_edge<F>(&self, src: &OffchainPublicKey, dest: &OffchainPublicKey, f: F)
182    where
183        F: FnOnce(&mut Observations),
184    {
185        let mut inner = self.inner.write();
186
187        let src_idx = if let Some(src_idx) = inner.indices.get_by_left(src) {
188            *src_idx
189        } else {
190            // src node missing, add it
191            let idx = inner.graph.add_node(*src);
192            inner.indices.insert(*src, idx);
193            idx
194        };
195
196        let dest_idx = if let Some(dest_idx) = inner.indices.get_by_left(dest) {
197            *dest_idx
198        } else {
199            // dest node missing, add it
200            let idx = inner.graph.add_node(*dest);
201            inner.indices.insert(*dest, idx);
202            idx
203        };
204
205        let edge_idx = inner
206            .graph
207            .find_edge(src_idx, dest_idx)
208            .unwrap_or_else(|| inner.graph.add_edge(src_idx, dest_idx, Observations::default()));
209
210        if let Some(weight) = inner.graph.edge_weight_mut(edge_idx) {
211            f(weight);
212            tracing::debug!(%src, %dest, ?weight, "updated edge weight with an observation");
213        }
214    }
215}
216
217impl hopr_api::graph::NetworkGraphConnectivity for ChannelGraph {
218    type NodeId = OffchainPublicKey;
219    type Observed = Observations;
220
221    fn connected_edges(&self) -> Vec<(OffchainPublicKey, OffchainPublicKey, Observations)> {
222        let inner = self.inner.read();
223        inner
224            .graph
225            .edge_indices()
226            .filter_map(|ei| {
227                let (src_idx, dst_idx) = inner.graph.edge_endpoints(ei)?;
228                let src = inner.graph.node_weight(src_idx)?;
229                let dst = inner.graph.node_weight(dst_idx)?;
230                let obs = inner.graph.edge_weight(ei)?;
231                Some((*src, *dst, *obs))
232            })
233            .collect()
234    }
235
236    fn reachable_edges(&self) -> Vec<(OffchainPublicKey, OffchainPublicKey, Observations)> {
237        let inner = self.inner.read();
238        let Some(&me_idx) = inner.indices.get_by_left(&self.me) else {
239            return vec![];
240        };
241
242        let mut reachable = std::collections::HashSet::new();
243        let mut bfs = petgraph::visit::Bfs::new(&inner.graph, me_idx);
244        while let Some(node_idx) = bfs.next(&inner.graph) {
245            reachable.insert(node_idx);
246        }
247
248        inner
249            .graph
250            .edge_indices()
251            .filter_map(|ei| {
252                let (src_idx, dst_idx) = inner.graph.edge_endpoints(ei)?;
253                if !reachable.contains(&src_idx) || !reachable.contains(&dst_idx) {
254                    return None;
255                }
256                let src = inner.graph.node_weight(src_idx)?;
257                let dst = inner.graph.node_weight(dst_idx)?;
258                let obs = inner.graph.edge_weight(ei)?;
259                Some((*src, *dst, *obs))
260            })
261            .collect()
262    }
263}
264
265#[cfg(test)]
266mod tests {
267    use hex_literal::hex;
268    use hopr_api::{
269        graph::{
270            EdgeLinkObservable, NetworkGraphConnectivity, NetworkGraphView, NetworkGraphWrite,
271            traits::{EdgeObservableRead, EdgeObservableWrite, EdgeWeightType},
272        },
273        types::crypto::prelude::{Keypair, OffchainKeypair},
274    };
275
276    use super::*;
277
278    /// Fixed test secret keys (reused from the broader codebase).
279    const SECRET_0: [u8; 32] = hex!("60741b83b99e36aa0c1331578156e16b8e21166d01834abb6c64b103f885734d");
280    const SECRET_1: [u8; 32] = hex!("71bf1f42ebbfcd89c3e197a3fd7cda79b92499e509b6fefa0fe44d02821d146a");
281    const SECRET_2: [u8; 32] = hex!("c24bd833704dd2abdae3933fcc9962c2ac404f84132224c474147382d4db2299");
282    const SECRET_3: [u8; 32] = hex!("e0bf93e9c916104da00b1850adc4608bd7e9087bbd3f805451f4556aa6b3fd6e");
283    const SECRET_4: [u8; 32] = hex!("cfc66f718ec66fb822391775d749d7a0d66b690927673634816b63339bc12a3c");
284    const SECRET_5: [u8; 32] = hex!("203ca4d3c5f98dd2066bb204b5930c10b15c095585c224c826b4e11f08bfa85d");
285    const SECRET_7: [u8; 32] = hex!("4ab03f6f75f845ca1bf8b7104804ea5bda18bda29d1ec5fc5d4267feca5fb8e1");
286
287    /// Creates an OffchainPublicKey from a fixed secret.
288    fn pubkey_from(secret: &[u8; 32]) -> OffchainPublicKey {
289        *OffchainKeypair::from_secret(secret).expect("valid secret key").public()
290    }
291
292    #[test]
293    fn new_graph_contains_self_node() -> anyhow::Result<()> {
294        let me = pubkey_from(&SECRET_0);
295        let graph = ChannelGraph::new(me);
296        assert!(graph.contains_node(&me));
297        assert_eq!(graph.node_count(), 1);
298        Ok(())
299    }
300
301    #[test]
302    fn adding_a_node_increases_count() -> anyhow::Result<()> {
303        let me = pubkey_from(&SECRET_0);
304        let graph = ChannelGraph::new(me);
305        let peer = pubkey_from(&SECRET_1);
306        graph.add_node(peer);
307        assert!(graph.contains_node(&peer));
308        assert_eq!(graph.node_count(), 2);
309        Ok(())
310    }
311
312    #[test]
313    fn adding_duplicate_node_is_idempotent() -> anyhow::Result<()> {
314        let me = pubkey_from(&SECRET_0);
315        let graph = ChannelGraph::new(me);
316        let peer = pubkey_from(&SECRET_1);
317        graph.add_node(peer);
318        graph.add_node(peer);
319        assert_eq!(graph.node_count(), 2);
320        Ok(())
321    }
322
323    #[test]
324    fn removing_a_node_decreases_count() -> anyhow::Result<()> {
325        let me = pubkey_from(&SECRET_0);
326        let graph = ChannelGraph::new(me);
327        let peer = pubkey_from(&SECRET_1);
328        graph.add_node(peer);
329        assert_eq!(graph.node_count(), 2);
330        graph.remove_node(&peer);
331        assert!(!graph.contains_node(&peer));
332        assert_eq!(graph.node_count(), 1);
333        Ok(())
334    }
335
336    #[test]
337    fn removing_nonexistent_node_is_noop() -> anyhow::Result<()> {
338        let me = pubkey_from(&SECRET_0);
339        let graph = ChannelGraph::new(me);
340        graph.remove_node(&pubkey_from(&SECRET_7));
341        assert_eq!(graph.node_count(), 1);
342        Ok(())
343    }
344
345    #[test]
346    fn adding_an_edge_between_nodes() -> anyhow::Result<()> {
347        let me = pubkey_from(&SECRET_0);
348        let graph = ChannelGraph::new(me);
349        let peer = pubkey_from(&SECRET_1);
350        graph.add_node(peer);
351        graph.add_edge(&me, &peer)?;
352        assert!(graph.has_edge(&me, &peer));
353        assert!(!graph.has_edge(&peer, &me));
354        Ok(())
355    }
356
357    #[test]
358    fn adding_edge_to_missing_node_errors() -> anyhow::Result<()> {
359        let me = pubkey_from(&SECRET_0);
360        let graph = ChannelGraph::new(me);
361        assert!(graph.add_edge(&me, &pubkey_from(&SECRET_7)).is_err());
362        Ok(())
363    }
364
365    #[test]
366    fn removing_a_node_also_removes_its_edges() -> anyhow::Result<()> {
367        let me = pubkey_from(&SECRET_0);
368        let graph = ChannelGraph::new(me);
369        let peer = pubkey_from(&SECRET_1);
370        graph.add_node(peer);
371        graph.add_edge(&me, &peer)?;
372        assert!(graph.has_edge(&me, &peer));
373        graph.remove_node(&peer);
374        assert!(!graph.has_edge(&me, &peer));
375        Ok(())
376    }
377
378    #[tokio::test]
379    async fn view_nodes_returns_all_graph_nodes() -> anyhow::Result<()> {
380        use futures::StreamExt;
381
382        let me = pubkey_from(&SECRET_0);
383        let graph = ChannelGraph::new(me);
384        let peers: Vec<_> = [SECRET_1, SECRET_2, SECRET_3, SECRET_4, SECRET_5]
385            .iter()
386            .map(pubkey_from)
387            .collect();
388        for &peer in &peers {
389            graph.add_node(peer);
390        }
391        let nodes: Vec<_> = graph.nodes().collect().await;
392        assert_eq!(nodes.len(), 6);
393        assert!(nodes.contains(&me));
394        for peer in &peers {
395            assert!(nodes.contains(peer));
396        }
397        Ok(())
398    }
399
400    #[test]
401    fn view_edge_returns_observations_for_existing_edge() -> anyhow::Result<()> {
402        let me = pubkey_from(&SECRET_0);
403        let graph = ChannelGraph::new(me);
404        let peer = pubkey_from(&SECRET_1);
405        graph.add_node(peer);
406        graph.add_edge(&me, &peer)?;
407        assert!(graph.edge(&me, &peer).is_some());
408        Ok(())
409    }
410
411    #[test]
412    fn view_edge_returns_none_for_missing_edge() -> anyhow::Result<()> {
413        let me = pubkey_from(&SECRET_0);
414        let graph = ChannelGraph::new(me);
415        let peer = pubkey_from(&SECRET_1);
416        assert!(graph.edge(&me, &peer).is_none());
417        Ok(())
418    }
419
420    #[test]
421    fn me_returns_self_identity() {
422        let me = pubkey_from(&SECRET_0);
423        let graph = ChannelGraph::new(me);
424        assert_eq!(*graph.me(), me);
425    }
426
427    #[test]
428    fn removing_an_edge_disconnects_nodes() -> anyhow::Result<()> {
429        let me = pubkey_from(&SECRET_0);
430        let peer = pubkey_from(&SECRET_1);
431        let graph = ChannelGraph::new(me);
432        graph.add_node(peer);
433        graph.add_edge(&me, &peer)?;
434        assert!(graph.has_edge(&me, &peer));
435
436        graph.remove_edge(&me, &peer);
437        assert!(!graph.has_edge(&me, &peer));
438        // Nodes should still exist
439        assert!(graph.contains_node(&me));
440        assert!(graph.contains_node(&peer));
441        Ok(())
442    }
443
444    #[test]
445    fn removing_nonexistent_edge_is_noop() {
446        let me = pubkey_from(&SECRET_0);
447        let peer = pubkey_from(&SECRET_1);
448        let graph = ChannelGraph::new(me);
449        graph.add_node(peer);
450        // No edge exists — should not panic
451        graph.remove_edge(&me, &peer);
452        assert!(!graph.has_edge(&me, &peer));
453    }
454
455    #[test]
456    fn removing_edge_for_unknown_nodes_is_noop() {
457        let me = pubkey_from(&SECRET_0);
458        let graph = ChannelGraph::new(me);
459        let unknown = pubkey_from(&SECRET_7);
460        // Neither node known — should not panic
461        graph.remove_edge(&me, &unknown);
462    }
463
464    #[test]
465    fn edge_should_not_be_present_when_nodes_not_in_graph() {
466        let me = pubkey_from(&SECRET_0);
467        let graph = ChannelGraph::new(me);
468        let unknown = pubkey_from(&SECRET_7);
469        assert!(!graph.has_edge(&me, &unknown));
470        assert!(!graph.has_edge(&unknown, &me));
471    }
472
473    #[test]
474    fn edge_returns_none_when_nodes_not_in_graph() {
475        let me = pubkey_from(&SECRET_0);
476        let graph = ChannelGraph::new(me);
477        let unknown = pubkey_from(&SECRET_7);
478        assert!(graph.edge(&me, &unknown).is_none());
479        assert!(graph.edge(&unknown, &me).is_none());
480    }
481
482    #[test]
483    fn upsert_edge_creates_edge_when_absent() {
484        let me = pubkey_from(&SECRET_0);
485        let peer = pubkey_from(&SECRET_1);
486        let graph = ChannelGraph::new(me);
487        graph.add_node(peer);
488
489        assert!(!graph.has_edge(&me, &peer));
490        graph.upsert_edge(&me, &peer, |obs| {
491            obs.record(EdgeWeightType::Immediate(Ok(std::time::Duration::from_millis(50))));
492        });
493        assert!(graph.has_edge(&me, &peer));
494
495        let obs = graph.edge(&me, &peer).expect("edge should exist after upsert");
496        assert!(obs.immediate_qos().is_some());
497    }
498
499    #[test]
500    fn upsert_edge_updates_existing_edge() -> anyhow::Result<()> {
501        let me = pubkey_from(&SECRET_0);
502        let peer = pubkey_from(&SECRET_1);
503        let graph = ChannelGraph::new(me);
504        graph.add_node(peer);
505        graph.add_edge(&me, &peer)?;
506
507        graph.upsert_edge(&me, &peer, |obs| {
508            obs.record(EdgeWeightType::Immediate(Ok(std::time::Duration::from_millis(100))));
509        });
510        graph.upsert_edge(&me, &peer, |obs| {
511            obs.record(EdgeWeightType::Immediate(Ok(std::time::Duration::from_millis(200))));
512        });
513
514        let obs = graph.edge(&me, &peer).expect("edge should exist");
515        let latency = obs
516            .immediate_qos()
517            .expect("should have immediate QoS")
518            .average_latency()
519            .expect("should have latency");
520        // After two updates (100ms and 200ms), average should be between 100 and 200
521        assert!(latency > std::time::Duration::from_millis(100));
522        assert!(latency < std::time::Duration::from_millis(200));
523        Ok(())
524    }
525
526    #[test]
527    fn upsert_edge_adds_missing_dest_node_and_creates_edge() {
528        let me = pubkey_from(&SECRET_0);
529        let unknown = pubkey_from(&SECRET_7);
530        let graph = ChannelGraph::new(me);
531
532        assert!(!graph.contains_node(&unknown));
533        graph.upsert_edge(&me, &unknown, |obs| {
534            obs.record(EdgeWeightType::Immediate(Ok(std::time::Duration::from_millis(50))));
535        });
536        assert!(graph.contains_node(&unknown), "dest node should be auto-added");
537        assert!(graph.has_edge(&me, &unknown), "edge should be created");
538        assert!(graph.edge(&me, &unknown).unwrap().immediate_qos().is_some());
539    }
540
541    #[test]
542    fn upsert_edge_adds_missing_src_node_and_creates_edge() {
543        let me = pubkey_from(&SECRET_0);
544        let unknown = pubkey_from(&SECRET_7);
545        let graph = ChannelGraph::new(me);
546
547        assert!(!graph.contains_node(&unknown));
548        graph.upsert_edge(&unknown, &me, |obs| {
549            obs.record(EdgeWeightType::Immediate(Ok(std::time::Duration::from_millis(50))));
550        });
551        assert!(graph.contains_node(&unknown), "src node should be auto-added");
552        assert!(graph.has_edge(&unknown, &me), "edge should be created");
553        assert!(graph.edge(&unknown, &me).unwrap().immediate_qos().is_some());
554    }
555
556    #[test]
557    fn upsert_edge_adds_both_missing_nodes_and_creates_edge() {
558        let me = pubkey_from(&SECRET_0);
559        let a = pubkey_from(&SECRET_1);
560        let b = pubkey_from(&SECRET_2);
561        let graph = ChannelGraph::new(me);
562
563        assert!(!graph.contains_node(&a));
564        assert!(!graph.contains_node(&b));
565        graph.upsert_edge(&a, &b, |obs| {
566            obs.record(EdgeWeightType::Immediate(Ok(std::time::Duration::from_millis(50))));
567        });
568        assert!(graph.contains_node(&a), "src node should be auto-added");
569        assert!(graph.contains_node(&b), "dest node should be auto-added");
570        assert!(graph.has_edge(&a, &b), "edge should be created");
571        assert!(graph.edge(&a, &b).unwrap().immediate_qos().is_some());
572    }
573
574    #[test]
575    fn removing_non_last_node_preserves_other_nodes() -> anyhow::Result<()> {
576        let me = pubkey_from(&SECRET_0);
577        let a = pubkey_from(&SECRET_1);
578        let b = pubkey_from(&SECRET_2);
579        let c = pubkey_from(&SECRET_3);
580
581        let graph = ChannelGraph::new(me);
582        graph.add_node(a);
583        graph.add_node(b);
584        graph.add_node(c);
585        assert_eq!(graph.node_count(), 4);
586
587        // Remove a node that is not the last one (triggers index swap in petgraph)
588        graph.remove_node(&a);
589        assert_eq!(graph.node_count(), 3);
590        assert!(!graph.contains_node(&a));
591        assert!(graph.contains_node(&me));
592        assert!(graph.contains_node(&b));
593        assert!(graph.contains_node(&c));
594
595        // Verify edges can still be added to remaining nodes
596        graph.add_edge(&me, &b)?;
597        graph.add_edge(&me, &c)?;
598        assert!(graph.has_edge(&me, &b));
599        assert!(graph.has_edge(&me, &c));
600        Ok(())
601    }
602
603    #[test]
604    fn removing_multiple_nodes_preserves_consistency() -> anyhow::Result<()> {
605        let me = pubkey_from(&SECRET_0);
606        let a = pubkey_from(&SECRET_1);
607        let b = pubkey_from(&SECRET_2);
608        let c = pubkey_from(&SECRET_3);
609        let d = pubkey_from(&SECRET_4);
610
611        let graph = ChannelGraph::new(me);
612        graph.add_node(a);
613        graph.add_node(b);
614        graph.add_node(c);
615        graph.add_node(d);
616
617        graph.add_edge(&me, &a)?;
618        graph.add_edge(&a, &b)?;
619        graph.add_edge(&b, &c)?;
620        graph.add_edge(&c, &d)?;
621
622        // Remove middle nodes
623        graph.remove_node(&b);
624        graph.remove_node(&c);
625
626        assert_eq!(graph.node_count(), 3);
627        assert!(graph.contains_node(&me));
628        assert!(graph.contains_node(&a));
629        assert!(graph.contains_node(&d));
630
631        // Edges through removed nodes should be gone
632        assert!(!graph.has_edge(&a, &b));
633        assert!(!graph.has_edge(&b, &c));
634        assert!(!graph.has_edge(&c, &d));
635
636        // Edge not involving removed nodes should survive
637        assert!(graph.has_edge(&me, &a));
638        Ok(())
639    }
640
641    #[test]
642    fn edges_are_directed() -> anyhow::Result<()> {
643        let me = pubkey_from(&SECRET_0);
644        let peer = pubkey_from(&SECRET_1);
645        let graph = ChannelGraph::new(me);
646        graph.add_node(peer);
647        graph.add_edge(&me, &peer)?;
648
649        assert!(graph.has_edge(&me, &peer));
650        assert!(!graph.has_edge(&peer, &me));
651
652        assert!(graph.edge(&me, &peer).is_some());
653        assert!(graph.edge(&peer, &me).is_none());
654        Ok(())
655    }
656
657    #[test]
658    fn connected_edges_should_exclude_isolated_nodes() {
659        let me = pubkey_from(&SECRET_0);
660        let a = pubkey_from(&SECRET_1);
661        let isolated = pubkey_from(&SECRET_2);
662        let graph = ChannelGraph::new(me);
663        graph.add_node(a);
664        graph.add_node(isolated); // no edges
665        graph.add_edge(&me, &a).unwrap();
666
667        let edges = graph.connected_edges();
668        assert_eq!(edges.len(), 1);
669        assert_eq!(edges[0].0, me);
670        assert_eq!(edges[0].1, a);
671
672        // isolated node must not appear
673        let all_keys: std::collections::HashSet<_> = edges.iter().flat_map(|(s, d, _)| [*s, *d]).collect();
674        assert!(!all_keys.contains(&isolated));
675    }
676
677    #[test]
678    fn connected_edges_should_preserve_observations() {
679        let me = pubkey_from(&SECRET_0);
680        let peer = pubkey_from(&SECRET_1);
681        let graph = ChannelGraph::new(me);
682        graph.add_node(peer);
683        graph.upsert_edge(&me, &peer, |obs| {
684            obs.record(EdgeWeightType::Connected(true));
685            obs.record(EdgeWeightType::Immediate(Ok(std::time::Duration::from_millis(42))));
686        });
687
688        let edges = graph.connected_edges();
689        assert_eq!(edges.len(), 1);
690        let obs = &edges[0].2;
691        assert!(obs.immediate_qos().is_some());
692    }
693
694    #[test]
695    fn connected_edges_should_be_empty_when_no_edges() {
696        let me = pubkey_from(&SECRET_0);
697        let graph = ChannelGraph::new(me);
698        graph.add_node(pubkey_from(&SECRET_1));
699        assert!(graph.connected_edges().is_empty());
700    }
701
702    #[test]
703    fn connected_edges_should_return_all_edges_in_diamond_topology() -> anyhow::Result<()> {
704        let me = pubkey_from(&SECRET_0);
705        let a = pubkey_from(&SECRET_1);
706        let b = pubkey_from(&SECRET_2);
707        let dest = pubkey_from(&SECRET_3);
708        let graph = ChannelGraph::new(me);
709        for n in [a, b, dest] {
710            graph.add_node(n);
711        }
712        graph.add_edge(&me, &a)?;
713        graph.add_edge(&me, &b)?;
714        graph.add_edge(&a, &dest)?;
715        graph.add_edge(&b, &dest)?;
716
717        let edges = graph.connected_edges();
718        assert_eq!(edges.len(), 4);
719        Ok(())
720    }
721}
hopr_network_graph/petgraph/graph.rs

hopr_network_graph/petgraph/
graph.rs
