1 /*
2 Copyright (c) 2008-2018, Benoit AUTHEMAN All rights reserved.
3
4 Redistribution and use in source and binary forms, with or without
5 modification, are permitted provided that the following conditions are met:
6 * Redistributions of source code must retain the above copyright
7 notice, this list of conditions and the following disclaimer.
8 * Redistributions in binary form must reproduce the above copyright
9 notice, this list of conditions and the following disclaimer in the
10 documentation and/or other materials provided with the distribution.
11 * Neither the name of the author or Destrat.io nor the
12 names of its contributors may be used to endorse or promote products
13 derived from this software without specific prior written permission.
14
15 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
16 ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
17 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
18 DISCLAIMED. IN NO EVENT SHALL AUTHOR BE LIABLE FOR ANY
19 DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
20 (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
21 LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
22 ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
24 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25 */
26
27 //-----------------------------------------------------------------------------
28 // This file is a part of the GTpo software.
29 //
30 // \file gtpo_algorithm_tests.cpp
31 // \author benoit@qanava.org
32 // \date 2018 06 19
33 //-----------------------------------------------------------------------------
34
35 // STD headers
36 #include <list>
37 #include <memory>
38 #include <iostream>
39
40 // GTpo headers
41 #include <GTpo>
42 #include <../src/algorithm.h>
43 #include <../src/functional.h>
44
45 // Google Test
46 #include <gtest/gtest.h>
47 #include <gmock/gmock.h>
48
49
50 //-----------------------------------------------------------------------------
51 // Graph is_dag()
52 //-----------------------------------------------------------------------------
53
TEST(GTpoGraph,is_dag_rec)54 TEST(GTpoGraph, is_dag_rec)
55 {
56 { // Basic positive tree test (empty graph)
57 gtpo::graph<> g;
58 EXPECT_TRUE(gtpo::is_dag_rec(g));
59
60 auto n1 = g.create_node();
61 EXPECT_TRUE(gtpo::is_dag_rec(g));
62
63 auto n2 = g.create_node();
64 g.create_edge(n1, n2);
65 EXPECT_TRUE(gtpo::is_dag_rec(g));
66
67 g.clear();
68 EXPECT_TRUE(gtpo::is_dag_rec(g));
69 }
70
71 { // Basic positive test
72 // g = { [n1, n2, n3], [(n1 -> n2), (n1 -> n3)] }
73 // Expect: true
74 gtpo::graph<> g;
75 auto n1 = g.create_node();
76 auto n2 = g.create_node();
77 auto n3 = g.create_node();
78 g.create_edge(n1, n2);
79 g.create_edge(n1, n3);
80 EXPECT_TRUE(gtpo::is_dag_rec(g));
81 }
82
83 { // g = { [n1, n2, n3], [(n1 -> n3), (n2 -> n3)] }
84 // Expect: true
85 gtpo::graph<> g;
86 auto n1 = g.create_node();
87 auto n2 = g.create_node();
88 auto n3 = g.create_node();
89 g.create_edge(n1, n3);
90 g.create_edge(n2, n3);
91 EXPECT_TRUE(gtpo::is_dag_rec(g));
92 }
93
94 { // Circuit == non DAG
95 gtpo::graph<> g;
96 auto n1 = g.create_node();
97 auto n2 = g.create_node();
98 g.create_edge(n1, n2);
99 g.create_edge(n2, n1);
100 EXPECT_FALSE(gtpo::is_dag_rec(g));
101 }
102 }
103
104
105 //-----------------------------------------------------------------------------
106 // Graph is_tree()
107 //-----------------------------------------------------------------------------
108
TEST(GTpoGraph,is_tree_rec)109 TEST(GTpoGraph, is_tree_rec)
110 {
111 { // Basic positive tree test (empty graph)
112 gtpo::graph<> g;
113 EXPECT_TRUE(gtpo::is_tree_rec(g));
114
115 auto n1 = g.create_node();
116 EXPECT_TRUE(gtpo::is_tree_rec(g));
117
118 auto n2 = g.create_node();
119 g.create_edge(n1, n2);
120 EXPECT_TRUE(gtpo::is_tree_rec(g));
121
122 g.clear();
123 EXPECT_TRUE(gtpo::is_tree_rec(g));
124 }
125
126 { // Basic positive test
127 // g = { [n1, n2, n3], [(n1 -> n2), (n1 -> n3)] }
128 // Expect: true
129 gtpo::graph<> g;
130 auto n1 = g.create_node();
131 auto n2 = g.create_node();
132 auto n3 = g.create_node();
133 g.create_edge(n1, n2);
134 g.create_edge(n1, n3);
135 EXPECT_TRUE(gtpo::is_tree_rec(g));
136 }
137
138 { // Basic negative test (n
139 // g = { [n1, n2, n3], [(n1 -> n3), (n2 -> n3)] }
140 // Expect: false since n3 in degree is > 1
141 gtpo::graph<> g;
142 auto n1 = g.create_node();
143 auto n2 = g.create_node();
144 auto n3 = g.create_node();
145 g.create_edge(n1, n3);
146 g.create_edge(n2, n3);
147 EXPECT_FALSE(gtpo::is_tree_rec(g));
148 }
149
150 { // Basic negative test (graph with degree 0 and more circuits)
151 gtpo::graph<> g;
152 auto n1 = g.create_node();
153 auto n2 = g.create_node();
154 g.create_edge(n1, n2);
155 g.create_edge(n2, n1);
156 EXPECT_FALSE(gtpo::is_tree_rec(g));
157 }
158 }
159
160 //-----------------------------------------------------------------------------
161 // Graph recursive traversal algorithms
162 //-----------------------------------------------------------------------------
163
TEST(GTpoGraph,tree_depth_rec)164 TEST(GTpoGraph, tree_depth_rec)
165 {
166 gtpo::graph<> g;
167 EXPECT_EQ(gtpo::tree_depth_rec(g), 0);
168
169 auto n1 = g.create_node();
170 EXPECT_EQ(gtpo::tree_depth_rec(g), 1);
171
172 auto n2 = g.create_node();
173 g.create_edge(n1, n2);
174 EXPECT_EQ(gtpo::tree_depth_rec(g), 2);
175
176 g.clear();
177 EXPECT_EQ(gtpo::tree_depth_rec(g), 0);
178 }
179
TEST(GTpoGraph,linearize_tree_dfs_rec)180 TEST(GTpoGraph, linearize_tree_dfs_rec)
181 {
182 {
183 gtpo::graph<> g;
184 auto r = linearize_tree_dfs_rec(g);
185 EXPECT_EQ(r.size(), 0);
186 }
187
188 {
189 gtpo::graph<> g;
190 auto n1 = g.create_node();
191 auto r = linearize_tree_dfs_rec(g);
192 EXPECT_EQ(r.size(), 1);
193 }
194
195 {
196 gtpo::graph<> g;
197 // g = {n1, (n2 -> n3)}
198 auto n1 = g.create_node();
199 auto n2 = g.create_node();
200 auto n3 = g.create_node();
201 g.create_edge(n2, n3);
202 auto r = linearize_tree_dfs_rec(g);
203 ASSERT_EQ(r.size(), 3);
204 EXPECT_EQ(r[0].lock().get(), n1.lock().get());
205 EXPECT_EQ(r[1].lock().get(), n2.lock().get());
206 EXPECT_EQ(r[2].lock().get(), n3.lock().get());
207 }
208
209 {
210 gtpo::graph<> g;
211 // g = {(n1 -> n3), (n4 -> n2)}
212 auto n1 = g.create_node();
213 auto n2 = g.create_node();
214 auto n3 = g.create_node();
215 auto n4 = g.create_node();
216 g.create_edge(n1, n3);
217 g.create_edge(n4, n2);
218 auto r = linearize_tree_dfs_rec(g);
219 ASSERT_EQ(r.size(), 4);
220 EXPECT_EQ(r[0].lock().get(), n1.lock().get());
221 EXPECT_EQ(r[1].lock().get(), n3.lock().get());
222 EXPECT_EQ(r[2].lock().get(), n4.lock().get());
223 EXPECT_EQ(r[3].lock().get(), n2.lock().get());
224 }
225 }
226
TEST(GTpoGraph,levelize_tree_dfs_rec)227 TEST(GTpoGraph, levelize_tree_dfs_rec)
228 {
229 { // Test empty graph, expecting empty result vector
230 // g = {[], []}
231 // Expect: r = []
232 gtpo::graph<> g;
233 auto r = gtpo::levelize_tree_dfs_rec(g);
234 EXPECT_EQ( r.size(), 0);
235 }
236
237 { // Test with one node (level 1) graph
238 // g = {[n1], []}
239 // Expect: r = [ [n1] ]
240 gtpo::graph<> g;
241 auto n1 = g.create_node();
242 auto r = gtpo::levelize_tree_dfs_rec(g);
243 ASSERT_EQ( r.size(), 1);
244 ASSERT_EQ( r[0].size(), 1);
245 EXPECT_EQ( r[0][0].lock().get(), n1.lock().get());
246 }
247
248 { // Test with level 1 graph with multiple nodes
249 // g = {[n1, n2, n3], []}
250 // Expect: r = [ [ n1, n2, n3] ]
251 gtpo::graph<> g;
252 auto n1 = g.create_node();
253 auto n2 = g.create_node();
254 auto n3 = g.create_node();
255 auto r = gtpo::levelize_tree_dfs_rec(g);
256 ASSERT_EQ( r.size(), 1);
257 ASSERT_EQ( r[0].size(), 3);
258 EXPECT_EQ( r[0][0].lock().get(), n1.lock().get());
259 EXPECT_EQ( r[0][1].lock().get(), n2.lock().get());
260 EXPECT_EQ( r[0][2].lock().get(), n3.lock().get());
261 }
262
263 { // Test with level 2 graph with 2 nodes
264 // g = {[n1, n2], [(n1 -> n2)]}
265 // Expect: r = [ [n1], [n2] ]
266 gtpo::graph<> g;
267 auto n1 = g.create_node();
268 auto n2 = g.create_node();
269 g.create_edge(n1, n2);
270 auto r = gtpo::levelize_tree_dfs_rec(g);
271 ASSERT_EQ( r.size(), 2);
272 ASSERT_EQ( r[0].size(), 1);
273 ASSERT_EQ( r[1].size(), 1);
274 EXPECT_EQ( r[0][0].lock().get(), n1.lock().get());
275 EXPECT_EQ( r[1][0].lock().get(), n2.lock().get());
276 }
277
278 { // Test with level 2 graph with multiple nodes
279 // g = {[n1, n3, n4, n2], [(n3 -> n4)]}
280 // Expect: r = [ [n1, n3, n2], [n4] ]
281 gtpo::graph<> g;
282 auto n1 = g.create_node();
283 auto n3 = g.create_node();
284 auto n4 = g.create_node();
285 auto n2 = g.create_node();
286 g.create_edge(n3, n4);
287 auto r = gtpo::levelize_tree_dfs_rec(g);
288 ASSERT_EQ( r.size(), 2);
289 ASSERT_EQ( r[0].size(), 3);
290 ASSERT_EQ( r[1].size(), 1);
291 EXPECT_EQ( r[0][1].lock().get(), n3.lock().get());
292 EXPECT_EQ( r[1][0].lock().get(), n4.lock().get());
293 }
294 }
295
296
297 //-----------------------------------------------------------------------------
298 // Graph (iterative) BFS iterator
299 //-----------------------------------------------------------------------------
300
TEST(GTpoGraph,linearize_dfs)301 TEST(GTpoGraph, linearize_dfs)
302 {
303 {
304 gtpo::graph<> g;
305 auto r = linearize_dfs(g);
306 EXPECT_EQ(r.size(), 0);
307 }
308
309 {
310 gtpo::graph<> g;
311 auto n1 = g.create_node();
312 auto r = linearize_dfs(g);
313 EXPECT_EQ(r.size(), 1);
314 }
315
316 {
317 gtpo::graph<> g;
318 // g = {[n1, n2, n3], [(n2 -> n3)] }
319 auto n1 = g.create_node();
320 auto n2 = g.create_node();
321 auto n3 = g.create_node();
322 g.create_edge(n2, n3);
323 auto r = linearize_dfs(g);
324 ASSERT_EQ(r.size(), 3);
325 EXPECT_EQ(r[0].lock().get(), n1.lock().get());
326 EXPECT_EQ(r[1].lock().get(), n2.lock().get());
327 EXPECT_EQ(r[2].lock().get(), n3.lock().get());
328 }
329
330 {
331 gtpo::graph<> g;
332 // g = {[n1, n2, n3, n4], [(n1 -> n3), (n4 -> n2)]}
333 auto n1 = g.create_node();
334 auto n2 = g.create_node();
335 auto n3 = g.create_node();
336 auto n4 = g.create_node();
337 g.create_edge(n1, n3);
338 g.create_edge(n4, n2);
339 auto r = linearize_dfs(g);
340 ASSERT_EQ(r.size(), 4);
341 EXPECT_EQ(r[0].lock().get(), n1.lock().get());
342 EXPECT_EQ(r[1].lock().get(), n3.lock().get());
343 EXPECT_EQ(r[2].lock().get(), n4.lock().get());
344 EXPECT_EQ(r[3].lock().get(), n2.lock().get());
345 }
346
347 {
348 // Depth first ...
349 // g = {[n1, n2, n3, n4],
350 // [(n1 -> n2), (n2 -> n3), (n1, n4)]}
351 gtpo::graph<> g;
352 auto n1 = g.create_node();
353 auto n2 = g.create_node();
354 auto n3 = g.create_node();
355 auto n4 = g.create_node();
356 g.create_edge(n1, n4);
357 g.create_edge(n1, n2);
358 g.create_edge(n2, n3);
359 auto r = linearize_dfs(g);
360 ASSERT_TRUE(r.size() == 4);
361 EXPECT_EQ(r[0].lock().get(), n1.lock().get());
362 EXPECT_EQ(r[1].lock().get(), n2.lock().get());
363 EXPECT_EQ(r[2].lock().get(), n3.lock().get());
364 EXPECT_EQ(r[3].lock().get(), n4.lock().get());
365 }
366 }
367
TEST(GTpoGraph,begin_end_dfs)368 TEST(GTpoGraph, begin_end_dfs)
369 {
370 {
371 gtpo::graph<> g;
372 auto it = gtpo::begin_dfs(g);
373 auto it_end = gtpo::end_dfs(g);
374
375 // begoin_dfs() has been called on an empty graph: it should be an end() iterator and equals gtpo::end_dfs()...
376 EXPECT_TRUE(it == it_end);
377 EXPECT_FALSE(it != it_end);
378 }
379
380 {
381 gtpo::graph<> g;
382 g.create_node();
383 auto it = gtpo::begin_dfs(g);
384 auto it_end = gtpo::end_dfs(g);
385
386 // begin iterator should not equal end iterator since graph is not empty...
387 EXPECT_FALSE(it == it_end);
388 EXPECT_TRUE(it != it_end);
389 }
390 }
391
TEST(GTpoGraph,dfs_iterator)392 TEST(GTpoGraph, dfs_iterator)
393 {
394 {
395 gtpo::graph<> g;
396 auto n = g.create_node();
397 auto it = gtpo::begin_dfs(g);
398
399 auto ni = *it;
400 EXPECT_EQ(ni.lock().get(), n.lock().get());
401
402 auto it_end = gtpo::end_dfs(g);
403 EXPECT_TRUE(it != it_end);
404 ++it;
405 EXPECT_TRUE(it == it_end);
406 }
407
408 using weak_nodes_t = std::vector<typename gtpo::graph<>::weak_node_t>;
409 const auto iterate_dfs = [](auto& graph) -> weak_nodes_t {
410 weak_nodes_t r;
411 for ( auto dfs_iter = gtpo::begin_dfs(graph);
412 dfs_iter != gtpo::end_dfs(graph);
413 ++dfs_iter ) {
414 r.push_back(*dfs_iter);
415 }
416 return r;
417 };
418
419 const auto compare_vector_of_weak = [](auto& a, auto& b) -> bool {
420 if ( a.size() != b.size() )
421 return false;
422 auto bit = b.begin();
423 for ( const auto& ait : a ) {
424 const auto a_ptr = ait.lock();
425 const auto b_ptr = (*bit).lock();
426 if ( a_ptr.get() != b_ptr.get() )
427 return false;
428 ++bit;
429 }
430 return true;
431 };
432
433 { // Linear graph
434 // g = {[n1, n2, n3], []}
435 gtpo::graph<> g;
436 auto n1 = g.create_node();
437 auto n2 = g.create_node();
438 auto n3 = g.create_node();
439 auto r = linearize_dfs(g);
440 auto r2 = iterate_dfs(g);
441 ASSERT_TRUE(compare_vector_of_weak(r, r2));
442 }
443
444 { // Simple tree
445 // g = {[n1, n2], [(n1 -> n2)] }
446 gtpo::graph<> g;
447 auto n1 = g.create_node();
448 auto n2 = g.create_node();
449 g.create_edge(n1, n2);
450 auto r = linearize_dfs(g);
451 auto r2 = iterate_dfs(g);
452 ASSERT_TRUE(compare_vector_of_weak(r, r2));
453 }
454
455 { // Simple forest
456 // g = {[n1, n2, n3], [(n2 -> n3)] }
457 gtpo::graph<> g;
458 auto n1 = g.create_node();
459 auto n2 = g.create_node();
460 auto n3 = g.create_node();
461 g.create_edge(n2, n3);
462 auto r = linearize_dfs(g);
463 auto r2 = iterate_dfs(g);
464 ASSERT_TRUE(compare_vector_of_weak(r, r2));
465 }
466
467 {
468 // "Complex" forest
469 // g = {[n1, n2, n3, n4], [(n1 -> n3), (n4 -> n2)]}
470 gtpo::graph<> g;
471 auto n1 = g.create_node();
472 auto n2 = g.create_node();
473 auto n3 = g.create_node();
474 auto n4 = g.create_node();
475 g.create_edge(n1, n3);
476 g.create_edge(n4, n2);
477 auto r = linearize_dfs(g);
478 auto r2 = iterate_dfs(g);
479 EXPECT_TRUE(compare_vector_of_weak(r, r2));
480 }
481
482 {
483 // Depth first ...
484 // g = {[n1, n2, n3, n4],
485 // [(n1 -> n2), (n2 -> n3), (n1, n4)]}
486 gtpo::graph<> g;
487 auto n1 = g.create_node();
488 auto n2 = g.create_node();
489 auto n3 = g.create_node();
490 auto n4 = g.create_node();
491 g.create_edge(n1, n4);
492 g.create_edge(n1, n2);
493 g.create_edge(n2, n3);
494 auto r = iterate_dfs(g);
495 ASSERT_TRUE(r.size() == 4);
496 EXPECT_EQ(r[0].lock().get(), n1.lock().get());
497 EXPECT_EQ(r[1].lock().get(), n2.lock().get());
498 EXPECT_EQ(r[2].lock().get(), n3.lock().get());
499 EXPECT_EQ(r[3].lock().get(), n4.lock().get());
500 }
501
502 {
503 // DAG
504 // g = {[n1, n2, n3, n4],
505 // [(n1 -> n2), (n1 -> n3), (n2, n4), (n3, n4), (n1, n4)]}
506 gtpo::graph<> g;
507 auto n1 = g.create_node();
508 auto n2 = g.create_node();
509 auto n3 = g.create_node();
510 auto n4 = g.create_node();
511 g.create_edge(n1, n2);
512 g.create_edge(n1, n4);
513 g.create_edge(n1, n3);
514 g.create_edge(n2, n4);
515 g.create_edge(n3, n4);
516 auto r = iterate_dfs(g);
517 ASSERT_TRUE(r.size() == 4);
518 EXPECT_EQ(r[0].lock().get(), n1.lock().get());
519 EXPECT_EQ(r[1].lock().get(), n3.lock().get());
520 EXPECT_EQ(r[2].lock().get(), n4.lock().get());
521 EXPECT_EQ(r[3].lock().get(), n2.lock().get());
522 }
523
524 // FIXME: Test a non DAG...
525 }
526