networkit_rs/
scd.rs

1use std::collections::BTreeMap;
2
3use cxx::UniquePtr;
4use miette::IntoDiagnostic;
5
6use crate::{
7    base::Algorithm,
8    bridge::{self, *},
9};
10
11pub struct ApproximatePageRank {
12    inner: UniquePtr<bridge::ApproximatePageRank>,
13}
14
15impl ApproximatePageRank {
16    pub fn new(g: &crate::Graph, alpha: f64, epsilon: Option<f64>) -> Self {
17        Self {
18            inner: NewApproximatePageRank(g, alpha, epsilon.unwrap_or(1e-12)),
19        }
20    }
21    pub fn run(&mut self, seeds: &[u64]) -> impl Iterator<Item = (u64, f64)> {
22        let mut ks = vec![];
23        let mut vs = vec![];
24        ApproximatePageRankRun(self.inner.pin_mut(), seeds, &mut ks, &mut vs);
25        ks.into_iter().zip(vs.into_iter())
26    }
27}
28
29pub struct SelectiveCommunityDetectorBase {
30    pub(crate) inner: UniquePtr<bridge::SelectiveCommunityDetector>,
31}
32
33pub trait SelectiveCommunityDetector {
34    fn run(&mut self, seeds: &[u64]) -> BTreeMap<u64, Vec<u64>>;
35    fn expand_one_community(&mut self, seeds: &[u64]) -> Vec<u64>;
36    fn into_base(self) -> SelectiveCommunityDetectorBase;
37}
38
39pub struct CliqueDetect {
40    inner: UniquePtr<bridge::CliqueDetect>,
41}
42
43impl CliqueDetect {
44    pub fn new(g: &crate::Graph) -> Self {
45        Self {
46            inner: NewCliqueDetect(g),
47        }
48    }
49}
50
51impl SelectiveCommunityDetector for CliqueDetect {
52    fn run(&mut self, seeds: &[u64]) -> BTreeMap<u64, Vec<u64>> {
53        let mut ks = vec![];
54        let mut vs = vec![];
55        CliqueDetectRun(self.inner.pin_mut(), seeds, &mut ks, &mut vs);
56        let mut ret: BTreeMap<u64, Vec<u64>> = BTreeMap::new();
57        for (k, v) in ks.into_iter().zip(vs.into_iter()) {
58            ret.entry(k).or_default().push(v);
59        }
60        ret
61    }
62
63    fn expand_one_community(&mut self, seeds: &[u64]) -> Vec<u64> {
64        let mut ret = vec![];
65        CliqueDetectExpandOneCommunity(self.inner.pin_mut(), seeds, &mut ret);
66        ret
67    }
68
69    fn into_base(self) -> SelectiveCommunityDetectorBase {
70        SelectiveCommunityDetectorBase {
71            inner: CliqueDetectAsBase(self.inner),
72        }
73    }
74}
75
76pub struct CombinedSCD {
77    inner: UniquePtr<bridge::CombinedSCD>,
78}
79
80impl CombinedSCD {
81    pub fn new(
82        g: &crate::Graph,
83        left: &mut SelectiveCommunityDetectorBase,
84        right: &mut SelectiveCommunityDetectorBase,
85    ) -> Self {
86        Self {
87            inner: NewCombinedSCD(g, left.inner.pin_mut(), right.inner.pin_mut()),
88        }
89    }
90}
91
92impl SelectiveCommunityDetector for CombinedSCD {
93    fn run(&mut self, seeds: &[u64]) -> BTreeMap<u64, Vec<u64>> {
94        let mut ks = vec![];
95        let mut vs = vec![];
96        CombinedSCDRun(self.inner.pin_mut(), seeds, &mut ks, &mut vs);
97        let mut ret: BTreeMap<u64, Vec<u64>> = BTreeMap::new();
98        for (k, v) in ks.into_iter().zip(vs.into_iter()) {
99            ret.entry(k).or_default().push(v);
100        }
101        ret
102    }
103
104    fn expand_one_community(&mut self, seeds: &[u64]) -> Vec<u64> {
105        let mut ret = vec![];
106        CombinedSCDExpandOneCommunity(self.inner.pin_mut(), seeds, &mut ret);
107        ret
108    }
109
110    fn into_base(self) -> SelectiveCommunityDetectorBase {
111        SelectiveCommunityDetectorBase {
112            inner: CombinedSCDAsBase(self.inner),
113        }
114    }
115}
116
117pub struct GCE {
118    inner: UniquePtr<bridge::GCE>,
119}
120
121impl GCE {
122    pub const M: &str = "M";
123    pub const L: &str = "L";
124
125    pub fn new(g: &crate::Graph, q: &str) -> Self {
126        Self {
127            inner: NewGCE(g, q),
128        }
129    }
130}
131
132impl SelectiveCommunityDetector for GCE {
133    fn run(&mut self, seeds: &[u64]) -> BTreeMap<u64, Vec<u64>> {
134        let mut ks = vec![];
135        let mut vs = vec![];
136        GCERun(self.inner.pin_mut(), seeds, &mut ks, &mut vs);
137        let mut ret: BTreeMap<u64, Vec<u64>> = BTreeMap::new();
138        for (k, v) in ks.into_iter().zip(vs.into_iter()) {
139            ret.entry(k).or_default().push(v);
140        }
141        ret
142    }
143
144    fn expand_one_community(&mut self, seeds: &[u64]) -> Vec<u64> {
145        let mut ret = vec![];
146        GCEExpandOneCommunity(self.inner.pin_mut(), seeds, &mut ret);
147        ret
148    }
149
150    fn into_base(self) -> SelectiveCommunityDetectorBase {
151        SelectiveCommunityDetectorBase {
152            inner: GCEAsBase(self.inner),
153        }
154    }
155}
156
157pub struct LFMLocal {
158    inner: UniquePtr<bridge::LFMLocal>,
159}
160
161impl LFMLocal {
162    pub fn new(g: &crate::Graph, alpha: Option<f64>) -> Self {
163        Self {
164            inner: NewLFMLocal(g, alpha.unwrap_or(1.)),
165        }
166    }
167}
168
169impl SelectiveCommunityDetector for LFMLocal {
170    fn run(&mut self, seeds: &[u64]) -> BTreeMap<u64, Vec<u64>> {
171        let mut ks = vec![];
172        let mut vs = vec![];
173        LFMLocalRun(self.inner.pin_mut(), seeds, &mut ks, &mut vs);
174        let mut ret: BTreeMap<u64, Vec<u64>> = BTreeMap::new();
175        for (k, v) in ks.into_iter().zip(vs.into_iter()) {
176            ret.entry(k).or_default().push(v);
177        }
178        ret
179    }
180
181    fn expand_one_community(&mut self, seeds: &[u64]) -> Vec<u64> {
182        let mut ret = vec![];
183        LFMLocalExpandOneCommunity(self.inner.pin_mut(), seeds, &mut ret);
184        ret
185    }
186
187    fn into_base(self) -> SelectiveCommunityDetectorBase {
188        SelectiveCommunityDetectorBase {
189            inner: LFMLocalAsBase(self.inner),
190        }
191    }
192}
193
194pub struct LocalT {
195    inner: UniquePtr<bridge::LocalT>,
196}
197
198impl LocalT {
199    pub fn new(g: &crate::Graph) -> Self {
200        Self {
201            inner: NewLocalT(g),
202        }
203    }
204}
205
206impl SelectiveCommunityDetector for LocalT {
207    fn run(&mut self, seeds: &[u64]) -> BTreeMap<u64, Vec<u64>> {
208        let mut ks = vec![];
209        let mut vs = vec![];
210        LocalTRun(self.inner.pin_mut(), seeds, &mut ks, &mut vs);
211        let mut ret: BTreeMap<u64, Vec<u64>> = BTreeMap::new();
212        for (k, v) in ks.into_iter().zip(vs.into_iter()) {
213            ret.entry(k).or_default().push(v);
214        }
215        ret
216    }
217
218    fn expand_one_community(&mut self, seeds: &[u64]) -> Vec<u64> {
219        let mut ret = vec![];
220        LocalTExpandOneCommunity(self.inner.pin_mut(), seeds, &mut ret);
221        ret
222    }
223
224    fn into_base(self) -> SelectiveCommunityDetectorBase {
225        SelectiveCommunityDetectorBase {
226            inner: LocalTAsBase(self.inner),
227        }
228    }
229}
230
231pub struct LocalTightnessExpansion {
232    inner: UniquePtr<bridge::LocalTightnessExpansion>,
233}
234
235impl LocalTightnessExpansion {
236    pub fn new(g: &crate::Graph, alpha: Option<f64>) -> Self {
237        Self {
238            inner: NewLocalTightnessExpansion(g, alpha.unwrap_or(1.)),
239        }
240    }
241}
242
243impl SelectiveCommunityDetector for LocalTightnessExpansion {
244    fn run(&mut self, seeds: &[u64]) -> BTreeMap<u64, Vec<u64>> {
245        let mut ks = vec![];
246        let mut vs = vec![];
247        LocalTightnessExpansionRun(self.inner.pin_mut(), seeds, &mut ks, &mut vs);
248        let mut ret: BTreeMap<u64, Vec<u64>> = BTreeMap::new();
249        for (k, v) in ks.into_iter().zip(vs.into_iter()) {
250            ret.entry(k).or_default().push(v);
251        }
252        ret
253    }
254
255    fn expand_one_community(&mut self, seeds: &[u64]) -> Vec<u64> {
256        let mut ret = vec![];
257        LocalTightnessExpansionExpandOneCommunity(self.inner.pin_mut(), seeds, &mut ret);
258        ret
259    }
260
261    fn into_base(self) -> SelectiveCommunityDetectorBase {
262        SelectiveCommunityDetectorBase {
263            inner: LocalTightnessExpansionAsBase(self.inner),
264        }
265    }
266}
267
268pub struct PageRankNibble {
269    inner: UniquePtr<bridge::PageRankNibble>,
270}
271
272impl PageRankNibble {
273    pub fn new(g: &crate::Graph, alpha: f64, epsilon: f64) -> Self {
274        Self {
275            inner: NewPageRankNibble(g, alpha, epsilon),
276        }
277    }
278}
279
280impl SelectiveCommunityDetector for PageRankNibble {
281    fn run(&mut self, seeds: &[u64]) -> BTreeMap<u64, Vec<u64>> {
282        let mut ks = vec![];
283        let mut vs = vec![];
284        PageRankNibbleRun(self.inner.pin_mut(), seeds, &mut ks, &mut vs);
285        let mut ret: BTreeMap<u64, Vec<u64>> = BTreeMap::new();
286        for (k, v) in ks.into_iter().zip(vs.into_iter()) {
287            ret.entry(k).or_default().push(v);
288        }
289        ret
290    }
291
292    fn expand_one_community(&mut self, seeds: &[u64]) -> Vec<u64> {
293        let mut ret = vec![];
294        PageRankNibbleExpandOneCommunity(self.inner.pin_mut(), seeds, &mut ret);
295        ret
296    }
297
298    fn into_base(self) -> SelectiveCommunityDetectorBase {
299        SelectiveCommunityDetectorBase {
300            inner: PageRankNibbleAsBase(self.inner),
301        }
302    }
303}
304
305pub struct RandomBFS {
306    inner: UniquePtr<bridge::RandomBFS>,
307}
308
309impl RandomBFS {
310    pub fn new(g: &crate::Graph, c: &crate::Cover) -> Self {
311        Self {
312            inner: NewRandomBFS(g, c),
313        }
314    }
315}
316
317impl SelectiveCommunityDetector for RandomBFS {
318    fn run(&mut self, seeds: &[u64]) -> BTreeMap<u64, Vec<u64>> {
319        let mut ks = vec![];
320        let mut vs = vec![];
321        RandomBFSRun(self.inner.pin_mut(), seeds, &mut ks, &mut vs);
322        let mut ret: BTreeMap<u64, Vec<u64>> = BTreeMap::new();
323        for (k, v) in ks.into_iter().zip(vs.into_iter()) {
324            ret.entry(k).or_default().push(v);
325        }
326        ret
327    }
328
329    fn expand_one_community(&mut self, seeds: &[u64]) -> Vec<u64> {
330        let mut ret = vec![];
331        RandomBFSExpandOneCommunity(self.inner.pin_mut(), seeds, &mut ret);
332        ret
333    }
334
335    fn into_base(self) -> SelectiveCommunityDetectorBase {
336        SelectiveCommunityDetectorBase {
337            inner: RandomBFSAsBase(self.inner),
338        }
339    }
340}
341
342pub struct SCDGroundTruthComparison {
343    inner: UniquePtr<bridge::SCDGroundTruthComparison>,
344}
345
346impl SCDGroundTruthComparison {
347    pub fn new(
348        g: &crate::Graph,
349        ground_truth: &crate::Cover,
350        found: &BTreeMap<u64, Vec<u64>>,
351        ignore_seeds: bool,
352    ) -> Self {
353        let mut ks = vec![];
354        let mut vs = vec![];
355
356        for (k, v) in found {
357            for vv in v {
358                ks.push(*k);
359                vs.push(*vv);
360            }
361        }
362
363        Self {
364            inner: NewSCDGroundTruthComparison(g, ground_truth, &ks, &vs, ignore_seeds),
365        }
366    }
367
368    pub fn get_individual_jaccard(&self) -> impl Iterator<Item = (u64, f64)> {
369        let mut ks = vec![];
370        let mut vs = vec![];
371        SCDGroundTruthComparisonGetIndividualJaccard(&self.inner, &mut ks, &mut vs);
372        ks.into_iter().zip(vs.into_iter())
373    }
374
375    pub fn get_individual_precision(&self) -> impl Iterator<Item = (u64, f64)> {
376        let mut ks = vec![];
377        let mut vs = vec![];
378        SCDGroundTruthComparisonGetIndividualPrecision(&self.inner, &mut ks, &mut vs);
379        ks.into_iter().zip(vs.into_iter())
380    }
381
382    pub fn get_individual_recall(&self) -> impl Iterator<Item = (u64, f64)> {
383        let mut ks = vec![];
384        let mut vs = vec![];
385        SCDGroundTruthComparisonGetIndividualRecall(&self.inner, &mut ks, &mut vs);
386        ks.into_iter().zip(vs.into_iter())
387    }
388
389    pub fn get_individual_f1(&self) -> impl Iterator<Item = (u64, f64)> {
390        let mut ks = vec![];
391        let mut vs = vec![];
392        SCDGroundTruthComparisonGetIndividualF1(&self.inner, &mut ks, &mut vs);
393        ks.into_iter().zip(vs.into_iter())
394    }
395
396    pub fn get_average_jaccard(&self) -> f64 {
397        self.inner.getAverageJaccard()
398    }
399
400    pub fn get_average_precision(&self) -> f64 {
401        self.inner.getAveragePrecision()
402    }
403
404    pub fn get_average_recall(&self) -> f64 {
405        self.inner.getAverageRecall()
406    }
407
408    pub fn get_average_f1(&self) -> f64 {
409        self.inner.getAverageF1()
410    }
411}
412
413impl Algorithm for SCDGroundTruthComparison {
414    fn run(&mut self) -> miette::Result<()> {
415        self.inner.pin_mut().run().into_diagnostic()
416    }
417
418    fn has_finished(&self) -> bool {
419        self.inner.hasFinished()
420    }
421}
422
423pub struct SetConductance {
424    inner: UniquePtr<bridge::SetConductance>,
425}
426
427impl SetConductance {
428    pub fn new(g: &crate::Graph, community: &[u64]) -> Self {
429        Self {
430            inner: NewSetConductance(g, community),
431        }
432    }
433    pub fn get_conductance(&self) -> f64 {
434        self.inner.getConductance()
435    }
436}
437
438impl Algorithm for SetConductance {
439    fn run(&mut self) -> miette::Result<()> {
440        self.inner.pin_mut().run().into_diagnostic()
441    }
442
443    fn has_finished(&self) -> bool {
444        self.inner.hasFinished()
445    }
446}
447
448pub struct TCE {
449    inner: UniquePtr<bridge::TCE>,
450}
451
452impl TCE {
453    pub fn new(g: &crate::Graph, refine: bool, use_jaccard: bool) -> Self {
454        Self {
455            inner: NewTCE(g, refine, use_jaccard),
456        }
457    }
458}
459
460impl SelectiveCommunityDetector for TCE {
461    fn run(&mut self, seeds: &[u64]) -> BTreeMap<u64, Vec<u64>> {
462        let mut ks = vec![];
463        let mut vs = vec![];
464        TCERun(self.inner.pin_mut(), seeds, &mut ks, &mut vs);
465        let mut ret: BTreeMap<u64, Vec<u64>> = BTreeMap::new();
466        for (k, v) in ks.into_iter().zip(vs.into_iter()) {
467            ret.entry(k).or_default().push(v);
468        }
469        ret
470    }
471
472    fn expand_one_community(&mut self, seeds: &[u64]) -> Vec<u64> {
473        let mut ret = vec![];
474        TCEExpandOneCommunity(self.inner.pin_mut(), seeds, &mut ret);
475        ret
476    }
477
478    fn into_base(self) -> SelectiveCommunityDetectorBase {
479        SelectiveCommunityDetectorBase {
480            inner: TCEAsBase(self.inner),
481        }
482    }
483}
484
485pub struct TwoPhaseL {
486    inner: UniquePtr<bridge::TwoPhaseL>,
487}
488
489impl TwoPhaseL {
490    pub fn new(g: &crate::Graph) -> Self {
491        Self {
492            inner: NewTwoPhaseL(g),
493        }
494    }
495}
496
497impl SelectiveCommunityDetector for TwoPhaseL {
498    fn run(&mut self, seeds: &[u64]) -> BTreeMap<u64, Vec<u64>> {
499        let mut ks = vec![];
500        let mut vs = vec![];
501        TwoPhaseLRun(self.inner.pin_mut(), seeds, &mut ks, &mut vs);
502        let mut ret: BTreeMap<u64, Vec<u64>> = BTreeMap::new();
503        for (k, v) in ks.into_iter().zip(vs.into_iter()) {
504            ret.entry(k).or_default().push(v);
505        }
506        ret
507    }
508
509    fn expand_one_community(&mut self, seeds: &[u64]) -> Vec<u64> {
510        let mut ret = vec![];
511        TwoPhaseLExpandOneCommunity(self.inner.pin_mut(), seeds, &mut ret);
512        ret
513    }
514
515    fn into_base(self) -> SelectiveCommunityDetectorBase {
516        SelectiveCommunityDetectorBase {
517            inner: TwoPhaseLAsBase(self.inner),
518        }
519    }
520}
networkit_rs/scd.rs

networkit_rs/
scd.rs
