1use super::WeightedPath;
2use crate::IndexGraphView;
3use crate::Vec;
4use alloc::collections::{BTreeSet, BinaryHeap};
5use core::cmp::Ordering;
6
7#[derive(Debug, Clone, PartialEq, Eq)]
8pub struct PathEnumeration<Node> {
9 paths: Vec<Vec<Node>>,
10 truncated: bool,
11}
12impl<Node> PathEnumeration<Node> {
13 #[must_use]
14 pub fn paths(&self) -> &[Vec<Node>] {
15 &self.paths
16 }
17 #[must_use]
18 pub const fn truncated(&self) -> bool {
19 self.truncated
20 }
21}
22pub fn all_simple_paths<G>(
23 graph: &G,
24 source: G::Node,
25 target: G::Node,
26 max_depth: usize,
27 max_paths: usize,
28) -> PathEnumeration<G::Node>
29where
30 G: IndexGraphView,
31{
32 if max_paths == 0 || !graph.contains_node(source) || !graph.contains_node(target) {
33 return PathEnumeration {
34 paths: Vec::new(),
35 truncated: false,
36 };
37 }
38 let mut state = PathState::new(graph, max_paths);
39 state.path.push(source);
40 state.seen[G::node_slot(source)] = true;
41 enumerate_paths(graph, source, target, max_depth, &mut state);
42 PathEnumeration {
43 paths: state.results,
44 truncated: state.truncated,
45 }
46}
47pub fn k_shortest_paths<G, F>(
48 graph: &G,
49 source: G::Node,
50 target: G::Node,
51 k: usize,
52 edge_cost: F,
53) -> Vec<WeightedPath<G::Node>>
54where
55 G: IndexGraphView,
56 F: Fn(G::Edge) -> u64,
57{
58 if k == 0 || !graph.contains_node(source) || !graph.contains_node(target) {
59 return Vec::new();
60 }
61 let source_slot = G::node_slot(source);
62 let mut queue = BinaryHeap::new();
63 queue.push(Candidate {
64 cost: 0,
65 slots: vec![source_slot],
66 nodes: vec![source],
67 });
68 let mut queued = BTreeSet::from([vec![source_slot]]);
69 let mut results = Vec::with_capacity(k);
70 while let Some(candidate) = queue.pop() {
71 if candidate.nodes.last() == Some(&target) {
72 results.push(WeightedPath::from_parts(candidate.nodes, candidate.cost));
73 if results.len() == k {
74 break;
75 }
76 continue;
77 }
78 let Some(&node) = candidate.nodes.last() else {
79 continue;
80 };
81 for (neighbor, weight) in weighted_outgoing(graph, node, &edge_cost) {
82 let slot = G::node_slot(neighbor);
83 if candidate.slots.contains(&slot) {
84 continue;
85 }
86 let Some(cost) = candidate.cost.checked_add(weight) else {
87 continue;
88 };
89 let mut slots = candidate.slots.clone();
90 slots.push(slot);
91 if !queued.insert(slots.clone()) {
92 continue;
93 }
94 let mut nodes = candidate.nodes.clone();
95 nodes.push(neighbor);
96 queue.push(Candidate { cost, slots, nodes });
97 }
98 }
99 results
100}
101struct PathState<Node> {
102 path: Vec<Node>,
103 seen: Vec<bool>,
104 results: Vec<Vec<Node>>,
105 limit: usize,
106 truncated: bool,
107}
108impl<Node> PathState<Node> {
109 fn new<G: IndexGraphView<Node = Node>>(graph: &G, limit: usize) -> Self {
110 Self {
111 path: Vec::new(),
112 seen: vec![false; graph.node_bound()],
113 results: Vec::new(),
114 limit,
115 truncated: false,
116 }
117 }
118}
119
120fn enumerate_paths<G>(
121 graph: &G,
122 node: G::Node,
123 target: G::Node,
124 depth_left: usize,
125 state: &mut PathState<G::Node>,
126) where
127 G: IndexGraphView,
128{
129 if node == target {
130 state.results.push(state.path.clone());
131 return;
132 }
133 if depth_left == 0 {
134 return;
135 }
136 for (_, neighbor) in outgoing(graph, node) {
137 let slot = G::node_slot(neighbor);
138 if state.seen[slot] {
139 continue;
140 }
141 if state.results.len() == state.limit {
142 state.truncated = true;
143 return;
144 }
145 state.seen[slot] = true;
146 state.path.push(neighbor);
147 enumerate_paths(graph, neighbor, target, depth_left - 1, state);
148 state.path.pop();
149 state.seen[slot] = false;
150 if state.truncated {
151 return;
152 }
153 }
154}
155
156fn outgoing<G: IndexGraphView>(graph: &G, node: G::Node) -> Vec<(G::Edge, G::Node)> {
157 let mut adjacent = graph
158 .outgoing_edges(node)
159 .filter_map(|edge| {
160 graph
161 .edge_endpoints(edge)
162 .map(|endpoints| (edge, endpoints.target()))
163 })
164 .collect::<Vec<_>>();
165 adjacent.sort_unstable_by_key(|(edge, target)| (G::node_slot(*target), G::edge_slot(*edge)));
166 adjacent.dedup_by_key(|(_, target)| G::node_slot(*target));
167 adjacent
168}
169
170fn weighted_outgoing<G, F>(graph: &G, node: G::Node, edge_cost: &F) -> Vec<(G::Node, u64)>
171where
172 G: IndexGraphView,
173 F: Fn(G::Edge) -> u64,
174{
175 let mut adjacent = graph
176 .outgoing_edges(node)
177 .filter_map(|edge| {
178 graph
179 .edge_endpoints(edge)
180 .map(|endpoints| (endpoints.target(), edge_cost(edge), G::edge_slot(edge)))
181 })
182 .collect::<Vec<_>>();
183 adjacent.sort_unstable_by_key(|(target, cost, edge)| (G::node_slot(*target), *cost, *edge));
184 adjacent.dedup_by_key(|(target, _, _)| G::node_slot(*target));
185 adjacent
186 .into_iter()
187 .map(|(target, cost, _)| (target, cost))
188 .collect()
189}
190
191struct Candidate<Node> {
192 cost: u64,
193 slots: Vec<usize>,
194 nodes: Vec<Node>,
195}
196
197impl<Node> PartialEq for Candidate<Node> {
198 fn eq(&self, other: &Self) -> bool {
199 self.cost == other.cost && self.slots == other.slots
200 }
201}
202
203impl<Node> Eq for Candidate<Node> {}
204
205impl<Node> PartialOrd for Candidate<Node> {
206 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
207 Some(self.cmp(other))
208 }
209}
210
211impl<Node> Ord for Candidate<Node> {
212 fn cmp(&self, other: &Self) -> Ordering {
213 other
214 .cost
215 .cmp(&self.cost)
216 .then_with(|| other.slots.cmp(&self.slots))
217 }
218}