graph_algo_ptas/data_structure/
list_graph.rs

1//! Contains an implementation of the data structure described in [A simple linear time algorithm
2//! for embedding maximal planar graphs](https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.31.9303&rep=rep1&type=pdf)
3
4use petgraph::stable_graph::StableGraph;
5
6use crate::utils::convert::UndirectedGraph;
7
8/// The type of the edge id
9pub type EdgeId = usize;
10/// The type of the node id
11pub type NodeId = usize;
12
13/// The structure containing the graphs
14pub struct ListGraph {
15    nodes: Vec<Vec<(NodeId, EdgeId, bool)>>,
16    edges: Vec<(NodeId, NodeId, bool)>,
17}
18
19impl ListGraph {
20    /// Creates a new empty ListGraph
21    pub fn new() -> ListGraph {
22        ListGraph {
23            nodes: Vec::new(),
24            edges: Vec::new(),
25        }
26    }
27
28    /// Creates a new ListGraph containing the edges and required odes
29    pub fn from_edges<'a>(edges: impl Iterator<Item = &'a (NodeId, NodeId)>) -> ListGraph {
30        let mut graph = ListGraph::new();
31        for (from, to) in edges {
32            graph.add_edge(*from, *to, None, None);
33        }
34        graph
35    }
36
37    /// Creates a k4 graph
38    pub fn k4() -> ListGraph {
39        ListGraph::from_edges_node_list(
40            [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)].iter(),
41            [
42                [0, 2, 1].as_slice(),
43                [3, 4, 0].as_slice(),
44                [1, 5, 3].as_slice(),
45                [2, 4, 5].as_slice(),
46            ]
47            .iter(),
48        )
49    }
50
51    /// Same as from_edges but with the addition of being able to define the order of the adjacency list for each node
52    pub fn from_edges_node_list<'a, 'b>(
53        edges: impl Iterator<Item = &'a (NodeId, NodeId)>,
54        nodes: impl Iterator<Item = &'b &'b [EdgeId]>,
55    ) -> ListGraph {
56        let mut graph = ListGraph::from_edges(edges);
57        for (i, node) in nodes.enumerate() {
58            graph.nodes[i] = node
59                .iter()
60                .map(|edge_id| {
61                    *graph.nodes[i]
62                        .iter()
63                        .find(|(_, inner_edge_id, _)| edge_id == inner_edge_id)
64                        .unwrap_or_else(|| panic!("edge {} not adjacent to node {}", edge_id, i))
65                })
66                .collect()
67        }
68        graph
69    }
70
71    fn add_dart(&mut self, from: NodeId, to: NodeId, edge_id: EdgeId, after: Option<EdgeId>) {
72        if self.nodes.len() < from + 1 {
73            self.nodes.resize_with(from + 1, Vec::new);
74        }
75
76        let current_pos = self.nodes[from]
77            .iter()
78            .position(|(_, curr, _)| edge_id == *curr);
79
80        match after {
81            Some(after) => {
82                if after == edge_id {
83                    return;
84                }
85                if let Some(current_pos) = current_pos {
86                    self.nodes[from].remove(current_pos);
87                }
88                let new_pos = self.nodes[from]
89                    .iter()
90                    .position(|(_, curr, active)| *active && after == *curr)
91                    .expect("after must be in the edge list");
92                self.nodes[from].insert(new_pos + 1, (to, edge_id, true));
93            }
94            None => {
95                if let Some(current_pos) = current_pos {
96                    self.nodes[from][current_pos].2 = true;
97                } else {
98                    self.nodes[from].push((to, edge_id, true))
99                }
100            }
101        }
102    }
103
104    fn remove_dart(&mut self, from: NodeId, edge_id: EdgeId) {
105        if let Some((_, _, active)) = self.nodes[from]
106            .iter_mut()
107            .find(|(_, item_id, active)| *active && &edge_id == item_id)
108        {
109            *active = false;
110        }
111    }
112
113    fn cyclic_incident_rel(&self, edge: EdgeId, node: NodeId, relative: isize) -> Option<EdgeId> {
114        self.nodes.get(node).and_then(|other_nodes| {
115            other_nodes
116                .iter()
117                .position(|(_, item_edge, active)| *active && &edge == item_edge)
118                .and_then(|index| {
119                    let mut new_index = index;
120                    let edge;
121                    loop {
122                        new_index = (other_nodes.len() as isize + (new_index as isize + relative))
123                            as usize
124                            % other_nodes.len();
125                        edge = match other_nodes.get(new_index) {
126                            Some((_, _, false)) => continue,
127                            Some((_, eid, true)) => Some(*eid),
128                            _ => None,
129                        };
130                        break;
131                    }
132                    edge
133                })
134        })
135    }
136
137    fn get_edge_id(&self, from: NodeId, to: NodeId, allow_inactive: bool) -> Option<EdgeId> {
138        self.nodes.get(from).and_then(|other_nodes| {
139            other_nodes
140                .iter()
141                .find(|(other_node, _, active)| (allow_inactive || *active) && &to == other_node)
142                .map(|(_, id, _)| *id)
143        })
144    }
145
146    /// Adds an edge to the graph
147    /// If the given nodes do not exist they are created
148    /// It is the responsibility of the caller of this function to ensure `from` != `to` or else this function will panic.
149    pub fn add_edge(
150        &mut self,
151        from: NodeId,
152        to: NodeId,
153        after_from: Option<EdgeId>,
154        after_to: Option<EdgeId>,
155    ) -> EdgeId {
156        if from == to {
157            panic!("self edges are not supported")
158        }
159        let edge_id = match self.get_edge_id(from, to, true) {
160            Some(edge_id) => edge_id,
161            _ => {
162                self.edges.push((from, to, true));
163                self.edges.len() - 1
164            }
165        };
166        self.add_dart(from, to, edge_id, after_from);
167        self.add_dart(to, from, edge_id, after_to);
168        edge_id
169    }
170
171    /// Removes an edge from the graph
172    pub fn remove_edge(&mut self, edge_id: EdgeId) {
173        if let Some((from_ref, to_ref, active)) = self.edges.get_mut(edge_id) {
174            if *active {
175                let from = *from_ref;
176                let to = *to_ref;
177                *active = false;
178                self.remove_dart(from, edge_id);
179                self.remove_dart(to, edge_id);
180            }
181        }
182    }
183
184    /// Returns an iterator iterating over all indexes of nodes in the graph
185    pub fn node_indexes(&self) -> NodeIndexIter {
186        IndexIter {
187            i: 0,
188            entries: &self.nodes,
189            validation_fn: |_| true,
190        }
191    }
192
193    /// Returns an iterator iterating over all indexes of edges in the graph
194    pub fn edge_indexes(&self) -> EdgeIndexIter {
195        IndexIter {
196            i: 0,
197            entries: &self.edges,
198            validation_fn: |(_, _, active)| *active,
199        }
200    }
201
202    /// Returns the ids of the nodes adjacent to the given edge
203    pub fn edge(&self, edge_id: EdgeId) -> Option<(NodeId, NodeId)> {
204        self.edges
205            .get(edge_id)
206            .and_then(|(from, to, active)| if *active { Some((*from, *to)) } else { None })
207    }
208
209    /// List the ids of all edges adjacent to the given node
210    pub fn edges(&self, node_id: NodeId) -> Option<Vec<EdgeId>> {
211        self.nodes.get(node_id).map(|edges| {
212            edges
213                .iter()
214                .filter(|(_, _, active)| *active)
215                .map(|(_, edge_id, _)| *edge_id)
216                .collect()
217        })
218    }
219
220    /// Returns the id of all neighbouring nodes to the given node
221    pub fn neighbors(&self, node_id: NodeId) -> Option<Vec<NodeId>> {
222        self.nodes.get(node_id).map(|edges| {
223            edges
224                .iter()
225                .filter(|(_, _, active)| *active)
226                .map(|(node_id, _, _)| *node_id)
227                .collect()
228        })
229    }
230
231    /// Returns the id of the edge following the given edge in the adjacency list of the given node
232    pub fn cyclic_incident_succ(&self, edge: EdgeId, node: NodeId) -> Option<EdgeId> {
233        self.cyclic_incident_rel(edge, node, 1)
234    }
235
236    /// Returns the id of the edge preceding the given edge in the adjacency list of the given node
237    pub fn cyclic_incident_prev(&self, edge: EdgeId, node: NodeId) -> Option<EdgeId> {
238        self.cyclic_incident_rel(edge, node, -1)
239    }
240
241    /// Returns the id of the node opposite to the given node on the given edge
242    pub fn opposite(&self, node: NodeId, edge: EdgeId) -> Option<NodeId> {
243        self.edges.get(edge).and_then(|(a_node, b_node, active)| {
244            if *active {
245                if node == *a_node {
246                    Some(*b_node)
247                } else if node == *b_node {
248                    Some(*a_node)
249                } else {
250                    None
251                }
252            } else {
253                None
254            }
255        })
256    }
257
258    /// Returns a vector containing all edges in the graph as a pair containing the id of the nodes the edge is connecting
259    pub fn all_edges(&self) -> Vec<(NodeId, NodeId)> {
260        return self
261            .edges
262            .iter()
263            .filter(|(_, _, active)| *active)
264            .map(|(from, to, _)| (*from, *to))
265            .collect();
266    }
267
268    /// Adds a new vertex to the graph
269    pub fn new_vertex(&mut self) -> NodeId {
270        let new_len = self.nodes.len() + 1;
271        self.nodes.resize_with(new_len, Vec::new);
272        new_len - 1
273    }
274
275    /// Returns the graph as a petgraph StableGraph
276    pub fn to_pet_graph(&self) -> UndirectedGraph {
277        StableGraph::from_edges(
278            self.all_edges()
279                .iter()
280                .map(|(from, to)| (*from as u32, *to as u32)),
281        )
282    }
283}
284
285impl Default for ListGraph {
286    fn default() -> Self {
287        ListGraph::new()
288    }
289}
290
291/// A helper struct for iterating over all nodes in the ListGraph
292pub type NodeIndexIter<'a> =
293    IndexIter<'a, Vec<(NodeId, EdgeId, bool)>, fn(&Vec<(NodeId, EdgeId, bool)>) -> bool>;
294/// A helper struct for iterating over all edges in the ListGraph
295pub type EdgeIndexIter<'a> =
296    IndexIter<'a, (NodeId, NodeId, bool), fn(&(NodeId, NodeId, bool)) -> bool>;
297
298/// A helper struct for iterating over all nodes/edges in the ListGraph
299pub struct IndexIter<'a, T, VF: Fn(&T) -> bool> {
300    i: usize,
301    entries: &'a [T],
302    validation_fn: VF,
303}
304
305impl<'a, T, VF: Fn(&T) -> bool> Iterator for IndexIter<'a, T, VF> {
306    type Item = usize;
307
308    fn next(&mut self) -> Option<Self::Item> {
309        loop {
310            if self.i < self.entries.len() {
311                let i = self.i;
312                self.i += 1;
313                if (self.validation_fn)(&self.entries[i]) {
314                    return Some(i);
315                }
316            } else {
317                return None;
318            }
319        }
320    }
321}
322
323#[cfg(test)]
324mod tests {
325    use super::ListGraph;
326
327    const K4_EDGE_LIST: [(usize, usize); 6] = [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)];
328
329    fn k4_graph() -> ListGraph {
330        ListGraph::from_edges(K4_EDGE_LIST.iter())
331    }
332
333    #[test]
334    fn test_list_graph_counts() {
335        let graph = k4_graph();
336
337        assert_eq!(graph.node_indexes().count(), 4);
338        assert_eq!(graph.edge_indexes().count(), 6);
339    }
340
341    #[test]
342    fn test_list_graph_edges() {
343        let graph = k4_graph();
344
345        assert_eq!(graph.edges(0), Some(vec![0, 1, 2]));
346    }
347
348    #[test]
349    fn test_list_graph_all_edges() {
350        let graph = k4_graph();
351
352        assert_eq!(graph.all_edges(), K4_EDGE_LIST);
353    }
354
355    #[test]
356    fn test_list_graph_new_vertex() {
357        let mut graph = k4_graph();
358
359        assert_eq!(graph.new_vertex(), 4);
360    }
361
362    #[test]
363    fn test_list_graph_opposite() {
364        let graph = k4_graph();
365        assert_eq!(graph.opposite(0, 0), Some(1));
366        assert_eq!(graph.opposite(1, 0), Some(0));
367        assert_eq!(graph.opposite(0, 1), Some(2));
368        assert_eq!(graph.opposite(2, 1), Some(0));
369    }
370
371    #[test]
372    fn test_list_graph_cyclic_incident_succ() {
373        let graph = k4_graph();
374        let a = graph.cyclic_incident_succ(0, 0).unwrap();
375        let b = graph.cyclic_incident_succ(a, 0).unwrap();
376        let c = graph.cyclic_incident_succ(b, 0).unwrap();
377        let d = graph.cyclic_incident_succ(c, 0).unwrap();
378
379        assert_eq!(a, 1);
380        assert_eq!(b, 2);
381        assert_eq!(c, 0);
382        assert_eq!(d, 1);
383    }
384
385    #[test]
386    fn test_list_graph_cyclic_incident_prev() {
387        let graph = k4_graph();
388        let a = graph.cyclic_incident_prev(0, 0).unwrap();
389        let b = graph.cyclic_incident_prev(a, 0).unwrap();
390        let c = graph.cyclic_incident_prev(b, 0).unwrap();
391        let d = graph.cyclic_incident_prev(c, 0).unwrap();
392        assert_eq!(a, 2);
393        assert_eq!(b, 1);
394        assert_eq!(c, 0);
395        assert_eq!(d, 2);
396    }
397
398    fn k4_p1() -> ListGraph {
399        let mut graph = k4_graph();
400        let new = graph.new_vertex();
401        graph.add_edge(1, new, None, None);
402        graph.add_edge(2, new, None, None);
403        graph.add_edge(3, new, None, None);
404        graph
405    }
406
407    #[test]
408    fn test_list_graph_add_connected_node() {
409        let graph = k4_p1();
410        assert_eq!(graph.neighbors(0), Some(vec![1, 2, 3]));
411        assert_eq!(graph.neighbors(1), Some(vec![0, 2, 3, 4]));
412        assert_eq!(graph.neighbors(2), Some(vec![0, 1, 3, 4]));
413        assert_eq!(graph.neighbors(3), Some(vec![0, 1, 2, 4]));
414    }
415
416    #[test]
417    fn test_list_graph_remove_connected_node() {
418        let mut graph = k4_p1();
419        graph.remove_edge(graph.get_edge_id(1, 4, false).unwrap());
420        graph.remove_edge(graph.get_edge_id(2, 4, false).unwrap());
421        graph.remove_edge(graph.get_edge_id(3, 4, false).unwrap());
422        assert_eq!(graph.neighbors(0), Some(vec![1, 2, 3]));
423        assert_eq!(graph.neighbors(1), Some(vec![0, 2, 3]));
424        assert_eq!(graph.neighbors(2), Some(vec![0, 1, 3]));
425        assert_eq!(graph.neighbors(3), Some(vec![0, 1, 2]));
426        assert_eq!(graph.neighbors(4), Some(vec![]));
427    }
428
429    #[test]
430    fn test_list_graph_multi_connected_node() {
431        let mut graph = k4_graph();
432        let a_edge = graph.add_edge(0, 4, None, None);
433        let b_edge = graph.add_edge(4, 0, None, None);
434        assert_eq!(a_edge, b_edge);
435        assert_eq!(graph.neighbors(0), Some(vec![1, 2, 3, 4]));
436        assert_eq!(graph.neighbors(4), Some(vec![0]));
437        assert_eq!(graph.edges(4), Some(vec![a_edge]));
438        graph.remove_edge(b_edge);
439        assert_eq!(graph.neighbors(0), Some(vec![1, 2, 3]));
440        assert_eq!(graph.neighbors(4), Some(vec![]));
441        assert_eq!(graph.edges(4), Some(vec![]));
442    }
443
444    #[test]
445    fn test_list_graph_add_ordered_edge_none() {
446        let mut graph = k4_graph();
447        let new = graph.new_vertex();
448        let new_edge = graph.add_edge(0, new, None, None);
449        assert_eq!(graph.edges(0), Some(vec![0, 1, 2, new_edge]));
450        assert_eq!(graph.edges(new), Some(vec![new_edge]));
451    }
452
453    #[test]
454    fn test_list_graph_add_ordered_edge_start() {
455        let mut graph = k4_graph();
456        let new = graph.new_vertex();
457        let new_edge = graph.add_edge(0, new, Some(0), None);
458        assert_eq!(graph.edges(0), Some(vec![0, new_edge, 1, 2]));
459        assert_eq!(graph.edges(new), Some(vec![new_edge]));
460    }
461
462    #[test]
463    fn test_list_graph_add_ordered_edge_middle() {
464        let mut graph = k4_graph();
465        let new = graph.new_vertex();
466        let new_edge = graph.add_edge(0, new, Some(1), None);
467        assert_eq!(graph.edges(0), Some(vec![0, 1, new_edge, 2]));
468        assert_eq!(graph.edges(new), Some(vec![new_edge]));
469    }
470
471    #[test]
472    fn test_list_graph_add_ordered_edge_end() {
473        let mut graph = k4_graph();
474        let new = graph.new_vertex();
475        let new_edge = graph.add_edge(0, new, Some(2), None);
476        assert_eq!(graph.edges(0), Some(vec![0, 1, 2, new_edge]));
477        assert_eq!(graph.edges(new), Some(vec![new_edge]));
478    }
479
480    #[test]
481    fn test_list_graph_add_ordered_edge_start_reverse() {
482        let mut graph = k4_graph();
483        let new = graph.new_vertex();
484        let new_edge = graph.add_edge(new, 0, None, Some(0));
485        assert_eq!(graph.edges(0), Some(vec![0, new_edge, 1, 2]));
486        assert_eq!(graph.edges(new), Some(vec![new_edge]));
487    }
488
489    #[test]
490    fn test_list_graph_add_ordered_edge_middle_reverse() {
491        let mut graph = k4_graph();
492        let new = graph.new_vertex();
493        let new_edge = graph.add_edge(new, 0, None, Some(1));
494        assert_eq!(graph.edges(0), Some(vec![0, 1, new_edge, 2]));
495        assert_eq!(graph.edges(new), Some(vec![new_edge]));
496    }
497
498    #[test]
499    fn test_list_graph_add_ordered_edge_end_reverse() {
500        let mut graph = k4_graph();
501        let new = graph.new_vertex();
502        let new_edge = graph.add_edge(new, 0, None, Some(2));
503        assert_eq!(graph.edges(0), Some(vec![0, 1, 2, new_edge]));
504        assert_eq!(graph.edges(new), Some(vec![new_edge]));
505    }
506
507    #[test]
508    fn test_list_graph_ordered_re_add() {
509        let mut graph = k4_graph();
510        let new = graph.new_vertex();
511        let new_edge = graph.add_edge(new, 0, None, Some(0));
512        assert_eq!(graph.neighbors(0), Some(vec![1, new, 2, 3]));
513        assert_eq!(graph.edges(0), Some(vec![0, new_edge, 1, 2]));
514        graph.remove_edge(new_edge);
515        assert_eq!(graph.neighbors(0), Some(vec![1, 2, 3]));
516        assert_eq!(graph.edges(0), Some(vec![0, 1, 2]));
517        graph.add_edge(new, 0, None, None);
518        assert_eq!(graph.neighbors(0), Some(vec![1, new, 2, 3]));
519        assert_eq!(graph.edges(0), Some(vec![0, new_edge, 1, 2]));
520    }
521
522    #[test]
523    fn test_list_graph_ordered_re_add_different_position() {
524        let mut graph = k4_graph();
525        let new = graph.new_vertex();
526        let new_edge = graph.add_edge(new, 0, None, Some(0));
527        assert_eq!(graph.edges(0), Some(vec![0, new_edge, 1, 2]));
528        assert_eq!(graph.neighbors(0), Some(vec![1, new, 2, 3]));
529        graph.remove_edge(new_edge);
530        assert_eq!(graph.edges(0), Some(vec![0, 1, 2]));
531        assert_eq!(graph.neighbors(0), Some(vec![1, 2, 3]));
532        graph.add_edge(new, 0, None, Some(1));
533        assert_eq!(graph.edges(0), Some(vec![0, 1, new_edge, 2]));
534        assert_eq!(graph.neighbors(0), Some(vec![1, 2, new, 3]));
535    }
536
537    #[test]
538    fn test_list_graph_ordered_re_add_cyclic() {
539        let mut graph = k4_graph();
540        let new = graph.new_vertex();
541        let new_edge = graph.add_edge(new, 0, None, Some(0));
542        let a = graph.cyclic_incident_succ(0, 0).unwrap();
543        let b = graph.cyclic_incident_succ(a, 0).unwrap();
544        let c = graph.cyclic_incident_succ(b, 0).unwrap();
545        let d = graph.cyclic_incident_succ(c, 0).unwrap();
546        assert_eq!(a, new_edge);
547        assert_eq!(b, 1);
548        assert_eq!(c, 2);
549        assert_eq!(d, 0);
550        graph.remove_edge(new_edge);
551        let a = graph.cyclic_incident_succ(0, 0).unwrap();
552        let b = graph.cyclic_incident_succ(a, 0).unwrap();
553        let c = graph.cyclic_incident_succ(b, 0).unwrap();
554        let d = graph.cyclic_incident_succ(c, 0).unwrap();
555        assert_eq!(a, 1);
556        assert_eq!(b, 2);
557        assert_eq!(c, 0);
558        assert_eq!(d, 1);
559        graph.add_edge(new, 0, None, None);
560        let a = graph.cyclic_incident_succ(0, 0).unwrap();
561        let b = graph.cyclic_incident_succ(a, 0).unwrap();
562        let c = graph.cyclic_incident_succ(b, 0).unwrap();
563        let d = graph.cyclic_incident_succ(c, 0).unwrap();
564        assert_eq!(a, new_edge);
565        assert_eq!(b, 1);
566        assert_eq!(c, 2);
567        assert_eq!(d, 0);
568    }
569
570    #[test]
571    fn test_list_graph_ordered_double_add_wit_after() {
572        let mut graph = k4_graph();
573        let new = graph.new_vertex();
574        let new_edge = graph.add_edge(new, 0, None, Some(0));
575        graph.add_edge(new, 0, None, Some(new_edge));
576        assert_eq!(graph.edges(0).unwrap(), vec![0, new_edge, 1, 2]);
577        assert_eq!(graph.edges(new).unwrap(), vec![new_edge]);
578    }
579
580    #[test]
581    fn from_edge_node_list_test() {
582        let graph = ListGraph::k4();
583        assert_eq!(graph.nodes.len(), 4);
584        assert_eq!(graph.edges.len(), 6);
585        assert_eq!(graph.edges(0), Some(vec![0, 2, 1]));
586        assert_eq!(graph.edges(1), Some(vec![3, 4, 0]));
587        assert_eq!(graph.edges(2), Some(vec![1, 5, 3]));
588        assert_eq!(graph.edges(3), Some(vec![2, 4, 5]));
589        assert_eq!(graph.neighbors(0), Some(vec![1, 3, 2]));
590        assert_eq!(graph.neighbors(1), Some(vec![2, 3, 0]));
591        assert_eq!(graph.neighbors(2), Some(vec![0, 3, 1]));
592        assert_eq!(graph.neighbors(3), Some(vec![0, 1, 2]));
593    }
594
595    #[test]
596    fn test_to_pet_graph() {
597        let pet_graph = ListGraph::k4().to_pet_graph();
598        assert_eq!(pet_graph.node_count(), 4);
599        assert_eq!(pet_graph.edge_count(), 6);
600    }
601}
graph_algo_ptas/data_structure/list_graph.rs

graph_algo_ptas/data_structure/
list_graph.rs
