traitgraph_algo/
eulerian.rs

1use traitgraph::interface::StaticGraph;
2
3/// Returns true if the graph contains a Eulerian cycle.
4pub fn decomposes_into_eulerian_cycles<Graph: StaticGraph>(graph: &Graph) -> bool {
5    for node_index in graph.node_indices() {
6        if graph.in_degree(node_index) != graph.out_degree(node_index) {
7            return false;
8        }
9    }
10
11    true
12}
13
14/// Compute a vector of nodes that has indegree != outdegree.
15pub fn find_non_eulerian_nodes<Graph: StaticGraph>(graph: &Graph) -> Vec<Graph::NodeIndex> {
16    let mut result = Vec::new();
17    for node_index in graph.node_indices() {
18        if graph.in_degree(node_index) != graph.out_degree(node_index) {
19            result.push(node_index);
20        }
21    }
22    result
23}
24
25/// Compute a vector of tuples of nodes and outdegree - indegree that has indegree != outdegree.
26pub fn find_non_eulerian_nodes_with_differences<Graph: StaticGraph>(
27    graph: &Graph,
28) -> Vec<(Graph::NodeIndex, isize)> {
29    let mut node_indices_and_differences = Vec::new();
30    for node_index in graph.node_indices() {
31        let difference =
32            graph.out_degree(node_index) as isize - graph.in_degree(node_index) as isize;
33        if difference != 0 {
34            node_indices_and_differences.push((node_index, difference));
35        }
36    }
37    node_indices_and_differences
38}