prepona/algo/
vertex_edge_cut.rs

1use std::{cmp::min, marker::PhantomData};
2
3use magnitude::Magnitude;
4
5use crate::{
6    graph::{Edge, UndirectedEdge},
7    provide::{Edges, Graph, IdMap, Vertices},
8};
9
10/// Finds cut vertices(articulation points) and cut edges(bridges).
11///
12/// # Examples
13/// ```
14/// use prepona::prelude::*;
15/// use prepona::storage::Mat;
16/// use prepona::graph::MatGraph;
17/// use prepona::algo::VertexEdgeCut;
18///
19/// // Given:
20/// //            .-- c --.
21/// //            |       |
22/// //      a --- b ----- d --- e
23/// //
24/// let mut graph = MatGraph::init(Mat::<usize>::init());
25/// let a = graph.add_vertex();
26/// let b = graph.add_vertex();
27/// let c = graph.add_vertex();
28/// let d = graph.add_vertex();
29/// let e = graph.add_vertex();
30/// let ab = graph.add_edge_unchecked(a, b, 1.into());
31/// graph.add_edge_unchecked(b, c, 1.into());
32/// graph.add_edge_unchecked(c, d, 1.into());
33/// graph.add_edge_unchecked(b, d, 1.into());
34/// let de = graph.add_edge_unchecked(d, e, 1.into());
35///
36/// let (cut_vertices, cut_edges) = VertexEdgeCut::init(&graph).execute(&graph);
37///
38/// assert_eq!(cut_vertices.len(), 2);
39/// assert!(vec![b, d]
40///     .iter()
41///     .all(|vertex_id| cut_vertices.contains(vertex_id)));
42/// assert_eq!(cut_edges.len(), 2);
43/// assert!(vec![ab, de].into_iter().all(|edge_id| cut_edges
44///     .iter()
45///     .find(|(_, _, edge)| edge.get_id() == edge_id)
46///     .is_some()))
47/// ```
48pub struct VertexEdgeCut<'a, W, E: Edge<W>> {
49    is_visited: Vec<bool>,
50    depth_of: Vec<Magnitude<usize>>,
51    low_of: Vec<Magnitude<usize>>,
52    parent_of: Vec<Magnitude<usize>>,
53    id_map: IdMap,
54    cut_vertices: Vec<usize>,
55    cut_edges: Vec<(usize, usize, &'a E)>,
56
57    phantom_w: PhantomData<W>,
58}
59
60impl<'a, W, E: Edge<W>> VertexEdgeCut<'a, W, E> {
61    /// Initializes the structure.
62    pub fn init<G>(graph: &G) -> Self
63    where
64        G: Vertices + Edges<W, E> + Graph<W, E, UndirectedEdge>,
65    {
66        let vertex_count = graph.vertex_count();
67
68        VertexEdgeCut {
69            is_visited: vec![false; vertex_count],
70            depth_of: vec![Magnitude::PosInfinite; vertex_count],
71            low_of: vec![Magnitude::PosInfinite; vertex_count],
72            parent_of: vec![Magnitude::PosInfinite; vertex_count],
73            id_map: graph.continuos_id_map(),
74            cut_vertices: vec![],
75            cut_edges: vec![],
76
77            phantom_w: PhantomData,
78        }
79    }
80
81    /// Finds cut vertices(articulation points) and cut edges(bridges).
82    ///
83    /// # Arguments
84    /// `graph`: Graph to search for cut vertices and edges in it.
85    ///
86    /// # Returns
87    /// Cut vertices(first) and cut edges(second). \
88    /// Cut vertices will be a vector of vertex ids. \
89    /// Cut edges will be vector of (src_id, dst_id, edge reference).
90    pub fn execute<G>(mut self, graph: &'a G) -> (Vec<usize>, Vec<(usize, usize, &E)>)
91    where
92        G: Vertices + Edges<W, E> + Graph<W, E, UndirectedEdge>,
93    {
94        if !self.is_visited.is_empty() {
95            self.find_cut_vertices(graph, 0, 0.into());
96        }
97
98        (self.cut_vertices, self.cut_edges)
99    }
100
101    fn find_cut_vertices<G>(&mut self, graph: &'a G, virt_id: usize, depth: Magnitude<usize>)
102    where
103        G: Vertices + Edges<W, E>,
104    {
105        let real_id = self.id_map.real_id_of(virt_id);
106
107        let mut child_count = 0;
108        let mut is_vertex_cut = false;
109        self.is_visited[virt_id] = true;
110        self.depth_of[virt_id] = depth;
111        self.low_of[virt_id] = depth;
112
113        for (n_real_id, edge) in graph.edges_from_unchecked(real_id) {
114            let n_virt_id = self.id_map.virt_id_of(n_real_id);
115
116            if !self.is_visited[n_virt_id] {
117                self.parent_of[n_virt_id] = virt_id.into();
118                self.find_cut_vertices(graph, n_virt_id, depth + 1.into());
119                child_count += 1;
120                is_vertex_cut = self.low_of[n_virt_id] >= self.depth_of[virt_id];
121                if self.low_of[n_virt_id] > self.depth_of[virt_id] {
122                    self.cut_edges.push((virt_id, n_real_id, edge));
123                }
124                self.low_of[virt_id] = min(self.low_of[virt_id], self.low_of[n_virt_id]);
125            } else if self.parent_of[virt_id] != n_virt_id.into() {
126                self.low_of[virt_id] = min(self.low_of[virt_id], self.depth_of[n_virt_id]);
127            }
128        }
129
130        if (self.parent_of[virt_id].is_finite() && is_vertex_cut)
131            || (!self.parent_of[virt_id].is_finite() && child_count > 1)
132        {
133            self.cut_vertices.push(virt_id);
134        }
135    }
136}
137
138#[cfg(test)]
139mod tests {
140    use super::*;
141    use crate::graph::MatGraph;
142    use crate::storage::Mat;
143
144    #[test]
145    fn empty_graph() {
146        let graph = MatGraph::init(Mat::<usize>::init());
147
148        let (cut_vertices, cut_edges) = VertexEdgeCut::init(&graph).execute(&graph);
149
150        assert!(cut_vertices.is_empty());
151        assert!(cut_edges.is_empty());
152    }
153
154    #[test]
155    fn one_vertex_graph() {
156        let mut graph = MatGraph::init(Mat::<usize>::init());
157        graph.add_vertex();
158
159        let (cut_vertices, cut_edges) = VertexEdgeCut::init(&graph).execute(&graph);
160
161        assert!(cut_vertices.is_empty());
162        assert!(cut_edges.is_empty());
163    }
164
165    #[test]
166    fn two_vertex_graph() {
167        // a --- b
168        let mut graph = MatGraph::init(Mat::<usize>::init());
169        let a = graph.add_vertex();
170        let b = graph.add_vertex();
171        let ab = graph.add_edge_unchecked(a, b, 1.into());
172
173        let (cut_vertices, cut_edges) = VertexEdgeCut::init(&graph).execute(&graph);
174
175        assert!(cut_vertices.is_empty());
176        assert_eq!(cut_edges.len(), 1);
177        assert!(cut_edges
178            .iter()
179            .find(|(_, _, edge)| edge.get_id() == ab)
180            .is_some());
181    }
182
183    #[test]
184    fn trivial_graph() {
185        // Give:
186        //
187        //      a --- b
188        //      |
189        //      c
190        let mut graph = MatGraph::init(Mat::<usize>::init());
191        let a = graph.add_vertex();
192        let b = graph.add_vertex();
193        let c = graph.add_vertex();
194        let ab = graph.add_edge_unchecked(a, b, 1.into());
195        let ac = graph.add_edge_unchecked(a, c, 1.into());
196
197        let (cut_vertices, cut_edges) = VertexEdgeCut::init(&graph).execute(&graph);
198
199        assert_eq!(cut_vertices.len(), 1);
200        assert!(cut_vertices.contains(&a));
201        assert_eq!(cut_edges.len(), 2);
202        assert!(vec![ab, ac].into_iter().all(|edge_id| cut_edges
203            .iter()
204            .find(|(_, _, edge)| edge.get_id() == edge_id)
205            .is_some()))
206    }
207
208    #[test]
209    fn trivial_graph_2() {
210        // Given:
211        //
212        //      a --- b
213        //      |       \
214        //      |        c
215        //      d
216        let mut graph = MatGraph::init(Mat::<usize>::init());
217        let a = graph.add_vertex();
218        let b = graph.add_vertex();
219        let c = graph.add_vertex();
220        let d = graph.add_vertex();
221        let ab = graph.add_edge_unchecked(a, b, 1.into());
222        let bc = graph.add_edge_unchecked(a, d, 1.into());
223        let ad = graph.add_edge_unchecked(b, c, 1.into());
224
225        let (cut_vertices, cut_edges) = VertexEdgeCut::init(&graph).execute(&graph);
226
227        assert_eq!(cut_vertices.len(), 2);
228        assert!(vec![a, b]
229            .iter()
230            .all(|vertex_id| cut_vertices.contains(vertex_id)));
231        assert_eq!(cut_edges.len(), 3);
232        assert!(vec![ab, bc, ad].into_iter().all(|edge_id| cut_edges
233            .iter()
234            .find(|(_, _, edge)| edge.get_id() == edge_id)
235            .is_some()))
236    }
237
238    #[test]
239    fn complex_graph() {
240        // Given
241        //                                  j
242        //                                /   \
243        //      a --- b                 i      k ---
244        //      |     |                 |           |
245        //      c --- d --- e --- f --- h --- m --- l
246        //                              |     |
247        //                              g     n
248        //
249        let mut graph = MatGraph::init(Mat::<usize>::init());
250        let a = graph.add_vertex();
251        let b = graph.add_vertex();
252        let c = graph.add_vertex();
253        let d = graph.add_vertex();
254        let e = graph.add_vertex();
255        let f = graph.add_vertex();
256        let g = graph.add_vertex();
257        let h = graph.add_vertex();
258        let i = graph.add_vertex();
259        let j = graph.add_vertex();
260        let k = graph.add_vertex();
261        let l = graph.add_vertex();
262        let m = graph.add_vertex();
263        let n = graph.add_vertex();
264        graph.add_edge_unchecked(a, b, 1.into());
265        graph.add_edge_unchecked(a, c, 1.into());
266
267        graph.add_edge_unchecked(b, d, 1.into());
268
269        graph.add_edge_unchecked(c, d, 1.into());
270
271        let de = graph.add_edge_unchecked(d, e, 1.into());
272
273        let ef = graph.add_edge_unchecked(e, f, 1.into());
274
275        let fh = graph.add_edge_unchecked(f, h, 1.into());
276
277        graph.add_edge_unchecked(h, i, 1.into());
278        let hg = graph.add_edge_unchecked(h, g, 1.into());
279        graph.add_edge_unchecked(h, m, 1.into());
280
281        graph.add_edge_unchecked(i, j, 1.into());
282
283        graph.add_edge_unchecked(j, k, 1.into());
284
285        graph.add_edge_unchecked(k, l, 1.into());
286
287        graph.add_edge_unchecked(l, m, 1.into());
288
289        let mn = graph.add_edge_unchecked(m, n, 1.into());
290
291        let (cut_vertices, cut_edges) = VertexEdgeCut::init(&graph).execute(&graph);
292
293        assert_eq!(cut_vertices.len(), 5);
294        assert!(vec![d, e, f, h, m]
295            .iter()
296            .all(|vertex_id| cut_vertices.contains(vertex_id)));
297        assert_eq!(cut_edges.len(), 5);
298        assert!(vec![de, ef, fh, hg, mn].into_iter().all(|edge_id| cut_edges
299            .iter()
300            .find(|(_, _, edge)| edge.get_id() == edge_id)
301            .is_some()))
302    }
303
304    #[test]
305    fn non_bridge_edge_between_two_cut_vertices() {
306        // Given:
307        //            .-- c --.
308        //            |       |
309        //      a --- b ----- d --- e
310        //
311        let mut graph = MatGraph::init(Mat::<usize>::init());
312        let a = graph.add_vertex();
313        let b = graph.add_vertex();
314        let c = graph.add_vertex();
315        let d = graph.add_vertex();
316        let e = graph.add_vertex();
317        let ab = graph.add_edge_unchecked(a, b, 1.into());
318        graph.add_edge_unchecked(b, c, 1.into());
319        graph.add_edge_unchecked(c, d, 1.into());
320        graph.add_edge_unchecked(b, d, 1.into());
321        let de = graph.add_edge_unchecked(d, e, 1.into());
322
323        let (cut_vertices, cut_edges) = VertexEdgeCut::init(&graph).execute(&graph);
324
325        assert_eq!(cut_vertices.len(), 2);
326        assert!(vec![b, d]
327            .iter()
328            .all(|vertex_id| cut_vertices.contains(vertex_id)));
329        assert_eq!(cut_edges.len(), 2);
330        assert!(vec![ab, de].into_iter().all(|edge_id| cut_edges
331            .iter()
332            .find(|(_, _, edge)| edge.get_id() == edge_id)
333            .is_some()))
334    }
335}
prepona/algo/vertex_edge_cut.rs

prepona/algo/
vertex_edge_cut.rs
