graph_algo_ptas/algorithm/
leveling.rs

1//! Contains the implementation of Leveling
2use crate::algorithm::spantree::Span;
3use crate::data_structure::link_graph::LinkVertex;
4use std::collections::HashSet;
5
6/// The structure containing the levels of a graph
7pub struct Leveling<T> {
8    /// Levels of the graph
9    pub levels: Vec<HashSet<T>>,
10}
11
12impl Leveling<LinkVertex> {
13    /// Returns a new Leveling of a graph along its span tree
14    pub fn compute(span: Span<LinkVertex>) -> Self {
15        let mut result = vec![];
16        let mut level = HashSet::new();
17        level.insert(span.root);
18        while !level.is_empty() {
19            result.push(level.clone());
20            let mut new_level = HashSet::new();
21            for v in &level {
22                let children = span.downwards.get(v);
23                if span.downwards.get(v).is_some() {
24                    children.unwrap().iter().for_each(|v| {
25                        new_level.insert(v.clone());
26                    });
27                }
28            }
29            level = new_level;
30        }
31        Leveling { levels: result }
32    }
33
34    /// Returns the number of levels
35    pub fn size(&self) -> usize {
36        self.levels.len()
37    }
38
39    /// Returns rings consisting of k levels.
40    /// The last ring can contain less than k levels if the number of levels mod k is not 0.
41    pub fn rings(&self, k: usize) -> Vec<HashSet<LinkVertex>> {
42        let mut result = vec![];
43        for c in self
44            .levels
45            .chunks(k)
46            .collect::<Vec<&[HashSet<LinkVertex>]>>()
47        {
48            let mut union: HashSet<LinkVertex> = HashSet::new();
49            for set in c {
50                union.extend(set.clone());
51            }
52            result.push(union);
53        }
54        result
55    }
56}
57
58#[cfg(test)]
59mod tests {
60    use crate::algorithm::leveling::Leveling;
61    use crate::algorithm::spantree::Span;
62    use crate::data_structure::link_graph::{LinkGraph, LinkVertex};
63    use std::collections::HashSet;
64
65    #[test]
66    fn triangle() {
67        let mut lg = LinkGraph::new();
68        let lv0 = lg.new_vertex();
69        let lv1 = lg.new_vertex();
70        let lv2 = lg.new_vertex();
71
72        let lt0 = lg.new_dart(lv1.clone(), lv0.clone(), None, None, None, None);
73        let lof = lg.new_face(lt0.clone()); // Outer Face first
74
75        let ld0 = lg.new_dart(
76            lv0.clone(),
77            lv1.clone(),
78            None,
79            None,
80            Some(lt0.clone()),
81            None,
82        );
83        let lf = lg.new_face(ld0.clone());
84
85        let ld1 = lg.new_dart(
86            lv1.clone(),
87            lv2.clone(),
88            Some(ld0.clone()),
89            None,
90            None,
91            Some(lf.clone()),
92        );
93        let ld2 = lg.new_dart(
94            lv2.clone(),
95            lv0.clone(),
96            Some(ld1.clone()),
97            Some(ld0),
98            None,
99            Some(lf),
100        );
101
102        let lt2 = lg.new_dart(
103            lv0.clone(),
104            lv2.clone(),
105            Some(lt0.clone()),
106            None,
107            Some(ld2),
108            Some(lof.clone()),
109        );
110        lg.new_dart(
111            lv2.clone(),
112            lv1.clone(),
113            Some(lt2),
114            Some(lt0),
115            Some(ld1),
116            Some(lof),
117        );
118
119        let span = Span::compute(&lg, lv1.clone());
120
121        let leveling = Leveling::compute(span);
122        let cs = 2;
123        println!("[RESULT]: {:?}", leveling.levels);
124        assert_eq!(leveling.size(), cs);
125        assert_eq!(
126            leveling.levels,
127            vec![HashSet::from([lv1]), HashSet::from([lv0, lv2])]
128        );
129
130        test_rings(leveling, cs);
131    }
132
133    #[test]
134    fn two_triangle() {
135        let mut lg = LinkGraph::new();
136        let lv0 = lg.new_vertex();
137        let lv1 = lg.new_vertex();
138        let lv2 = lg.new_vertex();
139        let lv3 = lg.new_vertex();
140
141        let lt0 = lg.new_dart(lv1.clone(), lv0.clone(), None, None, None, None);
142        let lof = lg.new_face(lt0.clone()); // Outer Face first
143
144        let ld0 = lg.new_dart(
145            lv0.clone(),
146            lv1.clone(),
147            None,
148            None,
149            Some(lt0.clone()),
150            None,
151        );
152        let lf = lg.new_face(ld0.clone());
153
154        let ld1 = lg.new_dart(
155            lv1.clone(),
156            lv2.clone(),
157            Some(ld0.clone()),
158            None,
159            None,
160            Some(lf.clone()),
161        );
162        let ld2 = lg.new_dart(
163            lv2.clone(),
164            lv0.clone(),
165            Some(ld1.clone()),
166            Some(ld0),
167            None,
168            Some(lf),
169        );
170
171        let lt2 = lg.new_dart(
172            lv0.clone(),
173            lv2.clone(),
174            Some(lt0.clone()),
175            None,
176            Some(ld2.clone()),
177            None,
178        );
179
180        lg.new_dart(
181            lv2.clone(),
182            lv1.clone(),
183            Some(lt2.clone()),
184            Some(lt0),
185            Some(ld1),
186            Some(lof.clone()),
187        );
188
189        let lf2 = lg.new_face(lt2.clone());
190        let ld3 = lg.new_dart(
191            lv2.clone(),
192            lv3.clone(),
193            Some(lt2.clone()),
194            None,
195            None,
196            Some(lf2.clone()),
197        );
198        let ld4 = lg.new_dart(
199            lv3.clone(),
200            lv0.clone(),
201            Some(ld3.clone()),
202            Some(lt2),
203            None,
204            Some(lf2),
205        );
206        let lt3 = lg.new_dart(
207            lv3.clone(),
208            lv2.clone(),
209            None,
210            Some(ld2.clone()),
211            Some(ld3),
212            Some(lof.clone()),
213        );
214        lg.new_dart(
215            lv0.clone(),
216            lv3.clone(),
217            Some(ld2),
218            Some(lt3),
219            Some(ld4),
220            Some(lof),
221        );
222
223        let span = Span::compute(&lg, lv1.clone());
224
225        let leveling = Leveling::compute(span);
226        let cs = 3;
227        println!("[RESULT]: {:?}", leveling.levels);
228        assert_eq!(leveling.size(), cs);
229        assert_eq!(
230            leveling.levels,
231            vec![
232                HashSet::from([lv1]),
233                HashSet::from([lv0, lv2]),
234                HashSet::from([lv3]),
235            ]
236        );
237
238        test_rings(leveling, cs);
239    }
240
241    #[test]
242    fn three_triangle() {
243        let mut lg = LinkGraph::new();
244        let lv0 = lg.new_vertex();
245        let lv1 = lg.new_vertex();
246        let lv2 = lg.new_vertex();
247        let lv3 = lg.new_vertex();
248        let lv4 = lg.new_vertex();
249
250        let lt0 = lg.new_dart(lv1.clone(), lv0.clone(), None, None, None, None);
251        let lof = lg.new_face(lt0.clone()); // Outer Face first
252
253        let ld0 = lg.new_dart(
254            lv0.clone(),
255            lv1.clone(),
256            None,
257            None,
258            Some(lt0.clone()),
259            None,
260        );
261        let lf = lg.new_face(ld0.clone());
262
263        let ld1 = lg.new_dart(
264            lv1.clone(),
265            lv2.clone(),
266            Some(ld0.clone()),
267            None,
268            None,
269            Some(lf.clone()),
270        );
271        let ld2 = lg.new_dart(
272            lv2.clone(),
273            lv0.clone(),
274            Some(ld1.clone()),
275            Some(ld0),
276            None,
277            Some(lf),
278        );
279
280        let lt2 = lg.new_dart(
281            lv0.clone(),
282            lv2.clone(),
283            Some(lt0.clone()),
284            None,
285            Some(ld2.clone()),
286            None,
287        );
288
289        lg.new_dart(
290            lv2.clone(),
291            lv1.clone(),
292            Some(lt2.clone()),
293            Some(lt0),
294            Some(ld1),
295            Some(lof.clone()),
296        );
297
298        let lf2 = lg.new_face(lt2.clone());
299        let ld3 = lg.new_dart(
300            lv2.clone(),
301            lv3.clone(),
302            Some(lt2.clone()),
303            None,
304            None,
305            Some(lf2.clone()),
306        );
307        let ld4 = lg.new_dart(
308            lv3.clone(),
309            lv0.clone(),
310            Some(ld3.clone()),
311            Some(lt2),
312            None,
313            Some(lf2),
314        );
315        let lt3 = lg.new_dart(
316            lv3.clone(),
317            lv2.clone(),
318            None,
319            Some(ld2.clone()),
320            Some(ld3),
321            Some(lof.clone()),
322        );
323        let lt4 = lg.new_dart(
324            lv0.clone(),
325            lv3.clone(),
326            Some(ld2),
327            Some(lt3),
328            Some(ld4.clone()),
329            None,
330        );
331
332        let lf3 = lg.new_face(lt4.clone());
333        let ld5 = lg.new_dart(
334            lv3.clone(),
335            lv4.clone(),
336            Some(lt4.clone()),
337            None,
338            None,
339            Some(lf3.clone()),
340        );
341        let ld6 = lg.new_dart(
342            lv4.clone(),
343            lv0.clone(),
344            Some(ld5.clone()),
345            Some(lt4),
346            None,
347            Some(lf3),
348        );
349        let lt6 = lg.new_dart(
350            lv0.clone(),
351            lv4.clone(),
352            Some(ld4.clone()),
353            None,
354            Some(ld6),
355            Some(lof.clone()),
356        );
357        lg.new_dart(
358            lv4.clone(),
359            lv3.clone(),
360            Some(lt6),
361            Some(ld4),
362            Some(ld5),
363            Some(lof),
364        );
365
366        let span = Span::compute(&lg, lv1.clone());
367
368        let leveling = Leveling::compute(span);
369        let cs = 3;
370        println!("[RESULT]: {:?}", leveling.levels);
371        assert_eq!(leveling.size(), cs);
372        assert_eq!(
373            leveling.levels,
374            vec![
375                HashSet::from([lv1]),
376                HashSet::from([lv0, lv2]),
377                HashSet::from([lv3, lv4]),
378            ]
379        );
380
381        test_rings(leveling, cs);
382    }
383
384    #[test]
385    fn test() {
386        let mut lg = LinkGraph::new();
387        let lv0 = lg.new_vertex();
388        let lv1 = lg.new_vertex();
389        let lv2 = lg.new_vertex();
390        let lv3 = lg.new_vertex();
391        let lv4 = lg.new_vertex();
392
393        let ld0 = lg.new_dart(lv0.clone(), lv1.clone(), None, None, None, None);
394        let lof = lg.new_face(ld0.clone());
395        let ld1 = lg.new_dart(
396            lv1.clone(),
397            lv2.clone(),
398            Some(ld0.clone()),
399            None,
400            None,
401            Some(lof.clone()),
402        );
403        let ld2 = lg.new_dart(
404            lv2.clone(),
405            lv3.clone(),
406            Some(ld1.clone()),
407            None,
408            None,
409            Some(lof.clone()),
410        );
411        let ld3 = lg.new_dart(
412            lv3.clone(),
413            lv4.clone(),
414            Some(ld2.clone()),
415            None,
416            None,
417            Some(lof.clone()),
418        );
419        let lt3 = lg.new_dart(
420            lv4.clone(),
421            lv3.clone(),
422            Some(ld3.clone()),
423            None,
424            Some(ld3),
425            Some(lof.clone()),
426        );
427        let lt2 = lg.new_dart(
428            lv3.clone(),
429            lv2.clone(),
430            Some(lt3),
431            None,
432            Some(ld2),
433            Some(lof.clone()),
434        );
435        let lt1 = lg.new_dart(
436            lv2.clone(),
437            lv1.clone(),
438            Some(lt2),
439            None,
440            Some(ld1),
441            Some(lof.clone()),
442        );
443        lg.new_dart(
444            lv1.clone(),
445            lv0.clone(),
446            Some(lt1),
447            Some(ld0.clone()),
448            Some(ld0),
449            Some(lof),
450        );
451
452        let span = Span::compute(&lg, lv1.clone());
453
454        let leveling = Leveling::compute(span);
455        let cs = 4;
456        println!("[RESULT]: {:?}", leveling.levels);
457        assert_eq!(leveling.size(), cs);
458        assert_eq!(
459            leveling.levels,
460            vec![
461                HashSet::from([lv1]),
462                HashSet::from([lv0, lv2]),
463                HashSet::from([lv3]),
464                HashSet::from([lv4]),
465            ]
466        );
467
468        test_rings(leveling, cs);
469    }
470
471    #[test]
472    fn rings() {
473        let mut lg = LinkGraph::new();
474        let leveling: Vec<HashSet<LinkVertex>> = vec![
475            HashSet::from([lg.new_vertex(), lg.new_vertex(), lg.new_vertex()]),
476            HashSet::from([lg.new_vertex()]),
477            HashSet::from([lg.new_vertex(), lg.new_vertex()]),
478        ];
479        test_rings(Leveling { levels: leveling }, 3);
480    }
481
482    fn test_rings(leveling: Leveling<LinkVertex>, size: usize) {
483        for k in 1..size + 1 {
484            let rings = leveling.rings(k);
485            assert_eq!(rings.len(), (size as f64 / k as f64).ceil() as usize);
486        }
487    }
488}
graph_algo_ptas/algorithm/leveling.rs

graph_algo_ptas/algorithm/
leveling.rs
