1use super::{EdgeMap, Graph, VertexMap};
2use std::collections::VecDeque;
3
4pub trait GraphOrderExt: Graph {
5 fn bfs_order(&self, root: Self::Vertex) -> Vec<Self::Vertex>
6 where
7 Self: VertexMap<bool>,
8 {
9 let mut visited = self.construct_vmap(|| false);
10 let mut order = Vec::with_capacity(self.vsize());
11 *self.vmap_get_mut(&mut visited, root) = true;
12 let mut queue = VecDeque::from([root]);
13 while let Some(u) = queue.pop_front() {
14 order.push(u);
15 for neighbor in self.neighbors(u) {
16 if !self.vmap_get(&visited, neighbor.to) {
17 *self.vmap_get_mut(&mut visited, neighbor.to) = true;
18 queue.push_back(neighbor.to);
19 }
20 }
21 }
22 order
23 }
24
25 fn dfs_order(&self, root: Self::Vertex) -> Vec<Self::Vertex>
26 where
27 Self: VertexMap<bool>,
28 {
29 let mut visited = self.construct_vmap(|| false);
30 let mut order = Vec::with_capacity(self.vsize());
31 *self.vmap_get_mut(&mut visited, root) = true;
32 let mut stack = vec![root];
33 while let Some(u) = stack.pop() {
34 order.push(u);
35 for neighbor in self.neighbors(u) {
36 if !self.vmap_get(&visited, neighbor.to) {
37 *self.vmap_get_mut(&mut visited, neighbor.to) = true;
38 stack.push(neighbor.to);
39 }
40 }
41 }
42 order
43 }
44
45 fn dfs_tree(&self, root: Self::Vertex) -> <Self as EdgeMap<bool>>::Emap
46 where
47 Self: EdgeMap<bool> + VertexMap<bool>,
48 {
49 let mut visited = self.construct_vmap(|| false);
50 let mut used = self.construct_emap(|| false);
51 *self.vmap_get_mut(&mut visited, root) = true;
52 let mut stack = vec![root];
53 while let Some(u) = stack.pop() {
54 for neighbor in self.neighbors(u) {
55 if !self.vmap_get(&visited, neighbor.to) {
56 *self.vmap_get_mut(&mut visited, neighbor.to) = true;
57 self.emap_set(&mut used, neighbor.label, true);
58 stack.push(neighbor.to);
59 }
60 }
61 }
62 used
63 }
64
65 fn for_each_connected_components<F>(&self, mut f: F)
67 where
68 Self: VertexMap<bool>,
69 F: FnMut(&Self, Self::Vertex, &[(Self::Vertex, Option<Self::Vertex>)]),
70 {
71 let mut visited = self.construct_vmap(|| false);
72 let mut order = Vec::with_capacity(self.vsize());
73 for root in self.vertices() {
74 if !self.vmap_get(&visited, root) {
75 *self.vmap_get_mut(&mut visited, root) = true;
76 order.push((root, None));
77 let mut i = 0;
78 while i < order.len() {
79 let u = order[i].0;
80 for neighbor in self.neighbors(u) {
81 if !self.vmap_get(&visited, neighbor.to) {
82 *self.vmap_get_mut(&mut visited, neighbor.to) = true;
83 order.push((neighbor.to, Some(u)));
84 }
85 }
86 i += 1;
87 }
88 f(self, root, &order);
89 order.clear();
90 }
91 }
92 }
93}
94
95impl<G> GraphOrderExt for G where G: Graph + ?Sized {}
96
97#[cfg(test)]
98mod tests {
99 use super::*;
100 use crate::{
101 graph::{AdjacencyListGraph, UndirectedSparseGraph, UsizeGraph},
102 rand,
103 tools::Xorshift,
104 };
105
106 fn reachable(n: usize, edges: &[(usize, usize)], root: usize, selected: &[bool]) -> Vec<bool> {
107 let mut reached = vec![false; n];
108 reached[root] = true;
109 let mut stack = vec![root];
110 while let Some(u) = stack.pop() {
111 for (eid, &(from, to)) in edges.iter().enumerate() {
112 if !selected[eid] {
113 continue;
114 }
115 let v = if from == u {
116 to
117 } else if to == u {
118 from
119 } else {
120 continue;
121 };
122 if !reached[v] {
123 reached[v] = true;
124 stack.push(v);
125 }
126 }
127 }
128 reached
129 }
130
131 #[test]
132 fn test_bfs_order() {
133 const Q: usize = 500;
134 const N: usize = 8;
135 const M: usize = 20;
136 let mut rng = Xorshift::default();
137 for _ in 0..Q {
138 rand!(rng, n: 1..=N, m: 0..=M, edges: [(0..n, 0..n); m]);
139 let sparse = UndirectedSparseGraph::from_edges(n, edges.clone());
140 let closure = UsizeGraph::new(n, |u| {
141 edges.iter().flat_map(move |&(from, to)| {
142 [
143 (from == u).then_some((to, ())),
144 (to == u).then_some((from, ())),
145 ]
146 .into_iter()
147 .flatten()
148 })
149 });
150 let mut adjacency_list = AdjacencyListGraph::new(n);
151 for &(u, v) in &edges {
152 adjacency_list.add_undirected_edge(u, v);
153 }
154 let all = vec![true; m];
155
156 for root in 0..n {
157 let expected = reachable(n, &edges, root, &all);
158 for order in [
159 sparse.bfs_order(root),
160 closure.bfs_order(root),
161 adjacency_list.bfs_order(root),
162 ] {
163 let mut visited = vec![false; n];
164 for vertex in order {
165 assert!(!std::mem::replace(&mut visited[vertex], true));
166 }
167 assert_eq!(visited, expected);
168 }
169 }
170 }
171 }
172
173 #[test]
174 fn test_dfs_order() {
175 const Q: usize = 500;
176 const N: usize = 8;
177 const M: usize = 20;
178 let mut rng = Xorshift::default();
179 for _ in 0..Q {
180 rand!(rng, n: 1..=N, m: 0..=M, edges: [(0..n, 0..n); m]);
181 let sparse = UndirectedSparseGraph::from_edges(n, edges.clone());
182 let closure = UsizeGraph::new(n, |u| {
183 edges.iter().flat_map(move |&(from, to)| {
184 [
185 (from == u).then_some((to, ())),
186 (to == u).then_some((from, ())),
187 ]
188 .into_iter()
189 .flatten()
190 })
191 });
192 let mut adjacency_list = AdjacencyListGraph::new(n);
193 for &(u, v) in &edges {
194 adjacency_list.add_undirected_edge(u, v);
195 }
196 let all = vec![true; m];
197
198 for root in 0..n {
199 let expected = reachable(n, &edges, root, &all);
200 for order in [
201 sparse.dfs_order(root),
202 closure.dfs_order(root),
203 adjacency_list.dfs_order(root),
204 ] {
205 let mut visited = vec![false; n];
206 for vertex in order {
207 assert!(!std::mem::replace(&mut visited[vertex], true));
208 }
209 assert_eq!(visited, expected);
210 }
211 }
212 }
213 }
214
215 #[test]
216 fn test_dfs_tree() {
217 const Q: usize = 500;
218 const N: usize = 8;
219 const M: usize = 20;
220 let mut rng = Xorshift::default();
221 for _ in 0..Q {
222 rand!(rng, n: 1..=N, m: 0..=M, edges: [(0..n, 0..n); m]);
223 let sparse = UndirectedSparseGraph::from_edges(n, edges.clone());
224 let mut adjacency_list = AdjacencyListGraph::new(n);
225 for &(u, v) in &edges {
226 adjacency_list.add_undirected_edge(u, v);
227 }
228 let all = vec![true; m];
229
230 for root in 0..n {
231 let expected = reachable(n, &edges, root, &all);
232 for selected in [sparse.dfs_tree(root), adjacency_list.dfs_tree(root)] {
233 assert_eq!(selected.len(), m);
234 assert_eq!(
235 selected.iter().filter(|&&selected| selected).count(),
236 expected.iter().filter(|&&reached| reached).count() - 1
237 );
238 assert_eq!(reachable(n, &edges, root, &selected), expected);
239 }
240 }
241 }
242 }
243
244 #[test]
245 fn test_for_each_connected_components() {
246 const Q: usize = 500;
247 const N: usize = 8;
248 const M: usize = 20;
249 let mut rng = Xorshift::default();
250 for _ in 0..Q {
251 rand!(rng, n: 1..=N, m: 0..=M, edges: [(0..n, 0..n); m]);
252 let sparse = UndirectedSparseGraph::from_edges(n, edges.clone());
253 let all = vec![true; m];
254 let mut expected_components = Vec::new();
255 let mut used = vec![false; n];
256 for root in 0..n {
257 if !used[root] {
258 let component: Vec<_> = reachable(n, &edges, root, &all)
259 .into_iter()
260 .enumerate()
261 .filter_map(|(vertex, reached)| reached.then_some(vertex))
262 .collect();
263 for &vertex in &component {
264 used[vertex] = true;
265 }
266 expected_components.push(component);
267 }
268 }
269 let mut actual_components = Vec::new();
270 sparse.for_each_connected_components(|_, root, order| {
271 assert_eq!(order[0], (root, None));
272 let mut component = Vec::with_capacity(order.len());
273 for &(vertex, parent) in order {
274 if let Some(parent) = parent {
275 assert!(edges.iter().any(|&(u, v)| {
276 (u == vertex && v == parent) || (u == parent && v == vertex)
277 }));
278 }
279 component.push(vertex);
280 }
281 component.sort_unstable();
282 actual_components.push(component);
283 });
284 assert_eq!(actual_components, expected_components);
285 }
286 }
287}