1use crate::analyzer::min_weight::{MinWeight, Score};
2use crate::visualizer::dot::{DotProcessor, ToStringProcessor};
3use crate::DiGraph;
4use graphviz_rust::attributes::*;
5use graphviz_rust::dot_generator::*;
6use graphviz_rust::dot_structures::Stmt;
7use graphviz_rust::dot_structures::*;
8use std::borrow::Borrow;
9use std::cmp::Ordering;
10use std::collections::{BinaryHeap, HashMap};
11use std::convert::identity;
12use std::fmt::Debug;
13use std::hash::Hash;
14use std::marker::PhantomData;
15use std::ops::{Add, Index};
16#[derive(Debug)]
17pub struct DijkstraPath<'a, NId, NL, EL>
18where
19 NId: Eq + Hash + Clone,
20{
21 graph: &'a DiGraph<NId, NL, EL>,
22}
23
24impl<'a, NId, NL, EL> DijkstraPath<'a, NId, NL, EL>
25where
26 NId: Eq + Hash + Clone,
27 EL: Ord + Add<Output = EL> + Clone,
28{
29 pub fn on_edge(&mut self, start: NId) -> MinPath<NId, EL> {
30 self.on_edge_custom(start, identity)
31 }
32}
33
34impl<'a, NId, NL, EL> DijkstraPath<'a, NId, NL, EL>
35where
36 NId: Eq + Hash + Clone,
37 EL: Clone,
38{
39 pub fn on_edge_custom<ScoreV, F>(&mut self, start: NId, to_score: F) -> MinPath<NId, ScoreV>
40 where
41 F: Fn(EL) -> ScoreV,
42 ScoreV: Ord + Add<Output = ScoreV> + Clone,
43 {
44 let mut dist = HashMap::from([(start.clone(), Score::Zero)]);
45 let mut path = HashMap::new();
46 let mut queue = BinaryHeap::new();
47
48 for (id, _) in &self.graph.nodes {
49 if id.ne(&start) {
50 dist.insert(id.clone(), Score::Inf);
51 }
52 queue.push(MinWeight(&start, dist[&id].clone()))
53 }
54
55 while let Some(MinWeight(from, _)) = queue.pop() {
56 if let Some(ss) = self.graph.edges.get(from) {
57 let dist_from = dist[from].clone();
58 for (to, ep) in ss {
59 let alt = dist_from.add_score_v(to_score(ep.clone()));
60 let dist_to = dist[to].clone();
61 if alt < dist_to {
62 dist.insert(to.clone(), alt.clone());
63 path.insert(to.clone(), from.clone());
64 queue.push(MinWeight(to, alt.clone()))
65 }
66 }
67 }
68 }
69 MinPath::new(start, dist, path)
70 }
71}
72
73impl<'a, NId, NL, EL> DijkstraPath<'a, NId, NL, EL>
74where
75 NId: Eq + Hash + Clone,
76{
77 pub fn new(graph: &'a DiGraph<NId, NL, EL>) -> Self {
78 Self { graph }
79 }
80}
81
82#[derive(Debug)]
83pub struct MinPath<NId, ScoreV>
84where
85 NId: Eq + Hash + Clone,
86 ScoreV: Clone,
87{
88 from: NId,
89 distance: HashMap<NId, Score<ScoreV>>,
90 path: HashMap<NId, NId>,
91}
92
93impl<NId, ScoreV> MinPath<NId, ScoreV>
94where
95 NId: Eq + Hash + Clone,
96 ScoreV: Clone,
97{
98 pub fn new(from: NId, distance: HashMap<NId, Score<ScoreV>>, path: HashMap<NId, NId>) -> Self {
99 Self {
100 from,
101 distance,
102 path,
103 }
104 }
105
106 pub fn score(&self, to: &NId) -> Score<ScoreV> {
107 self.distance[to].clone()
108 }
109 pub fn trail(&self, to: &NId) -> Option<Vec<NId>> {
110 let mut rhs = to;
111 let mut trail = vec![];
112 while let Some(start) = self.path.get(rhs) {
113 trail.push(rhs.clone());
114 rhs = start;
115 if rhs.eq(&self.from) {
116 trail.push(rhs.clone());
117 trail.reverse();
118 return Some(trail);
119 }
120 }
121 None
122 }
123}
124
125struct MinScorePathProcessor<NId, ScoreV>
126where
127 NId: Eq + Hash + Clone,
128 ScoreV: Clone,
129{
130 from: NId,
131 distance: HashMap<NId, Score<ScoreV>>,
132 delegate: ToStringProcessor,
133}
134
135impl<NId, ScoreV> MinScorePathProcessor<NId, ScoreV>
136where
137 NId: Eq + Hash + Clone,
138 ScoreV: Clone,
139{
140 pub fn new(from: NId, distance: HashMap<NId, Score<ScoreV>>) -> Self {
141 Self {
142 from,
143 distance,
144 delegate: ToStringProcessor {},
145 }
146 }
147}
148
149impl<'a, NId, NL, EL, ScoreV> DotProcessor<'a, NId, NL, EL> for MinScorePathProcessor<NId, ScoreV>
150where
151 NId: Eq + Hash + Clone + ToString,
152 NL: ToString,
153 EL: ToString,
154 ScoreV: ToString + Clone,
155{
156 fn node(&self, id: &'a NId, nl: &'a NL) -> Stmt {
157 if let Some(score) = self.distance.get(id) {
158 let mut attrs = vec![NodeAttributes::xlabel(score.to_string())];
159 if &self.from == id {
160 attrs.push(NodeAttributes::color(color_name::red));
161 }
162 self.delegate.node_with_attrs(id, nl, attrs)
163 } else {
164 self.delegate.node_with_attrs(id, nl, vec![])
165 }
166 }
167
168 fn edge(&self, from: &'a NId, to: &'a NId, el: &'a EL) -> Stmt {
169 (&self.delegate as &dyn DotProcessor<NId, NL, EL>).edge(from, to, el)
170 }
171}
172
173pub struct MinPathProcessor<NId>
174where
175 NId: Clone,
176{
177 path: Vec<NId>,
178 delegate: ToStringProcessor,
179}
180
181impl<NId> MinPathProcessor<NId>
182where
183 NId: Eq + Hash + Clone,
184{
185 pub fn new(path: Vec<NId>) -> Self {
186 Self {
187 path,
188 delegate: ToStringProcessor {},
189 }
190 }
191}
192
193impl<'a, NId, NL, EL> DotProcessor<'a, NId, NL, EL> for MinPathProcessor<NId>
194where
195 NId: Eq + Hash + Clone + ToString,
196 NL: ToString,
197 EL: ToString,
198{
199 fn node(&self, id: &'a NId, nl: &'a NL) -> Stmt {
200 if self.path.is_empty() {
201 (&self.delegate as &dyn DotProcessor<NId, NL, EL>).node(id, nl)
202 } else {
203 let f = self.path.get(0).unwrap();
204 let l = self.path.last().unwrap();
205 let green = NodeAttributes::color(color_name::green);
206 if f == id || l == id {
207 let bold = NodeAttributes::style("bold".to_string());
208 self.delegate.node_with_attrs(id, nl, vec![green, bold])
209 } else if self.path.contains(id) {
210 self.delegate.node_with_attrs(id, nl, vec![green])
211 } else {
212 (&self.delegate as &dyn DotProcessor<NId, NL, EL>).node(id, nl)
213 }
214 }
215 }
216
217 fn edge(&self, from: &'a NId, to: &'a NId, el: &'a EL) -> Stmt {
218 let mut f = None;
219 let mut t = None;
220
221 for (idx, id) in self.path.iter().enumerate() {
222 if id == from {
223 f = Some(idx)
224 };
225 if id == to {
226 t = Some(idx)
227 };
228 }
229
230 let dotted = EdgeAttributes::style("dotted".to_string());
231 match (f, t) {
232 (Some(f), Some(t)) if f < t => {
233 (&self.delegate as &dyn DotProcessor<NId, NL, EL>).edge(from, to, el)
234 }
235 _ => self.delegate.edge_with_attrs(from, to, el, vec![dotted]),
236 }
237 }
238}
239
240#[cfg(test)]
243mod tests {
244 use crate::analyzer::dijkstra::{
245 DijkstraPath, MinPathProcessor, MinScorePathProcessor, MinWeight,
246 };
247 use crate::analyzer::min_weight::Score;
248 use crate::analyzer::min_weight::Score::*;
249 use crate::DiGraph;
250 use crate::EmptyPayload;
251 use crate::{digraph, extend_edges, extend_nodes};
252 use std::collections::BinaryHeap;
253 use std::ops::Add;
254
255 #[test]
256 fn simple_test() {
257 let mut q = BinaryHeap::new();
258 q.push(MinWeight(&EmptyPayload, Zero));
259 q.push(MinWeight(&EmptyPayload, Inf));
260 q.push(MinWeight(&EmptyPayload, Value(1)));
261 q.push(MinWeight(&EmptyPayload, Value(5)));
262 q.push(MinWeight(&EmptyPayload, Value(3)));
263 q.push(MinWeight(&EmptyPayload, Zero));
264
265 assert_eq!(q.pop(), Some(MinWeight(&EmptyPayload, Zero)));
266 assert_eq!(q.pop(), Some(MinWeight(&EmptyPayload, Zero)));
267 assert_eq!(q.pop(), Some(MinWeight(&EmptyPayload, Value(1))));
268 assert_eq!(q.pop(), Some(MinWeight(&EmptyPayload, Value(3))));
269 assert_eq!(q.pop(), Some(MinWeight(&EmptyPayload, Value(5))));
270 assert_eq!(q.pop(), Some(MinWeight(&EmptyPayload, Inf)));
271 assert_eq!(q.pop(), None);
272 }
273 #[test]
274 fn simple_dijkstra_test() {
275 let graph = digraph!((usize,_,usize) => [1,2,3,4,5,6,7,8,9,10,11,] => {
276 1 => [(2,1),(3,1)];
277 2 => (4,2);
278 3 => (5,3);
279 [4,5] => (6,1);
280 6 => (7,1);
281 7 => [(8,1),(9,2),(10,3)];
282 [8,9,10] => (11,1)
283
284 });
285 let mut d = DijkstraPath::new(&graph);
286 let d = d.on_edge(1).score(&11);
287 println!("{:?}", d)
288 }
289 #[test]
290 fn cycled_dijkstra_test() {
291 let graph = digraph!((_,_,usize) => [1,2,3,4,5,6,7,8,9,10,11,] => {
292 1 => [(2,1),(3,1)];
293 2 => (4,2);
294 3 => (5,3);
295 [4,5] => (6,1);
296 5 => (11,4);
297 6 => [(7,1),(1,1)];
298 7 => [(8,1),(9,2),(10,3)];
299 [8,9,10] => (11,1)
300
301 });
302 let _ = graph.visualize().str_to_dot_file("dots/output.svg");
303
304 let mut d = DijkstraPath::new(&graph);
305 let to = d.on_edge(1).score(&11);
306 assert_eq!(to, Value(7));
307
308 let mut d = DijkstraPath::new(&graph);
309 let to = d.on_edge(8).score(&1);
310 assert_eq!(to, Inf);
311
312 let mut d = DijkstraPath::new(&graph);
313 let to = d.on_edge(1).trail(&11);
314
315 assert_eq!(to, Some(vec![1, 2, 4, 6, 7, 8, 11]));
316
317 let mut d = DijkstraPath::new(&graph);
318 let to = d.on_edge(8).trail(&1);
319 assert_eq!(to, None);
320 }
321
322 #[test]
323 fn viz_cycled_dijkstra_test() {
324 let graph = digraph!((_,_,usize) => [1,2,3,4,5,6,7,8,9,10,11,] => {
325 1 => [(2,1),(3,1)];
326 2 => (4,2);
327 3 => (5,3);
328 [4,5] => (6,1);
329 5 => (11,4);
330 6 => [(7,1),(1,1)];
331 7 => [(8,1),(9,2),(10,3)];
332 [8,9,10] => (11,1)
333
334 });
335
336 let mut d = DijkstraPath::new(&graph);
337 let to = d.on_edge(1).trail(&11).unwrap();
338 assert_eq!(to, vec![1, 2, 4, 6, 7, 8, 11]);
339 let r = graph
340 .visualize()
341 .to_dot_file("dots/output1.svg", MinPathProcessor::new(to));
342 println!("{:?}", r);
343 }
344 #[test]
345 fn viz_l_cycled_dijkstra_test() {
346 let graph = digraph!((_,&str,usize) => [
347 (1,"a"),
348 (2,"b"),
349 (3,"c"),
350 (4,"d"),
351 (5,"e"),
352 (6,"f"),
353 (7,"g"),
354 (8,"h"),
355 (9,"y"),
356 (10,"u"),
357 (11,"i"),
358
359 ] => {
360 1 => [(2,1),(3,1)];
361 2 => (4,2);
362 3 => (5,3);
363 [4,5] => (6,1);
364 5 => (11,4);
365 6 => [(7,1),(1,1)];
366 7 => [(8,1),(9,2),(10,3)];
367 [8,9,10] => (11,1)
368
369 });
370 let _ = graph.visualize().str_to_dot_file("dots/output.svg");
371 let mut dijkstra = DijkstraPath::new(&graph);
372 let map = dijkstra.on_edge(1);
373 let to = map.trail(&11).unwrap();
374 assert_eq!(to, vec![1, 2, 4, 6, 7, 8, 11]);
375 let r = graph
376 .visualize()
377 .to_dot_file("dots/output_path.svg", MinPathProcessor::new(to));
378 println!("{:?}", r);
379 let r = graph.visualize().to_dot_file(
380 "dots/output_sc.svg",
381 MinScorePathProcessor::new(map.from, map.distance),
382 );
383 println!("{:?}", r);
384 }
385 #[derive(Clone, Ord, PartialOrd, PartialEq, Eq)]
386 struct One(usize);
387
388 impl Add for One {
389 type Output = One;
390
391 fn add(self, rhs: Self) -> Self::Output {
392 One(self.0 + rhs.0)
393 }
394 }
395
396 impl ToString for One {
397 fn to_string(&self) -> String {
398 self.0.to_string()
399 }
400 }
401
402 impl Default for One {
403 fn default() -> Self {
404 One(1)
405 }
406 }
407
408 #[test]
409 fn one_dijkstra_test() {
410 let graph = digraph!((_,_,One) => [1,2,3,4,5,6,7,8] => {
411 1 => [2,3,4];
412 [2,3] => 5;
413 4 => 6;
414 5 => 6;
415 6 => 7;
416 7 => 8;
417 });
418 let r = graph.visualize().str_to_dot_file("dots/graph.svg");
419 assert!(r.is_ok());
420 let mut d_path = DijkstraPath::new(&graph);
421 let path = d_path.on_edge(1);
422 let trail = path.trail(&8).unwrap();
423
424 let r = graph
425 .visualize()
426 .to_dot_file("dots/graph_path.svg", MinPathProcessor::new(trail));
427 assert!(r.is_ok());
428 }
429}