Algorithms Library Toolkit
A toolkit for algorithms, especially for algorithms on formal languages
IDDFS.hpp
Go to the documentation of this file.
1
6// Copyright (c) 2017 Czech Technical University in Prague | Faculty of Information Technology. All rights reserved.
7
8#pragma once
9
10#include <functional>
11#include <alib/vector>
12#include <queue>
13#include <limits>
14#include <alib/set>
15#include <alib/map>
16
17#include <common/ReconstructPath.hpp>
18
19namespace graph {
20
21namespace traverse {
22
23class IDDFS {
24// ---------------------------------------------------------------------------------------------------------------------
25
26 public:
27
39 template<
40 typename TGraph,
41 typename TNode,
42 typename F = std::function<bool(const TNode &, const size_t &)>>
43 static
44 void
45 run(const TGraph &graph,
46 const TNode &start,
47 unsigned long max_depth = std::numeric_limits<unsigned long>::max(),
48 F f_user = [](const TNode &, const size_t &) -> bool { return false; });
49
50// ---------------------------------------------------------------------------------------------------------------------
51
65 template<
66 typename TGraph,
67 typename TNode,
68 typename F = std::function<void(const TNode &, const size_t &)>>
69 static
70 ext::vector<TNode>
71 findPath(const TGraph &graph,
72 const TNode &start,
73 const TNode &goal,
74 unsigned long max_depth = std::numeric_limits<unsigned long>::max(),
75 F f_user = [](const TNode &, const size_t &) {});
76
77 template<typename TGraph, typename TNode>
78 static
79 ext::vector<TNode>
80 findPathRegistration(const TGraph &graph,
81 const TNode &start,
82 const TNode &goal) {
83 return findPath(graph, start, goal);
84
85 }
86
87// ---------------------------------------------------------------------------------------------------------------------
88
103 template<
104 typename TGraph,
105 typename TNode,
106 typename F = std::function<void(const TNode &, const size_t &)>>
107 static
108 ext::vector<TNode>
109 findPathBidirectional(const TGraph &graph,
110 const TNode &start,
111 const TNode &goal,
112 unsigned long max_depth = std::numeric_limits<unsigned long>::max(),
113 F f_user = [](const TNode &, const size_t &) {});
114
115 template<typename TGraph, typename TNode>
116 static
117 ext::vector<TNode>
118 findPathBidirectionalRegistration(const TGraph &graph,
119 const TNode &start,
120 const TNode &goal) {
121 return findPath(graph, start, goal);
122
123 }
124
125// =====================================================================================================================
126
127 private:
128
129// ---------------------------------------------------------------------------------------------------------------------
130
131 template<typename TNode>
132 struct Data {
133 ext::vector<TNode> path; // current path
134 ext::set<TNode> path_set; // current path set for quick search
135 ext::set<TNode> v; // visited
136 };
137
138// ---------------------------------------------------------------------------------------------------------------------
139
140 template<typename TGraph, typename TNode, typename F1, typename F2>
141 static
142 ext::vector<TNode>
143 implNormal(const TGraph &graph,
144 const TNode &start,
145 unsigned long max_depth,
146 F1 f_user,
147 F2 f_stop);
148
149// ---------------------------------------------------------------------------------------------------------------------
150
151 template<typename FSucc, typename TNode, typename F1, typename F2>
152 static
153 bool
154 expansion(FSucc successors,
155 IDDFS::Data<TNode> &data,
156 const TNode &n,
157 bool save_nodes,
158 unsigned long max_depth,
159 F1 f_user,
160 F2 f_stop);
161
162// ---------------------------------------------------------------------------------------------------------------------
163
164 template<typename TGraph, typename TNode, typename F1, typename F2>
165 static
166 ext::vector<TNode>
167 implBidirectional(const TGraph &graph,
168 const TNode &start,
169 const TNode &goal,
170 unsigned long max_depth,
171 F1 f_user,
172 F2 f_stop);
173
174// ---------------------------------------------------------------------------------------------------------------------
175
176 template<typename FSucc, typename TNode, typename F1, typename F2>
177 static
178 ext::set<TNode>
179 backward_expansion(FSucc successors,
180 const IDDFS::Data<TNode> &forward_data,
181 IDDFS::Data<TNode> &backward_data,
182 const TNode &node,
183 unsigned long max_depth,
184 F1 f_user,
185 F2 f_stop);
186
187// ---------------------------------------------------------------------------------------------------------------------
188
189 template<typename TGraph, typename TNode>
190 static
191 ext::vector<TNode>
192 constructPath(const TGraph &graph,
193 const TNode &start,
194 const TNode &goal,
195 TNode intersection,
196 unsigned long max_forward_depth,
197 unsigned long max_backward_depth);
198
199// ---------------------------------------------------------------------------------------------------------------------
200
201 template<typename TNode>
202 inline static void init(IDDFS::Data<TNode> &data, const TNode &start);
203
204// ---------------------------------------------------------------------------------------------------------------------
205
206};
207
208// =====================================================================================================================
209
210template<typename TGraph, typename TNode, typename F>
211void IDDFS::run(const TGraph &graph, const TNode &start, unsigned long max_depth, F f_user) {
212 implNormal(graph, start, max_depth, f_user, [](const TNode &) -> bool { return false; });
213}
214
215// ---------------------------------------------------------------------------------------------------------------------
216
217template<typename TGraph, typename TNode, typename F>
218ext::vector<TNode> IDDFS::findPath(const TGraph &graph,
219 const TNode &start,
220 const TNode &goal,
221 unsigned long max_depth,
222 F f_user) {
223 return implNormal(graph, start, max_depth,
224 [&](const TNode &n, const auto &d) -> bool {
225 f_user(n, d);
226 return false;
227 },
228 [&goal](const TNode &n) -> bool { return goal == n; });
229}
230
231// ---------------------------------------------------------------------------------------------------------------------
232
233template<typename TGraph, typename TNode, typename F>
234ext::vector<TNode> IDDFS::findPathBidirectional(const TGraph &graph,
235 const TNode &start,
236 const TNode &goal,
237 unsigned long max_depth,
238 F f_user) {
239 return implBidirectional(graph, start, goal, max_depth,
240 [&](const TNode &n, const auto &d) -> bool {
241 f_user(n, d);
242 return false;
243 },
244 [](const TNode &) -> bool { return false; });
245}
246
247// =====================================================================================================================
248
249// ---------------------------------------------------------------------------------------------------------------------
250
251template<typename TGraph, typename TNode, typename F1, typename F2>
252ext::vector<TNode> IDDFS::implNormal(const TGraph &graph,
253 const TNode &start,
254 unsigned long max_depth,
255 F1 f_user,
256 F2 f_stop) {
257 for (unsigned long i = 1; i < max_depth; ++i) {
258 Data<TNode> data;
259
260 // Init search
261 init(data, start);
262
263 bool stop =
264 expansion([&](const TNode &node) { return graph.successors(node); }, data, start, false, i, f_user, f_stop);
265
266 if (stop) {
267 return data.path;
268 }
269 }
270
271 return ext::vector<TNode>();
272}
273
274// ---------------------------------------------------------------------------------------------------------------------
275
276template<typename FSucc, typename TNode, typename F1, typename F2>
277bool IDDFS::expansion(FSucc successors,
278 IDDFS::Data<TNode> &data,
279 const TNode &n,
280 bool save_nodes,
281 unsigned long max_depth,
282 F1 f_user,
283 F2 f_stop) {
284 if (max_depth == 0) return false; // Continue with search
285 else if (save_nodes && max_depth == 1) {
286 data.v.insert(n); // Remember only the deepest nodes
287 }
288
289 // Run user's function
290 if (f_user(n, data.path.size())) {
291 return true; // Stop algorithm
292 }
293
294 // Stop if reach the goal
295 if (f_stop(n)) {
296 return true; // Stop algorithm
297 }
298
299 for (const auto &s : successors(n)) {
300
301 // Check if node is not in path
302 if (data.path_set.find(s) != data.path_set.end()) {
303 continue;
304 }
305
306 data.path.push_back(s); // Insert current node
307 data.path_set.insert(s);
308 bool stop = expansion(successors, data, s, save_nodes, max_depth - 1, f_user, f_stop);
309
310 if (stop) {
311 return true; // Stop algorithm
312 }
313
314 data.path.pop_back(); // Remove current node
315 data.path_set.erase(data.path_set.find(s));
316 }
317
318 return false; // Continue with search
319}
320
321// ---------------------------------------------------------------------------------------------------------------------
322
323template<typename TGraph, typename TNode, typename F1, typename F2>
324ext::vector<TNode> IDDFS::implBidirectional(const TGraph &graph,
325 const TNode &start,
326 const TNode &goal,
327 unsigned long max_depth,
328 F1 f_user,
329 F2 f_stop) {
330 for (unsigned long i = 1; i < max_depth; ++i) {
331 // -------------------------------
332 // Forward search
333 Data<TNode> forward_data;
334
335 // Init forward search
336 init(forward_data, start);
337
338 expansion([&](const TNode &n) { return graph.successors(n); }, forward_data, start, true, i, f_user, f_stop);
339
340 // -------------------------------
341 // Backward search
342
343 ext::set<TNode> intersection;
344
345 Data<TNode> backward_data;
346
347 // Init backward search
348 init(backward_data, goal);
349
350 intersection = backward_expansion([&](const TNode &node) { return graph.predecessors(node); },
351 forward_data,
352 backward_data,
353 goal,
354 i,
355 f_user,
356 f_stop); // even run
357
358 // If there is a intersection, then we can construct path
359 if (!intersection.empty()) {
360 return constructPath(graph, start, goal, *intersection.begin(), i, i);
361 }
362
363 // Init backward search
364 init(backward_data, goal);
365
366 intersection = backward_expansion([&](const TNode &node) { return graph.predecessors(node); },
367 forward_data,
368 backward_data,
369 goal,
370 i + 1,
371 f_user,
372 f_stop); // odd run
373
374 // If there is a intersection, then we can reconstruct path
375 if (!intersection.empty()) {
376 return constructPath(graph, start, goal, *intersection.begin(), i, i + 1);
377 }
378 }
379
380 return ext::vector<TNode>();
381}
382
383// ---------------------------------------------------------------------------------------------------------------------
384
385template<typename FSucc, typename TNode, typename F1, typename F2>
386ext::set<TNode> IDDFS::backward_expansion(FSucc successors,
387 const IDDFS::Data<TNode> &forward_data,
388 IDDFS::Data<TNode> &backward_data,
389 const TNode &node,
390 unsigned long max_depth,
391 F1 f_user,
392 F2 f_stop) {
393 expansion(successors, backward_data, node, true, max_depth, f_user, f_stop);
394
395 // Check for intersection
396 ext::set<TNode> intersection;
397 std::set_intersection(forward_data.v.begin(), forward_data.v.end(),
398 backward_data.v.begin(), backward_data.v.end(),
399 std::inserter(intersection, intersection.begin()));
400
401 return intersection;
402}
403
404// ---------------------------------------------------------------------------------------------------------------------
405
406template<typename TGraph, typename TNode>
407ext::vector<TNode> IDDFS::constructPath(const TGraph &graph,
408 const TNode &start,
409 const TNode &goal,
410 TNode intersection,
411 unsigned long max_forward_depth,
412 unsigned long max_backward_depth) {
413 Data<TNode> forward_data;
414 Data<TNode> backward_data;
415 init(forward_data, start);
416 init(backward_data, goal);
417
418 // Re-run forward search
419 expansion([&](const TNode &node) { return graph.successors(node); },
420 forward_data,
421 start,
422 false,
423 max_forward_depth,
424 [](const TNode &, const size_t &) -> bool { return false; },
425 [&](const TNode &n) -> bool { return n == intersection; }
426 );
427
428 // Re-run backward search
429 expansion([&](const TNode &node) { return graph.predecessors(node); },
430 backward_data,
431 goal,
432 false,
433 max_backward_depth,
434 [](const TNode &, const size_t &) -> bool { return false; },
435 [&](const TNode &n) -> bool { return n == intersection; }
436 );
437
438 return common::ReconstructPath::joinPath(forward_data.path, backward_data.path);
439}
440
441// ---------------------------------------------------------------------------------------------------------------------
442
443template<typename TNode>
444void IDDFS::init(IDDFS::Data<TNode> &data, const TNode &start) {
445 // Make sure that data are wiped
446 data.path.clear();
447 data.v.clear();
448
449 data.path.push_back(start);
450 data.path_set.insert(start);
451}
452
453// ---------------------------------------------------------------------------------------------------------------------
454
455} // namespace traverse
456
457} // namespace graph
458
ext::set
Definition: set.hpp:44
ext::set::begin
auto begin() &
Inherited behavior of begin for non-const instance.
Definition: set.hpp:99
ext::vector
Class extending the vector class from the standard library. Original reason is to allow printing of t...
Definition: vector.hpp:45
graph::common::ReconstructPath::joinPath
static ext::vector< TNode > joinPath(ext::vector< TNode > &forward_path, const ext::vector< TNode > &backward_path)
Definition: ReconstructPath.hpp:163
graph::traverse::IDDFS
Definition: IDDFS.hpp:23
graph::traverse::IDDFS::findPath
static ext::vector< TNode > findPath(const TGraph &graph, const TNode &start, const TNode &goal, unsigned long max_depth=std::numeric_limits< unsigned long >::max(), F f_user=[](const TNode &, const size_t &) {})
Definition: IDDFS.hpp:218
graph::traverse::IDDFS::findPathBidirectionalRegistration
static ext::vector< TNode > findPathBidirectionalRegistration(const TGraph &graph, const TNode &start, const TNode &goal)
Definition: IDDFS.hpp:118
graph::traverse::IDDFS::findPathRegistration
static ext::vector< TNode > findPathRegistration(const TGraph &graph, const TNode &start, const TNode &goal)
Definition: IDDFS.hpp:80
graph::traverse::IDDFS::run
static void run(const TGraph &graph, const TNode &start, unsigned long max_depth=std::numeric_limits< unsigned long >::max(), F f_user=[](const TNode &, const size_t &) -> bool { return false;})
Definition: IDDFS.hpp:211
graph::traverse::IDDFS::findPathBidirectional
static ext::vector< TNode > findPathBidirectional(const TGraph &graph, const TNode &start, const TNode &goal, unsigned long max_depth=std::numeric_limits< unsigned long >::max(), F f_user=[](const TNode &, const size_t &) {})
Definition: IDDFS.hpp:234
automaton::properties::i
int i
Definition: AllEpsilonClosure.h:118
ext::max
constexpr const T & max(const T &a)
Root case of maximum computation. The maximum from one value is the value itself.
Definition: algorithm.hpp:278
graph
Definition: ReconstructPath.hpp:14
measurements::start
void start(measurements::stealth_string name, measurements::Type type)
Definition: measurements.cpp:14
node
Definition: Node.cpp:11
Generated on Mon Dec 27 2021 10:21:54 for Algorithms Library Toolkit by doxygen 1.9.2