graph_algo_ptas/data_structure/
link_graph.rs

1//! Contains a linked implementation of the DCEL trait
2use std::collections::HashSet;
3use std::{cell::RefCell, cmp::PartialEq, fmt::Debug, hash::Hash, rc::Rc};
4
5use dot::GraphWalk;
6
7use super::graph_dcel::{Dart, Face, GraphDCEL, Vertex};
8
9macro_rules! impl_non_recursive_eq {
10    ($struct:ident) => {
11        impl PartialEq for $struct {
12            fn eq(&self, other: &Self) -> bool {
13                self.id == other.id
14            }
15        }
16        impl Eq for $struct {}
17    };
18}
19
20macro_rules! impl_non_recursive_debug {
21    ($struct:ident, $name:expr) => {
22        impl Debug for $struct {
23            fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
24                f.debug_struct($name).field("id", &self.id).finish()
25            }
26        }
27    };
28}
29
30macro_rules! impl_inner_debug {
31    ($struct:ident) => {
32        impl Debug for $struct {
33            fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
34                self.0.borrow().fmt(f)
35            }
36        }
37    };
38}
39
40macro_rules! impl_hash_and_eq {
41    ($struct:ident) => {
42        impl Hash for $struct {
43            fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
44                self.0.borrow().id.hash(state)
45            }
46        }
47        impl PartialEq for $struct {
48            fn eq(&self, other: &Self) -> bool {
49                self.0.borrow().id == other.0.borrow().id
50            }
51        }
52    };
53}
54
55macro_rules! impl_ord {
56    ($struct:ident) => {
57        impl PartialOrd for $struct {
58            fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
59                self.0.borrow().id.partial_cmp(&other.0.borrow().id)
60            }
61        }
62
63        impl Ord for $struct {
64            fn cmp(&self, other: &Self) -> std::cmp::Ordering {
65                self.0.borrow().id.cmp(&other.0.borrow().id)
66            }
67        }
68    };
69}
70
71#[derive(Default)]
72struct LinkVertexStruct {
73    id: usize,
74    dart: Option<LinkDart>,
75}
76
77impl_non_recursive_eq!(LinkVertexStruct);
78impl Debug for LinkVertexStruct {
79    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
80        f.debug_struct("LinkVertex")
81            .field("id", &self.id)
82            .field("dart", &self.dart.as_ref().map(|dart| dart.0.borrow().id))
83            .finish()
84    }
85}
86
87/// A vertex in the LinkGraph
88#[derive(Clone, Default, Eq)]
89pub struct LinkVertex(Rc<RefCell<LinkVertexStruct>>);
90
91impl LinkVertex {
92    fn new(id: usize) -> LinkVertex {
93        LinkVertex(Rc::new(RefCell::new(LinkVertexStruct {
94            id,
95            ..Default::default()
96        })))
97    }
98
99    /// Returns the id of this LinkVertex
100    pub fn get_id(&self) -> usize {
101        return self.0.clone().borrow().id;
102    }
103}
104
105impl_inner_debug!(LinkVertex);
106impl_hash_and_eq!(LinkVertex);
107impl_ord!(LinkVertex);
108impl Vertex for LinkVertex {}
109
110#[derive(Default, Clone)]
111struct LinkDartStructure {
112    id: usize,
113    target: LinkVertex,
114    twin: Option<LinkDart>,
115    next: Option<LinkDart>,
116    prev: Option<LinkDart>,
117    face: Option<LinkFace>,
118}
119
120impl_non_recursive_eq!(LinkDartStructure);
121impl Debug for LinkDartStructure {
122    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
123        f.debug_struct("LinkDart")
124            .field("id", &self.id)
125            .field("target", &self.target.0.borrow().id)
126            .field(
127                "next_id",
128                &self.next.as_ref().map(|next| next.0.borrow().id),
129            )
130            .field(
131                "prev_id",
132                &self.prev.as_ref().map(|prev| prev.0.borrow().id),
133            )
134            .field(
135                "twin_id",
136                &self.twin.as_ref().map(|twin| twin.0.borrow().id),
137            )
138            .field(
139                "face_id",
140                &self.face.as_ref().map(|twin| twin.0.borrow().id),
141            )
142            .finish()
143    }
144}
145
146/// A dart in the LinkGraph
147#[derive(Clone, Default, Eq)]
148pub struct LinkDart(Rc<RefCell<LinkDartStructure>>);
149
150impl_inner_debug!(LinkDart);
151impl_hash_and_eq!(LinkDart);
152impl_ord!(LinkDart);
153impl Dart for LinkDart {}
154
155impl LinkDart {
156    fn new(id: usize, target: LinkVertex) -> LinkDart {
157        LinkDart(Rc::new(RefCell::new(LinkDartStructure {
158            id,
159            target,
160            ..Default::default()
161        })))
162    }
163
164    /// Returns the id of this LinkDart
165    pub fn get_id(&self) -> usize {
166        return self.0.clone().borrow().id;
167    }
168
169    /// Change the face of the dart
170    pub fn change_face(
171        &mut self,
172        face: Option<LinkFace>,
173        prev: Option<LinkDart>,
174        next: Option<LinkDart>,
175    ) {
176        let mut dart = self.0.borrow_mut();
177        dart.face = face;
178        dart.prev = prev;
179        dart.next = next;
180    }
181}
182
183#[derive(Default)]
184struct LinkFaceStructure {
185    id: usize,
186    dart: LinkDart,
187}
188
189impl_non_recursive_eq!(LinkFaceStructure);
190impl_non_recursive_debug!(LinkFaceStructure, "LinkFace");
191
192/// A face in the LinkGraph
193#[derive(Clone, Default, Eq)]
194pub struct LinkFace(Rc<RefCell<LinkFaceStructure>>);
195
196impl_inner_debug!(LinkFace);
197impl_hash_and_eq!(LinkFace);
198impl_ord!(LinkFace);
199impl Face for LinkFace {}
200
201impl LinkFace {
202    fn new(id: usize, dart: LinkDart) -> LinkFace {
203        LinkFace(Rc::new(RefCell::new(LinkFaceStructure { id, dart })))
204    }
205
206    /// Returns the id of this LinkFace
207    pub fn get_id(&self) -> usize {
208        return self.0.clone().borrow().id;
209    }
210}
211
212/// A linked implementation of the DCEL trait
213pub struct LinkGraph {
214    id_counter: usize,
215    vertexes: Vec<LinkVertex>,
216    darts: Vec<LinkDart>,
217    faces: Vec<LinkFace>,
218    #[cfg(feature = "debug_link_graph_panic_on_double_edges")]
219    created_darts: HashSet<(usize, usize)>,
220}
221
222/// A helper struct to iterate over the LinkGraph
223pub struct LinkGraphIter<T: Clone> {
224    counter: usize,
225    inner: Vec<T>,
226}
227
228impl<T: Clone> LinkGraphIter<T> {
229    fn new(inner: Vec<T>) -> LinkGraphIter<T> {
230        LinkGraphIter { counter: 0, inner }
231    }
232}
233
234impl<T: Clone> Iterator for LinkGraphIter<T> {
235    type Item = T;
236
237    fn next(&mut self) -> Option<Self::Item> {
238        let i = self.counter;
239        self.counter += 1;
240        self.inner.get(i).cloned()
241    }
242}
243
244impl
245    GraphDCEL<
246        LinkVertex,
247        LinkDart,
248        LinkFace,
249        LinkGraphIter<LinkVertex>,
250        LinkGraphIter<LinkDart>,
251        LinkGraphIter<LinkFace>,
252    > for LinkGraph
253{
254    fn get_vertexes(&self) -> LinkGraphIter<LinkVertex> {
255        LinkGraphIter::new(self.vertexes.clone())
256    }
257    fn get_darts(&self) -> LinkGraphIter<LinkDart> {
258        LinkGraphIter::new(self.darts.clone())
259    }
260    fn get_faces(&self) -> LinkGraphIter<LinkFace> {
261        LinkGraphIter::new(self.faces.clone())
262    }
263
264    fn vertex_count(&self) -> usize {
265        self.vertexes.len()
266    }
267
268    fn dart_count(&self) -> usize {
269        self.darts.len()
270    }
271
272    fn edge_count(&self) -> usize {
273        self.dart_count() / 2
274    }
275
276    fn face_count(&self) -> usize {
277        self.faces.len()
278    }
279
280    fn face_vertex_count(&self, face: &LinkFace) -> usize {
281        let mut count = 1;
282        let dart = self.dart_face(face);
283        let mut current_dart = dart.clone();
284
285        loop {
286            current_dart = self.next(&current_dart);
287
288            if current_dart == dart {
289                break count;
290            }
291
292            count += 1;
293        }
294    }
295
296    fn neighbors_count(&self, vertex: &LinkVertex) -> usize {
297        self.neighbors(vertex).len()
298    }
299
300    fn neighbors(&self, vertex: &LinkVertex) -> Vec<LinkVertex> {
301        let mut current_dart = self.dart_vertex(vertex);
302        let first_dart = current_dart.clone();
303        let mut current_neighbor = self.dart_target(&current_dart);
304        let mut result = vec![];
305        loop {
306            result.push(current_neighbor);
307            let twin_dart = self.twin(&current_dart);
308            current_dart = self.next(&twin_dart);
309            if current_dart == first_dart {
310                break;
311            }
312            current_neighbor = self.dart_target(&current_dart);
313        }
314        result
315    }
316
317    fn get_dart(&self, vertex: &LinkVertex, target: &LinkVertex) -> Option<LinkDart> {
318        let first_dart = self.dart_vertex(vertex);
319        let mut dart = first_dart.clone();
320
321        loop {
322            if &self.target(&dart.clone()) == target {
323                break Some(dart);
324            }
325
326            dart = self.next(&self.twin(&dart));
327            if dart.clone() == first_dart.clone() {
328                break None;
329            }
330        }
331    }
332
333    fn dart_vertex(&self, vertex: &LinkVertex) -> LinkDart {
334        vertex.0.borrow().dart.clone().unwrap()
335    }
336
337    fn dart_face(&self, face: &LinkFace) -> LinkDart {
338        face.0.borrow().dart.clone()
339    }
340
341    fn twin(&self, dart: &LinkDart) -> LinkDart {
342        dart.0.borrow().twin.clone().unwrap()
343    }
344
345    fn dart_target(&self, dart: &LinkDart) -> LinkVertex {
346        dart.0.borrow().target.clone()
347    }
348
349    fn face(&self, dart: &LinkDart) -> LinkFace {
350        dart.0.borrow().face.clone().unwrap()
351    }
352
353    fn next(&self, current: &LinkDart) -> LinkDart {
354        current.0.borrow().next.clone().unwrap()
355    }
356
357    fn prev(&self, current: &LinkDart) -> LinkDart {
358        current.0.borrow().prev.clone().unwrap()
359    }
360
361    fn add_vertex(&mut self) -> LinkVertex {
362        self.new_vertex()
363    }
364
365    fn add_dart(
366        &mut self,
367        from: LinkVertex,
368        to: LinkVertex,
369        prev: Option<LinkDart>,
370        next: Option<LinkDart>,
371        twin: Option<LinkDart>,
372        face: Option<LinkFace>,
373    ) -> LinkDart {
374        self.new_dart(from, to, prev, next, twin, face)
375    }
376
377    fn add_face(&mut self, dart: LinkDart) -> LinkFace {
378        self.new_face(dart)
379    }
380
381    fn set_face(&self, dart: &LinkDart, face: LinkFace) {
382        dart.0.borrow_mut().face = Some(face);
383    }
384
385    fn vertex_by_id(&self, id: usize) -> Option<LinkVertex> {
386        self.vertexes.iter().find(|v| v.get_id() == id).cloned()
387    }
388}
389
390impl LinkGraph {
391    /// Returns a new empty ListGraph
392    pub fn new() -> LinkGraph {
393        LinkGraph {
394            id_counter: 0,
395            vertexes: Vec::new(),
396            darts: Vec::new(),
397            faces: Vec::new(),
398            #[cfg(feature = "debug_link_graph_panic_on_double_edges")]
399            created_darts: HashSet::new(),
400        }
401    }
402    fn next_id(&mut self) -> usize {
403        let id = self.id_counter;
404        self.id_counter += 1;
405        id
406    }
407
408    /// Adds a new vertex to this LinkGraph
409    pub fn new_vertex(&mut self) -> LinkVertex {
410        let lv = LinkVertex::new(self.next_id());
411        self.vertexes.push(lv.clone());
412        lv
413    }
414
415    /// Adds a new dart to this LinkGraph
416    pub fn new_dart(
417        &mut self,
418        from: LinkVertex,
419        to: LinkVertex,
420        prev: Option<LinkDart>,
421        next: Option<LinkDart>,
422        twin: Option<LinkDart>,
423        face: Option<LinkFace>,
424    ) -> LinkDart {
425        let ld = LinkDart::new(self.next_id(), to);
426
427        let prev_dart = match prev {
428            Some(prev_dart) => prev_dart,
429            None => next
430                .clone()
431                .and_then(|next| next.0.borrow().prev.clone())
432                .unwrap_or_else(|| ld.clone()),
433        };
434        let next_dart = match next {
435            Some(next_dart) => next_dart,
436            None => prev_dart
437                .0
438                .borrow()
439                .next
440                .clone()
441                .unwrap_or_else(|| ld.clone()),
442        };
443
444        next_dart.0.borrow_mut().prev = Some(ld.clone());
445        ld.0.borrow_mut().next = Some(next_dart);
446        prev_dart.0.borrow_mut().next = Some(ld.clone());
447        ld.0.borrow_mut().prev = Some(prev_dart);
448
449        match twin {
450            Some(twin_dart) => {
451                twin_dart.0.borrow_mut().twin = Some(ld.clone());
452                ld.0.borrow_mut().twin = Some(twin_dart);
453            }
454            None => {}
455        };
456        match face {
457            Some(link_face) => {
458                ld.0.borrow_mut().face = Some(link_face);
459            }
460            None => {}
461        }
462        self.darts.push(ld.clone());
463        from.0.borrow_mut().dart = Some(ld.clone());
464        ld
465    }
466
467    /// Adds a new face to this LinkGraph
468    pub fn new_face(&mut self, dart: LinkDart) -> LinkFace {
469        let lv = LinkFace::new(self.next_id(), dart.clone());
470        self.faces.push(lv.clone());
471        dart.0.borrow_mut().face = Some(lv.clone());
472        lv
473    }
474
475    /// Adds an edge to the graph
476    pub fn new_edge(
477        &mut self,
478        from: LinkVertex,
479        to: LinkVertex,
480        prev: Option<LinkDart>,
481        next: Option<LinkDart>,
482        face: Option<LinkFace>,
483        twin_face: Option<LinkFace>,
484    ) -> (LinkDart, LinkDart) {
485        #[cfg(feature = "debug_link_graph_panic_on_double_edges")]
486        {
487            let edge_pair = (
488                from.get_id().min(to.get_id()),
489                from.get_id().max(to.get_id()),
490            );
491            if self.created_darts.contains(&edge_pair) {
492                panic!(
493                    "dart from {} to {} already exists",
494                    from.get_id(),
495                    to.get_id()
496                );
497            }
498            self.created_darts.insert(edge_pair);
499        }
500        let dart = self.new_dart(
501            from.clone(),
502            to.clone(),
503            prev.clone(),
504            next.clone(),
505            None,
506            face,
507        );
508        let twin = self.new_dart(
509            to,
510            from,
511            next.and_then(|n| n.0.borrow().twin.clone()),
512            prev.and_then(|n| n.0.borrow().twin.clone()),
513            Some(dart.clone()),
514            twin_face,
515        );
516        (dart, twin)
517    }
518
519    fn remove_dart(
520        &mut self,
521        from: &LinkVertex,
522        dart: LinkDart,
523        twin_data: LinkDartStructure,
524    ) -> LinkDart {
525        let mut dart_ref = dart.0.borrow_mut();
526        let next = dart_ref.next.take();
527        let prev = dart_ref.prev.take();
528        dart_ref.face.take();
529        drop(dart_ref);
530
531        let twin_next = twin_data.next.clone();
532        let twin_prev = twin_data.prev;
533
534        if let Some(next) = next.clone() {
535            next.0.borrow_mut().prev = twin_prev;
536        }
537        if let Some(prev) = prev {
538            prev.0.borrow_mut().next = twin_next;
539        }
540
541        if let Some(dart_pos) = self.darts.iter().position(|d| &dart == d) {
542            self.darts.remove(dart_pos);
543        }
544        from.0.borrow_mut().dart = if self.target(&next.clone().unwrap()) == *from {
545            Some(self.twin(&next.unwrap()))
546        } else {
547            next
548        };
549        dart
550    }
551
552    /// Removes the given dart and its twin from the graph
553    pub fn remove_edge(&mut self, from: &LinkVertex, dart: LinkDart) -> (LinkDart, LinkDart) {
554        let (twin, next) = {
555            let dart_ref = dart.0.borrow();
556            let twin = dart_ref.twin.clone();
557            let next = dart_ref.next.clone();
558            drop(dart_ref);
559            (twin, next)
560        };
561        let dart_data = {
562            let dart_borrow = dart.0.borrow();
563            let dart_data = dart_borrow.clone();
564            drop(dart_borrow);
565            dart_data
566        };
567        let (twin, twin_data) = if let Some(twin) = twin {
568            let twin_from = self.target(&dart);
569            let twin_data = twin.0.borrow().clone();
570            (self.remove_dart(&twin_from, twin, dart_data), twin_data)
571        } else {
572            (dart.clone(), dart.0.borrow().clone())
573        };
574        #[cfg(feature = "debug_link_graph_panic_on_double_edges")]
575        {
576            let to = twin_data.target.clone();
577            let insert_touple = (
578                from.get_id().min(to.get_id()),
579                from.get_id().max(to.get_id()),
580            );
581            self.created_darts.remove(&insert_touple);
582        }
583        let res = (self.remove_dart(from, dart, twin_data), twin);
584        if let Some(next) = next {
585            self.auto_face_dart(next);
586        }
587        res
588    }
589
590    fn validate_darts(&self) {
591        for dart in self.get_darts() {
592            let dart_inner = dart.0.borrow();
593            let next = dart_inner.next.as_ref().expect("next required");
594            self.get_darts()
595                .position(|global_dart| &global_dart == next)
596                .expect("next not found in darts");
597            let prev = dart_inner.prev.as_ref().expect("prev required");
598            self.get_darts()
599                .position(|global_dart| &global_dart == prev)
600                .expect("prev not found in darts");
601            let twin = dart_inner.twin.as_ref().expect("twin required");
602            self.get_darts()
603                .position(|global_dart| &global_dart == twin)
604                .expect("twin not found in darts");
605            dart_inner.face.as_ref().expect("face required");
606        }
607    }
608
609    fn validate_vertexes(&self) {
610        for vertex in self.get_vertexes() {
611            let vertex_inner = vertex.0.borrow();
612            let dart = vertex_inner.dart.as_ref().expect("dart required");
613            self.get_darts()
614                .position(|global_dart| &global_dart == dart)
615                .expect("dart not found in darts");
616        }
617    }
618
619    fn validate_circle<W: Fn(&LinkDart) -> LinkDart>(&self, description: &str, walk_fn: W) {
620        let max = self.edge_count() + 1;
621        for dart in &self.darts {
622            let mut current_dart = dart.clone();
623            let mut i = 0;
624            while {
625                if i > max {
626                    panic!("{} does not form circle", description)
627                }
628                i += 1;
629                let last_dart = current_dart.clone();
630                current_dart = walk_fn(&current_dart);
631                self.darts
632                    .iter()
633                    .position(|d| d == &current_dart)
634                    .unwrap_or_else(|| {
635                        panic!(
636                            "reference to removed dart {} found on {} from {}",
637                            current_dart.get_id(),
638                            description,
639                            last_dart.get_id()
640                        )
641                    });
642                dart != &current_dart
643            } {}
644        }
645    }
646
647    fn validate_next_circle(&self) {
648        self.validate_circle("next", |dart| {
649            dart.0.borrow().next.clone().expect("dart has no next")
650        });
651    }
652
653    fn validate_prev_circle(&self) {
654        self.validate_circle("prev", |dart| {
655            dart.0.borrow().prev.clone().expect("dart has no prev")
656        });
657    }
658
659    fn validate_twin(&self) {
660        for dart in &self.darts {
661            let twin = self.twin(dart);
662            let back = self.twin(&twin);
663            if dart != &back {
664                panic!("twin link non symmetric");
665            }
666        }
667    }
668
669    /// Validates the integrity of the graph. Panics if graph is invalid. Therefor mainly usefully for debugging.
670    pub fn validate(&self) {
671        self.validate_darts();
672        self.validate_vertexes();
673        self.validate_prev_circle();
674        self.validate_next_circle();
675        self.validate_twin();
676    }
677
678    fn auto_face_dart(&mut self, dart: LinkDart) -> HashSet<LinkDart> {
679        let mut current_dart = dart.clone();
680        let face = self.new_face(current_dart.clone());
681        let mut visited = HashSet::new();
682        while {
683            current_dart = self.next(&current_dart);
684            current_dart.0.borrow_mut().face = Some(face.clone());
685            visited.insert(current_dart.clone());
686            current_dart != dart
687        } {}
688        visited
689    }
690
691    /// Automatically generates faces for the graph
692    pub fn auto_face(&mut self) {
693        let mut todo_darts = self.get_darts().collect::<HashSet<_>>();
694        while !todo_darts.is_empty() {
695            let next_dart = todo_darts.iter().next().unwrap().clone();
696            todo_darts.remove(&next_dart);
697            let darts = self.auto_face_dart(next_dart);
698            for dart in darts {
699                todo_darts.remove(&dart);
700            }
701        }
702    }
703}
704
705impl Default for LinkGraph {
706    fn default() -> Self {
707        LinkGraph::new()
708    }
709}
710
711impl Drop for LinkGraph {
712    fn drop(&mut self) {
713        for vertex in &self.vertexes {
714            vertex.0.borrow_mut().dart.take();
715        }
716        for dart in &self.darts {
717            let mut dart_ref = dart.0.borrow_mut();
718            dart_ref.twin.take();
719            dart_ref.next.take();
720            dart_ref.prev.take();
721            dart_ref.face.take();
722        }
723    }
724}
725
726pub mod example;
727
728#[cfg(test)]
729mod tests {
730    use dot::GraphWalk;
731    use std::{cmp::Ordering, collections::HashSet};
732
733    use crate::data_structure::link_graph::example::three_ring_graph;
734    use crate::data_structure::{graph_dcel::GraphDCEL, link_graph::LinkGraph};
735
736    fn example_graph() -> LinkGraph {
737        let mut lg = LinkGraph::new();
738        let lv1 = lg.new_vertex();
739        assert_eq!(lv1.get_id(), 0);
740        let lv2 = lg.new_vertex();
741        assert_eq!(lv2.get_id(), 1);
742        let lv3 = lg.new_vertex();
743        assert_eq!(lv3.get_id(), 2);
744        let ld1 = lg.new_dart(lv1.clone(), lv2.clone(), None, None, None, None);
745        assert_eq!(ld1.get_id(), 3);
746        let lf = lg.new_face(ld1.clone());
747        assert_eq!(lf.get_id(), 4);
748        let ld2 = lg.new_dart(
749            lv2.clone(),
750            lv3.clone(),
751            Some(ld1.clone()),
752            None,
753            None,
754            Some(lf.clone()),
755        );
756        let ld3 = lg.new_dart(
757            lv3.clone(),
758            lv1.clone(),
759            Some(ld2.clone()),
760            Some(ld1.clone()),
761            None,
762            Some(lf),
763        );
764        let lt1 = lg.new_dart(lv2.clone(), lv1.clone(), None, None, Some(ld1), None);
765        let lof = lg.new_face(lt1.clone());
766        let lt2 = lg.new_dart(
767            lv3.clone(),
768            lv2,
769            None,
770            Some(lt1.clone()),
771            Some(ld2),
772            Some(lof.clone()),
773        );
774        let _lt3 = lg.new_dart(lv1, lv3, Some(lt1), Some(lt2), Some(ld3), Some(lof));
775        lg.validate();
776        lg
777    }
778
779    #[test]
780    fn test() {
781        let graph = example_graph();
782        let vertex = graph.vertexes.first().unwrap().clone();
783        let dart = graph.dart_vertex(&vertex);
784        let dart_2 = graph.next(&dart);
785        let dart_3 = graph.next(&dart_2);
786        let dart_4 = graph.next(&dart_3);
787        assert_eq!(dart, dart_4);
788        let twin_dart = graph.twin(&dart);
789        let twin_back_dart = graph.twin(&twin_dart);
790        assert_eq!(twin_back_dart, dart);
791        let twin_2_dart = graph.next(&twin_dart);
792        let twin_dart_3 = graph.twin(&dart_3);
793        assert_eq!(twin_2_dart, twin_dart_3);
794        let face = graph.face(&dart);
795        graph.dart_face(&face);
796        let prev_dart = graph.prev(&dart);
797        assert_eq!(prev_dart, dart_3);
798        let target_vertex = graph.dart_target(&twin_dart);
799        assert_eq!(target_vertex, vertex);
800        format!("{:?}", vertex);
801        format!("{:?}", dart);
802        format!("{:?}", face);
803    }
804
805    #[test]
806    fn iter_test() {
807        let graph = example_graph();
808
809        assert_eq!(graph.get_vertexes().count(), 3);
810        assert_eq!(graph.get_darts().count(), 6);
811        assert_eq!(graph.get_faces().count(), 2);
812    }
813
814    #[test]
815    fn hash_test() {
816        let graph = example_graph();
817        let mut vs = HashSet::new();
818        let mut vi = graph.get_vertexes();
819        vs.insert(vi.next().unwrap());
820        vs.insert(vi.next().unwrap());
821        assert_eq!(vs.len(), 2);
822        let mut ds = HashSet::new();
823        let mut di = graph.get_vertexes();
824        ds.insert(di.next().unwrap());
825        ds.insert(di.next().unwrap());
826        assert_eq!(ds.len(), 2);
827        let mut fs = HashSet::new();
828        let mut fi = graph.get_vertexes();
829        fs.insert(fi.next().unwrap());
830        fs.insert(fi.next().unwrap());
831        assert_eq!(fs.len(), 2);
832    }
833
834    #[test]
835    fn eq_test() {
836        let graph = example_graph();
837        let mut vi = graph.get_vertexes();
838        let v1 = vi.next().unwrap();
839        let v2 = vi.next().unwrap();
840        assert_eq!(v1, v1);
841        assert_ne!(v1, v2);
842        let mut di = graph.get_vertexes();
843        let d1 = di.next().unwrap();
844        let d2 = di.next().unwrap();
845        assert_eq!(d1, d1);
846        assert_ne!(d1, d2);
847        let mut fi = graph.get_vertexes();
848        let f1 = fi.next().unwrap();
849        let f2 = fi.next().unwrap();
850        assert_eq!(f1, f1);
851        assert_ne!(f1, f2);
852    }
853
854    #[test]
855    fn cmp_test() {
856        let graph = example_graph();
857        let mut vi = graph.get_vertexes();
858        let v1 = vi.next().unwrap();
859        let v2 = vi.next().unwrap();
860        assert_eq!(v1.partial_cmp(&v2), Some(Ordering::Less));
861        assert_eq!(v2.partial_cmp(&v1), Some(Ordering::Greater));
862        assert_eq!(v1.cmp(&v2), Ordering::Less);
863        assert_eq!(v2.cmp(&v1), Ordering::Greater);
864        let mut di = graph.get_vertexes();
865        let d1 = di.next().unwrap();
866        let d2 = di.next().unwrap();
867        assert_eq!(d1.partial_cmp(&d2), Some(Ordering::Less));
868        assert_eq!(d2.partial_cmp(&d1), Some(Ordering::Greater));
869        assert_eq!(d1.cmp(&d2), Ordering::Less);
870        assert_eq!(d2.cmp(&d1), Ordering::Greater);
871        let mut fi = graph.get_vertexes();
872        let f1 = fi.next().unwrap();
873        let f2 = fi.next().unwrap();
874        assert_eq!(f1.partial_cmp(&f2), Some(Ordering::Less));
875        assert_eq!(f2.partial_cmp(&f1), Some(Ordering::Greater));
876        assert_eq!(f1.cmp(&f2), Ordering::Less);
877        assert_eq!(f2.cmp(&f1), Ordering::Greater);
878    }
879
880    #[test]
881    fn neighbors_single_edge() {
882        let mut lg = LinkGraph::new();
883        let lv1 = lg.new_vertex();
884        let lv2 = lg.new_vertex();
885
886        let ld1 = lg.new_dart(lv1.clone(), lv2.clone(), None, None, None, None);
887        let lf = lg.new_face(ld1.clone());
888        lg.new_dart(
889            lv2.clone(),
890            lv1.clone(),
891            Some(ld1.clone()),
892            Some(ld1.clone()),
893            Some(ld1),
894            Some(lf),
895        );
896
897        assert_eq!(lg.neighbors(&lv1), vec![lv2.clone()]);
898        assert_eq!(lg.neighbors(&lv2), vec![lv1]);
899    }
900
901    #[test]
902    fn neighbors_triangle() {
903        let mut lg = LinkGraph::new();
904        let lv0 = lg.new_vertex();
905        let lv1 = lg.new_vertex();
906        let lv2 = lg.new_vertex();
907
908        let ld0 = lg.new_dart(lv0.clone(), lv1.clone(), None, None, None, None);
909        let lf = lg.new_face(ld0.clone());
910        let ld1 = lg.new_dart(
911            lv1.clone(),
912            lv2.clone(),
913            Some(ld0.clone()),
914            None,
915            None,
916            Some(lf.clone()),
917        );
918        let ld2 = lg.new_dart(
919            lv2.clone(),
920            lv0.clone(),
921            Some(ld1.clone()),
922            Some(ld0.clone()),
923            None,
924            Some(lf),
925        );
926
927        let lt0 = lg.new_dart(lv1.clone(), lv0.clone(), None, None, Some(ld0), None);
928        let lof = lg.new_face(lt0.clone());
929        let lt2 = lg.new_dart(
930            lv0.clone(),
931            lv2.clone(),
932            Some(lt0.clone()),
933            None,
934            Some(ld2),
935            Some(lof.clone()),
936        );
937        lg.new_dart(
938            lv2.clone(),
939            lv1.clone(),
940            Some(lt2),
941            Some(lt0),
942            Some(ld1),
943            Some(lof),
944        );
945
946        assert_eq!(lg.neighbors(&lv0), vec![lv2.clone(), lv1.clone()]);
947        assert_eq!(lg.neighbors(&lv1), vec![lv0.clone(), lv2.clone()]);
948        assert_eq!(lg.neighbors(&lv2), vec![lv1, lv0]);
949    }
950
951    #[test]
952    fn dart_count() {
953        let g = example_graph();
954
955        assert_eq!(g.dart_count(), 6)
956    }
957
958    #[test]
959    fn edge_count() {
960        let g = example_graph();
961
962        assert_eq!(g.edge_count(), 3);
963    }
964
965    #[test]
966    fn face_count() {
967        let g = example_graph();
968
969        assert_eq!(g.face_count(), 2);
970    }
971
972    #[test]
973    fn face_vertex_count() {
974        let g = example_graph();
975        let f = g.face(&g.get_darts().next().unwrap());
976
977        assert_eq!(g.face_vertex_count(&f), 3);
978    }
979
980    #[test]
981    fn neighbors_count() {
982        let g = example_graph();
983
984        assert_eq!(g.neighbors_count(&g.get_vertexes().next().unwrap()), 2);
985    }
986
987    #[test]
988    fn test_add_edge() {
989        let mut g = example_graph();
990        let first_vertex = g.vertexes[0].clone();
991        let dart = g.dart_vertex(&first_vertex);
992        let prev_dart = g.prev(&dart);
993        let new_vertex = g.new_vertex();
994        let (inner_dart, outer_dart) = g.new_edge(
995            first_vertex.clone(),
996            new_vertex.clone(),
997            Some(prev_dart),
998            Some(dart),
999            None,
1000            None,
1001        );
1002        g.new_face(inner_dart);
1003        g.new_face(outer_dart);
1004        g.validate();
1005        assert!(g.neighbors(&first_vertex).contains(&new_vertex));
1006        assert!(g.neighbors(&new_vertex).contains(&first_vertex));
1007        assert_eq!(g.edge_count(), 4)
1008    }
1009
1010    #[test]
1011    fn test_remove_edge() {
1012        let mut g = example_graph();
1013        let first_vertex = g.vertexes[0].clone();
1014        let dart = g.dart_vertex(&first_vertex);
1015        let target = g.target(&dart);
1016        g.remove_edge(&first_vertex, dart);
1017        g.validate();
1018        assert!(!g.neighbors(&first_vertex).contains(&target));
1019        assert_eq!(g.edge_count(), 2);
1020    }
1021
1022    #[test]
1023    fn test_remove_edge_from_complex_graph() {
1024        let (mut g, vertexes, darts) = three_ring_graph();
1025
1026        assert_eq!(g.edge_count(), 28);
1027        assert_eq!(g.prev(&darts[1]), darts[0].clone());
1028        assert_eq!(g.next(&darts[10]), darts[11].clone());
1029        assert_eq!(g.prev(&darts[9]), darts[11].clone());
1030        assert_eq!(g.next(&darts[2]), darts[0].clone());
1031        assert_ne!(darts[10].0.borrow().face, darts[1].0.borrow().face);
1032
1033        g.remove_edge(&vertexes[0], darts[0].clone());
1034        g.validate();
1035
1036        assert_eq!(g.edge_count(), 27);
1037        assert_eq!(g.prev(&darts[1]), darts[10].clone());
1038        assert_eq!(g.next(&darts[10]), darts[1].clone());
1039        assert_eq!(g.prev(&darts[9]), darts[2].clone());
1040        assert_eq!(g.next(&darts[2]), darts[9].clone());
1041        assert_eq!(darts[10].0.borrow().face, darts[1].0.borrow().face);
1042    }
1043
1044    #[cfg(feature = "debug_link_graph_panic_on_double_edges")]
1045    #[test]
1046    #[should_panic]
1047    fn test_add_already_existing_edge() {
1048        let mut g = LinkGraph::new();
1049        let first_vertex = g.new_vertex();
1050        let second_vertex = g.new_vertex();
1051        g.new_edge(
1052            first_vertex.clone(),
1053            second_vertex.clone(),
1054            None,
1055            None,
1056            None,
1057            None,
1058        );
1059        g.new_edge(first_vertex, second_vertex, None, None, None, None);
1060    }
1061}
graph_algo_ptas/data_structure/link_graph.rs

graph_algo_ptas/data_structure/
link_graph.rs
