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

hopr_network_graph/petgraph/
graph.rs
