gdsl/sync_digraph/node/algo/
dfs.rs1use super::{method::*, path::*, *};
2use ahash::AHashSet as HashSet;
3use std::{fmt::Display, hash::Hash};
4
5pub struct Dfs<'a, K, N, E>
6where
7 K: Clone + Hash + Display + PartialEq + Eq,
8 N: Clone,
9 E: Clone,
10{
11 root: Node<K, N, E>,
12 target: Option<K>,
13 method: Method<'a, K, N, E>,
14 transpose: Transposition,
15}
16
17impl<'a, K, N, E> Dfs<'a, K, N, E>
18where
19 K: Clone + Hash + Display + PartialEq + Eq,
20 N: Clone,
21 E: Clone,
22{
23 pub fn new(root: &Node<K, N, E>) -> Self {
24 Dfs {
25 root: root.clone(),
26 target: None,
27 method: Method::Empty,
28 transpose: Transposition::Outbound,
29 }
30 }
31
32 pub fn target(mut self, target: &K) -> Self {
33 self.target = Some(target.clone());
34 self
35 }
36
37 pub fn transpose(mut self) -> Self {
38 self.transpose = Transposition::Inbound;
39 self
40 }
41
42 pub fn for_each(mut self, f: ForEach<'a, K, N, E>) -> Self {
43 self.method = Method::ForEach(f);
44 self
45 }
46
47 pub fn filter(mut self, f: Filter<'a, K, N, E>) -> Self {
48 self.method = Method::Filter(f);
49 self
50 }
51
52 pub fn search(&'a mut self) -> Option<Node<K, N, E>> {
53 let mut queue = vec![];
54 let mut visited = HashSet::default();
55
56 queue.push(self.root.clone());
57 visited.insert(self.root.key().clone());
58
59 match self.transpose {
60 Transposition::Outbound => self.recurse_outbound_find(&mut visited, &mut queue),
61 Transposition::Inbound => self.recurse_inbound_find(&mut visited, &mut queue),
62 }
63 }
64
65 pub fn search_cycle(&'a mut self) -> Option<Path<K, N, E>> {
66 let mut edges = vec![];
67 let mut queue = vec![];
68 let mut visited = HashSet::default();
69
70 self.target = Some(self.root.key().clone());
71 queue.push(self.root.clone());
72
73 match self.transpose {
74 Transposition::Outbound => {
75 match self.recurse_outbound(&mut edges, &mut visited, &mut queue) {
76 true => Some(Path::from_edge_tree(edges)),
77 false => None,
78 }
79 }
80 Transposition::Inbound => {
81 match self.recurse_inbound(&mut edges, &mut visited, &mut queue) {
82 true => Some(Path::from_edge_tree(edges)),
83 false => None,
84 }
85 }
86 }
87 }
88
89 pub fn search_path(&mut self) -> Option<Path<K, N, E>> {
90 let mut edges = vec![];
91 let mut queue = vec![];
92 let mut visited = HashSet::default();
93
94 queue.push(self.root.clone());
95 visited.insert(self.root.key().clone());
96
97 match self.transpose {
98 Transposition::Outbound => {
99 match self.recurse_outbound(&mut edges, &mut visited, &mut queue) {
100 true => Some(Path::from_edge_tree(edges)),
101 false => None,
102 }
103 }
104 Transposition::Inbound => {
105 match self.recurse_inbound(&mut edges, &mut visited, &mut queue) {
106 true => Some(Path::from_edge_tree(edges)),
107 false => None,
108 }
109 }
110 }
111 }
112
113 fn recurse_outbound(
114 &mut self,
115 result: &mut Vec<Edge<K, N, E>>,
116 visited: &mut HashSet<K>,
117 queue: &mut Vec<Node<K, N, E>>,
118 ) -> bool {
119 if let Some(node) = queue.pop() {
120 for edge in node.iter_out() {
121 if self.method.exec(&edge) {
122 let v = edge.target().clone();
123 if !visited.contains(v.key()) {
124 visited.insert(v.key().clone());
125 result.push(edge);
126 if let Some(ref t) = self.target {
127 if v.key() == t {
128 return true;
129 }
130 }
131 queue.push(v.clone());
132 if self.recurse_outbound(result, visited, queue) {
133 return true;
134 }
135 }
136 }
137 }
138 }
139 false
140 }
141
142 fn recurse_inbound(
143 &mut self,
144 result: &mut Vec<Edge<K, N, E>>,
145 visited: &mut HashSet<K>,
146 queue: &mut Vec<Node<K, N, E>>,
147 ) -> bool {
148 if let Some(node) = queue.pop() {
149 for edge in node.iter_in() {
150 let edge = edge.reverse();
151 if self.method.exec(&edge) {
152 let v = edge.target().clone();
153 if !visited.contains(v.key()) {
154 visited.insert(v.key().clone());
155 result.push(edge);
156 if let Some(ref t) = self.target {
157 if v.key() == t {
158 return true;
159 }
160 }
161 queue.push(v.clone());
162 if self.recurse_inbound(result, visited, queue) {
163 return true;
164 }
165 }
166 }
167 }
168 }
169 false
170 }
171
172 fn recurse_outbound_find(
173 &mut self,
174 visited: &mut HashSet<K>,
175 queue: &mut Vec<Node<K, N, E>>,
176 ) -> Option<Node<K, N, E>> {
177 if let Some(node) = queue.pop() {
178 for edge in node.iter_out() {
179 if self.method.exec(&edge) {
180 let v = edge.target();
181 if !visited.contains(v.key()) {
182 visited.insert(v.key().clone());
183 if let Some(ref t) = self.target {
184 if v.key() == t {
185 return Some(v.clone());
186 }
187 }
188 queue.push(v.clone());
189 match self.recurse_outbound_find(visited, queue) {
190 Some(t) => return Some(t),
191 None => continue,
192 }
193 }
194 }
195 }
196 }
197 None
198 }
199
200 fn recurse_inbound_find(
201 &mut self,
202 visited: &mut HashSet<K>,
203 queue: &mut Vec<Node<K, N, E>>,
204 ) -> Option<Node<K, N, E>> {
205 if let Some(node) = queue.pop() {
206 for edge in node.iter_in() {
207 let edge = edge.reverse();
208 if self.method.exec(&edge) {
209 let v = edge.target();
210 if !visited.contains(v.key()) {
211 visited.insert(v.key().clone());
212 if let Some(ref t) = self.target {
213 if v.key() == t {
214 return Some(v.clone());
215 }
216 }
217 queue.push(v.clone());
218 match self.recurse_inbound_find(visited, queue) {
219 Some(t) => return Some(t),
220 None => continue,
221 }
222 }
223 }
224 }
225 }
226 None
227 }
228}