algorithms_edu/algo/graph/
eulerian_path.rs

1//! Implementation of finding an Eulerian Path on a graph. This implementation verifies that the
2//! input graph is fully connected and supports self loops and repeated edges between nodes.
3//!
4//! Time Complexity: $O(E)$
5//!
6//! # Resources
7//!
8//! - [W. Fiset's video 1](https://www.youtube.com/watch?v=xR4sGgwtR2I&list=PLDV1Zeh2NRsDGO4--qE8yH72HFL1Km93P&index=27)
9//! - [W. Fiset's video 2](https://www.youtube.com/watch?v=8MpoO2zA2l4&list=PLDV1Zeh2NRsDGO4--qE8yH72HFL1Km93P&index=28)
10
11use crate::algo::graph::UnweightedAdjacencyList;
12
13#[derive(Debug)]
14pub enum EulerianPathError {
15    DisconnectedGraph,
16    InvalidDegrees,
17}
18
19impl UnweightedAdjacencyList {
20    fn count_in_out_degrees(&self) -> [Vec<usize>; 2] {
21        let mut in_degrees = vec![0; self.node_count()];
22        let mut out_degrees = vec![0; self.node_count()];
23        for [from, to] in self.edges() {
24            out_degrees[from] += 1;
25            in_degrees[to] += 1;
26        }
27        [in_degrees, out_degrees]
28    }
29    /// Returns a list of `edge_count + 1` node ids that give the Eulerian path or
30    /// an `EulerianPathError` if no path exists or the graph is disconnected.
31    pub fn eulerian_path(&self) -> Result<Vec<usize>, EulerianPathError> {
32        let n = self.node_count();
33        let has_eulerian_path = |[in_degrees, out_degrees]: [&[usize]; 2]| {
34            let mut start = None;
35            let mut has_end = false;
36            let mut start_default = None;
37            for (node, (&i, &o)) in in_degrees.iter().zip(out_degrees.iter()).enumerate() {
38                if (i as isize - o as isize).abs() > 1 {
39                    return None;
40                }
41                if i.wrapping_sub(o) == 1 {
42                    if has_end {
43                        return None;
44                    } else {
45                        has_end = true;
46                    }
47                }
48                if o.wrapping_sub(i) == 1 {
49                    if start.is_some() {
50                        return None;
51                    } else {
52                        start = Some(node)
53                    }
54                }
55                if start_default.is_none() && o > 0 {
56                    start_default = Some(node);
57                }
58            }
59            if start.is_some() ^ has_end {
60                None
61            } else {
62                Some(start.unwrap_or_else(|| start_default.unwrap()))
63            }
64        };
65        let [i, mut o] = self.count_in_out_degrees();
66        fn _dfs(
67            g: &UnweightedAdjacencyList,
68            out: &mut Vec<usize>,
69            path: &mut Vec<usize>,
70            at: usize,
71        ) {
72            // while the current node still has outgoing edge(s)
73            while out[at] > 0 {
74                out[at] -= 1;
75                // select the next unvisited outgoing edge
76                let next = g[at][out[at]];
77                _dfs(g, out, path, next);
78            }
79            // add current node to solution.
80            path.push(at);
81        };
82        has_eulerian_path([&i, &o]).map_or(Err(EulerianPathError::InvalidDegrees), |start| {
83            let mut path = Vec::with_capacity(n);
84            _dfs(self, &mut o, &mut path, start);
85            path.reverse();
86            // Make sure all edges of the graph were traversed. It could be the
87            // case that the graph is disconnected.
88            if path.len() == self.edge_count() + 1 {
89                Ok(path)
90            } else {
91                // disconnected graph
92                Err(EulerianPathError::DisconnectedGraph)
93            }
94        })
95    }
96}
97#[cfg(test)]
98mod tests {
99
100    use super::*;
101    #[test]
102    fn test_eulerian_path() {
103        let g = UnweightedAdjacencyList::new_directed(
104            7,
105            &[
106                [1, 2],
107                [1, 3],
108                [2, 2],
109                [2, 4],
110                [2, 4],
111                [3, 1],
112                [3, 2],
113                [3, 5],
114                [4, 3],
115                [4, 6],
116                [5, 6],
117                [6, 3],
118            ],
119        );
120        let path = g.eulerian_path().unwrap();
121        assert_eq!(&path, &[1, 3, 5, 6, 3, 2, 4, 3, 1, 2, 2, 4, 6]);
122
123        let g = UnweightedAdjacencyList::new_directed(
124            5,
125            &[[0, 1], [1, 2], [1, 4], [1, 3], [2, 1], [4, 1]],
126        );
127        let path = g.eulerian_path().unwrap();
128        assert_eq!(&path, &[0, 1, 4, 1, 2, 1, 3]);
129    }
130    #[test]
131    fn test_eulerian_path_invalid1() {
132        let g = UnweightedAdjacencyList::new_directed(2, &[[0, 1], [0, 1]]);
133        assert!(matches!(
134            g.eulerian_path(),
135            Err(EulerianPathError::InvalidDegrees)
136        ));
137    }
138    #[test]
139    fn test_eulerian_path_invalid2() {
140        let g = UnweightedAdjacencyList::new_directed(3, &[[0, 1], [1, 0], [1, 2], [2, 0], [2, 0]]);
141        assert!(matches!(
142            g.eulerian_path(),
143            Err(EulerianPathError::InvalidDegrees)
144        ));
145    }
146    #[test]
147    fn test_eulerian_path_invalid3() {
148        let g = UnweightedAdjacencyList::new_directed(
149            4,
150            &[
151                [0, 2],
152                [2, 1],
153                [2, 3],
154                [3, 0],
155                [3, 1],
156                [1, 3],
157                [1, 0],
158                [1, 2],
159                [0, 3],
160                [2, 0],
161            ],
162        );
163        assert!(matches!(
164            g.eulerian_path(),
165            Err(EulerianPathError::InvalidDegrees)
166        ));
167    }
168
169    #[test]
170    fn test_eulerian_path_invalid4() {
171        let g = UnweightedAdjacencyList::new_directed(
172            8,
173            &[
174                [0, 1],
175                [1, 2],
176                [2, 3],
177                [3, 1],
178                [4, 5],
179                [5, 6],
180                [6, 7],
181                [7, 4],
182            ],
183        );
184        assert!(matches!(
185            g.eulerian_path(),
186            Err(EulerianPathError::DisconnectedGraph)
187        ));
188    }
189}
algorithms_edu/algo/graph/eulerian_path.rs

algorithms_edu/algo/graph/
eulerian_path.rs
