unlab_gpu/
dfs.rs

1//
2// Copyright (c) 2025-2026 Łukasz Szpakowski
3//
4// This Source Code Form is subject to the terms of the Mozilla Public
5// License, v. 2.0. If a copy of the MPL was not distributed with this
6// file, You can obtain one at https://mozilla.org/MPL/2.0/.
7//
8//! A module of DFS algorithm.
9use std::collections::HashSet;
10use std::hash::Hash;
11
12/// An enumeration of DFS result.
13#[derive(Clone, Debug)]
14pub enum DfsResult<T>
15{
16    /// A success
17    Success,
18    /// A cycle.
19    Cycle(Vec<T>),
20}
21
22fn find_cycle<T: Clone + Eq + Hash>(u: &T, vs: &[T], stack: &[(T, Vec<T>)], processeds: &HashSet<T>) -> DfsResult<T>
23{
24    match vs.iter().find(|v| processeds.contains(v)) {
25        Some(v) => {
26            let mut cycle: Vec<T> = stack.iter().map(|p| p.0.clone()).collect();
27            cycle.push(u.clone());
28            cycle.push(v.clone());
29            DfsResult::Cycle(cycle)
30        },
31        None => DfsResult::Success,
32    }
33}
34
35/// This function is an implementation of DFS algorithm with a cycle detection.
36///
37/// A graph is depth-first searched by this function. This function returns a path with the cycle
38/// if this function detects a cycle in the graph, otherwise returns a success.
39pub fn dfs<T: Clone + Eq + Hash, U, F, G, E>(start: &T, visiteds: &mut HashSet<T>, data: &mut U, mut f: F, mut g: G) -> Result<DfsResult<T>, E>
40    where F: FnMut(&T, &mut U) -> Result<Vec<T>, E>,
41          G: FnMut(&T, &mut U) -> Result<(), E>
42{
43    let mut stack: Vec<(T, Vec<T>)> = Vec::new();
44    let mut processeds: HashSet<T> = HashSet::new();
45    processeds.insert(start.clone());
46    let mut us = f(start, data)?;
47    match find_cycle(start, us.as_slice(), stack.as_slice(), &processeds) {
48        DfsResult::Success => (),
49        res @ DfsResult::Cycle(_) => return Ok(res),
50    }
51    us.reverse();
52    stack.push((start.clone(), us));
53    visiteds.insert(start.clone());
54    loop {
55        match stack.last_mut() {
56            Some((u, vs)) => {
57                let v = loop {
58                    match vs.pop() {
59                        Some(w) if !visiteds.contains(&w) => break Some(w),
60                        Some(_) => (),
61                        None => break None,
62                    }
63                };
64                match v {
65                    Some(v) => {
66                        processeds.insert(v.clone());
67                        let mut ws = f(&v, data)?;
68                        match find_cycle(&v, ws.as_slice(), stack.as_slice(), &processeds) {
69                            DfsResult::Success => (),
70                            res @ DfsResult::Cycle(_) => return Ok(res),
71                        }
72                        ws.reverse();
73                        stack.push((v.clone(), ws));
74                        visiteds.insert(v);
75                    },
76                    None => {
77                        g(u, data)?;
78                        processeds.remove(u);
79                        stack.pop();
80                    },
81                }
82            },
83            None => break,
84        }
85    }
86    Ok(DfsResult::Success)
87}
88
89#[cfg(test)]
90mod tests;
unlab_gpu/dfs.rs

unlab_gpu/
dfs.rs
