1use super::*;
2use std::{
3 cmp::{Ordering, Reverse},
4 collections::{BinaryHeap, VecDeque},
5 iter::once,
6 marker::PhantomData,
7};
8
9pub trait ShortestPathSemiRing {
10 type T: Clone + Ord;
11 fn source() -> Self::T;
12 fn inf() -> Self::T;
13 fn mul(x: &Self::T, y: &Self::T) -> Self::T;
14 fn add_assign(x: &mut Self::T, y: &Self::T) -> bool;
15}
16
17pub struct StandardSp<M>(PhantomData<fn() -> M>);
18impl<M> ShortestPathSemiRing for StandardSp<M>
19where
20 M: Monoid,
21 M::T: Bounded + Ord,
22{
23 type T = M::T;
24 fn source() -> Self::T {
25 M::unit()
26 }
27 fn inf() -> Self::T {
28 M::T::maximum()
29 }
30 fn mul(x: &Self::T, y: &Self::T) -> Self::T {
31 M::operate(x, y)
32 }
33 fn add_assign(x: &mut Self::T, y: &Self::T) -> bool {
34 if &*x > y {
35 *x = y.clone();
36 true
37 } else {
38 false
39 }
40 }
41}
42
43pub struct OptionSp<M>(PhantomData<fn() -> M>);
44impl<M> ShortestPathSemiRing for OptionSp<M>
45where
46 M: Monoid,
47 M::T: Ord,
48{
49 type T = Option<M::T>;
50 fn source() -> Self::T {
51 Some(M::unit())
52 }
53 fn inf() -> Self::T {
54 None
55 }
56 fn mul(x: &Self::T, y: &Self::T) -> Self::T {
57 match (x, y) {
58 (Some(x), Some(y)) => Some(M::operate(x, y)),
59 _ => None,
60 }
61 }
62 fn add_assign(x: &mut Self::T, y: &Self::T) -> bool {
63 if let Some(y) = y {
64 if let Some(x) = x {
65 if &*x > y {
66 *x = y.clone();
67 true
68 } else {
69 false
70 }
71 } else {
72 *x = Some(y.clone());
73 true
74 }
75 } else {
76 false
77 }
78 }
79}
80
81pub struct PathFoldingSp<M, S>(PhantomData<fn() -> (M, S)>);
82impl<M, S> ShortestPathSemiRing for PathFoldingSp<M, S>
83where
84 M: Monoid,
85 M::T: Bounded + Ord,
86 S: SemiRing,
87{
88 type T = PartialIgnoredOrd<M::T, S::T>;
89 fn source() -> Self::T {
90 PartialIgnoredOrd(M::unit(), S::one())
91 }
92 fn inf() -> Self::T {
93 PartialIgnoredOrd(M::T::maximum(), S::zero())
94 }
95 fn mul(x: &Self::T, y: &Self::T) -> Self::T {
96 PartialIgnoredOrd(M::operate(&x.0, &y.0), S::mul(&x.1, &y.1))
97 }
98 fn add_assign(x: &mut Self::T, y: &Self::T) -> bool {
99 match x.0.cmp(&y.0) {
100 Ordering::Equal => {
101 x.1 = S::add(&x.1, &y.1);
102 false
103 }
104 Ordering::Greater => {
105 *x = y.clone();
106 true
107 }
108 _ => false,
109 }
110 }
111}
112
113pub trait ShortestPathExt: GraphBase {
114 fn bfs_distance_ss<'a, S, M>(
115 &self,
116 source: Self::VIndex,
117 weight: &'a M,
118 ) -> <Self as VertexMap<S::T>>::Vmap
119 where
120 Self: VertexMap<S::T> + AdjacencyView<'a, M, S::T>,
121 S: ShortestPathSemiRing,
122 {
123 self.bfs_distance_ms::<S, M, _>(once(source), weight)
124 }
125 fn bfs_distance_ms<'a, S, M, I>(
126 &self,
127 sources: I,
128 weight: &'a M,
129 ) -> <Self as VertexMap<S::T>>::Vmap
130 where
131 Self: VertexMap<S::T> + AdjacencyView<'a, M, S::T>,
132 S: ShortestPathSemiRing,
133 I: IntoIterator<Item = Self::VIndex>,
134 {
135 let mut cost = self.construct_vmap(S::inf);
136 let mut deq = VecDeque::new();
137 for source in sources.into_iter() {
138 *self.vmap_get_mut(&mut cost, source) = S::source();
139 deq.push_back(source);
140 }
141 let zero = S::source();
142 while let Some(u) = deq.pop_front() {
143 for a in self.aviews(weight, u) {
144 let v = a.vindex();
145 let w = a.avalue();
146 let nd = S::mul(self.vmap_get(&cost, u), &w);
147 if S::add_assign(self.vmap_get_mut(&mut cost, v), &nd) {
148 if w == zero {
149 deq.push_front(v);
150 } else {
151 deq.push_back(v);
152 }
153 }
154 }
155 }
156 cost
157 }
158 fn dijkstra_ss<'a, S, M>(
159 &self,
160 source: Self::VIndex,
161 weight: &'a M,
162 ) -> <Self as VertexMap<S::T>>::Vmap
163 where
164 Self: VertexMap<S::T> + AdjacencyView<'a, M, S::T>,
165 S: ShortestPathSemiRing,
166 {
167 self.dijkstra_ms::<S, M, _>(once(source), weight)
168 }
169 fn dijkstra_ms<'a, S, M, I>(&self, sources: I, weight: &'a M) -> <Self as VertexMap<S::T>>::Vmap
170 where
171 Self: VertexMap<S::T> + AdjacencyView<'a, M, S::T>,
172 S: ShortestPathSemiRing,
173 I: IntoIterator<Item = Self::VIndex>,
174 {
175 let mut cost = self.construct_vmap(S::inf);
176 let mut heap = BinaryHeap::new();
177 for source in sources.into_iter() {
178 *self.vmap_get_mut(&mut cost, source) = S::source();
179 heap.push(PartialIgnoredOrd(Reverse(S::source()), source));
180 }
181 while let Some(PartialIgnoredOrd(Reverse(d), u)) = heap.pop() {
182 if self.vmap_get(&cost, u) != &d {
183 continue;
184 }
185 let d = self.vmap_get(&cost, u).clone();
186 for a in self.aviews(weight, u) {
187 let v = a.vindex();
188 let nd = S::mul(&d, &a.avalue());
189 if S::add_assign(self.vmap_get_mut(&mut cost, v), &nd) {
190 heap.push(PartialIgnoredOrd(Reverse(nd), v));
191 }
192 }
193 }
194 cost
195 }
196 fn bellman_ford_ss<'a, S, M>(
197 &self,
198 source: Self::VIndex,
199 weight: &'a M,
200 check: bool,
201 ) -> Option<<Self as VertexMap<S::T>>::Vmap>
202 where
203 Self: Vertices + VertexMap<S::T> + AdjacencyView<'a, M, S::T> + VertexSize,
204 S: ShortestPathSemiRing,
205 {
206 self.bellman_ford_ms::<S, M, _>(once(source), weight, check)
207 }
208 fn bellman_ford_ms<'a, S, M, I>(
209 &self,
210 sources: I,
211 weight: &'a M,
212 check: bool,
213 ) -> Option<<Self as VertexMap<S::T>>::Vmap>
214 where
215 Self: Vertices + VertexMap<S::T> + AdjacencyView<'a, M, S::T> + VertexSize,
216 S: ShortestPathSemiRing,
217 I: IntoIterator<Item = Self::VIndex>,
218 {
219 let mut cost = self.construct_vmap(S::inf);
220 for source in sources.into_iter() {
221 *self.vmap_get_mut(&mut cost, source) = S::source();
222 }
223 let vsize = self.vsize();
224 for _ in 1..vsize {
225 let mut updated = false;
226 for u in self.vertices() {
227 for a in self.aviews(weight, u) {
228 let v = a.vindex();
229 let nd = S::mul(self.vmap_get(&cost, u), &a.avalue());
230 updated |= S::add_assign(self.vmap_get_mut(&mut cost, v), &nd);
231 }
232 }
233 if !updated {
234 break;
235 }
236 }
237 if check {
238 for u in self.vertices() {
239 for a in self.aviews(weight, u) {
240 let v = a.vindex();
241 let nd = S::mul(self.vmap_get(&cost, u), &a.avalue());
242 if S::add_assign(self.vmap_get_mut(&mut cost, v), &nd) {
243 return None;
244 }
245 }
246 }
247 }
248 Some(cost)
249 }
250 fn warshall_floyd_ap<'a, S, M>(
251 &self,
252 weight: &'a M,
253 ) -> <Self as VertexMap<<Self as VertexMap<S::T>>::Vmap>>::Vmap
254 where
255 Self: Vertices
256 + VertexMap<S::T>
257 + VertexMap<<Self as VertexMap<S::T>>::Vmap>
258 + AdjacencyView<'a, M, S::T>,
259 <Self as VertexMap<S::T>>::Vmap: Clone,
260 S: ShortestPathSemiRing,
261 {
262 let mut cost = self.construct_vmap(|| self.construct_vmap(S::inf));
263 for u in self.vertices() {
264 *self.vmap_get_mut(self.vmap_get_mut(&mut cost, u), u) = S::source();
265 }
266 for u in self.vertices() {
267 for a in self.aviews(weight, u) {
268 *self.vmap_get_mut(self.vmap_get_mut(&mut cost, u), a.vindex()) = a.avalue();
269 }
270 }
271 for k in self.vertices() {
272 for i in self.vertices() {
273 for j in self.vertices() {
274 let d1 = self.vmap_get(self.vmap_get(&cost, i), k);
275 let d2 = self.vmap_get(self.vmap_get(&cost, k), j);
276 let nd = S::mul(d1, d2);
277 S::add_assign(self.vmap_get_mut(self.vmap_get_mut(&mut cost, i), j), &nd);
278 }
279 }
280 }
281 cost
282 }
283}
284impl<G> ShortestPathExt for G where G: GraphBase {}