1use alloc::{collections::VecDeque, vec::Vec};
2
3use super::{
4 GraphRef, IntoNeighbors, IntoNeighborsDirected, IntoNodeIdentifiers, Reversed, VisitMap,
5 Visitable,
6};
7use crate::Incoming;
8
9#[derive(Clone, Debug)]
40pub struct Dfs<N, VM> {
41 pub stack: Vec<N>,
43 pub discovered: VM,
45}
46
47impl<N, VM> Default for Dfs<N, VM>
48where
49 VM: Default,
50{
51 fn default() -> Self {
52 Dfs {
53 stack: Vec::new(),
54 discovered: VM::default(),
55 }
56 }
57}
58
59impl<N, VM> Dfs<N, VM>
60where
61 N: Copy + PartialEq,
62 VM: VisitMap<N>,
63{
64 pub fn new<G>(graph: G, start: N) -> Self
67 where
68 G: GraphRef + Visitable<NodeId = N, Map = VM>,
69 {
70 let mut dfs = Dfs::empty(graph);
71 dfs.move_to(start);
72 dfs
73 }
74
75 pub fn from_parts(stack: Vec<N>, discovered: VM) -> Self {
77 Dfs { stack, discovered }
78 }
79
80 pub fn reset<G>(&mut self, graph: G)
82 where
83 G: GraphRef + Visitable<NodeId = N, Map = VM>,
84 {
85 graph.reset_map(&mut self.discovered);
86 self.stack.clear();
87 }
88
89 pub fn empty<G>(graph: G) -> Self
91 where
92 G: GraphRef + Visitable<NodeId = N, Map = VM>,
93 {
94 Dfs {
95 stack: Vec::new(),
96 discovered: graph.visit_map(),
97 }
98 }
99
100 pub fn move_to(&mut self, start: N) {
103 self.stack.clear();
104 self.stack.push(start);
105 }
106
107 pub fn next<G>(&mut self, graph: G) -> Option<N>
109 where
110 G: IntoNeighbors<NodeId = N>,
111 {
112 while let Some(node) = self.stack.pop() {
113 if self.discovered.visit(node) {
114 for succ in graph.neighbors(node) {
115 if !self.discovered.is_visited(&succ) {
116 self.stack.push(succ);
117 }
118 }
119 return Some(node);
120 }
121 }
122 None
123 }
124}
125
126#[derive(Clone, Debug)]
134pub struct DfsPostOrder<N, VM> {
135 pub stack: Vec<N>,
137 pub discovered: VM,
139 pub finished: VM,
141}
142
143impl<N, VM> Default for DfsPostOrder<N, VM>
144where
145 VM: Default,
146{
147 fn default() -> Self {
148 DfsPostOrder {
149 stack: Vec::new(),
150 discovered: VM::default(),
151 finished: VM::default(),
152 }
153 }
154}
155
156impl<N, VM> DfsPostOrder<N, VM>
157where
158 N: Copy + PartialEq,
159 VM: VisitMap<N>,
160{
161 pub fn new<G>(graph: G, start: N) -> Self
164 where
165 G: GraphRef + Visitable<NodeId = N, Map = VM>,
166 {
167 let mut dfs = Self::empty(graph);
168 dfs.move_to(start);
169 dfs
170 }
171
172 pub fn empty<G>(graph: G) -> Self
174 where
175 G: GraphRef + Visitable<NodeId = N, Map = VM>,
176 {
177 DfsPostOrder {
178 stack: Vec::new(),
179 discovered: graph.visit_map(),
180 finished: graph.visit_map(),
181 }
182 }
183
184 pub fn reset<G>(&mut self, graph: G)
186 where
187 G: GraphRef + Visitable<NodeId = N, Map = VM>,
188 {
189 graph.reset_map(&mut self.discovered);
190 graph.reset_map(&mut self.finished);
191 self.stack.clear();
192 }
193
194 pub fn move_to(&mut self, start: N) {
197 self.stack.clear();
198 self.stack.push(start);
199 }
200
201 pub fn next<G>(&mut self, graph: G) -> Option<N>
203 where
204 G: IntoNeighbors<NodeId = N>,
205 {
206 while let Some(&nx) = self.stack.last() {
207 if self.discovered.visit(nx) {
208 for succ in graph.neighbors(nx) {
210 if !self.discovered.is_visited(&succ) {
211 self.stack.push(succ);
212 }
213 }
214 } else {
215 self.stack.pop();
216 if self.finished.visit(nx) {
217 return Some(nx);
219 }
220 }
221 }
222 None
223 }
224}
225
226#[derive(Clone)]
256pub struct Bfs<N, VM> {
257 pub stack: VecDeque<N>,
259 pub discovered: VM,
261}
262
263impl<N, VM> Default for Bfs<N, VM>
264where
265 VM: Default,
266{
267 fn default() -> Self {
268 Bfs {
269 stack: VecDeque::new(),
270 discovered: VM::default(),
271 }
272 }
273}
274
275impl<N, VM> Bfs<N, VM>
276where
277 N: Copy + PartialEq,
278 VM: VisitMap<N>,
279{
280 pub fn new<G>(graph: G, start: N) -> Self
283 where
284 G: GraphRef + Visitable<NodeId = N, Map = VM>,
285 {
286 let mut discovered = graph.visit_map();
287 discovered.visit(start);
288 let mut stack = VecDeque::new();
289 stack.push_front(start);
290 Bfs { stack, discovered }
291 }
292
293 pub fn next<G>(&mut self, graph: G) -> Option<N>
295 where
296 G: IntoNeighbors<NodeId = N>,
297 {
298 if let Some(node) = self.stack.pop_front() {
299 for succ in graph.neighbors(node) {
300 if self.discovered.visit(succ) {
301 self.stack.push_back(succ);
302 }
303 }
304
305 return Some(node);
306 }
307 None
308 }
309}
310
311#[derive(Clone)]
317pub struct Topo<N, VM> {
318 tovisit: Vec<N>,
319 ordered: VM,
320}
321
322impl<N, VM> Default for Topo<N, VM>
323where
324 VM: Default,
325{
326 fn default() -> Self {
327 Topo {
328 tovisit: Vec::new(),
329 ordered: VM::default(),
330 }
331 }
332}
333
334impl<N, VM> Topo<N, VM>
335where
336 N: Copy + PartialEq,
337 VM: VisitMap<N>,
338{
339 pub fn new<G>(graph: G) -> Self
342 where
343 G: IntoNodeIdentifiers + IntoNeighborsDirected + Visitable<NodeId = N, Map = VM>,
344 {
345 let mut topo = Self::empty(graph);
346 topo.extend_with_initials(graph);
347 topo
348 }
349
350 pub fn with_initials<G, I>(graph: G, initials: I) -> Self
354 where
355 G: IntoNeighborsDirected + Visitable<NodeId = N, Map = VM>,
356 I: IntoIterator<Item = N>,
357 {
358 Topo {
359 tovisit: initials
360 .into_iter()
361 .filter(|&n| graph.neighbors_directed(n, Incoming).next().is_none())
362 .collect(),
363 ordered: graph.visit_map(),
364 }
365 }
366
367 fn extend_with_initials<G>(&mut self, g: G)
368 where
369 G: IntoNodeIdentifiers + IntoNeighborsDirected<NodeId = N>,
370 {
371 self.tovisit.extend(
373 g.node_identifiers()
374 .filter(move |&a| g.neighbors_directed(a, Incoming).next().is_none()),
375 );
376 }
377
378 fn empty<G>(graph: G) -> Self
382 where
383 G: GraphRef + Visitable<NodeId = N, Map = VM>,
384 {
385 Topo {
386 ordered: graph.visit_map(),
387 tovisit: Vec::new(),
388 }
389 }
390
391 pub fn reset<G>(&mut self, graph: G)
393 where
394 G: IntoNodeIdentifiers + IntoNeighborsDirected + Visitable<NodeId = N, Map = VM>,
395 {
396 graph.reset_map(&mut self.ordered);
397 self.tovisit.clear();
398 self.extend_with_initials(graph);
399 }
400
401 pub fn next<G>(&mut self, g: G) -> Option<N>
407 where
408 G: IntoNeighborsDirected + Visitable<NodeId = N, Map = VM>,
409 {
410 while let Some(nix) = self.tovisit.pop() {
412 if self.ordered.is_visited(&nix) {
413 continue;
414 }
415 self.ordered.visit(nix);
416 for neigh in g.neighbors(nix) {
417 if Reversed(g)
420 .neighbors(neigh)
421 .all(|b| self.ordered.is_visited(&b))
422 {
423 self.tovisit.push(neigh);
424 }
425 }
426 return Some(nix);
427 }
428 None
429 }
430}
431
432pub trait Walker<Context> {
438 type Item;
439 fn walk_next(&mut self, context: Context) -> Option<Self::Item>;
441
442 fn iter(self, context: Context) -> WalkerIter<Self, Context>
444 where
445 Self: Sized,
446 Context: Clone,
447 {
448 WalkerIter {
449 walker: self,
450 context,
451 }
452 }
453}
454
455#[derive(Clone, Debug)]
457pub struct WalkerIter<W, C> {
458 walker: W,
459 context: C,
460}
461
462impl<W, C> WalkerIter<W, C>
463where
464 W: Walker<C>,
465 C: Clone,
466{
467 pub fn context(&self) -> C {
468 self.context.clone()
469 }
470
471 pub fn inner_ref(&self) -> &W {
472 &self.walker
473 }
474
475 pub fn inner_mut(&mut self) -> &mut W {
476 &mut self.walker
477 }
478}
479
480impl<W, C> Iterator for WalkerIter<W, C>
481where
482 W: Walker<C>,
483 C: Clone,
484{
485 type Item = W::Item;
486 fn next(&mut self) -> Option<Self::Item> {
487 self.walker.walk_next(self.context.clone())
488 }
489}
490
491impl<C, W: ?Sized> Walker<C> for &mut W
492where
493 W: Walker<C>,
494{
495 type Item = W::Item;
496 fn walk_next(&mut self, context: C) -> Option<Self::Item> {
497 (**self).walk_next(context)
498 }
499}
500
501impl<G> Walker<G> for Dfs<G::NodeId, G::Map>
502where
503 G: IntoNeighbors + Visitable,
504{
505 type Item = G::NodeId;
506 fn walk_next(&mut self, context: G) -> Option<Self::Item> {
507 self.next(context)
508 }
509}
510
511impl<G> Walker<G> for DfsPostOrder<G::NodeId, G::Map>
512where
513 G: IntoNeighbors + Visitable,
514{
515 type Item = G::NodeId;
516 fn walk_next(&mut self, context: G) -> Option<Self::Item> {
517 self.next(context)
518 }
519}
520
521impl<G> Walker<G> for Bfs<G::NodeId, G::Map>
522where
523 G: IntoNeighbors + Visitable,
524{
525 type Item = G::NodeId;
526 fn walk_next(&mut self, context: G) -> Option<Self::Item> {
527 self.next(context)
528 }
529}
530
531impl<G> Walker<G> for Topo<G::NodeId, G::Map>
532where
533 G: IntoNeighborsDirected + Visitable,
534{
535 type Item = G::NodeId;
536 fn walk_next(&mut self, context: G) -> Option<Self::Item> {
537 self.next(context)
538 }
539}