digraph_rs/analyzer/
fs.rs

1use graphviz_rust::{
2    attributes::{color_name, NodeAttributes},
3    dot_structures::Stmt,
4};
5
6use crate::{
7    analyzer::SearchRes,
8    visualizer::dot::{DotProcessor, ToStringProcessor},
9};
10use std::collections::VecDeque;
11use std::fmt::Debug;
12use std::hash::Hash;
13
14use super::visit::{Visited, VisitedSet};
15use crate::DiGraph;
16
17struct DFS<'a, NId, NL, EL>
18where
19    NId: Eq + Hash,
20{
21    graph: &'a DiGraph<NId, NL, EL>,
22}
23
24impl<'a, NId, NL, EL> DFS<'a, NId, NL, EL>
25where
26    NId: Eq + Hash + Clone,
27{
28    fn new(graph: &'a DiGraph<NId, NL, EL>) -> Self {
29        Self { graph }
30    }
31    pub fn search_by_eq(&self, start: &'a NId, target: &'a NId) -> Option<&'a NId> {
32        self.search(start, |n| {
33            if target == n {
34                SearchRes::Find
35            } else {
36                SearchRes::Next
37            }
38        })
39    }
40    fn search<S>(&self, start: &'a NId, target: S) -> Option<&'a NId>
41    where
42        S: Fn(&'a NId) -> SearchRes,
43    {
44        let mut visited = VisitedSet::default();
45        let mut q = vec![];
46
47        q.push(start);
48
49        while let Some(node) = q.pop() {
50            visited.visit(node);
51            match target(node) {
52                SearchRes::Next => {
53                    for nexts in self.graph.successors(node.clone()) {
54                        for s in nexts.keys() {
55                            if !visited.already_visited(s) {
56                                q.push(s)
57                            }
58                        }
59                    }
60                }
61                SearchRes::Skip => (),
62                SearchRes::Find => return Some(node),
63                SearchRes::Stop => return None,
64            }
65        }
66
67        None
68    }
69}
70
71struct BFS<'a, NId, NL, EL>
72where
73    NId: Eq + Hash,
74{
75    graph: &'a DiGraph<NId, NL, EL>,
76}
77
78impl<'a, NId, NL, EL> BFS<'a, NId, NL, EL>
79where
80    NId: Eq + Hash + Clone,
81{
82    fn new(graph: &'a DiGraph<NId, NL, EL>) -> Self {
83        BFS { graph }
84    }
85
86    pub fn search_by_eq(&self, start: &'a NId, target: &'a NId) -> Option<&'a NId> {
87        self.search(start, |n| {
88            if target == n {
89                SearchRes::Find
90            } else {
91                SearchRes::Next
92            }
93        })
94    }
95    fn search<S>(&self, start: &'a NId, target: S) -> Option<&'a NId>
96    where
97        S: Fn(&'a NId) -> SearchRes,
98    {
99        let mut visited = VisitedSet::default();
100        let mut q = VecDeque::new();
101
102        q.push_back(start);
103
104        while let Some(node) = q.pop_front() {
105            visited.visit(node);
106            match target(node) {
107                SearchRes::Next => {
108                    for nexts in self.graph.successors(node.clone()) {
109                        for s in nexts.keys() {
110                            if !visited.already_visited(s) {
111                                q.push_back(s)
112                            }
113                        }
114                    }
115                }
116                SearchRes::Skip => (),
117                SearchRes::Find => return Some(node),
118                SearchRes::Stop => return None,
119            }
120        }
121
122        None
123    }
124}
125
126struct SrcTrgHighlighter<'a, NId>
127where
128    NId: Eq + Hash + Clone + ToString,
129{
130    src: &'a NId,
131    trg: &'a NId,
132    delegate: ToStringProcessor,
133}
134
135impl<'a, NId> SrcTrgHighlighter<'a, NId>
136where
137    NId: Eq + Hash + Clone + ToString,
138{
139    fn new(src: &'a NId, trg: &'a NId) -> Self {
140        Self {
141            src,
142            trg,
143            delegate: ToStringProcessor {},
144        }
145    }
146}
147
148impl<'a, NId, NL, EL> DotProcessor<'a, NId, NL, EL> for SrcTrgHighlighter<'a, NId>
149where
150    NId: Eq + Hash + Clone + ToString,
151    EL: ToString,
152    NL: ToString,
153{
154    fn node(&self, id: &'a NId, nl: &'a NL) -> Stmt {
155        if id != self.src && id != self.trg {
156            (&self.delegate as &dyn DotProcessor<NId, NL, EL>).node(id, nl)
157        } else {
158            let green = NodeAttributes::color(color_name::green);
159            let bold = NodeAttributes::style("bold".to_string());
160            self.delegate.node_with_attrs(id, nl, vec![green, bold])
161        }
162    }
163
164    fn edge(&self, from: &'a NId, to: &'a NId, el: &'a EL) -> Stmt {
165        (&self.delegate as &dyn DotProcessor<NId, NL, EL>).edge(from, to, el)
166    }
167}
168
169#[cfg(test)]
170mod tests {
171    use crate::analyzer::fs::{SearchRes, SrcTrgHighlighter, BFS, DFS};
172    use crate::DiGraph;
173    use crate::EmptyPayload;
174    use crate::{digraph, extend_edges, extend_nodes};
175
176    #[test]
177    fn bfs_simple_test() {
178        let graph = digraph!((usize,_,_) => [1,2,3,4,5,6,7,8,9,10] => {
179            1 => 2;
180            2 => [3,4,5];
181            3 => 6;
182            6 => [1,7,8];
183            8 => 9;
184            9 => [1,10];
185        });
186
187        let res = graph.visualize().str_to_dot_file("dots/bfs.svg");
188        assert!(res.is_ok());
189
190        let bfs = BFS::new(&graph);
191
192        let res = bfs.search_by_eq(&1, &10);
193        assert_eq!(res, Some(&10))
194    }
195
196    #[test]
197    fn simple_test2() {
198        let graph = digraph!((usize,_,_) => [1,2,3,4,5,6,7,8,9,10] => {
199            1 => 2;
200            2 => [3,4,5];
201            3 => 6;
202            6 => [1,7,8];
203            8 => 9;
204            9 => [1,10];
205        });
206
207        let res = graph.visualize().str_to_dot_file("dots/bfs.svg");
208        assert!(res.is_ok());
209
210        let dfs = DFS::new(&graph);
211
212        let res = dfs.search_by_eq(&1, &10);
213        assert_eq!(res, Some(&10))
214    }
215    #[test]
216    fn cap_test() {
217        let graph = digraph!((usize,_,_) => [1,2,3,4,5,6,7,8,9,10] => {
218            1 => 2;
219            2 => [3,4,5];
220            3 => 6;
221            6 => [1,7,8];
222            8 => 9;
223            9 => [1,10];
224        });
225
226        let res = graph.visualize().str_to_dot_file("dots/bfs.svg");
227        assert!(res.is_ok());
228
229        let dfs = DFS::new(&graph);
230        let bfs = BFS::new(&graph);
231
232        let res = dfs.search(&1, move |n| {
233            if &10 == n {
234                SearchRes::Find
235            } else {
236                println!("n = {}", n);
237                SearchRes::Next
238            }
239        });
240        assert_eq!(res, Some(&10));
241
242        println!("bfs");
243
244        let res = bfs.search(&1, move |n| {
245            if &10 == n {
246                SearchRes::Find
247            } else {
248                println!("n = {}", n);
249                SearchRes::Next
250            }
251        });
252        assert_eq!(res, Some(&10));
253        graph
254            .visualize()
255            .to_dot_file("dots/test.svg", SrcTrgHighlighter::new(&1, &10));
256    }
257}
digraph_rs/analyzer/fs.rs

digraph_rs/analyzer/
fs.rs
