weavatrix_graph/algo/
traversal.rs

1use super::walk::{TraversalWorkspace, bfs_iter_filtered, dfs_iter_filtered};
2use crate::IndexGraphView;
3use crate::Vec;
4use alloc::collections::VecDeque;
5
6#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
7pub enum Direction {
8    #[default]
9    Outgoing,
10    Incoming,
11    Both,
12}
13
14#[must_use]
15pub fn bfs<G>(graph: &G, start: G::Node) -> Vec<G::Node>
16where
17    G: IndexGraphView,
18{
19    if !graph.contains_node(start) {
20        return Vec::new();
21    }
22    let mut seen = vec![false; graph.node_bound()];
23    let mut visited = Vec::with_capacity(graph.node_count());
24    seen[G::node_slot(start)] = true;
25    visited.push(start);
26    let mut cursor = 0;
27    while cursor < visited.len() {
28        let node = visited[cursor];
29        cursor += 1;
30        for edge in graph.outgoing_edges(node) {
31            let Some(endpoints) = graph.edge_endpoints(edge) else {
32                continue;
33            };
34            let neighbor = endpoints.target();
35            let slot = G::node_slot(neighbor);
36            if !seen[slot] {
37                seen[slot] = true;
38                visited.push(neighbor);
39            }
40        }
41    }
42    visited
43}
44
45#[must_use]
46pub fn bfs_filtered<G, F>(
47    graph: &G,
48    start: G::Node,
49    direction: Direction,
50    keep_edge: F,
51) -> Vec<G::Node>
52where
53    G: IndexGraphView,
54    F: FnMut(G::Edge) -> bool,
55{
56    let mut workspace = TraversalWorkspace::new();
57    bfs_iter_filtered(graph, start, direction, &mut workspace, keep_edge).collect()
58}
59
60#[must_use]
61pub fn dfs<G>(graph: &G, start: G::Node) -> Vec<G::Node>
62where
63    G: IndexGraphView,
64{
65    dfs_filtered(graph, start, Direction::Outgoing, |_| true)
66}
67
68#[must_use]
69pub fn dfs_filtered<G, F>(
70    graph: &G,
71    start: G::Node,
72    direction: Direction,
73    keep_edge: F,
74) -> Vec<G::Node>
75where
76    G: IndexGraphView,
77    F: FnMut(G::Edge) -> bool,
78{
79    let mut workspace = TraversalWorkspace::new();
80    dfs_iter_filtered(graph, start, direction, &mut workspace, keep_edge).collect()
81}
82
83#[must_use]
84pub fn reachable<G>(graph: &G, source: G::Node, target: G::Node) -> bool
85where
86    G: IndexGraphView,
87{
88    reachable_filtered(graph, source, target, Direction::Outgoing, |_| true)
89}
90
91pub fn reachable_filtered<G, F>(
92    graph: &G,
93    source: G::Node,
94    target: G::Node,
95    direction: Direction,
96    keep_edge: F,
97) -> bool
98where
99    G: IndexGraphView,
100    F: FnMut(G::Edge) -> bool,
101{
102    graph.contains_node(target)
103        && bfs_filtered(graph, source, direction, keep_edge)
104            .into_iter()
105            .any(|node| node == target)
106}
107
108#[must_use]
109pub fn shortest_path<G>(graph: &G, source: G::Node, target: G::Node) -> Option<Vec<G::Node>>
110where
111    G: IndexGraphView,
112{
113    shortest_path_filtered(graph, source, target, Direction::Outgoing, |_| true)
114}
115
116pub fn shortest_path_filtered<G, F>(
117    graph: &G,
118    source: G::Node,
119    target: G::Node,
120    direction: Direction,
121    mut keep_edge: F,
122) -> Option<Vec<G::Node>>
123where
124    G: IndexGraphView,
125    F: FnMut(G::Edge) -> bool,
126{
127    if !graph.contains_node(source) || !graph.contains_node(target) {
128        return None;
129    }
130    let mut predecessor = vec![None; graph.node_bound()];
131    let mut seen = vec![false; graph.node_bound()];
132    let mut queue = VecDeque::with_capacity(graph.node_count());
133    seen[G::node_slot(source)] = true;
134    queue.push_back(source);
135    while let Some(node) = queue.pop_front() {
136        if node == target {
137            return Some(reconstruct_path::<G>(source, target, &predecessor));
138        }
139        for_each_neighbor(graph, node, direction, &mut keep_edge, |neighbor| {
140            let slot = G::node_slot(neighbor);
141            if !seen[slot] {
142                seen[slot] = true;
143                predecessor[slot] = Some(node);
144                queue.push_back(neighbor);
145            }
146        });
147    }
148    None
149}
150
151fn reconstruct_path<G: IndexGraphView>(
152    source: G::Node,
153    target: G::Node,
154    predecessor: &[Option<G::Node>],
155) -> Vec<G::Node> {
156    let mut path = vec![target];
157    let mut cursor = target;
158    while cursor != source {
159        cursor = predecessor[G::node_slot(cursor)].expect("visited nodes have predecessors");
160        path.push(cursor);
161    }
162    path.reverse();
163    path
164}
165
166pub(super) fn for_each_neighbor<G, F, V>(
167    graph: &G,
168    node: G::Node,
169    direction: Direction,
170    keep_edge: &mut F,
171    mut visit: V,
172) where
173    G: IndexGraphView,
174    F: FnMut(G::Edge) -> bool,
175    V: FnMut(G::Node),
176{
177    for_each_adjacent(graph, node, direction, keep_edge, |_, neighbor| {
178        visit(neighbor);
179    });
180}
181
182pub(super) fn for_each_adjacent<G, F, V>(
183    graph: &G,
184    node: G::Node,
185    direction: Direction,
186    keep_edge: &mut F,
187    mut visit: V,
188) where
189    G: IndexGraphView,
190    F: FnMut(G::Edge) -> bool,
191    V: FnMut(G::Edge, G::Node),
192{
193    if matches!(direction, Direction::Outgoing | Direction::Both) {
194        for edge in graph.outgoing_edges(node).filter(|edge| keep_edge(*edge)) {
195            if let Some(endpoints) = graph.edge_endpoints(edge) {
196                visit(edge, endpoints.target());
197            }
198        }
199    }
200    if matches!(direction, Direction::Incoming | Direction::Both) {
201        for edge in graph.incoming_edges(node).filter(|edge| keep_edge(*edge)) {
202            if let Some(endpoints) = graph.edge_endpoints(edge) {
203                visit(edge, endpoints.source());
204            }
205        }
206    }
207}
weavatrix_graph/algo/traversal.rs

weavatrix_graph/algo/
traversal.rs
