zrx_graph/graph/algorithm/
path.rs

1// Copyright (c) 2025 Zensical and contributors
2
3// SPDX-License-Identifier: MIT
4// Third-party contributions licensed under DCO
5
6// Permission is hereby granted, free of charge, to any person obtaining a copy
7// of this software and associated documentation files (the "Software"), to
8// deal in the Software without restriction, including without limitation the
9// rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
10// sell copies of the Software, and to permit persons to whom the Software is
11// furnished to do so, subject to the following conditions:
12
13// The above copyright notice and this permission notice shall be included in
14// all copies or substantial portions of the Software.
15
16// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18// FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. IN NO EVENT SHALL THE
19// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
21// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
22// IN THE SOFTWARE.
23
24// ----------------------------------------------------------------------------
25
26//! Graph algorithms related to paths.
27
28use ahash::HashSet;
29use std::collections::VecDeque;
30
31use crate::graph::Graph;
32
33// ----------------------------------------------------------------------------
34// Functions
35// ----------------------------------------------------------------------------
36
37/// Returns the length of the shortest path between two nodes in the graph.
38///
39/// # Examples
40///
41/// ```
42/// # use std::error::Error;
43/// # fn main() -> Result<(), Box<dyn Error>> {
44/// use zrx_graph::algorithm::shortest_path_length;
45/// use zrx_graph::Graph;
46///
47/// // Create graph builder and add nodes
48/// let mut builder = Graph::builder();
49/// let a = builder.add_node("a");
50/// let b = builder.add_node("b");
51/// let c = builder.add_node("c");
52///
53/// // Create edges between nodes
54/// builder.add_edge(a, b, 0)?;
55/// builder.add_edge(b, c, 0)?;
56/// builder.add_edge(a, c, 0)?;
57///
58/// // Create graph from builder
59/// let graph = builder.build();
60///
61/// // Obtain shortest path length
62/// let len = shortest_path_length(&graph, a, c);
63/// assert_eq!(len, Some(1));
64/// # Ok(())
65/// # }
66/// ```
67#[must_use]
68pub fn shortest_path_length<T>(
69    graph: &Graph<T>, source: usize, target: usize,
70) -> Option<usize> {
71    let outgoing = graph.topology().outgoing();
72
73    // Initialize set to track visited nodes
74    let mut visited = HashSet::default();
75
76    // Perform a breadth-first search to find the shortest path between the
77    // two given nodes within the graph, starting at the source node. Breadth-
78    // first search guarantees, that we reach the target node on the shortest
79    // path, which makes this implementation ridiculously simple.
80    let mut queue = VecDeque::from([(source, 0)]);
81    while let Some((node, len)) = queue.pop_front() {
82        if node == target {
83            return Some(len);
84        }
85
86        // Add unvisited descendants to the queue, since we're performing a
87        // breadth-first search, and mark them as visited
88        for &descendant in &outgoing[node] {
89            if visited.insert(descendant) {
90                queue.push_back((descendant, len + 1));
91            }
92        }
93    }
94
95    // No path between nodes found
96    None
97}
zrx_graph/graph/algorithm/path.rs

zrx_graph/graph/algorithm/
path.rs
