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