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

hopr_network_graph/petgraph/
graph.rs
