//! This module provides functionality to find an Eulerian path in a directed graph.
//! An Eulerian path visits every edge exactly once. The algorithm checks if an Eulerian
//! path exists and, if so, constructs and returns the path.
use std::collections::LinkedList;
/// Finds an Eulerian path in a directed graph.
///
/// # Arguments
///
/// * `node_count` - The number of nodes in the graph.
/// * `edge_list` - A vector of tuples representing directed edges, where each tuple is of the form `(start, end)`.
///
/// # Returns
///
/// An `Option<Vec<usize>>` containing the Eulerian path if it exists; otherwise, `None`.
pub fn find_eulerian_path(node_count: usize, edge_list: Vec<(usize, usize)>) -> Option<Vec<usize>> {
let mut adjacency_list = vec![Vec::new(); node_count];
for (start, end) in edge_list {
adjacency_list[start].push(end);
}
let mut eulerian_solver = EulerianPathSolver::new(adjacency_list);
eulerian_solver.find_path()
}
/// Struct to represent the solver for finding an Eulerian path in a directed graph.
pub struct EulerianPathSolver {
node_count: usize,
edge_count: usize,
in_degrees: Vec<usize>,
out_degrees: Vec<usize>,
eulerian_path: LinkedList<usize>,
adjacency_list: Vec<Vec<usize>>,
}
impl EulerianPathSolver {
/// Creates a new instance of `EulerianPathSolver`.
///
/// # Arguments
///
/// * `adjacency_list` - The graph represented as an adjacency list.
///
/// # Returns
///
/// A new instance of `EulerianPathSolver`.
pub fn new(adjacency_list: Vec<Vec<usize>>) -> Self {
Self {
node_count: adjacency_list.len(),
edge_count: 0,
in_degrees: vec![0; adjacency_list.len()],
out_degrees: vec![0; adjacency_list.len()],
eulerian_path: LinkedList::new(),
adjacency_list,
}
}
/// Find the Eulerian path if it exists.
///
/// # Returns
///
/// An `Option<Vec<usize>>` containing the Eulerian path if found; otherwise, `None`.
///
/// If multiple Eulerian paths exist, the one found will be returned, but it may not be unique.
fn find_path(&mut self) -> Option<Vec<usize>> {
self.initialize_degrees();
if !self.has_eulerian_path() {
return None;
}
let start_node = self.get_start_node();
self.depth_first_search(start_node);
if self.eulerian_path.len() != self.edge_count + 1 {
return None;
}
let mut path = Vec::with_capacity(self.edge_count + 1);
while let Some(node) = self.eulerian_path.pop_front() {
path.push(node);
}
Some(path)
}
/// Initializes in-degrees and out-degrees for each node and counts total edges.
fn initialize_degrees(&mut self) {
for (start_node, neighbors) in self.adjacency_list.iter().enumerate() {
for &end_node in neighbors {
self.in_degrees[end_node] += 1;
self.out_degrees[start_node] += 1;
self.edge_count += 1;
}
}
}
/// Checks if an Eulerian path exists in the graph.
///
/// # Returns
///
/// `true` if an Eulerian path exists; otherwise, `false`.
fn has_eulerian_path(&self) -> bool {
if self.edge_count == 0 {
return false;
}
let (mut start_nodes, mut end_nodes) = (0, 0);
for i in 0..self.node_count {
let (in_degree, out_degree) =
(self.in_degrees[i] as isize, self.out_degrees[i] as isize);
match out_degree - in_degree {
1 => start_nodes += 1,
-1 => end_nodes += 1,
degree_diff if degree_diff.abs() > 1 => return false,
_ => (),
}
}
(start_nodes == 0 && end_nodes == 0) || (start_nodes == 1 && end_nodes == 1)
}
/// Finds the starting node for the Eulerian path.
///
/// # Returns
///
/// The index of the starting node.
fn get_start_node(&self) -> usize {
for i in 0..self.node_count {
if self.out_degrees[i] > self.in_degrees[i] {
return i;
}
}
(0..self.node_count)
.find(|&i| self.out_degrees[i] > 0)
.unwrap_or(0)
}
/// Performs depth-first search to construct the Eulerian path.
///
/// # Arguments
///
/// * `curr_node` - The current node being visited in the DFS traversal.
fn depth_first_search(&mut self, curr_node: usize) {
while self.out_degrees[curr_node] > 0 {
let next_node = self.adjacency_list[curr_node][self.out_degrees[curr_node] - 1];
self.out_degrees[curr_node] -= 1;
self.depth_first_search(next_node);
}
self.eulerian_path.push_front(curr_node);
}
}
#[cfg(test)]
mod tests {
use super::*;
macro_rules! test_cases {
($($name:ident: $test_case:expr,)*) => {
$(
#[test]
fn $name() {
let (n, edges, expected) = $test_case;
assert_eq!(find_eulerian_path(n, edges), expected);
}
)*
}
}
test_cases! {
test_eulerian_cycle: (
7,
vec![
(1, 2),
(1, 3),
(2, 2),
(2, 4),
(2, 4),
(3, 1),
(3, 2),
(3, 5),
(4, 3),
(4, 6),
(5, 6),
(6, 3)
],
Some(vec![1, 3, 5, 6, 3, 2, 4, 3, 1, 2, 2, 4, 6])
),
test_simple_path: (
5,
vec![
(0, 1),
(1, 2),
(1, 4),
(1, 3),
(2, 1),
(4, 1)
],
Some(vec![0, 1, 4, 1, 2, 1, 3])
),
test_disconnected_graph: (
4,
vec![
(0, 1),
(2, 3)
],
None::<Vec<usize>>
),
test_single_cycle: (
4,
vec![
(0, 1),
(1, 2),
(2, 3),
(3, 0)
],
Some(vec![0, 1, 2, 3, 0])
),
test_empty_graph: (
3,
vec![],
None::<Vec<usize>>
),
test_unbalanced_path: (
3,
vec![
(0, 1),
(1, 2),
(2, 0),
(0, 2)
],
Some(vec![0, 2, 0, 1, 2])
),
test_no_eulerian_path: (
3,
vec![
(0, 1),
(0, 2)
],
None::<Vec<usize>>
),
test_complex_eulerian_path: (
6,
vec![
(0, 1),
(1, 2),
(2, 3),
(3, 4),
(4, 0),
(0, 5),
(5, 0),
(2, 0)
],
Some(vec![2, 0, 5, 0, 1, 2, 3, 4, 0])
),
test_single_node_self_loop: (
1,
vec![(0, 0)],
Some(vec![0, 0])
),
test_complete_graph: (
3,
vec![
(0, 1),
(0, 2),
(1, 0),
(1, 2),
(2, 0),
(2, 1)
],
Some(vec![0, 2, 1, 2, 0, 1, 0])
),
test_multiple_disconnected_components: (
6,
vec![
(0, 1),
(2, 3),
(4, 5)
],
None::<Vec<usize>>
),
test_unbalanced_graph_with_path: (
4,
vec![
(0, 1),
(1, 2),
(2, 3),
(3, 1)
],
Some(vec![0, 1, 2, 3, 1])
),
test_node_with_no_edges: (
4,
vec![
(0, 1),
(1, 2)
],
Some(vec![0, 1, 2])
),
test_multiple_edges_between_same_nodes: (
3,
vec![
(0, 1),
(1, 2),
(1, 2),
(2, 0)
],
Some(vec![1, 2, 0, 1, 2])
),
test_larger_graph_with_eulerian_path: (
10,
vec![
(0, 1),
(1, 2),
(2, 3),
(3, 4),
(4, 5),
(5, 6),
(6, 7),
(7, 8),
(8, 9),
(9, 0),
(1, 6),
(6, 3),
(3, 8)
],
Some(vec![1, 6, 3, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8])
),
test_no_edges_multiple_nodes: (
5,
vec![],
None::<Vec<usize>>
),
test_multiple_start_and_end_nodes: (
4,
vec![
(0, 1),
(1, 2),
(2, 0),
(0, 2),
(1, 3)
],
None::<Vec<usize>>
),
test_single_edge: (
2,
vec![(0, 1)],
Some(vec![0, 1])
),
test_multiple_eulerian_paths: (
4,
vec![
(0, 1),
(1, 2),
(2, 0),
(0, 3),
(3, 0)
],
Some(vec![0, 3, 0, 1, 2, 0])
),
test_dag_path: (
4,
vec![
(0, 1),
(1, 2),
(2, 3)
],
Some(vec![0, 1, 2, 3])
),
test_parallel_edges_case: (
2,
vec![
(0, 1),
(0, 1),
(1, 0)
],
Some(vec![0, 1, 0, 1])
),
}
}