1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147

use crate::{errors::Result, graph::storage::EdgeContainer, types::NodeID};
use rustc_hash::FxHashSet;

pub struct CycleSafeDFS<'a> {
    min_distance: usize,
    max_distance: usize,
    inverse: bool,
    container: &'a dyn EdgeContainer,

    stack: Vec<(NodeID, usize)>,
    path: Vec<NodeID>,
    nodes_in_path: FxHashSet<NodeID>,
    last_distance: usize,
    cycle_detected: bool,
}

pub struct DFSStep {
    pub node: NodeID,
    pub distance: usize,
}

impl<'a> CycleSafeDFS<'a> {
    pub fn new(
        container: &'a dyn EdgeContainer,
        node: NodeID,
        min_distance: usize,
        max_distance: usize,
    ) -> CycleSafeDFS<'a> {
        CycleSafeDFS {
            min_distance,
            max_distance,
            inverse: false,
            container,
            stack: vec![(node, 0)],
            path: Vec::default(),
            nodes_in_path: FxHashSet::default(),
            last_distance: 0,
            cycle_detected: false,
        }
    }

    pub fn new_inverse(
        container: &'a dyn EdgeContainer,
        node: NodeID,
        min_distance: usize,
        max_distance: usize,
    ) -> CycleSafeDFS<'a> {
        CycleSafeDFS {
            min_distance,
            max_distance,
            inverse: true,
            container,
            stack: vec![(node, 0)],
            path: Vec::default(),
            nodes_in_path: FxHashSet::default(),
            last_distance: 0,
            cycle_detected: true,
        }
    }

    pub fn is_cyclic(&self) -> bool {
        self.cycle_detected
    }

    fn enter_node(&mut self, entry: (NodeID, usize)) -> Result<bool> {
        let node = entry.0;
        let dist = entry.1;

        trace!("enter node {}", node);
        // test if subgraph was completed
        if self.last_distance >= dist {
            // remove all entries below the parent node from the path
            for i in dist..self.path.len() {
                trace!("truncating {} from path", &self.path[i]);
                self.nodes_in_path.remove(&self.path[i]);
            }
            self.path.truncate(dist);
        }
        // test for cycle
        if self.nodes_in_path.contains(&node) {
            trace!("cycle detected for node {} with distance {}", &node, dist);
            self.last_distance = dist;
            self.cycle_detected = true;
            trace!("removing from stack because of cycle");
            self.stack.pop();
            Ok(false)
        } else {
            self.path.push(node);
            self.nodes_in_path.insert(node);
            self.last_distance = dist;
            trace!("removing from stack");
            self.stack.pop();

            // check if distance is in valid range
            let found = dist >= self.min_distance && dist <= self.max_distance;

            if dist < self.max_distance {
                if self.inverse {
                    // add all parent nodes to the stack
                    for o in self.container.get_ingoing_edges(node) {
                        let o = o?;
                        self.stack.push((o, dist + 1));
                        trace!("adding {} to stack with new size {}", o, self.stack.len());
                    }
                } else {
                    // add all child nodes to the stack
                    for o in self.container.get_outgoing_edges(node) {
                        let o = o?;
                        self.stack.push((o, dist + 1));
                        trace!("adding {} to stack with new size {}", o, self.stack.len());
                    }
                }
            }
            trace!(
                "enter_node finished with result {} for node {}",
                found,
                node
            );
            Ok(found)
        }
    }
}

impl<'a> Iterator for CycleSafeDFS<'a> {
    type Item = Result<DFSStep>;

    fn next(&mut self) -> Option<Self::Item> {
        let mut result: Option<Result<DFSStep>> = None;
        while result.is_none() && !self.stack.is_empty() {
            if let Some(top) = self.stack.last().copied() {
                match self.enter_node(top) {
                    Ok(entered) => {
                        if entered {
                            result = Some(Ok(DFSStep {
                                node: top.0,
                                distance: top.1,
                            }));
                        }
                    }
                    Err(e) => return Some(Err(e)),
                }
            }
        }

        result
    }
}