contest_algorithms/graph/
connectivity.rs

1//! Graph connectivity structures.
2use super::Graph;
3
4/// Helper struct that carries data needed for the depth-first searches in
5/// ConnectivityGraph's constructor.
6struct ConnectivityData {
7    time: usize,
8    vis: Box<[usize]>,
9    low: Box<[usize]>,
10    v_stack: Vec<usize>,
11    e_stack: Vec<usize>,
12}
13
14impl ConnectivityData {
15    fn new(num_v: usize) -> Self {
16        Self {
17            time: 0,
18            vis: vec![0; num_v].into_boxed_slice(),
19            low: vec![0; num_v].into_boxed_slice(),
20            v_stack: vec![],
21            e_stack: vec![],
22        }
23    }
24
25    fn visit(&mut self, u: usize) {
26        self.time += 1;
27        self.vis[u] = self.time;
28        self.low[u] = self.time;
29        self.v_stack.push(u);
30    }
31
32    fn lower(&mut self, u: usize, val: usize) {
33        if self.low[u] > val {
34            self.low[u] = val
35        }
36    }
37}
38
39/// Represents the decomposition of a graph into any of its constituent parts:
40///
41/// - Connected components (CC),
42/// - Strongly connected components (SCC),
43/// - 2-edge-connected components (2ECC),
44/// - 2-vertex-connected components (2VCC)
45///
46/// Multiple-edges and self-loops are correctly handled.
47pub struct ConnectivityGraph<'a> {
48    // Immutable graph, frozen for the lifetime of the ConnectivityGraph object.
49    pub graph: &'a Graph,
50    /// ID of a vertex's CC, SCC or 2ECC, whichever applies. Range 1 to num_cc.
51    pub cc: Vec<usize>,
52    /// ID of an edge's 2VCC, where applicable. Ranges from 1 to num_vcc.
53    pub vcc: Vec<usize>,
54    /// Total number of CCs, SCCs or 2ECCs, whichever applies.
55    pub num_cc: usize,
56    /// Total number of 2VCCs, where applicable.
57    pub num_vcc: usize,
58}
59
60impl<'a> ConnectivityGraph<'a> {
61    /// Computes CCs (connected components), SCCs (strongly connected
62    /// components), 2ECCs (2-edge-connected components), and/or 2VCCs
63    /// (2-vertex-connected components), depending on the parameter and graph:
64    /// - is_directed == true on directed graph: SCCs in rev-topological order
65    /// - is_directed == true on undirected graph: CCs
66    /// - is_directed == false on undirected graph: 2ECCs and 2VCCs
67    /// - is_directed == false on directed graph: undefined behavior
68    pub fn new(graph: &'a Graph, is_directed: bool) -> Self {
69        let mut connect = Self {
70            graph,
71            cc: vec![0; graph.num_v()],
72            vcc: vec![0; graph.num_e()],
73            num_cc: 0,
74            num_vcc: 0,
75        };
76        let mut data = ConnectivityData::new(graph.num_v());
77        for u in 0..graph.num_v() {
78            if data.vis[u] == 0 {
79                if is_directed {
80                    connect.scc(&mut data, u);
81                } else {
82                    connect.bcc(&mut data, u, graph.num_e() + 1);
83                }
84            }
85        }
86        connect
87    }
88
89    fn scc(&mut self, data: &mut ConnectivityData, u: usize) {
90        data.visit(u);
91        for (_, v) in self.graph.adj_list(u) {
92            if data.vis[v] == 0 {
93                self.scc(data, v);
94            }
95            if self.cc[v] == 0 {
96                data.lower(u, data.low[v]);
97            }
98        }
99        if data.vis[u] == data.low[u] {
100            self.num_cc += 1;
101            while let Some(v) = data.v_stack.pop() {
102                self.cc[v] = self.num_cc;
103                if v == u {
104                    break;
105                }
106            }
107        }
108    }
109
110    /// From the directed implication graph corresponding to a 2-SAT clause,
111    /// finds a satisfying assignment if it exists or returns None otherwise.
112    pub fn two_sat_assign(&self) -> Option<Vec<bool>> {
113        (0..self.graph.num_v() / 2)
114            .map(|i| {
115                let scc_true = self.cc[2 * i];
116                let scc_false = self.cc[2 * i + 1];
117                if scc_true == scc_false {
118                    None
119                } else {
120                    Some(scc_true < scc_false)
121                }
122            })
123            .collect()
124    }
125
126    /// Gets the vertices of a graph according to a topological order of the
127    /// strongly connected components. Most often used on DAGs.
128    pub fn topological_sort(&self) -> Vec<usize> {
129        let mut vertices = (0..self.graph.num_v()).collect::<Vec<_>>();
130        vertices.sort_unstable_by_key(|&u| self.num_cc - self.cc[u]);
131        vertices
132    }
133
134    fn bcc(&mut self, data: &mut ConnectivityData, u: usize, par: usize) {
135        data.visit(u);
136        for (e, v) in self.graph.adj_list(u) {
137            if data.vis[v] == 0 {
138                data.e_stack.push(e);
139                self.bcc(data, v, e);
140                data.lower(u, data.low[v]);
141                if data.vis[u] <= data.low[v] {
142                    // u is a cut vertex unless it's a one-child root
143                    self.num_vcc += 1;
144                    while let Some(top_e) = data.e_stack.pop() {
145                        self.vcc[top_e] = self.num_vcc;
146                        self.vcc[top_e ^ 1] = self.num_vcc;
147                        if e ^ top_e <= 1 {
148                            break;
149                        }
150                    }
151                }
152            } else if data.vis[v] < data.vis[u] && e ^ par != 1 {
153                data.lower(u, data.vis[v]);
154                data.e_stack.push(e);
155            } else if v == u {
156                // e is a self-loop
157                self.num_vcc += 1;
158                self.vcc[e] = self.num_vcc;
159                self.vcc[e ^ 1] = self.num_vcc;
160            }
161        }
162        if data.vis[u] == data.low[u] {
163            // par is a cut edge unless par==-1
164            self.num_cc += 1;
165            while let Some(v) = data.v_stack.pop() {
166                self.cc[v] = self.num_cc;
167                if v == u {
168                    break;
169                }
170            }
171        }
172    }
173
174    /// In an undirected graph, determines whether u is an articulation vertex.
175    pub fn is_cut_vertex(&self, u: usize) -> bool {
176        if let Some(first_e) = self.graph.first[u] {
177            self.graph
178                .adj_list(u)
179                .any(|(e, _)| self.vcc[first_e] != self.vcc[e])
180        } else {
181            false
182        }
183    }
184
185    /// In an undirected graph, determines whether e is a bridge
186    pub fn is_cut_edge(&self, e: usize) -> bool {
187        let u = self.graph.endp[e ^ 1];
188        let v = self.graph.endp[e];
189        self.cc[u] != self.cc[v]
190    }
191}
192
193#[cfg(test)]
194mod test {
195    use super::*;
196
197    #[test]
198    fn test_toposort() {
199        let mut graph = Graph::new(4, 5);
200        graph.add_edge(0, 0);
201        graph.add_edge(0, 2);
202        graph.add_edge(3, 2);
203        graph.add_edge(3, 1);
204        graph.add_edge(1, 0);
205
206        assert_eq!(
207            ConnectivityGraph::new(&graph, true).topological_sort(),
208            vec![3, 1, 0, 2]
209        );
210    }
211
212    #[test]
213    fn test_two_sat() {
214        let mut graph = Graph::new(6, 8);
215        let (x, y, z) = (0, 2, 4);
216
217        graph.add_two_sat_clause(x, z);
218        graph.add_two_sat_clause(y ^ 1, z ^ 1);
219        graph.add_two_sat_clause(y, y);
220        assert_eq!(
221            ConnectivityGraph::new(&graph, true).two_sat_assign(),
222            Some(vec![true, true, false])
223        );
224
225        graph.add_two_sat_clause(z, z);
226        assert_eq!(ConnectivityGraph::new(&graph, true).two_sat_assign(), None);
227    }
228
229    #[test]
230    fn test_biconnected() {
231        let mut graph = Graph::new(3, 6);
232        graph.add_undirected_edge(0, 1);
233        graph.add_undirected_edge(1, 2);
234        graph.add_undirected_edge(1, 2);
235
236        let cg = ConnectivityGraph::new(&graph, false);
237        let bridges = (0..graph.num_e())
238            .filter(|&e| cg.is_cut_edge(e))
239            .collect::<Vec<_>>();
240        let articulation_points = (0..graph.num_v())
241            .filter(|&u| cg.is_cut_vertex(u))
242            .collect::<Vec<_>>();
243
244        assert_eq!(bridges, vec![0, 1]);
245        assert_eq!(articulation_points, vec![1]);
246    }
247}
contest_algorithms/graph/connectivity.rs

contest_algorithms/graph/
connectivity.rs
