networkit_rs/
component.rs

1use std::collections::BTreeMap;
2
3use cxx::UniquePtr;
4use miette::IntoDiagnostic;
5
6use crate::{
7    base::{Algorithm, DynAlgorithm},
8    bridge::{self, *},
9};
10
11pub trait ComponentDecomposition {
12    fn number_of_components(&self) -> u64;
13    fn component_of_node(&self, u: u64) -> u64;
14    fn get_partition(&self) -> crate::Partition;
15    fn get_component_sizes(&self) -> BTreeMap<u64, u64>;
16    fn get_components(&self) -> Vec<Vec<u64>>;
17}
18
19pub struct BiconnectedComponents {
20    inner: UniquePtr<bridge::BiconnectedComponents>,
21}
22
23impl BiconnectedComponents {
24    pub fn new(g: &crate::Graph) -> Self {
25        Self {
26            inner: NewBiconnectedComponents(g),
27        }
28    }
29    pub fn number_of_components(&self) -> u64 {
30        self.inner.numberOfComponents()
31    }
32    pub fn get_component_sizes(&self) -> BTreeMap<u64, u64> {
33        let mut ks = vec![];
34        let mut vs = vec![];
35        BiconnectedComponentsGetComponentSizes(&self.inner, &mut ks, &mut vs);
36        ks.into_iter().zip(vs).collect()
37    }
38    pub fn get_components(&self) -> Vec<Vec<u64>> {
39        let mut ks = vec![];
40        let mut vs = vec![];
41        BiconnectedComponentsGetComponents(&self.inner, &mut ks, &mut vs);
42        if ks.is_empty() {
43            vec![]
44        } else {
45            let l = ks.last().unwrap();
46            let mut ret = vec![vec![]; *l as usize + 1];
47            for (idx, v) in ks.into_iter().zip(vs) {
48                ret[idx as usize].push(v);
49            }
50            ret
51        }
52    }
53    pub fn get_component_of_node(&self, u: u64) -> Vec<u64> {
54        let mut vs = vec![];
55        BiconnectedComponentsGetComponentOfNode(&self.inner, u, &mut vs);
56        vs
57    }
58}
59
60impl Algorithm for BiconnectedComponents {
61    fn run(&mut self) -> miette::Result<()> {
62        self.inner.pin_mut().run().into_diagnostic()
63    }
64
65    fn has_finished(&self) -> bool {
66        self.inner.hasFinished()
67    }
68}
69
70pub struct ConnectedComponents {
71    inner: UniquePtr<bridge::ConnectedComponents>,
72}
73
74impl ConnectedComponents {
75    pub fn new(g: &crate::Graph) -> Self {
76        Self {
77            inner: NewConnectedComponents(g),
78        }
79    }
80
81    pub fn extract_largest_connected_component(
82        g: &crate::Graph,
83        compact_graph: bool,
84    ) -> crate::Graph {
85        ConnectedComponentsExtractLargestConnectedComponent(g, compact_graph).into()
86    }
87}
88
89impl Algorithm for ConnectedComponents {
90    fn run(&mut self) -> miette::Result<()> {
91        self.inner.pin_mut().run().into_diagnostic()
92    }
93
94    fn has_finished(&self) -> bool {
95        self.inner.hasFinished()
96    }
97}
98
99impl ComponentDecomposition for ConnectedComponents {
100    fn number_of_components(&self) -> u64 {
101        self.inner.numberOfComponents()
102    }
103    fn get_component_sizes(&self) -> BTreeMap<u64, u64> {
104        let mut ks = vec![];
105        let mut vs = vec![];
106        ConnectedComponentsGetComponentSizes(&self.inner, &mut ks, &mut vs);
107        ks.into_iter().zip(vs).collect()
108    }
109    fn get_components(&self) -> Vec<Vec<u64>> {
110        let mut ks = vec![];
111        let mut vs = vec![];
112        ConnectedComponentsGetComponents(&self.inner, &mut ks, &mut vs);
113        if ks.is_empty() {
114            vec![]
115        } else {
116            let l = ks.last().unwrap();
117            let mut ret = vec![vec![]; *l as usize + 1];
118            for (idx, v) in ks.into_iter().zip(vs) {
119                ret[idx as usize].push(v);
120            }
121            ret
122        }
123    }
124    fn component_of_node(&self, u: u64) -> u64 {
125        self.inner.componentOfNode(u)
126    }
127
128    fn get_partition(&self) -> crate::Partition {
129        ConnectedComponentsGetPartition(&self.inner).into()
130    }
131}
132
133pub struct DynConnectedComponents {
134    inner: UniquePtr<bridge::DynConnectedComponents>,
135}
136
137impl DynConnectedComponents {
138    pub fn new(g: &crate::Graph) -> Self {
139        Self {
140            inner: NewDynConnectedComponents(g),
141        }
142    }
143}
144
145impl Algorithm for DynConnectedComponents {
146    fn run(&mut self) -> miette::Result<()> {
147        self.inner.pin_mut().run().into_diagnostic()
148    }
149
150    fn has_finished(&self) -> bool {
151        self.inner.hasFinished()
152    }
153}
154
155impl ComponentDecomposition for DynConnectedComponents {
156    fn number_of_components(&self) -> u64 {
157        self.inner.numberOfComponents()
158    }
159    fn get_component_sizes(&self) -> BTreeMap<u64, u64> {
160        let mut ks = vec![];
161        let mut vs = vec![];
162        DynConnectedComponentsGetComponentSizes(&self.inner, &mut ks, &mut vs);
163        ks.into_iter().zip(vs).collect()
164    }
165    fn get_components(&self) -> Vec<Vec<u64>> {
166        let mut ks = vec![];
167        let mut vs = vec![];
168        DynConnectedComponentsGetComponents(&self.inner, &mut ks, &mut vs);
169        if ks.is_empty() {
170            vec![]
171        } else {
172            let l = ks.last().unwrap();
173            let mut ret = vec![vec![]; *l as usize + 1];
174            for (idx, v) in ks.into_iter().zip(vs) {
175                ret[idx as usize].push(v);
176            }
177            ret
178        }
179    }
180    fn component_of_node(&self, u: u64) -> u64 {
181        self.inner.componentOfNode(u)
182    }
183
184    fn get_partition(&self) -> crate::Partition {
185        DynConnectedComponentsGetPartition(&self.inner).into()
186    }
187}
188
189impl DynAlgorithm for DynConnectedComponents {
190    fn update(&mut self, e: crate::base::GraphEvent) {
191        DynConnectedComponentsUpdate(self.inner.pin_mut(), e.kind as u8, e.u, e.v, e.ew)
192    }
193
194    fn update_batch(&mut self, es: &[crate::base::GraphEvent]) {
195        let mut kinds = Vec::with_capacity(es.len());
196        let mut us = Vec::with_capacity(es.len());
197        let mut vs = Vec::with_capacity(es.len());
198        let mut ews = Vec::with_capacity(es.len());
199        for ev in es {
200            kinds.push(ev.kind as u8);
201            us.push(ev.u);
202            vs.push(ev.v);
203            ews.push(ev.ew);
204        }
205        DynConnectedComponentsUpdateBatch(self.inner.pin_mut(), &kinds, &us, &vs, &ews);
206    }
207}
208
209pub struct DynWeaklyConnectedComponents {
210    inner: UniquePtr<bridge::DynWeaklyConnectedComponents>,
211}
212
213impl DynWeaklyConnectedComponents {
214    pub fn new(g: &crate::Graph) -> Self {
215        Self {
216            inner: NewDynWeaklyConnectedComponents(g),
217        }
218    }
219}
220
221impl Algorithm for DynWeaklyConnectedComponents {
222    fn run(&mut self) -> miette::Result<()> {
223        self.inner.pin_mut().run().into_diagnostic()
224    }
225
226    fn has_finished(&self) -> bool {
227        self.inner.hasFinished()
228    }
229}
230
231impl ComponentDecomposition for DynWeaklyConnectedComponents {
232    fn number_of_components(&self) -> u64 {
233        self.inner.numberOfComponents()
234    }
235    fn get_component_sizes(&self) -> BTreeMap<u64, u64> {
236        let mut ks = vec![];
237        let mut vs = vec![];
238        DynWeaklyConnectedComponentsGetComponentSizes(&self.inner, &mut ks, &mut vs);
239        ks.into_iter().zip(vs).collect()
240    }
241    fn get_components(&self) -> Vec<Vec<u64>> {
242        let mut ks = vec![];
243        let mut vs = vec![];
244        DynWeaklyConnectedComponentsGetComponents(&self.inner, &mut ks, &mut vs);
245        if ks.is_empty() {
246            vec![]
247        } else {
248            let l = ks.last().unwrap();
249            let mut ret = vec![vec![]; *l as usize + 1];
250            for (idx, v) in ks.into_iter().zip(vs) {
251                ret[idx as usize].push(v);
252            }
253            ret
254        }
255    }
256    fn component_of_node(&self, u: u64) -> u64 {
257        self.inner.componentOfNode(u)
258    }
259
260    fn get_partition(&self) -> crate::Partition {
261        DynWeaklyConnectedComponentsGetPartition(&self.inner).into()
262    }
263}
264
265impl DynAlgorithm for DynWeaklyConnectedComponents {
266    fn update(&mut self, e: crate::base::GraphEvent) {
267        DynWeaklyConnectedComponentsUpdate(self.inner.pin_mut(), e.kind as u8, e.u, e.v, e.ew)
268    }
269
270    fn update_batch(&mut self, es: &[crate::base::GraphEvent]) {
271        let mut kinds = Vec::with_capacity(es.len());
272        let mut us = Vec::with_capacity(es.len());
273        let mut vs = Vec::with_capacity(es.len());
274        let mut ews = Vec::with_capacity(es.len());
275        for ev in es {
276            kinds.push(ev.kind as u8);
277            us.push(ev.u);
278            vs.push(ev.v);
279            ews.push(ev.ew);
280        }
281        DynWeaklyConnectedComponentsUpdateBatch(self.inner.pin_mut(), &kinds, &us, &vs, &ews);
282    }
283}
284
285pub struct ParallelConnectedComponents {
286    inner: UniquePtr<bridge::ParallelConnectedComponents>,
287}
288
289impl ParallelConnectedComponents {
290    pub fn new(g: &crate::Graph, coarsening: bool) -> Self {
291        Self {
292            inner: NewParallelConnectedComponents(g, coarsening),
293        }
294    }
295}
296
297impl Algorithm for ParallelConnectedComponents {
298    fn run(&mut self) -> miette::Result<()> {
299        self.inner.pin_mut().run().into_diagnostic()
300    }
301
302    fn has_finished(&self) -> bool {
303        self.inner.hasFinished()
304    }
305}
306
307impl ComponentDecomposition for ParallelConnectedComponents {
308    fn number_of_components(&self) -> u64 {
309        self.inner.numberOfComponents()
310    }
311    fn get_component_sizes(&self) -> BTreeMap<u64, u64> {
312        let mut ks = vec![];
313        let mut vs = vec![];
314        ParallelConnectedComponentsGetComponentSizes(&self.inner, &mut ks, &mut vs);
315        ks.into_iter().zip(vs).collect()
316    }
317    fn get_components(&self) -> Vec<Vec<u64>> {
318        let mut ks = vec![];
319        let mut vs = vec![];
320        ParallelConnectedComponentsGetComponents(&self.inner, &mut ks, &mut vs);
321        if ks.is_empty() {
322            vec![]
323        } else {
324            let l = ks.last().unwrap();
325            let mut ret = vec![vec![]; *l as usize + 1];
326            for (idx, v) in ks.into_iter().zip(vs) {
327                ret[idx as usize].push(v);
328            }
329            ret
330        }
331    }
332    fn component_of_node(&self, u: u64) -> u64 {
333        self.inner.componentOfNode(u)
334    }
335
336    fn get_partition(&self) -> crate::Partition {
337        ParallelConnectedComponentsGetPartition(&self.inner).into()
338    }
339}
340
341pub struct StronglyConnectedComponents {
342    inner: UniquePtr<bridge::StronglyConnectedComponents>,
343}
344
345impl StronglyConnectedComponents {
346    pub fn new(g: &crate::Graph) -> Self {
347        Self {
348            inner: NewStronglyConnectedComponents(g),
349        }
350    }
351}
352
353impl Algorithm for StronglyConnectedComponents {
354    fn run(&mut self) -> miette::Result<()> {
355        self.inner.pin_mut().run().into_diagnostic()
356    }
357
358    fn has_finished(&self) -> bool {
359        self.inner.hasFinished()
360    }
361}
362
363impl ComponentDecomposition for StronglyConnectedComponents {
364    fn number_of_components(&self) -> u64 {
365        self.inner.numberOfComponents()
366    }
367    fn get_component_sizes(&self) -> BTreeMap<u64, u64> {
368        let mut ks = vec![];
369        let mut vs = vec![];
370        StronglyConnectedComponentsGetComponentSizes(&self.inner, &mut ks, &mut vs);
371        ks.into_iter().zip(vs).collect()
372    }
373    fn get_components(&self) -> Vec<Vec<u64>> {
374        let mut ks = vec![];
375        let mut vs = vec![];
376        StronglyConnectedComponentsGetComponents(&self.inner, &mut ks, &mut vs);
377        if ks.is_empty() {
378            vec![]
379        } else {
380            let l = ks.last().unwrap();
381            let mut ret = vec![vec![]; *l as usize + 1];
382            for (idx, v) in ks.into_iter().zip(vs) {
383                ret[idx as usize].push(v);
384            }
385            ret
386        }
387    }
388    fn component_of_node(&self, u: u64) -> u64 {
389        self.inner.componentOfNode(u)
390    }
391
392    fn get_partition(&self) -> crate::Partition {
393        StronglyConnectedComponentsGetPartition(&self.inner).into()
394    }
395}
396
397pub struct WeaklyConnectedComponents {
398    inner: UniquePtr<bridge::WeaklyConnectedComponents>,
399}
400
401impl WeaklyConnectedComponents {
402    pub fn new(g: &crate::Graph) -> Self {
403        Self {
404            inner: NewWeaklyConnectedComponents(g),
405        }
406    }
407}
408
409impl Algorithm for WeaklyConnectedComponents {
410    fn run(&mut self) -> miette::Result<()> {
411        self.inner.pin_mut().run().into_diagnostic()
412    }
413
414    fn has_finished(&self) -> bool {
415        self.inner.hasFinished()
416    }
417}
418
419impl ComponentDecomposition for WeaklyConnectedComponents {
420    fn number_of_components(&self) -> u64 {
421        self.inner.numberOfComponents()
422    }
423    fn get_component_sizes(&self) -> BTreeMap<u64, u64> {
424        let mut ks = vec![];
425        let mut vs = vec![];
426        WeaklyConnectedComponentsGetComponentSizes(&self.inner, &mut ks, &mut vs);
427        ks.into_iter().zip(vs).collect()
428    }
429    fn get_components(&self) -> Vec<Vec<u64>> {
430        let mut ks = vec![];
431        let mut vs = vec![];
432        WeaklyConnectedComponentsGetComponents(&self.inner, &mut ks, &mut vs);
433        if ks.is_empty() {
434            vec![]
435        } else {
436            let l = ks.last().unwrap();
437            let mut ret = vec![vec![]; *l as usize + 1];
438            for (idx, v) in ks.into_iter().zip(vs) {
439                ret[idx as usize].push(v);
440            }
441            ret
442        }
443    }
444    fn component_of_node(&self, u: u64) -> u64 {
445        self.inner.componentOfNode(u)
446    }
447
448    fn get_partition(&self) -> crate::Partition {
449        WeaklyConnectedComponentsGetPartition(&self.inner).into()
450    }
451}
networkit_rs/component.rs

networkit_rs/
component.rs
