graphannis_core/
dfs.rs

1use crate::{errors::Result, graph::storage::EdgeContainer, types::NodeID};
2use rustc_hash::FxHashSet;
3
4pub struct CycleSafeDFS<'a> {
5    min_distance: usize,
6    max_distance: usize,
7    inverse: bool,
8    container: &'a dyn EdgeContainer,
9
10    stack: Vec<(NodeID, usize)>,
11    path: Vec<NodeID>,
12    nodes_in_path: FxHashSet<NodeID>,
13    last_distance: usize,
14    cycle_detected: bool,
15}
16
17pub struct DFSStep {
18    pub node: NodeID,
19    pub distance: usize,
20}
21
22impl<'a> CycleSafeDFS<'a> {
23    pub fn new(
24        container: &'a dyn EdgeContainer,
25        node: NodeID,
26        min_distance: usize,
27        max_distance: usize,
28    ) -> CycleSafeDFS<'a> {
29        CycleSafeDFS {
30            min_distance,
31            max_distance,
32            inverse: false,
33            container,
34            stack: vec![(node, 0)],
35            path: Vec::default(),
36            nodes_in_path: FxHashSet::default(),
37            last_distance: 0,
38            cycle_detected: false,
39        }
40    }
41
42    pub fn new_inverse(
43        container: &'a dyn EdgeContainer,
44        node: NodeID,
45        min_distance: usize,
46        max_distance: usize,
47    ) -> CycleSafeDFS<'a> {
48        CycleSafeDFS {
49            min_distance,
50            max_distance,
51            inverse: true,
52            container,
53            stack: vec![(node, 0)],
54            path: Vec::default(),
55            nodes_in_path: FxHashSet::default(),
56            last_distance: 0,
57            cycle_detected: true,
58        }
59    }
60
61    pub fn is_cyclic(&self) -> bool {
62        self.cycle_detected
63    }
64
65    fn enter_node(&mut self, entry: (NodeID, usize)) -> Result<bool> {
66        let node = entry.0;
67        let dist = entry.1;
68
69        trace!("enter node {}", node);
70        // test if subgraph was completed
71        if self.last_distance >= dist {
72            // remove all entries below the parent node from the path
73            for i in dist..self.path.len() {
74                trace!("truncating {} from path", &self.path[i]);
75                self.nodes_in_path.remove(&self.path[i]);
76            }
77            self.path.truncate(dist);
78        }
79        // test for cycle
80        if self.nodes_in_path.contains(&node) {
81            trace!("cycle detected for node {} with distance {}", &node, dist);
82            self.last_distance = dist;
83            self.cycle_detected = true;
84            trace!("removing from stack because of cycle");
85            self.stack.pop();
86            Ok(false)
87        } else {
88            self.path.push(node);
89            self.nodes_in_path.insert(node);
90            self.last_distance = dist;
91            trace!("removing from stack");
92            self.stack.pop();
93
94            // check if distance is in valid range
95            let found = dist >= self.min_distance && dist <= self.max_distance;
96
97            if dist < self.max_distance {
98                if self.inverse {
99                    // add all parent nodes to the stack
100                    for o in self.container.get_ingoing_edges(node) {
101                        let o = o?;
102                        self.stack.push((o, dist + 1));
103                        trace!("adding {} to stack with new size {}", o, self.stack.len());
104                    }
105                } else {
106                    // add all child nodes to the stack
107                    for o in self.container.get_outgoing_edges(node) {
108                        let o = o?;
109                        self.stack.push((o, dist + 1));
110                        trace!("adding {} to stack with new size {}", o, self.stack.len());
111                    }
112                }
113            }
114            trace!(
115                "enter_node finished with result {} for node {}",
116                found,
117                node
118            );
119            Ok(found)
120        }
121    }
122}
123
124impl Iterator for CycleSafeDFS<'_> {
125    type Item = Result<DFSStep>;
126
127    fn next(&mut self) -> Option<Self::Item> {
128        let mut result: Option<Result<DFSStep>> = None;
129        while result.is_none() && !self.stack.is_empty() {
130            if let Some(top) = self.stack.last().copied() {
131                match self.enter_node(top) {
132                    Ok(entered) => {
133                        if entered {
134                            result = Some(Ok(DFSStep {
135                                node: top.0,
136                                distance: top.1,
137                            }));
138                        }
139                    }
140                    Err(e) => return Some(Err(e)),
141                }
142            }
143        }
144
145        result
146    }
147}
graphannis_core/dfs.rs

graphannis_core/
dfs.rs
