1use super::{
2 Adjacencies, AdjacenciesWithValue, AdjacencyView, AdjacencyViewIterFromValue, GraphBase,
3 VIndexWithValue, VertexMap, VertexView, Vertices,
4};
5use std::{collections::HashMap, hash::Hash, iter::Map, marker::PhantomData, ops::Range};
6
7pub struct UsizeGraph<Fa> {
8 vsize: usize,
9 adj: Fa,
10}
11impl<Fa> UsizeGraph<Fa> {
12 pub fn new(vsize: usize, adj: Fa) -> Self {
13 Self { vsize, adj }
14 }
15}
16
17impl<Fa> GraphBase for UsizeGraph<Fa> {
18 type VIndex = usize;
19}
20
21impl<Fa> Vertices for UsizeGraph<Fa> {
22 type VIter<'g>
23 = Range<usize>
24 where
25 Fa: 'g;
26 fn vertices(&self) -> Self::VIter<'_> {
27 0..self.vsize
28 }
29}
30
31impl<Fa, I, T> Adjacencies for UsizeGraph<Fa>
32where
33 I: Iterator<Item = (usize, T)>,
34 Fa: Fn(usize) -> I,
35 T: Clone,
36{
37 type AIndex = VIndexWithValue<usize, T>;
38 type AIter<'g>
39 = Map<I, fn((usize, T)) -> VIndexWithValue<usize, T>>
40 where
41 Fa: 'g;
42
43 fn adjacencies(&self, vid: Self::VIndex) -> Self::AIter<'_> {
44 (self.adj)(vid).map(|a| a.into())
45 }
46}
47impl<Fa, I, T> AdjacenciesWithValue<T> for UsizeGraph<Fa>
48where
49 I: Iterator<Item = (usize, T)>,
50 Fa: Fn(usize) -> I,
51 T: Clone,
52{
53 type AIndex = VIndexWithValue<usize, T>;
54 type AIter<'g>
55 = Map<I, fn((usize, T)) -> VIndexWithValue<usize, T>>
56 where
57 Fa: 'g;
58
59 fn adjacencies_with_value(&self, vid: Self::VIndex) -> Self::AIter<'_> {
60 (self.adj)(vid).map(|a| a.into())
61 }
62}
63
64impl<Fa, T> VertexMap<T> for UsizeGraph<Fa> {
65 type Vmap = Vec<T>;
66 fn construct_vmap<F>(&self, f: F) -> Self::Vmap
67 where
68 F: FnMut() -> T,
69 {
70 let mut v = Vec::with_capacity(self.vsize);
71 v.resize_with(self.vsize, f);
72 v
73 }
74 fn vmap_get<'a>(&self, map: &'a Self::Vmap, vid: Self::VIndex) -> &'a T {
75 assert!(vid < self.vsize, "expected 0..{}, but {}", self.vsize, vid);
76 unsafe { map.get_unchecked(vid) }
77 }
78 fn vmap_get_mut<'a>(&self, map: &'a mut Self::Vmap, vid: Self::VIndex) -> &'a mut T {
79 assert!(vid < self.vsize, "expected 0..{}, but {}", self.vsize, vid);
80 unsafe { map.get_unchecked_mut(vid) }
81 }
82}
83impl<Fa, T> VertexView<Vec<T>, T> for UsizeGraph<Fa>
84where
85 T: Clone,
86{
87 fn vview(&self, map: &Vec<T>, vid: Self::VIndex) -> T {
88 self.vmap_get(map, vid).clone()
89 }
90}
91impl<Fa, T> VertexView<[T], T> for UsizeGraph<Fa>
92where
93 T: Clone,
94{
95 fn vview(&self, map: &[T], vid: Self::VIndex) -> T {
96 assert!(vid < self.vsize, "expected 0..{}, but {}", self.vsize, vid);
97 unsafe { map.get_unchecked(vid) }.clone()
98 }
99}
100impl<'a, Fa, M, I, T, U> AdjacencyView<'a, M, U> for UsizeGraph<Fa>
101where
102 I: Iterator<Item = (usize, T)>,
103 Fa: Fn(usize) -> I,
104 T: Clone,
105 M: 'a + Fn(T) -> U,
106{
107 type AViewIter<'g>
108 = AdjacencyViewIterFromValue<'g, 'a, Self, M, T, U>
109 where
110 Fa: 'g;
111 fn aviews<'g>(&'g self, map: &'a M, vid: Self::VIndex) -> Self::AViewIter<'g> {
112 AdjacencyViewIterFromValue::new(self.adjacencies_with_value(vid), map)
113 }
114}
115
116pub struct ClosureGraph<V, Fv, Fa> {
117 vs: Fv,
118 adj: Fa,
119 _marker: PhantomData<fn() -> V>,
120}
121
122impl<V, Fv, Fa> ClosureGraph<V, Fv, Fa> {
123 pub fn new(vs: Fv, adj: Fa) -> Self {
124 Self {
125 vs,
126 adj,
127 _marker: PhantomData,
128 }
129 }
130}
131
132impl<V, Fv, Fa> GraphBase for ClosureGraph<V, Fv, Fa>
133where
134 V: Eq + Copy,
135{
136 type VIndex = V;
137}
138
139impl<V, Fv, Fa, Iv> Vertices for ClosureGraph<V, Fv, Fa>
140where
141 V: Eq + Copy,
142 Iv: Iterator<Item = V>,
143 Fv: Fn() -> Iv,
144{
145 type VIter<'g>
146 = Iv
147 where
148 V: 'g,
149 Fv: 'g,
150 Fa: 'g;
151 fn vertices(&self) -> Self::VIter<'_> {
152 (self.vs)()
153 }
154}
155
156impl<V, Fv, Fa, Ia, T> Adjacencies for ClosureGraph<V, Fv, Fa>
157where
158 V: Eq + Copy,
159 Ia: Iterator<Item = (V, T)>,
160 Fa: Fn(V) -> Ia,
161 T: Clone,
162{
163 type AIndex = VIndexWithValue<V, T>;
164 type AIter<'g>
165 = Map<Ia, fn((V, T)) -> VIndexWithValue<V, T>>
166 where
167 V: 'g,
168 Fv: 'g,
169 Fa: 'g;
170
171 fn adjacencies(&self, vid: Self::VIndex) -> Self::AIter<'_> {
172 (self.adj)(vid).map(|a| a.into())
173 }
174}
175impl<V, Fv, Fa, Ia, T> AdjacenciesWithValue<T> for ClosureGraph<V, Fv, Fa>
176where
177 V: Eq + Copy,
178 Ia: Iterator<Item = (V, T)>,
179 Fa: Fn(V) -> Ia,
180 T: Clone,
181{
182 type AIndex = VIndexWithValue<V, T>;
183 type AIter<'g>
184 = Map<Ia, fn((V, T)) -> VIndexWithValue<V, T>>
185 where
186 V: 'g,
187 Fv: 'g,
188 Fa: 'g;
189
190 fn adjacencies_with_value(&self, vid: Self::VIndex) -> Self::AIter<'_> {
191 (self.adj)(vid).map(|a| a.into())
192 }
193}
194
195impl<V, Fv, Fa, T> VertexMap<T> for ClosureGraph<V, Fv, Fa>
196where
197 V: Eq + Copy + Hash,
198 T: Clone,
199{
200 type Vmap = (HashMap<V, T>, T);
201 fn construct_vmap<F>(&self, mut f: F) -> Self::Vmap
202 where
203 F: FnMut() -> T,
204 {
205 (HashMap::new(), f())
206 }
207 fn vmap_get<'a>(&self, (map, val): &'a Self::Vmap, vid: Self::VIndex) -> &'a T {
208 map.get(&vid).unwrap_or(val)
209 }
210 fn vmap_get_mut<'a>(&self, (map, val): &'a mut Self::Vmap, vid: Self::VIndex) -> &'a mut T {
211 map.entry(vid).or_insert_with(|| val.clone())
212 }
213}
214impl<V, Fv, Fa, T> VertexView<(HashMap<V, T>, T), T> for ClosureGraph<V, Fv, Fa>
215where
216 V: Eq + Copy + Hash,
217 T: Clone,
218{
219 fn vview(&self, map: &(HashMap<V, T>, T), vid: Self::VIndex) -> T {
220 self.vmap_get(map, vid).clone()
221 }
222}
223impl<'a, V, Fv, Fa, M, Ia, T, U> AdjacencyView<'a, M, U> for ClosureGraph<V, Fv, Fa>
224where
225 V: Eq + Copy,
226 Ia: Iterator<Item = (V, T)>,
227 Fa: Fn(V) -> Ia,
228 T: Clone,
229 M: 'a + Fn(T) -> U,
230{
231 type AViewIter<'g>
232 = AdjacencyViewIterFromValue<'g, 'a, Self, M, T, U>
233 where
234 Fa: 'g,
235 Fv: 'g,
236 V: 'g;
237 fn aviews<'g>(&'g self, map: &'a M, vid: Self::VIndex) -> Self::AViewIter<'g> {
238 AdjacencyViewIterFromValue::new(self.adjacencies_with_value(vid), map)
239 }
240}
241
242#[cfg(test)]
243mod tests {
244 use crate::{
245 algebra::AdditiveOperation,
246 graph::{ClosureGraph, GridGraph, ShortestPathExt, StandardSp, UsizeGraph, VertexMap},
247 num::Saturating,
248 tools::Xorshift,
249 };
250 use std::iter::repeat_with;
251
252 #[test]
253 fn closure_graph_sssp() {
254 let mut rng = Xorshift::default();
255 const A: u64 = 1_000_000_000;
256 let h = rng.rand(15) as usize + 1;
257 let w = rng.rand(15) as usize + 1;
258
259 let weight: Vec<_> = repeat_with(|| Saturating(rng.rand(A - 1) + 1))
260 .take(8)
261 .collect();
262 let visitable: Vec<Vec<bool>> =
263 repeat_with(|| repeat_with(|| rng.gen_bool(0.8)).take(w).collect())
264 .take(h)
265 .collect();
266 type Sp = StandardSp<AdditiveOperation<Saturating<u64>>>;
267
268 let g = GridGraph::new_adj8(h, w);
269 let g1 = UsizeGraph::new(h * w, |u| {
270 g.adj8(g.unflat(u)).filter_map(|a| {
271 if *g.vmap_get(&visitable, a.0) {
272 Some((g.flat(a.0), a.1))
273 } else {
274 None
275 }
276 })
277 });
278 let g2 = ClosureGraph::new(
279 || {
280 (0..h)
281 .flat_map(|i| (0..w).map(move |j| (i, j)))
282 .filter(|&(i, j)| visitable[i][j])
283 },
284 |u| g.adj8(u).filter(|&((i, j), _)| visitable[i][j]),
285 );
286 for (i, visitable) in visitable.iter().enumerate() {
287 for (j, visitable) in visitable.iter().enumerate() {
288 assert_eq!((i, j), g.unflat(g.flat((i, j))));
289 if !visitable {
290 continue;
291 }
292 let cost1 = g1.dijkstra_ss::<Sp, _>(g.flat((i, j)), &|dir| weight[dir as usize]);
293 let cost2 = g2.dijkstra_ss::<Sp, _>((i, j), &|dir| weight[dir as usize]);
294 for ni in 0..h {
295 for nj in 0..w {
296 assert_eq!(
297 g1.vmap_get(&cost1, g.flat((ni, nj))),
298 g2.vmap_get(&cost2, (ni, nj))
299 );
300 }
301 }
302 }
303 }
304 }
305
306 #[test]
307 fn closure_graph_apsp() {
308 let mut rng = Xorshift::default();
309 const A: u64 = 1_000_000_000;
310 let h = rng.rand(15) as usize + 1;
311 let w = rng.rand(15) as usize + 1;
312
313 let weight: Vec<_> = repeat_with(|| Saturating(rng.rand(A - 1) + 1))
314 .take(8)
315 .collect();
316 type Sp = StandardSp<AdditiveOperation<Saturating<u64>>>;
317
318 let g = GridGraph::new_adj4(h, w);
319 let cost: Vec<Vec<Vec<Vec<_>>>> = (0..h)
320 .map(|i| {
321 (0..w)
322 .map(|j| g.dijkstra_ss::<Sp, _>((i, j), &|dir| weight[dir as usize]))
323 .collect()
324 })
325 .collect();
326 let g2 = ClosureGraph::new(
327 || (0..h).flat_map(|i| (0..w).map(move |j| (i, j))),
328 |u| g.adj4(u),
329 );
330 let cost2 = g2.warshall_floyd_ap::<Sp, _>(&|dir| weight[dir as usize]);
331 for i in 0..h {
332 for j in 0..w {
333 for ni in 0..h {
334 for nj in 0..w {
335 assert_eq!(
336 g.vmap_get(g.vmap_get(&cost, (i, j)), (ni, nj)),
337 g2.vmap_get(g2.vmap_get(&cost2, (i, j)), (ni, nj))
338 );
339 }
340 }
341 }
342 }
343 }
344}