routee_compass_core/algorithm/component/
scc.rs

1use crate::model::network::{Graph, NetworkError, VertexId};
2use std::collections::HashSet;
3
4/// Conducts a depth-first search (DFS) on a directed graph.
5///
6/// This function takes a directed graph, a vertex ID, a mutable HashSet to keep track of visited vertices,
7/// and a mutable Vec as a container to store the order in which vertices are visited.
8/// The function returns an empty Result on successful completion, and a GraphError if something went wrong.
9///
10/// # Arguments
11///
12/// * `graph` - A directed graph to perform DFS on.
13/// * `vertex` - A VertexId to start the DFS from.
14/// * `visited` - A mutable reference to a HashSet storing visited VertexIds.
15/// * `stack` - A mutable reference to a stack storing VertexIds in the order of DFS traversal.
16///
17/// # Errors
18///
19/// Returns an error if the `graph` has an issue like a non-existing vertex.
20///
21pub fn depth_first_search(
22    graph: &Graph,
23    vertex: &VertexId,
24    visited: &mut HashSet<VertexId>,
25    stack: &mut Vec<VertexId>,
26) -> Result<(), NetworkError> {
27    if visited.contains(vertex) {
28        return Ok(());
29    }
30
31    visited.insert(*vertex);
32
33    let edges = graph.out_edges(vertex);
34    for (edge_list_id, edge_id) in edges {
35        let dst = graph.dst_vertex_id(&edge_list_id, &edge_id)?;
36        depth_first_search(graph, &dst, visited, stack)?;
37    }
38
39    stack.push(*vertex);
40
41    Ok(())
42}
43
44/// Conducts a reverse depth-first search (DFS) on a directed graph.
45///
46/// This function takes a directed graph, a vertex ID, a mutable HashSet to keep track of visited vertices,
47/// and a mutable Vec as a container to store the order in which vertices are visited. The function returns an empty Result on successful
48/// completion, and a GraphError if something went wrong.
49///
50/// # Arguments
51///
52/// * `graph` - A directed graph to perform DFS on.
53/// * `vertex` - A VertexId to start the DFS from.
54/// * `visited` - A mutable reference to a HashSet storing visited VertexIds.
55/// * `stack` - A mutable reference to a stack storing VertexIds in the order of reverse DFS traversal.
56///
57/// # Errors
58///
59/// Returns an error if the `graph` has an issue like a non-existing vertex.
60///
61pub fn reverse_depth_first_search(
62    graph: &Graph,
63    vertex: &VertexId,
64    visited: &mut HashSet<VertexId>,
65    stack: &mut Vec<VertexId>,
66) -> Result<(), NetworkError> {
67    if visited.contains(vertex) {
68        return Ok(());
69    }
70
71    visited.insert(*vertex);
72
73    let edges = graph.in_edges(vertex);
74    for (edge_list_id, edge_id) in edges {
75        let src = graph.src_vertex_id(&edge_list_id, &edge_id)?;
76        reverse_depth_first_search(graph, &src, visited, stack)?;
77    }
78
79    stack.push(*vertex);
80
81    Ok(())
82}
83
84/// Finds all strongly connected components in a directed graph.
85///
86/// This function takes a directed graph and returns a Vec of Vecs of VertexIds, where each Vec of VertexIds is a strongly connected component.
87///
88/// # Arguments
89///
90/// * `graph` - A directed graph to find strongly connected components in.
91///
92/// # Errors
93///
94/// Returns an error if the `graph` has an issue like a non-existing vertex.
95///
96pub fn all_strongly_connected_componenets(
97    graph: &Graph,
98) -> Result<Vec<Vec<VertexId>>, NetworkError> {
99    let mut visited: HashSet<VertexId> = HashSet::new();
100    let mut container: Vec<VertexId> = Vec::new();
101    let mut result: Vec<Vec<VertexId>> = Vec::new();
102
103    for vertex_id in graph.vertex_ids() {
104        depth_first_search(graph, &vertex_id, &mut visited, &mut container)?;
105    }
106
107    visited.clear();
108
109    while let Some(vertex_id) = container.pop() {
110        if visited.contains(&vertex_id) {
111            continue;
112        }
113
114        let mut component: Vec<VertexId> = Vec::new();
115        reverse_depth_first_search(graph, &vertex_id, &mut visited, &mut component)?;
116        result.push(component);
117    }
118
119    Ok(result)
120}
121
122/// Finds the largest strongly connected component in a directed graph.
123///
124/// This function takes a directed graph and returns a Vec of VertexIds, where each VertexId is a vertex in the largest strongly connected component.
125///
126/// # Arguments
127///
128/// * `graph` - A directed graph to find the largest strongly connected component in.
129///
130/// # Errors
131///
132/// Returns an error if the `graph` has an issue like a non-existing vertex.
133///
134pub fn largest_strongly_connected_component(graph: &Graph) -> Result<Vec<VertexId>, NetworkError> {
135    let components = all_strongly_connected_componenets(graph)?;
136
137    let mut largest_component: Vec<VertexId> = Vec::new();
138
139    for component in components {
140        if component.len() > largest_component.len() {
141            largest_component = component;
142        }
143    }
144
145    Ok(largest_component)
146}
147
148#[cfg(test)]
149mod tests {
150    use indexmap::IndexMap;
151    use uom::si::f64::Length;
152
153    use super::*;
154    use crate::model::network::{Edge, EdgeList, EdgeListId, Graph, Vertex};
155
156    fn build_mock_graph() -> Graph {
157        let vertices = vec![
158            Vertex::new(0, 0.0, 0.0),
159            Vertex::new(1, 1.0, 1.0),
160            Vertex::new(2, 2.0, 2.0),
161            Vertex::new(3, 3.0, 3.0),
162            Vertex::new(4, 4.0, 4.0),
163        ];
164
165        let length = Length::new::<uom::si::length::kilometer>(10.0);
166
167        let edges = vec![
168            Edge::new(0, 0, 0, 1, length),
169            Edge::new(0, 1, 1, 0, length),
170            Edge::new(0, 2, 1, 2, length),
171            Edge::new(0, 3, 2, 1, length),
172            Edge::new(0, 4, 2, 3, length),
173            Edge::new(0, 5, 3, 2, length),
174            Edge::new(0, 6, 3, 0, length),
175            Edge::new(0, 7, 0, 3, length),
176            Edge::new(0, 8, 0, 2, length),
177            Edge::new(0, 9, 1, 3, length),
178            Edge::new(0, 10, 2, 0, length),
179            Edge::new(0, 11, 3, 1, length),
180            Edge::new(0, 12, 4, 4, length),
181        ];
182
183        // Create the adjacency and reverse adjacency lists.
184        let mut adj = vec![IndexMap::new(); vertices.len()];
185        let mut rev = vec![IndexMap::new(); vertices.len()];
186        let edge_list_id = EdgeListId(0);
187
188        for edge in &edges {
189            adj[edge.src_vertex_id.0].insert((edge_list_id, edge.edge_id), edge.dst_vertex_id);
190            rev[edge.dst_vertex_id.0].insert((edge_list_id, edge.edge_id), edge.src_vertex_id);
191        }
192
193        // Construct the Graph instance.
194
195        Graph {
196            vertices: vertices.into_boxed_slice(),
197            edge_lists: vec![EdgeList(edges.into_boxed_slice())],
198            adj: adj.into_boxed_slice(),
199            rev: rev.into_boxed_slice(),
200        }
201    }
202
203    #[test]
204    fn test_largest_strongly_connected_component() {
205        let graph = build_mock_graph();
206        let component = largest_strongly_connected_component(&graph).unwrap();
207        assert_eq!(component.len(), 4);
208        assert!(component.contains(&VertexId(0)));
209        assert!(component.contains(&VertexId(1)));
210        assert!(component.contains(&VertexId(2)));
211        assert!(component.contains(&VertexId(3)));
212    }
213
214    #[test]
215    fn test_all_strongly_connected_components() {
216        let graph = build_mock_graph();
217        let mut components = all_strongly_connected_componenets(&graph).unwrap();
218        components.sort_by_key(|c| c.len());
219        assert_eq!(components.len(), 2);
220        assert_eq!(components[1].len(), 4);
221        assert_eq!(components[0].len(), 1);
222    }
223}
routee_compass_core/algorithm/component/scc.rs

routee_compass_core/algorithm/component/
scc.rs
