networkit_rs/
distance.rs

1use std::collections::BTreeMap;
2
3use cxx::{CxxVector, UniquePtr};
4use miette::IntoDiagnostic;
5
6use crate::{
7    base::Algorithm,
8    base::DynAlgorithm,
9    bridge::{self, *},
10    community::ValueIter,
11    tools::NodeIter,
12};
13
14pub trait STSP: Algorithm {
15    fn get_path(&self) -> NodeIter;
16    fn get_predecessors(&self) -> NodeIter;
17    fn get_distance(&self) -> f64;
18    fn get_distances(&self) -> ValueIter;
19    fn set_source(&mut self, u: u64);
20    fn set_target(&mut self, v: u64);
21    fn set_targets(&mut self, vs: &[u64]);
22    fn get_target_index_map(&self) -> BTreeMap<u64, u64>;
23}
24
25pub trait SSSP: Algorithm {
26    fn distance(&self, t: u64) -> f64;
27    fn get_distances(&mut self) -> ValueIter;
28    fn number_of_paths(&self, t: u64) -> f64;
29    fn get_predecessors(&self, t: u64) -> NodeIter;
30    fn get_path(&self, t: u64, forward: bool) -> NodeIter;
31    fn get_paths(&self, t: u64, forward: bool) -> Vec<Vec<u64>>;
32    fn get_node_sorted_by_distances(&self) -> NodeIter;
33    fn get_num_reachable_nodes(&self) -> u64;
34    fn set_source(&mut self, u: u64);
35    fn set_target(&mut self, v: u64);
36    fn get_sum_of_distances(&self) -> f64;
37}
38
39pub trait DynSSSP: SSSP + DynAlgorithm {
40    fn modified(&mut self) -> bool;
41    fn set_target_node(&mut self, t: u64);
42}
43
44pub trait NodeDistance {
45    fn preprocess(&mut self);
46    fn distance(&mut self, u: u64, v: u64) -> f64;
47    fn get_edge_scores(&self) -> ValueIter;
48}
49
50pub struct APSP {
51    inner: UniquePtr<bridge::APSP>,
52}
53
54impl APSP {
55    pub fn new(g: &crate::Graph) -> Self {
56        Self { inner: NewAPSP(g) }
57    }
58    pub fn get_distance(&self, u: u64, v: u64) -> f64 {
59        self.inner.getDistance(u, v)
60    }
61    pub fn get_distances(&self) -> BTreeMap<u64, BTreeMap<u64, f64>> {
62        let mut ret: BTreeMap<u64, BTreeMap<u64, f64>> = BTreeMap::new();
63        let mut r = vec![];
64        let n = APSPGetDistances(&self.inner, &mut r);
65        for (i, wt) in r.into_iter().enumerate() {
66            let i = i as u64;
67            let src = i / n;
68            let dst = i % n;
69            ret.entry(src).or_default().insert(dst, wt);
70        }
71        ret
72    }
73}
74
75impl Algorithm for APSP {
76    fn run(&mut self) -> miette::Result<()> {
77        self.inner.pin_mut().run().into_diagnostic()
78    }
79
80    fn has_finished(&self) -> bool {
81        self.inner.hasFinished()
82    }
83}
84
85pub struct AStar {
86    inner: UniquePtr<bridge::AStar>,
87    _heu: UniquePtr<CxxVector<f64>>,
88}
89
90impl AStar {
91    pub fn new(g: &crate::Graph, heuristic: &[f64], src: u64, dst: u64, store_pred: bool) -> Self {
92        let heu = MakeWeightVector(heuristic);
93        let inner = NewAStar(g, &heu, src, dst, store_pred);
94        Self { inner, _heu: heu }
95    }
96}
97
98impl Algorithm for AStar {
99    fn run(&mut self) -> miette::Result<()> {
100        self.inner.pin_mut().run().into_diagnostic()
101    }
102
103    fn has_finished(&self) -> bool {
104        self.inner.hasFinished()
105    }
106}
107
108impl STSP for AStar {
109    fn get_path(&self) -> NodeIter {
110        NodeIter {
111            at: 0,
112            nodes: AStarGetPath(&self.inner),
113        }
114    }
115
116    fn get_predecessors(&self) -> NodeIter {
117        NodeIter {
118            at: 0,
119            nodes: AStarGetPredecessors(&self.inner),
120        }
121    }
122
123    fn set_source(&mut self, u: u64) {
124        self.inner.pin_mut().setSource(u)
125    }
126
127    fn set_target(&mut self, v: u64) {
128        self.inner.pin_mut().setTarget(v)
129    }
130
131    fn set_targets(&mut self, vs: &[u64]) {
132        AStarSetTargets(self.inner.pin_mut(), vs);
133    }
134
135    fn get_target_index_map(&self) -> BTreeMap<u64, u64> {
136        let mut ks = vec![];
137        let mut vs = vec![];
138        AStarGetTargetIndexMap(&self.inner, &mut ks, &mut vs);
139        ks.into_iter().zip(vs).collect()
140    }
141
142    fn get_distance(&self) -> f64 {
143        self.inner.getDistance()
144    }
145
146    fn get_distances(&self) -> ValueIter {
147        ValueIter {
148            inner: AStarGetDistances(&self.inner),
149            at: 0,
150        }
151    }
152}
153
154pub struct AdamicAdarDistance {
155    inner: UniquePtr<bridge::AdamicAdarDistance>,
156}
157
158impl AdamicAdarDistance {
159    pub fn new(g: &crate::Graph) -> Self {
160        Self {
161            inner: NewAdamicAdarDistance(g),
162        }
163    }
164}
165
166impl NodeDistance for AdamicAdarDistance {
167    fn preprocess(&mut self) {
168        self.inner.pin_mut().preprocess()
169    }
170
171    fn distance(&mut self, u: u64, v: u64) -> f64 {
172        self.inner.pin_mut().distance(u, v)
173    }
174
175    fn get_edge_scores(&self) -> ValueIter {
176        ValueIter {
177            at: 0,
178            inner: AdamicAdarDistanceGetEdgeScores(&self.inner),
179        }
180    }
181}
182
183pub struct AlgebraicDistance {
184    inner: UniquePtr<bridge::AlgebraicDistance>,
185}
186
187impl AlgebraicDistance {
188    pub fn new(
189        g: &crate::Graph,
190        n_systems: Option<u64>,
191        n_iterations: Option<u64>,
192        omega: Option<f64>,
193        norm: Option<u64>,
194        with_edge_scores: bool,
195    ) -> Self {
196        Self {
197            inner: NewAlgebraicDistance(
198                g,
199                n_systems.unwrap_or(10),
200                n_iterations.unwrap_or(30),
201                omega.unwrap_or(0.5),
202                norm.unwrap_or(0),
203                with_edge_scores,
204            ),
205        }
206    }
207}
208
209impl NodeDistance for AlgebraicDistance {
210    fn preprocess(&mut self) {
211        self.inner.pin_mut().preprocess()
212    }
213
214    fn distance(&mut self, u: u64, v: u64) -> f64 {
215        self.inner.pin_mut().distance(u, v)
216    }
217
218    fn get_edge_scores(&self) -> ValueIter {
219        ValueIter {
220            at: 0,
221            inner: AlgebraicDistanceGetEdgeScores(&self.inner),
222        }
223    }
224}
225
226pub struct AllSimplePaths {
227    inner: UniquePtr<bridge::AllSimplePaths>,
228}
229
230impl AllSimplePaths {
231    pub fn new(g: &crate::Graph, src: u64, dst: u64, cutoff: u64) -> Self {
232        Self {
233            inner: NewAllSimplePaths(g, src, dst, cutoff),
234        }
235    }
236
237    pub fn number_of_simple_paths(&mut self) -> u64 {
238        self.inner.pin_mut().numberOfSimplePaths()
239    }
240
241    pub fn get_all_simple_paths(&mut self) -> Vec<Vec<u64>> {
242        let mut temp = vec![];
243        AllSimplePathsGetAllSimplePaths(self.inner.pin_mut(), &mut temp);
244        let mut ret = vec![];
245        let mut cur = vec![];
246        for n in temp {
247            if n == u64::MAX {
248                ret.push(cur);
249                cur = vec![];
250            } else {
251                cur.push(n);
252            }
253        }
254        ret
255    }
256}
257
258impl Algorithm for AllSimplePaths {
259    fn run(&mut self) -> miette::Result<()> {
260        self.inner.pin_mut().run().into_diagnostic()
261    }
262
263    fn has_finished(&self) -> bool {
264        self.inner.hasFinished()
265    }
266}
267
268pub struct Dijkstra {
269    inner: UniquePtr<bridge::Dijkstra>,
270}
271
272impl Dijkstra {
273    pub fn new(
274        g: &crate::Graph,
275        src: u64,
276        store_paths: bool,
277        store_nodes_sorted_by_distance: bool,
278        dst: Option<u64>,
279    ) -> Self {
280        Self {
281            inner: NewDijkstra(
282                g,
283                src,
284                store_paths,
285                store_nodes_sorted_by_distance,
286                dst.unwrap_or(u64::MAX),
287            ),
288        }
289    }
290}
291
292impl Algorithm for Dijkstra {
293    fn run(&mut self) -> miette::Result<()> {
294        self.inner.pin_mut().run().into_diagnostic()
295    }
296
297    fn has_finished(&self) -> bool {
298        self.inner.hasFinished()
299    }
300}
301
302impl SSSP for Dijkstra {
303    fn distance(&self, t: u64) -> f64 {
304        self.inner.distance(t)
305    }
306
307    fn get_distances(&mut self) -> ValueIter {
308        ValueIter {
309            at: 0,
310            inner: DijkstraGetDistances(self.inner.pin_mut()),
311        }
312    }
313
314    fn number_of_paths(&self, t: u64) -> f64 {
315        self.inner._numberOfPaths(t)
316    }
317
318    fn get_predecessors(&self, t: u64) -> NodeIter {
319        NodeIter {
320            at: 0,
321            nodes: DijkstraGetPredecessors(&self.inner, t),
322        }
323    }
324
325    fn get_path(&self, t: u64, forward: bool) -> NodeIter {
326        NodeIter {
327            at: 0,
328            nodes: DijkstraGetPath(&self.inner, t, forward),
329        }
330    }
331
332    fn get_paths(&self, t: u64, forward: bool) -> Vec<Vec<u64>> {
333        let mut temp = vec![];
334        DijkstraGetPaths(&self.inner, t, forward, &mut temp);
335        let mut ret = vec![];
336        let mut cur = vec![];
337        for n in temp {
338            if n == u64::MAX {
339                ret.push(cur);
340                cur = vec![];
341            } else {
342                cur.push(n);
343            }
344        }
345        ret
346    }
347
348    fn get_node_sorted_by_distances(&self) -> NodeIter {
349        NodeIter {
350            at: 0,
351            nodes: DijkstraGetNodeSortedByDistance(&self.inner),
352        }
353    }
354
355    fn get_num_reachable_nodes(&self) -> u64 {
356        self.inner.getReachableNodes()
357    }
358
359    fn set_source(&mut self, u: u64) {
360        self.inner.pin_mut().setSource(u)
361    }
362
363    fn set_target(&mut self, v: u64) {
364        self.inner.pin_mut().setTarget(v)
365    }
366
367    fn get_sum_of_distances(&self) -> f64 {
368        self.inner.getSumOfDistances()
369    }
370}
371
372pub struct BidirectionalBFS {
373    inner: UniquePtr<bridge::BidirectionalBFS>,
374}
375
376impl BidirectionalBFS {
377    pub fn new(g: &crate::Graph, src: u64, dst: u64, store_pred: bool) -> Self {
378        let inner = NewBidirectionalBFS(g, src, dst, store_pred);
379        Self { inner }
380    }
381}
382
383impl Algorithm for BidirectionalBFS {
384    fn run(&mut self) -> miette::Result<()> {
385        self.inner.pin_mut().run().into_diagnostic()
386    }
387
388    fn has_finished(&self) -> bool {
389        self.inner.hasFinished()
390    }
391}
392
393impl STSP for BidirectionalBFS {
394    fn get_path(&self) -> NodeIter {
395        NodeIter {
396            at: 0,
397            nodes: BidirectionalBFSGetPath(&self.inner),
398        }
399    }
400
401    fn get_predecessors(&self) -> NodeIter {
402        NodeIter {
403            at: 0,
404            nodes: BidirectionalBFSGetPredecessors(&self.inner),
405        }
406    }
407
408    fn set_source(&mut self, u: u64) {
409        self.inner.pin_mut().setSource(u)
410    }
411
412    fn set_target(&mut self, v: u64) {
413        self.inner.pin_mut().setTarget(v)
414    }
415
416    fn set_targets(&mut self, vs: &[u64]) {
417        BidirectionalBFSSetTargets(self.inner.pin_mut(), vs);
418    }
419
420    fn get_target_index_map(&self) -> BTreeMap<u64, u64> {
421        let mut ks = vec![];
422        let mut vs = vec![];
423        BidirectionalBFSGetTargetIndexMap(&self.inner, &mut ks, &mut vs);
424        ks.into_iter().zip(vs).collect()
425    }
426
427    fn get_distance(&self) -> f64 {
428        self.inner.getDistance()
429    }
430
431    fn get_distances(&self) -> ValueIter {
432        ValueIter {
433            inner: BidirectionalBFSGetDistances(&self.inner),
434            at: 0,
435        }
436    }
437}
438
439pub struct BidirectionalDijkstra {
440    inner: UniquePtr<bridge::BidirectionalDijkstra>,
441}
442
443impl BidirectionalDijkstra {
444    pub fn new(g: &crate::Graph, src: u64, dst: u64, store_pred: bool) -> Self {
445        let inner = NewBidirectionalDijkstra(g, src, dst, store_pred);
446        Self { inner }
447    }
448}
449
450impl Algorithm for BidirectionalDijkstra {
451    fn run(&mut self) -> miette::Result<()> {
452        self.inner.pin_mut().run().into_diagnostic()
453    }
454
455    fn has_finished(&self) -> bool {
456        self.inner.hasFinished()
457    }
458}
459
460impl STSP for BidirectionalDijkstra {
461    fn get_path(&self) -> NodeIter {
462        NodeIter {
463            at: 0,
464            nodes: BidirectionalDijkstraGetPath(&self.inner),
465        }
466    }
467
468    fn get_predecessors(&self) -> NodeIter {
469        NodeIter {
470            at: 0,
471            nodes: BidirectionalDijkstraGetPredecessors(&self.inner),
472        }
473    }
474
475    fn set_source(&mut self, u: u64) {
476        self.inner.pin_mut().setSource(u)
477    }
478
479    fn set_target(&mut self, v: u64) {
480        self.inner.pin_mut().setTarget(v)
481    }
482
483    fn set_targets(&mut self, vs: &[u64]) {
484        BidirectionalDijkstraSetTargets(self.inner.pin_mut(), vs);
485    }
486
487    fn get_target_index_map(&self) -> BTreeMap<u64, u64> {
488        let mut ks = vec![];
489        let mut vs = vec![];
490        BidirectionalDijkstraGetTargetIndexMap(&self.inner, &mut ks, &mut vs);
491        ks.into_iter().zip(vs).collect()
492    }
493
494    fn get_distance(&self) -> f64 {
495        self.inner.getDistance()
496    }
497
498    fn get_distances(&self) -> ValueIter {
499        ValueIter {
500            inner: BidirectionalDijkstraGetDistances(&self.inner),
501            at: 0,
502        }
503    }
504}
505
506pub struct CommuteTimeDistance {
507    inner: UniquePtr<bridge::CommuteTimeDistance>,
508}
509
510impl CommuteTimeDistance {
511    pub fn new(g: &crate::Graph, tol: Option<f64>) -> Self {
512        let inner = NewCommuteTimeDistance(g, tol.unwrap_or(0.1));
513        Self { inner }
514    }
515
516    pub fn run_approximation(&mut self) {
517        self.inner.pin_mut().runApproximation()
518    }
519    pub fn run_parallel_approximation(&mut self) {
520        self.inner.pin_mut().runParallelApproximation()
521    }
522    pub fn get_startup_time(&self) -> u64 {
523        self.inner.getSetupTime()
524    }
525    pub fn run_single_pair(&mut self, u: u64, v: u64) -> f64 {
526        self.inner.pin_mut().runSinglePair(u, v)
527    }
528    pub fn distance(&mut self, u: u64, v: u64) -> f64 {
529        self.inner.pin_mut().distance(u, v)
530    }
531    pub fn run_single_source(&mut self, u: u64) -> f64 {
532        self.inner.pin_mut().runSingleSource(u)
533    }
534}
535
536impl Algorithm for CommuteTimeDistance {
537    fn run(&mut self) -> miette::Result<()> {
538        self.inner.pin_mut().run().into_diagnostic()
539    }
540
541    fn has_finished(&self) -> bool {
542        self.inner.hasFinished()
543    }
544}
545
546pub struct Diameter {
547    inner: UniquePtr<bridge::Diameter>,
548}
549
550#[derive(Default, Copy, Clone, Eq, PartialEq)]
551#[repr(u8)]
552
553pub enum DiameterAlgorithm {
554    #[default]
555    Automatic = 0,
556    Exact = 1,
557    EstimatedRange = 2,
558    EstimatedSamples = 3,
559    EstimatedPedantic = 4,
560}
561
562impl Diameter {
563    pub fn new(
564        g: &crate::Graph,
565        algo: DiameterAlgorithm,
566        error: Option<f64>,
567        n_samples: Option<u64>,
568    ) -> Self {
569        let inner = NewDiameter(g, algo as u8, error.unwrap_or(-1.), n_samples.unwrap_or(0));
570        Self { inner }
571    }
572    pub fn get_diameter(&self) -> (u64, u64) {
573        let mut lower = 0;
574        let mut upper = 0;
575        DiameterGetDiameter(&self.inner, &mut lower, &mut upper);
576        (lower, upper)
577    }
578}
579
580impl Algorithm for Diameter {
581    fn run(&mut self) -> miette::Result<()> {
582        self.inner.pin_mut().run().into_diagnostic()
583    }
584
585    fn has_finished(&self) -> bool {
586        self.inner.hasFinished()
587    }
588}
589
590pub struct BFS {
591    inner: UniquePtr<bridge::BFS>,
592}
593
594impl BFS {
595    pub fn new(
596        g: &crate::Graph,
597        src: u64,
598        store_paths: bool,
599        store_nodes_sorted_by_distance: bool,
600        dst: Option<u64>,
601    ) -> Self {
602        Self {
603            inner: NewBFS(
604                g,
605                src,
606                store_paths,
607                store_nodes_sorted_by_distance,
608                dst.unwrap_or(u64::MAX),
609            ),
610        }
611    }
612}
613
614impl Algorithm for BFS {
615    fn run(&mut self) -> miette::Result<()> {
616        self.inner.pin_mut().run().into_diagnostic()
617    }
618
619    fn has_finished(&self) -> bool {
620        self.inner.hasFinished()
621    }
622}
623
624impl SSSP for BFS {
625    fn distance(&self, t: u64) -> f64 {
626        self.inner.distance(t)
627    }
628
629    fn get_distances(&mut self) -> ValueIter {
630        ValueIter {
631            at: 0,
632            inner: BFSGetDistances(self.inner.pin_mut()),
633        }
634    }
635
636    fn number_of_paths(&self, t: u64) -> f64 {
637        self.inner._numberOfPaths(t)
638    }
639
640    fn get_predecessors(&self, t: u64) -> NodeIter {
641        NodeIter {
642            at: 0,
643            nodes: BFSGetPredecessors(&self.inner, t),
644        }
645    }
646
647    fn get_path(&self, t: u64, forward: bool) -> NodeIter {
648        NodeIter {
649            at: 0,
650            nodes: BFSGetPath(&self.inner, t, forward),
651        }
652    }
653
654    fn get_paths(&self, t: u64, forward: bool) -> Vec<Vec<u64>> {
655        let mut temp = vec![];
656        BFSGetPaths(&self.inner, t, forward, &mut temp);
657        let mut ret = vec![];
658        let mut cur = vec![];
659        for n in temp {
660            if n == u64::MAX {
661                ret.push(cur);
662                cur = vec![];
663            } else {
664                cur.push(n);
665            }
666        }
667        ret
668    }
669
670    fn get_node_sorted_by_distances(&self) -> NodeIter {
671        NodeIter {
672            at: 0,
673            nodes: BFSGetNodeSortedByDistance(&self.inner),
674        }
675    }
676
677    fn get_num_reachable_nodes(&self) -> u64 {
678        self.inner.getReachableNodes()
679    }
680
681    fn set_source(&mut self, u: u64) {
682        self.inner.pin_mut().setSource(u)
683    }
684
685    fn set_target(&mut self, v: u64) {
686        self.inner.pin_mut().setTarget(v)
687    }
688
689    fn get_sum_of_distances(&self) -> f64 {
690        self.inner.getSumOfDistances()
691    }
692}
693
694pub struct DynAPSP {
695    inner: UniquePtr<bridge::DynAPSP>,
696}
697
698impl DynAPSP {
699    pub fn new(g: &mut crate::Graph) -> Self {
700        Self {
701            inner: NewDynAPSP(g.inner.pin_mut()),
702        }
703    }
704    pub fn get_distance(&self, u: u64, v: u64) -> f64 {
705        self.inner.getDistance(u, v)
706    }
707    pub fn get_distances(&self) -> BTreeMap<u64, BTreeMap<u64, f64>> {
708        let mut ret: BTreeMap<u64, BTreeMap<u64, f64>> = BTreeMap::new();
709        let mut r = vec![];
710        let n = DynAPSPGetDistances(&self.inner, &mut r);
711        for (i, wt) in r.into_iter().enumerate() {
712            let i = i as u64;
713            let src = i / n;
714            let dst = i % n;
715            ret.entry(src).or_default().insert(dst, wt);
716        }
717        ret
718    }
719}
720
721impl Algorithm for DynAPSP {
722    fn run(&mut self) -> miette::Result<()> {
723        self.inner.pin_mut().run().into_diagnostic()
724    }
725
726    fn has_finished(&self) -> bool {
727        self.inner.hasFinished()
728    }
729}
730
731impl DynAlgorithm for DynAPSP {
732    fn update(&mut self, e: crate::base::GraphEvent) {
733        DynAPSPUpdate(self.inner.pin_mut(), e.kind as u8, e.u, e.v, e.ew)
734    }
735
736    fn update_batch(&mut self, es: &[crate::base::GraphEvent]) {
737        let mut kinds = Vec::with_capacity(es.len());
738        let mut us = Vec::with_capacity(es.len());
739        let mut vs = Vec::with_capacity(es.len());
740        let mut ews = Vec::with_capacity(es.len());
741        for ev in es {
742            kinds.push(ev.kind as u8);
743            us.push(ev.u);
744            vs.push(ev.v);
745            ews.push(ev.ew);
746        }
747        DynAPSPUpdateBatch(self.inner.pin_mut(), &kinds, &us, &vs, &ews);
748    }
749}
750
751pub struct DynBFS {
752    inner: UniquePtr<bridge::DynBFS>,
753}
754
755impl DynBFS {
756    pub fn new(g: &crate::Graph, src: u64, store_predecessors: bool) -> Self {
757        Self {
758            inner: NewDynBFS(g, src, store_predecessors),
759        }
760    }
761}
762
763impl Algorithm for DynBFS {
764    fn run(&mut self) -> miette::Result<()> {
765        self.inner.pin_mut().run().into_diagnostic()
766    }
767
768    fn has_finished(&self) -> bool {
769        self.inner.hasFinished()
770    }
771}
772
773impl SSSP for DynBFS {
774    fn distance(&self, t: u64) -> f64 {
775        self.inner.distance(t)
776    }
777
778    fn get_distances(&mut self) -> ValueIter {
779        ValueIter {
780            at: 0,
781            inner: DynBFSGetDistances(self.inner.pin_mut()),
782        }
783    }
784
785    fn number_of_paths(&self, t: u64) -> f64 {
786        self.inner._numberOfPaths(t)
787    }
788
789    fn get_predecessors(&self, t: u64) -> NodeIter {
790        NodeIter {
791            at: 0,
792            nodes: DynBFSGetPredecessors(&self.inner, t),
793        }
794    }
795
796    fn get_path(&self, t: u64, forward: bool) -> NodeIter {
797        NodeIter {
798            at: 0,
799            nodes: DynBFSGetPath(&self.inner, t, forward),
800        }
801    }
802
803    fn get_paths(&self, t: u64, forward: bool) -> Vec<Vec<u64>> {
804        let mut temp = vec![];
805        DynBFSGetPaths(&self.inner, t, forward, &mut temp);
806        let mut ret = vec![];
807        let mut cur = vec![];
808        for n in temp {
809            if n == u64::MAX {
810                ret.push(cur);
811                cur = vec![];
812            } else {
813                cur.push(n);
814            }
815        }
816        ret
817    }
818
819    fn get_node_sorted_by_distances(&self) -> NodeIter {
820        NodeIter {
821            at: 0,
822            nodes: DynBFSGetNodeSortedByDistance(&self.inner),
823        }
824    }
825
826    fn get_num_reachable_nodes(&self) -> u64 {
827        self.inner.getReachableNodes()
828    }
829
830    fn set_source(&mut self, u: u64) {
831        self.inner.pin_mut().setSource(u)
832    }
833
834    fn set_target(&mut self, v: u64) {
835        self.inner.pin_mut().setTarget(v)
836    }
837
838    fn get_sum_of_distances(&self) -> f64 {
839        self.inner.getSumOfDistances()
840    }
841}
842
843impl DynAlgorithm for DynBFS {
844    fn update(&mut self, e: crate::base::GraphEvent) {
845        DynBFSUpdate(self.inner.pin_mut(), e.kind as u8, e.u, e.v, e.ew)
846    }
847
848    fn update_batch(&mut self, es: &[crate::base::GraphEvent]) {
849        let mut kinds = Vec::with_capacity(es.len());
850        let mut us = Vec::with_capacity(es.len());
851        let mut vs = Vec::with_capacity(es.len());
852        let mut ews = Vec::with_capacity(es.len());
853        for ev in es {
854            kinds.push(ev.kind as u8);
855            us.push(ev.u);
856            vs.push(ev.v);
857            ews.push(ev.ew);
858        }
859        DynBFSUpdateBatch(self.inner.pin_mut(), &kinds, &us, &vs, &ews);
860    }
861}
862
863impl DynSSSP for DynBFS {
864    fn modified(&mut self) -> bool {
865        self.inner.pin_mut().modified()
866    }
867
868    fn set_target_node(&mut self, t: u64) {
869        self.inner.pin_mut().setTargetNode(t)
870    }
871}
872
873pub struct Eccentricity;
874
875impl Eccentricity {
876    pub fn get_value(g: &crate::Graph, u: u64) -> (u64, u64) {
877        let mut fartherest = 0;
878        let mut dist = 0;
879        EccentricityGetValue(g, u, &mut fartherest, &mut dist);
880        (fartherest, dist)
881    }
882}
883
884pub struct EffectiveDiameter {
885    inner: UniquePtr<bridge::EffectiveDiameter>,
886}
887
888impl EffectiveDiameter {
889    pub fn new(g: &crate::Graph, ratio: Option<f64>) -> Self {
890        let inner = NewEffectiveDiameter(g, ratio.unwrap_or(0.9));
891        Self { inner }
892    }
893    pub fn get_effective_diameter(&self) -> f64 {
894        self.inner.getEffectiveDiameter()
895    }
896}
897
898impl Algorithm for EffectiveDiameter {
899    fn run(&mut self) -> miette::Result<()> {
900        self.inner.pin_mut().run().into_diagnostic()
901    }
902
903    fn has_finished(&self) -> bool {
904        self.inner.hasFinished()
905    }
906}
907
908pub struct EffectiveDiameterApproximation {
909    inner: UniquePtr<bridge::EffectiveDiameterApproximation>,
910}
911
912impl EffectiveDiameterApproximation {
913    pub fn new(g: &crate::Graph, ratio: Option<f64>, k: Option<u64>, r: Option<u64>) -> Self {
914        let inner = NewEffectiveDiameterApproximation(
915            g,
916            ratio.unwrap_or(0.9),
917            k.unwrap_or(64),
918            r.unwrap_or(7),
919        );
920        Self { inner }
921    }
922    pub fn get_effective_diameter(&self) -> f64 {
923        self.inner.getEffectiveDiameter()
924    }
925}
926
927impl Algorithm for EffectiveDiameterApproximation {
928    fn run(&mut self) -> miette::Result<()> {
929        self.inner.pin_mut().run().into_diagnostic()
930    }
931
932    fn has_finished(&self) -> bool {
933        self.inner.hasFinished()
934    }
935}
936
937pub struct HopPlotApproximation {
938    inner: UniquePtr<bridge::HopPlotApproximation>,
939}
940
941impl HopPlotApproximation {
942    pub fn new(
943        g: &crate::Graph,
944        max_distance: Option<u64>,
945        k: Option<u64>,
946        r: Option<u64>,
947    ) -> Self {
948        let inner = NewHopPlotApproximation(
949            g,
950            max_distance.unwrap_or(0),
951            k.unwrap_or(64),
952            r.unwrap_or(7),
953        );
954        Self { inner }
955    }
956    pub fn get_hop_plot(&self) -> BTreeMap<u64, f64> {
957        let mut ks = vec![];
958        let mut vs = vec![];
959        HopPlotApproximationGetHopPlot(&self.inner, &mut ks, &mut vs);
960        ks.into_iter().zip(vs).collect()
961    }
962}
963
964impl Algorithm for HopPlotApproximation {
965    fn run(&mut self) -> miette::Result<()> {
966        self.inner.pin_mut().run().into_diagnostic()
967    }
968
969    fn has_finished(&self) -> bool {
970        self.inner.hasFinished()
971    }
972}
973
974pub struct JaccardDistance {
975    inner: UniquePtr<bridge::JaccardDistance>,
976    _triangles: UniquePtr<CxxVector<u64>>,
977}
978
979impl JaccardDistance {
980    pub fn new(g: &crate::Graph, triangles: &[u64]) -> Self {
981        let t = MakeCountVector(triangles);
982        let inner = NewJaccardDistance(g, &t);
983        Self {
984            inner,
985            _triangles: t,
986        }
987    }
988}
989
990impl NodeDistance for JaccardDistance {
991    fn preprocess(&mut self) {
992        self.inner.pin_mut().preprocess()
993    }
994
995    fn distance(&mut self, u: u64, v: u64) -> f64 {
996        self.inner.pin_mut().distance(u, v)
997    }
998
999    fn get_edge_scores(&self) -> ValueIter {
1000        ValueIter {
1001            at: 0,
1002            inner: JaccardDistanceGetEdgeScores(&self.inner),
1003        }
1004    }
1005}
1006
1007pub struct MultiTargetBFS {
1008    inner: UniquePtr<bridge::MultiTargetBFS>,
1009}
1010
1011impl MultiTargetBFS {
1012    pub fn new(g: &crate::Graph, src: u64, targets: &[u64]) -> Self {
1013        let inner = NewMultiTargetBFS(g, src, targets);
1014        Self { inner }
1015    }
1016}
1017
1018impl Algorithm for MultiTargetBFS {
1019    fn run(&mut self) -> miette::Result<()> {
1020        self.inner.pin_mut().run().into_diagnostic()
1021    }
1022
1023    fn has_finished(&self) -> bool {
1024        self.inner.hasFinished()
1025    }
1026}
1027
1028impl STSP for MultiTargetBFS {
1029    fn get_path(&self) -> NodeIter {
1030        NodeIter {
1031            at: 0,
1032            nodes: MultiTargetBFSGetPath(&self.inner),
1033        }
1034    }
1035
1036    fn get_predecessors(&self) -> NodeIter {
1037        NodeIter {
1038            at: 0,
1039            nodes: MultiTargetBFSGetPredecessors(&self.inner),
1040        }
1041    }
1042
1043    fn set_source(&mut self, u: u64) {
1044        self.inner.pin_mut().setSource(u)
1045    }
1046
1047    fn set_target(&mut self, v: u64) {
1048        self.inner.pin_mut().setTarget(v)
1049    }
1050
1051    fn set_targets(&mut self, vs: &[u64]) {
1052        MultiTargetBFSSetTargets(self.inner.pin_mut(), vs);
1053    }
1054
1055    fn get_target_index_map(&self) -> BTreeMap<u64, u64> {
1056        let mut ks = vec![];
1057        let mut vs = vec![];
1058        MultiTargetBFSGetTargetIndexMap(&self.inner, &mut ks, &mut vs);
1059        ks.into_iter().zip(vs).collect()
1060    }
1061
1062    fn get_distance(&self) -> f64 {
1063        self.inner.getDistance()
1064    }
1065
1066    fn get_distances(&self) -> ValueIter {
1067        ValueIter {
1068            inner: MultiTargetBFSGetDistances(&self.inner),
1069            at: 0,
1070        }
1071    }
1072}
1073
1074pub struct MultiTargetDijkstra {
1075    inner: UniquePtr<bridge::MultiTargetDijkstra>,
1076}
1077
1078impl MultiTargetDijkstra {
1079    pub fn new(g: &crate::Graph, src: u64, targets: &[u64]) -> Self {
1080        let inner = NewMultiTargetDijkstra(g, src, targets);
1081        Self { inner }
1082    }
1083}
1084
1085impl Algorithm for MultiTargetDijkstra {
1086    fn run(&mut self) -> miette::Result<()> {
1087        self.inner.pin_mut().run().into_diagnostic()
1088    }
1089
1090    fn has_finished(&self) -> bool {
1091        self.inner.hasFinished()
1092    }
1093}
1094
1095impl STSP for MultiTargetDijkstra {
1096    fn get_path(&self) -> NodeIter {
1097        NodeIter {
1098            at: 0,
1099            nodes: MultiTargetDijkstraGetPath(&self.inner),
1100        }
1101    }
1102
1103    fn get_predecessors(&self) -> NodeIter {
1104        NodeIter {
1105            at: 0,
1106            nodes: MultiTargetDijkstraGetPredecessors(&self.inner),
1107        }
1108    }
1109
1110    fn set_source(&mut self, u: u64) {
1111        self.inner.pin_mut().setSource(u)
1112    }
1113
1114    fn set_target(&mut self, v: u64) {
1115        self.inner.pin_mut().setTarget(v)
1116    }
1117
1118    fn set_targets(&mut self, vs: &[u64]) {
1119        MultiTargetDijkstraSetTargets(self.inner.pin_mut(), vs);
1120    }
1121
1122    fn get_target_index_map(&self) -> BTreeMap<u64, u64> {
1123        let mut ks = vec![];
1124        let mut vs = vec![];
1125        MultiTargetDijkstraGetTargetIndexMap(&self.inner, &mut ks, &mut vs);
1126        ks.into_iter().zip(vs).collect()
1127    }
1128
1129    fn get_distance(&self) -> f64 {
1130        self.inner.getDistance()
1131    }
1132
1133    fn get_distances(&self) -> ValueIter {
1134        ValueIter {
1135            inner: MultiTargetDijkstraGetDistances(&self.inner),
1136            at: 0,
1137        }
1138    }
1139}
1140
1141pub struct NeighborhoodFunction {
1142    inner: UniquePtr<bridge::NeighborhoodFunction>,
1143}
1144
1145impl NeighborhoodFunction {
1146    pub fn new(g: &crate::Graph) -> Self {
1147        let inner = NewNeighborhoodFunction(g);
1148        Self { inner }
1149    }
1150    pub fn get_neighbourhood_function(&self) -> NodeIter {
1151        NodeIter {
1152            at: 0,
1153            nodes: NeighborhoodFunctionGetNeighborhoodFunction(&self.inner),
1154        }
1155    }
1156}
1157
1158impl Algorithm for NeighborhoodFunction {
1159    fn run(&mut self) -> miette::Result<()> {
1160        self.inner.pin_mut().run().into_diagnostic()
1161    }
1162
1163    fn has_finished(&self) -> bool {
1164        self.inner.hasFinished()
1165    }
1166}
1167
1168pub struct NeighborhoodFunctionApproximation {
1169    inner: UniquePtr<bridge::NeighborhoodFunctionApproximation>,
1170}
1171
1172impl NeighborhoodFunctionApproximation {
1173    pub fn new(g: &crate::Graph, k: Option<u64>, r: Option<u64>) -> Self {
1174        let inner = NewNeighborhoodFunctionApproximation(g, k.unwrap_or(64), r.unwrap_or(7));
1175        Self { inner }
1176    }
1177    pub fn get_neighbourhood_function(&self) -> NodeIter {
1178        NodeIter {
1179            at: 0,
1180            nodes: NeighborhoodFunctionApproximationGetNeighborhoodFunction(&self.inner),
1181        }
1182    }
1183}
1184
1185impl Algorithm for NeighborhoodFunctionApproximation {
1186    fn run(&mut self) -> miette::Result<()> {
1187        self.inner.pin_mut().run().into_diagnostic()
1188    }
1189
1190    fn has_finished(&self) -> bool {
1191        self.inner.hasFinished()
1192    }
1193}
1194
1195pub struct NeighborhoodFunctionHeuristic {
1196    inner: UniquePtr<bridge::NeighborhoodFunctionHeuristic>,
1197}
1198
1199#[derive(Default, Copy, Clone, Eq, PartialEq)]
1200#[repr(u8)]
1201
1202pub enum NeighborhoodFunctionHeuristicStrategy {
1203    Random = 0,
1204    #[default]
1205    Split = 1,
1206}
1207
1208impl NeighborhoodFunctionHeuristic {
1209    pub fn new(
1210        g: &crate::Graph,
1211        n_samples: Option<u64>,
1212        strategy: NeighborhoodFunctionHeuristicStrategy,
1213    ) -> Self {
1214        let inner = NewNeighborhoodFunctionHeuristic(g, n_samples.unwrap_or(0), strategy as u8);
1215        Self { inner }
1216    }
1217    pub fn get_neighbourhood_function(&self) -> NodeIter {
1218        NodeIter {
1219            at: 0,
1220            nodes: NeighborhoodFunctionHeuristicGetNeighborhoodFunction(&self.inner),
1221        }
1222    }
1223}
1224
1225impl Algorithm for NeighborhoodFunctionHeuristic {
1226    fn run(&mut self) -> miette::Result<()> {
1227        self.inner.pin_mut().run().into_diagnostic()
1228    }
1229
1230    fn has_finished(&self) -> bool {
1231        self.inner.hasFinished()
1232    }
1233}
1234
1235pub struct PrunedLandmarkLabeling {
1236    inner: UniquePtr<bridge::PrunedLandmarkLabeling>,
1237}
1238
1239impl PrunedLandmarkLabeling {
1240    pub fn new(g: &crate::Graph) -> Self {
1241        let inner = NewPrunedLandmarkLabeling(g);
1242        Self { inner }
1243    }
1244    pub fn query(&self, u: u64, v: u64) -> u64 {
1245        self.inner.query(u, v)
1246    }
1247}
1248
1249impl Algorithm for PrunedLandmarkLabeling {
1250    fn run(&mut self) -> miette::Result<()> {
1251        self.inner.pin_mut().run().into_diagnostic()
1252    }
1253
1254    fn has_finished(&self) -> bool {
1255        self.inner.hasFinished()
1256    }
1257}
1258
1259pub struct ReverseBFS {
1260    inner: UniquePtr<bridge::ReverseBFS>,
1261}
1262
1263impl ReverseBFS {
1264    pub fn new(
1265        g: &crate::Graph,
1266        src: u64,
1267        store_paths: bool,
1268        store_nodes_sorted_by_distance: bool,
1269        dst: Option<u64>,
1270    ) -> Self {
1271        Self {
1272            inner: NewReverseBFS(
1273                g,
1274                src,
1275                store_paths,
1276                store_nodes_sorted_by_distance,
1277                dst.unwrap_or(u64::MAX),
1278            ),
1279        }
1280    }
1281}
1282
1283impl Algorithm for ReverseBFS {
1284    fn run(&mut self) -> miette::Result<()> {
1285        self.inner.pin_mut().run().into_diagnostic()
1286    }
1287
1288    fn has_finished(&self) -> bool {
1289        self.inner.hasFinished()
1290    }
1291}
1292
1293impl SSSP for ReverseBFS {
1294    fn distance(&self, t: u64) -> f64 {
1295        self.inner.distance(t)
1296    }
1297
1298    fn get_distances(&mut self) -> ValueIter {
1299        ValueIter {
1300            at: 0,
1301            inner: ReverseBFSGetDistances(self.inner.pin_mut()),
1302        }
1303    }
1304
1305    fn number_of_paths(&self, t: u64) -> f64 {
1306        self.inner._numberOfPaths(t)
1307    }
1308
1309    fn get_predecessors(&self, t: u64) -> NodeIter {
1310        NodeIter {
1311            at: 0,
1312            nodes: ReverseBFSGetPredecessors(&self.inner, t),
1313        }
1314    }
1315
1316    fn get_path(&self, t: u64, forward: bool) -> NodeIter {
1317        NodeIter {
1318            at: 0,
1319            nodes: ReverseBFSGetPath(&self.inner, t, forward),
1320        }
1321    }
1322
1323    fn get_paths(&self, t: u64, forward: bool) -> Vec<Vec<u64>> {
1324        let mut temp = vec![];
1325        ReverseBFSGetPaths(&self.inner, t, forward, &mut temp);
1326        let mut ret = vec![];
1327        let mut cur = vec![];
1328        for n in temp {
1329            if n == u64::MAX {
1330                ret.push(cur);
1331                cur = vec![];
1332            } else {
1333                cur.push(n);
1334            }
1335        }
1336        ret
1337    }
1338
1339    fn get_node_sorted_by_distances(&self) -> NodeIter {
1340        NodeIter {
1341            at: 0,
1342            nodes: ReverseBFSGetNodeSortedByDistance(&self.inner),
1343        }
1344    }
1345
1346    fn get_num_reachable_nodes(&self) -> u64 {
1347        self.inner.getReachableNodes()
1348    }
1349
1350    fn set_source(&mut self, u: u64) {
1351        self.inner.pin_mut().setSource(u)
1352    }
1353
1354    fn set_target(&mut self, v: u64) {
1355        self.inner.pin_mut().setTarget(v)
1356    }
1357
1358    fn get_sum_of_distances(&self) -> f64 {
1359        self.inner.getSumOfDistances()
1360    }
1361}
1362
1363pub struct Volume;
1364
1365impl Volume {
1366    pub fn volume(g: &crate::Graph, radius: f64, n_samples: u64) -> f64 {
1367        VolumeVolume(g, radius, n_samples)
1368    }
1369    pub fn volumes(g: &crate::Graph, radii: &[f64], n_samples: u64) -> ValueIter {
1370        ValueIter {
1371            at: 0,
1372            inner: VolumeVolumes(g, radii, n_samples),
1373        }
1374    }
1375}
networkit_rs/distance.rs

networkit_rs/
distance.rs
