Algorithms Library Toolkit
A toolkit for algorithms, especially for algorithms on formal languages
•All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Concepts
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