1 // Copyright (C) 2018 Intel Corporation
2 //
3 //
4 // SPDX-License-Identifier: Apache-2.0
5 //
6
7 #include <gtest/gtest.h>
8
9 #include <unordered_set>
10 #include <vector>
11 #include <iostream>
12
13 #include <ade/graph.hpp>
14 #include <ade/helpers/subgraphs.hpp>
15
16 #include <ade/util/iota_range.hpp>
17
18 namespace
19 {
hasNode(const ade::NodeHandle & node,const std::vector<ade::NodeHandle> & subgraph)20 bool hasNode(const ade::NodeHandle& node,
21 const std::vector<ade::NodeHandle>& subgraph)
22 {
23 ADE_ASSERT(nullptr != node);
24 return subgraph.end() != std::find(subgraph.begin(), subgraph.end(), node);
25 }
26
isSame(const std::vector<ade::NodeHandle> & subgraph1,const std::vector<ade::NodeHandle> & subgraph2)27 bool isSame(const std::vector<ade::NodeHandle>& subgraph1,
28 const std::vector<ade::NodeHandle>& subgraph2)
29 {
30 if (subgraph1.size() != subgraph2.size())
31 {
32 return false;
33 }
34
35 for (auto&& node: subgraph1)
36 {
37 if (!hasNode(node, subgraph2))
38 {
39 return false;
40 }
41 }
42 for (auto&& node: subgraph2)
43 {
44 if (!hasNode(node, subgraph1))
45 {
46 return false;
47 }
48 }
49 return true;
50 }
51 }
52
TEST(Helpers,Subgraphs)53 TEST(Helpers, Subgraphs)
54 {
55 // Graph:
56 //
57 // 0 1 2
58 // | \ /
59 // 3 4
60 // | |
61 // S S
62 // \ / \
63 // 5 6
64 // | |
65 // 7 S
66 // | |
67 // S |
68 // \ /
69 // 8
70 // |
71 // 9
72 //
73 // Roots: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
74 // S - plitter nodes
75 //
76 // Resulting subgraphs:
77 // 0, 3
78 // 1, 2, 4
79 // 5, 7
80 // 6
81 // 8, 9
82 //
83 // Splitter nodes not accessible from roots
84
85 ade::Graph gr;
86
87 std::vector<ade::NodeHandle> nodes{
88 gr.createNode(),
89 gr.createNode(),
90 gr.createNode(),
91 gr.createNode(),
92 gr.createNode(),
93 gr.createNode(),
94 gr.createNode(),
95 gr.createNode(),
96 gr.createNode(),
97 gr.createNode()
98 };
99
100 std::vector<ade::NodeHandle> splitterNodes{
101 gr.createNode(),
102 gr.createNode(),
103 gr.createNode(),
104 gr.createNode()
105 };
106
107 gr.link(nodes[0],nodes[3]);
108 gr.link(nodes[3],splitterNodes[0]);
109
110 gr.link(nodes[1],nodes[4]);
111 gr.link(nodes[2],nodes[4]);
112 gr.link(nodes[4],splitterNodes[1]);
113
114 gr.link(splitterNodes[0],nodes[5]);
115 gr.link(splitterNodes[1],nodes[5]);
116 gr.link(nodes[5],nodes[7]);
117 gr.link(nodes[7],splitterNodes[2]);
118
119 gr.link(splitterNodes[1],nodes[6]);
120 gr.link(nodes[6],splitterNodes[3]);
121
122 gr.link(splitterNodes[2],nodes[8]);
123 gr.link(splitterNodes[3],nodes[8]);
124 gr.link(nodes[8],nodes[9]);
125
126 const auto subgraphs = ade::splitSubgraphs(nodes,
127 [&](const ade::EdgeHandle& edge)
128 {
129 return (splitterNodes.end() != std::find(splitterNodes.begin(), splitterNodes.end(), edge->srcNode())) ||
130 (splitterNodes.end() != std::find(splitterNodes.begin(), splitterNodes.end(), edge->dstNode()));
131 });
132
133 std::vector<std::vector<ade::NodeHandle>> expected{
134 {nodes[0],nodes[3]},
135 {nodes[1],nodes[2],nodes[4]},
136 {nodes[5],nodes[7]},
137 {nodes[6]},
138 {nodes[8],nodes[9]}
139 };
140
141 ASSERT_EQ(expected.size(), subgraphs.size());
142
143 for (auto&& expected_subgraph: expected)
144 {
145 bool found = false;
146 for (auto&& subgraph: subgraphs)
147 {
148 if (isSame(expected_subgraph, subgraph))
149 {
150 found = true;
151 break;
152 }
153 }
154 EXPECT_TRUE(found);
155 }
156 }
157
158 namespace
159 {
160 using node_set = std::unordered_set<ade::NodeHandle, ade::HandleHasher<ade::Node>>;
161
162 template<typename C>
sort_subgraphs(C & c)163 void sort_subgraphs(C& c)
164 {
165 std::sort(c.begin(), c.end(),
166 [](const decltype(c.front())& val1,
167 const decltype(c.front())& val2)
168 {
169 return val1.front().get() < val2.front().get();
170 });
171 }
172
173 template<bool Value>
174 struct Always
175 {
176 template<typename... T>
operator ()__anon3b7f20da0311::Always177 bool operator()(T&&...) const
178 {
179 return Value;
180 }
181 };
182 }
183
TEST(Helpers,AssembleSubgraphSimple)184 TEST(Helpers, AssembleSubgraphSimple)
185 {
186 // 0
187 // /|
188 // 1 |
189 // /|/
190 // 2 3
191 // \|
192 // 4
193 // |
194 // 5
195
196 ade::Graph gr;
197 ade::NodeHandle nodes[] = {
198 gr.createNode(),
199 gr.createNode(),
200 gr.createNode(),
201 gr.createNode(),
202 gr.createNode(),
203 gr.createNode()};
204 gr.link(nodes[0], nodes[1]);
205 gr.link(nodes[0], nodes[3]);
206 gr.link(nodes[1], nodes[2]);
207 gr.link(nodes[1], nodes[3]);
208 gr.link(nodes[2], nodes[4]);
209 gr.link(nodes[3], nodes[4]);
210 gr.link(nodes[4], nodes[5]);
211 for (auto&& node : nodes)
212 {
213 auto subgraph = ade::assembleSubgraph(node, Always<true>{},Always<true>{});
214
215 EXPECT_EQ((node_set(std::begin(nodes), std::end(nodes))), node_set(subgraph.begin(),subgraph.end()));
216 }
217 }
218
219 namespace
220 {
hasCycle(const ade::subgraphs::NodesSet & acceptedNodes,const ade::subgraphs::NodesSet & rejectedNodes)221 bool hasCycle(const ade::subgraphs::NodesSet& acceptedNodes,
222 const ade::subgraphs::NodesSet& rejectedNodes)
223 {
224 for (auto&& srcNode : acceptedNodes)
225 {
226 ADE_ASSERT(nullptr != srcNode);
227 if (srcNode->outNodes().size() > 1)
228 {
229 for (auto&& dstNode : acceptedNodes)
230 {
231 ADE_ASSERT(nullptr != dstNode);
232 if (srcNode != dstNode &&
233 dstNode->inNodes().size() > 1)
234 {
235 bool invalidPath = false;
236 ade::findPaths(srcNode, dstNode,
237 [&](const std::vector<ade::NodeHandle>& path)
238 {
239 for (auto&& node : path)
240 {
241 ADE_ASSERT(nullptr != node);
242 if (ade::util::contains(rejectedNodes, node))
243 {
244 invalidPath = true;
245 return true;
246 }
247 }
248 return false;
249 });
250 if (invalidPath)
251 {
252 return true;
253 }
254 }
255 }
256 }
257 }
258 return false;
259 }
260 }
261
TEST(Helpers,AssembleSubgraphCycles1)262 TEST(Helpers, AssembleSubgraphCycles1)
263 {
264 // 0
265 // |
266 // 1
267 // / \
268 // 2 3
269 // | |
270 // 4 5
271 // \ /
272 // 6
273 // |
274 // 7
275
276 ade::Graph gr;
277 ade::NodeHandle nodes[] = {
278 gr.createNode(),
279 gr.createNode(),
280 gr.createNode(),
281 gr.createNode(),
282 gr.createNode(),
283 gr.createNode(),
284 gr.createNode(),
285 gr.createNode()};
286 gr.link(nodes[0], nodes[1]);
287 gr.link(nodes[1], nodes[2]);
288 gr.link(nodes[1], nodes[3]);
289 gr.link(nodes[2], nodes[4]);
290 gr.link(nodes[3], nodes[5]);
291 gr.link(nodes[4], nodes[6]);
292 gr.link(nodes[5], nodes[6]);
293 gr.link(nodes[6], nodes[7]);
294
295 auto mergeChecker = [&](
296 const ade::EdgeHandle& edge,
297 ade::SubgraphMergeDirection direction)
298 {
299 auto dstNode = ade::getDstMergeNode(edge, direction);
300
301 if (dstNode == nodes[3] || dstNode == nodes[5])
302 {
303 return false;
304 }
305
306 return true;
307 };
308 ade::SubgraphSelfReferenceChecker cycleChecker(nodes);
309 auto topoChecker = [&](
310 const ade::subgraphs::NodesSet& acceptedNodes,
311 const ade::subgraphs::NodesSet& rejectedNodes)
312 {
313 EXPECT_EQ(hasCycle(acceptedNodes, rejectedNodes),
314 cycleChecker(acceptedNodes, rejectedNodes));
315 return !cycleChecker(acceptedNodes, rejectedNodes);
316 };
317 ade::NodeHandle roots[] = {
318 nodes[0],
319 nodes[1],
320 nodes[2],
321 nodes[4],
322 nodes[6],
323 nodes[7]
324 };
325 auto subgraphs = ade::selectSubgraphs(roots, mergeChecker, topoChecker);
326 ASSERT_EQ(2, subgraphs.size());
327 auto res0 = node_set(subgraphs[0].begin(), subgraphs[0].end());
328 auto res1 = node_set(subgraphs[1].begin(), subgraphs[1].end());
329 auto exp0 = node_set{nodes[0],nodes[1],nodes[2],nodes[4]};
330 auto exp1 = node_set{nodes[2],nodes[4],nodes[6],nodes[7]};
331 EXPECT_TRUE((exp0 == res0 && exp1 == res1) ||
332 (exp0 == res1 && exp1 == res0));
333 }
334
TEST(Helpers,AssembleSubgraphCycles2)335 TEST(Helpers, AssembleSubgraphCycles2)
336 {
337 // 0
338 // |
339 // 1
340 // / \
341 // 2 3
342 // | |
343 // 4 5
344 // | |
345 // 6 7
346 // \ /
347 // 8
348 // |
349 // 9
350
351 ade::Graph gr;
352 ade::NodeHandle nodes[] = {
353 gr.createNode(),
354 gr.createNode(),
355 gr.createNode(),
356 gr.createNode(),
357 gr.createNode(),
358 gr.createNode(),
359 gr.createNode(),
360 gr.createNode(),
361 gr.createNode(),
362 gr.createNode()};
363 gr.link(nodes[0], nodes[1]);
364 gr.link(nodes[1], nodes[2]);
365 gr.link(nodes[1], nodes[3]);
366 gr.link(nodes[2], nodes[4]);
367 gr.link(nodes[3], nodes[5]);
368 gr.link(nodes[4], nodes[6]);
369 gr.link(nodes[5], nodes[7]);
370 gr.link(nodes[6], nodes[8]);
371 gr.link(nodes[7], nodes[8]);
372 gr.link(nodes[8], nodes[9]);
373
374 auto mergeChecker = [&](
375 const ade::EdgeHandle& edge,
376 ade::SubgraphMergeDirection direction)
377 {
378 auto dstNode = ade::getDstMergeNode(edge, direction);
379
380 if (dstNode == nodes[5])
381 {
382 return false;
383 }
384
385 return true;
386 };
387 ade::SubgraphSelfReferenceChecker cycleChecker(nodes);
388 auto topoChecker = [&](
389 const ade::subgraphs::NodesSet& acceptedNodes,
390 const ade::subgraphs::NodesSet& rejectedNodes)
391 {
392 EXPECT_EQ(hasCycle(acceptedNodes, rejectedNodes),
393 cycleChecker(acceptedNodes, rejectedNodes));
394 return !cycleChecker(acceptedNodes, rejectedNodes);
395 };
396 ade::NodeHandle roots[] = {
397 nodes[0],
398 nodes[1],
399 nodes[2],
400 nodes[3],
401 nodes[4],
402 nodes[6],
403 nodes[7],
404 nodes[8],
405 nodes[9]
406 };
407 auto subgraphs = ade::selectSubgraphs(roots, mergeChecker, topoChecker);
408 ASSERT_EQ(2, subgraphs.size());
409 auto res0 = node_set(subgraphs[0].begin(), subgraphs[0].end());
410 auto res1 = node_set(subgraphs[1].begin(), subgraphs[1].end());
411 auto exp0 = node_set{nodes[0],nodes[1],nodes[2],nodes[3],nodes[4],nodes[6]};
412 auto exp1 = node_set{nodes[2],nodes[4],nodes[6],nodes[7],nodes[8],nodes[9]};
413 EXPECT_TRUE((exp0 == res0 && exp1 == res1) ||
414 (exp0 == res1 && exp1 == res0));
415 }
416
TEST(Helpers,AssembleSubgraphCyclesStress1)417 TEST(Helpers, AssembleSubgraphCyclesStress1)
418 {
419 // 0
420 // |
421 // --1--
422 // / / \ \
423 // 2 3 4 5
424 // \ \ / /
425 // --6--
426 // |
427 // ...
428 // repeat 50 times
429
430
431 ade::Graph gr;
432 std::vector<ade::NodeHandle> nodes;
433 ade::NodeHandle prevNode;
434
435 for (auto i : ade::util::iota(50))
436 {
437 (void)i;
438 ade::NodeHandle tempNodes[] = {
439 gr.createNode(),
440 gr.createNode(),
441 gr.createNode(),
442 gr.createNode(),
443 gr.createNode(),
444 gr.createNode(),
445 gr.createNode()
446 };
447 if (nullptr != prevNode)
448 {
449 gr.link(prevNode, tempNodes[0]);
450 }
451 gr.link(tempNodes[0], tempNodes[1]);
452 gr.link(tempNodes[1], tempNodes[2]);
453 gr.link(tempNodes[1], tempNodes[3]);
454 gr.link(tempNodes[1], tempNodes[4]);
455 gr.link(tempNodes[1], tempNodes[5]);
456 gr.link(tempNodes[2], tempNodes[6]);
457 gr.link(tempNodes[3], tempNodes[6]);
458 gr.link(tempNodes[4], tempNodes[6]);
459 gr.link(tempNodes[5], tempNodes[6]);
460 prevNode = tempNodes[6];
461 ade::util::copy(tempNodes, std::back_inserter(nodes));
462 }
463
464 auto mergeChecker = [&](
465 const ade::EdgeHandle& /*edge*/,
466 ade::SubgraphMergeDirection /*direction*/)
467 {
468 return true;
469 };
470 ade::SubgraphSelfReferenceChecker cycleChecker(nodes);
471 auto topoChecker = [&](
472 const ade::subgraphs::NodesSet& acceptedNodes,
473 const ade::subgraphs::NodesSet& rejectedNodes)
474 {
475 return !cycleChecker(acceptedNodes, rejectedNodes);
476 };
477 auto subgraphs = ade::selectSubgraphs(nodes, mergeChecker, topoChecker);
478 ASSERT_EQ(1, subgraphs.size());
479 ASSERT_EQ(nodes.size(), subgraphs.front().size());
480 }
481
TEST(Helpers,AssembleSubgraphCyclesStress2)482 TEST(Helpers, AssembleSubgraphCyclesStress2)
483 {
484 // ...
485 // / \
486 // | 0*
487 // | |
488 // | 1
489 // | |
490 // | 2
491 // | |
492 // | 3
493 // \ /
494 // 4*
495 // / \
496 // ...
497 // repeat N times
498
499
500 ade::Graph gr;
501 std::vector<ade::NodeHandle> nodes;
502 ade::subgraphs::NodesSet rejectedNodes;
503 ade::NodeHandle prevNode = gr.createNode();
504
505 int N = 20;
506
507 for (auto i : ade::util::iota(N))
508 {
509 (void)i;
510 ade::NodeHandle tempNodes[] = {
511 gr.createNode(),
512 gr.createNode(),
513 gr.createNode(),
514 gr.createNode(),
515 gr.createNode()
516 };
517 if (nullptr != prevNode)
518 {
519 gr.link(prevNode, tempNodes[0]);
520 gr.link(prevNode, tempNodes[4]);
521 }
522
523 rejectedNodes.insert(tempNodes[0]);
524 rejectedNodes.insert(tempNodes[4]);
525
526 gr.link(tempNodes[0], tempNodes[1]);
527 gr.link(tempNodes[1], tempNodes[2]);
528 gr.link(tempNodes[2], tempNodes[3]);
529 gr.link(tempNodes[3], tempNodes[4]);
530 prevNode = tempNodes[4];
531 ade::util::copy(tempNodes, std::back_inserter(nodes));
532 }
533
534 auto mergeChecker = [&](
535 const ade::EdgeHandle& edge,
536 ade::SubgraphMergeDirection /*direction*/)
537 {
538 return ade::util::contains(rejectedNodes, edge->srcNode()) ==
539 ade::util::contains(rejectedNodes, edge->dstNode());
540 };
541 ade::SubgraphSelfReferenceChecker cycleChecker(nodes);
542 auto topoChecker = [&](
543 const ade::subgraphs::NodesSet& acceptedNodes,
544 const ade::subgraphs::NodesSet& rejectedNodes)
545 {
546 return !cycleChecker(acceptedNodes, rejectedNodes);
547 };
548 auto subgraphs = ade::selectSubgraphs(nodes, mergeChecker, topoChecker);
549 ASSERT_EQ(N * 2 + 1, subgraphs.size());
550 }
551
552 namespace
553 {
hasMultipleInputs(const ade::subgraphs::NodesSet & acceptedNodes,const ade::subgraphs::NodesSet & rejectedNodes)554 bool hasMultipleInputs(const ade::subgraphs::NodesSet& acceptedNodes,
555 const ade::subgraphs::NodesSet& rejectedNodes)
556 {
557 int numInputs = 0;
558 for (auto&& node : acceptedNodes)
559 {
560 if (node->inEdges().empty())
561 {
562 ++numInputs;
563 if (numInputs > 1)
564 {
565 return true;
566 }
567 }
568 else
569 {
570 for (auto&& node1 : node->inNodes())
571 {
572 if (ade::util::contains(rejectedNodes, node1))
573 {
574 ++numInputs;
575 if (numInputs > 1)
576 {
577 return true;
578 }
579 }
580 }
581 }
582 }
583 return false;
584 }
585 }
586
TEST(Helpers,AssembleSubgraphMultipleInputs1)587 TEST(Helpers, AssembleSubgraphMultipleInputs1)
588 {
589 // Forbid graphs with multiple inputs
590 // 0
591 // |
592 // 1 2
593 // \ /
594 // 3
595 // |
596 // 4
597
598 ade::Graph gr;
599 ade::NodeHandle nodes[] = {
600 gr.createNode(),
601 gr.createNode(),
602 gr.createNode(),
603 gr.createNode(),
604 gr.createNode()};
605 gr.link(nodes[0], nodes[1]);
606 gr.link(nodes[1], nodes[3]);
607 gr.link(nodes[2], nodes[3]);
608 gr.link(nodes[3], nodes[4]);
609
610 Always<true> mergeChecker;
611 auto topoChecker = [](
612 const ade::subgraphs::NodesSet& acceptedNodes,
613 const ade::subgraphs::NodesSet& rejectedNodes)
614 {
615 return !hasMultipleInputs(acceptedNodes,rejectedNodes);
616 };
617
618 auto subgraphs = ade::selectSubgraphs(nodes, mergeChecker, topoChecker);
619 ASSERT_EQ(3, subgraphs.size());
620 sort_subgraphs(subgraphs);
621
622 std::vector<std::vector<ade::NodeHandle>> resSubgraphs = {
623 {nodes[0],nodes[1]},
624 {nodes[2]},
625 {nodes[4]}};
626 sort_subgraphs(resSubgraphs);
627
628 EXPECT_EQ(resSubgraphs, subgraphs);
629 }
630
TEST(Helpers,AssembleSubgraphMultipleInputs2)631 TEST(Helpers, AssembleSubgraphMultipleInputs2)
632 {
633 // Forbid graphs with multiple inputs
634 // 0
635 // / \
636 // 1 2
637 // \ /
638 // 3
639 // |
640 // 4
641
642 ade::Graph gr;
643 ade::NodeHandle nodes[] = {
644 gr.createNode(),
645 gr.createNode(),
646 gr.createNode(),
647 gr.createNode(),
648 gr.createNode()};
649 gr.link(nodes[0], nodes[1]);
650 gr.link(nodes[0], nodes[2]);
651 gr.link(nodes[1], nodes[3]);
652 gr.link(nodes[2], nodes[3]);
653 gr.link(nodes[3], nodes[4]);
654
655 Always<true> mergeChecker;
656 auto topoChecker = [](
657 const ade::subgraphs::NodesSet& acceptedNodes,
658 const ade::subgraphs::NodesSet& rejectedNodes)
659 {
660 return !hasMultipleInputs(acceptedNodes,rejectedNodes);
661 };
662
663 auto subgraphs = ade::selectSubgraphs(std::vector<ade::NodeHandle>{nodes[4]},
664 mergeChecker, topoChecker);
665 ASSERT_EQ(1, subgraphs.size());
666
667 EXPECT_EQ((node_set{nodes[0],nodes[1],nodes[2],nodes[3],nodes[4]}),
668 node_set(subgraphs[0].begin(), subgraphs[0].end()));
669 }
670
671 namespace
672 {
getLongestSubgraph(const std::vector<std::vector<ade::NodeHandle>> & subgraphs)673 std::size_t getLongestSubgraph(
674 const std::vector<std::vector<ade::NodeHandle>>& subgraphs)
675 {
676 std::size_t ret = ade::SubgraphSelectResult::NoSubgraph;
677 std::size_t maxlen = 0;
678 for (auto i : ade::util::iota(subgraphs.size()))
679 {
680 const auto& s = subgraphs[i];
681 if (s.size() > maxlen)
682 {
683 maxlen = s.size();
684 ret = i;
685 }
686 }
687 return ret;
688 }
689 }
690
TEST(Helpers,SelectAllSubgraphs1)691 TEST(Helpers, SelectAllSubgraphs1)
692 {
693 // 0
694 // | \
695 // 1 |
696 // / | |
697 // 2 3 4
698 // | | |
699 // 5 6 7
700 // \ | /
701 // 8
702 // |
703 // 9
704
705 ade::Graph gr;
706 std::vector<ade::NodeHandle> nodes;
707 for (auto i : ade::util::iota(10))
708 {
709 (void)i;
710 nodes.push_back(gr.createNode());
711 }
712 gr.link(nodes[0], nodes[1]);
713 gr.link(nodes[1], nodes[2]);
714 gr.link(nodes[1], nodes[3]);
715 gr.link(nodes[0], nodes[4]);
716 gr.link(nodes[2], nodes[5]);
717 gr.link(nodes[3], nodes[6]);
718 gr.link(nodes[4], nodes[7]);
719 gr.link(nodes[5], nodes[8]);
720 gr.link(nodes[6], nodes[8]);
721 gr.link(nodes[7], nodes[8]);
722 gr.link(nodes[8], nodes[9]);
723
724 ade::subgraphs::NodesSet nodes1;
725 ade::subgraphs::NodesSet nodes2;
726 for (auto i : ade::util::iota(10))
727 {
728 if (0 == i || 4 == i || 7 == i || 8 == i || 9 == i)
729 {
730 nodes2.insert(nodes[i]);
731 }
732 else
733 {
734 nodes1.insert(nodes[i]);
735 }
736 }
737
738 ade::SubgraphSelfReferenceChecker cycleChecker(nodes);
739 auto subgraphs1 = ade::selectAllSubgraphs(
740 nodes1,
741 [&](
742 const ade::EdgeHandle& edge,
743 const ade::SubgraphMergeDirection dir)
744 {
745 auto dstNode = ade::getDstMergeNode(edge, dir);
746 ADE_ASSERT(nullptr != dstNode);
747 return ade::util::contains(nodes1, dstNode);
748 },
749 [&](
750 const ade::subgraphs::NodesSet& acceptedNodes,
751 const ade::subgraphs::NodesSet& rejectedNodes)
752 {
753 EXPECT_EQ(hasCycle(acceptedNodes, rejectedNodes),
754 cycleChecker(acceptedNodes, rejectedNodes));
755 return !cycleChecker(acceptedNodes, rejectedNodes);
756 },
757 [](const std::vector<std::vector<ade::NodeHandle>>& subgraphs)
758 {
759 ade::SubgraphSelectResult ret;
760 ret.index = getLongestSubgraph(subgraphs);
761 ret.continueSelect = true;
762 return ret;
763 });
764 auto subgraphs2 = ade::selectAllSubgraphs(
765 nodes2,
766 [&](
767 const ade::EdgeHandle& edge,
768 const ade::SubgraphMergeDirection dir)
769 {
770 auto dstNode = ade::getDstMergeNode(edge, dir);
771 ADE_ASSERT(nullptr != dstNode);
772 return ade::util::contains(nodes2, dstNode);
773 },
774 [&](
775 const ade::subgraphs::NodesSet& acceptedNodes,
776 const ade::subgraphs::NodesSet& rejectedNodes)
777 {
778 EXPECT_EQ(hasCycle(acceptedNodes, rejectedNodes),
779 cycleChecker(acceptedNodes, rejectedNodes));
780 return !cycleChecker(acceptedNodes, rejectedNodes);
781 },
782 [](const std::vector<std::vector<ade::NodeHandle>>& subgraphs)
783 {
784 ade::SubgraphSelectResult ret;
785 ret.index = getLongestSubgraph(subgraphs);
786 ret.continueSelect = true;
787 return ret;
788 });
789 ASSERT_EQ(1, subgraphs1.size());
790 ASSERT_EQ(2, subgraphs2.size());
791
792 EXPECT_EQ((node_set{nodes[1],nodes[2],nodes[3],nodes[5],nodes[6]}),
793 node_set(subgraphs1[0].begin(), subgraphs1[0].end()));
794
795 EXPECT_EQ((node_set{nodes[4],nodes[7],nodes[8],nodes[9]}),
796 node_set(subgraphs2[0].begin(), subgraphs2[0].end()));
797 EXPECT_EQ((node_set{nodes[0]}),
798 node_set(subgraphs2[1].begin(), subgraphs2[1].end()));
799 }
800
TEST(Helpers,SelectAllSubgraphs2)801 TEST(Helpers, SelectAllSubgraphs2)
802 {
803 // 0 1
804 // | |
805 // 2 3
806 // \ / \
807 // 4 5
808 // | |
809 // 6 7
810 // / \ /
811 // 8 9
812 // | |
813 // 10 11
814 // \ /
815 // 12
816
817 ade::Graph gr;
818 std::vector<ade::NodeHandle> nodes;
819 for (auto i : ade::util::iota(13))
820 {
821 (void)i;
822 nodes.push_back(gr.createNode());
823 }
824 gr.link(nodes[0], nodes[2]);
825 gr.link(nodes[1], nodes[3]);
826 gr.link(nodes[2], nodes[4]);
827 gr.link(nodes[3], nodes[4]);
828 gr.link(nodes[3], nodes[5]);
829 gr.link(nodes[4], nodes[6]);
830 gr.link(nodes[5], nodes[7]);
831 gr.link(nodes[6], nodes[8]);
832 gr.link(nodes[6], nodes[9]);
833 gr.link(nodes[7], nodes[9]);
834 gr.link(nodes[8], nodes[10]);
835 gr.link(nodes[9], nodes[11]);
836 gr.link(nodes[10], nodes[12]);
837 gr.link(nodes[11], nodes[12]);
838
839 ade::subgraphs::NodesSet nodes1;
840 ade::subgraphs::NodesSet nodes2;
841 for (auto i : ade::util::iota(std::size_t(13)))
842 {
843 if (5 == i || 7 == i || 8 == i || 10 == i)
844 {
845 nodes2.insert(nodes[i]);
846 }
847 else
848 {
849 nodes1.insert(nodes[i]);
850 }
851 }
852
853 ade::SubgraphSelfReferenceChecker cycleChecker(nodes);
854 auto subgraphs1 = ade::selectAllSubgraphs(
855 nodes1,
856 [&](
857 const ade::EdgeHandle& edge,
858 const ade::SubgraphMergeDirection dir)
859 {
860 auto dstNode = ade::getDstMergeNode(edge, dir);
861 ADE_ASSERT(nullptr != dstNode);
862 return ade::util::contains(nodes1, dstNode);
863 },
864 [&](
865 const ade::subgraphs::NodesSet& acceptedNodes,
866 const ade::subgraphs::NodesSet& rejectedNodes)
867 {
868 EXPECT_EQ(hasCycle(acceptedNodes, rejectedNodes),
869 cycleChecker(acceptedNodes, rejectedNodes));
870 return !cycleChecker(acceptedNodes, rejectedNodes);
871 },
872 [](const std::vector<std::vector<ade::NodeHandle>>& subgraphs)
873 {
874 ade::SubgraphSelectResult ret;
875 ret.index = getLongestSubgraph(subgraphs);
876 ret.continueSelect = false;
877 return ret;
878 });
879 auto subgraphs2 = ade::selectAllSubgraphs(
880 nodes2,
881 [&](
882 const ade::EdgeHandle& /*edge*/,
883 const ade::SubgraphMergeDirection /*dir*/)
884 {
885 return true;
886 },
887 [&](
888 const ade::subgraphs::NodesSet& acceptedNodes,
889 const ade::subgraphs::NodesSet& rejectedNodes)
890 {
891 EXPECT_EQ(hasCycle(acceptedNodes, rejectedNodes),
892 cycleChecker(acceptedNodes, rejectedNodes));
893 return !cycleChecker(acceptedNodes, rejectedNodes);
894 },
895 [](const std::vector<std::vector<ade::NodeHandle>>& subgraphs)
896 {
897 ade::SubgraphSelectResult ret;
898 ret.index = getLongestSubgraph(subgraphs);
899 ret.continueSelect = true;
900 return ret;
901 });
902 ASSERT_EQ(1, subgraphs1.size());
903 ASSERT_EQ(2, subgraphs2.size());
904
905 EXPECT_EQ((node_set{nodes[0],nodes[2],nodes[4],nodes[3],nodes[1],nodes[6]}),
906 node_set(subgraphs1[0].begin(), subgraphs1[0].end()));
907
908 // EXPECT_EQ((node_set{nodes[5],nodes[7],nodes[9],nodes[11]}),
909 // node_set(subgraphs2[0].begin(), subgraphs2[0].end()));
910 // EXPECT_EQ((node_set{nodes[8],nodes[10],nodes[12]}),
911 // node_set(subgraphs2[1].begin(), subgraphs2[1].end()));
912 }
913
TEST(Helpers,FindPaths1)914 TEST(Helpers, FindPaths1)
915 {
916 // 0
917 // |
918 // 1
919 // / \
920 // 2 3
921 // | |
922 // 4 5
923 // \ /
924 // 6
925 // |
926 // 7
927
928 ade::Graph gr;
929 ade::NodeHandle nodes[] = {
930 gr.createNode(),
931 gr.createNode(),
932 gr.createNode(),
933 gr.createNode(),
934 gr.createNode(),
935 gr.createNode(),
936 gr.createNode(),
937 gr.createNode()};
938 gr.link(nodes[0], nodes[1]);
939 gr.link(nodes[1], nodes[2]);
940 gr.link(nodes[1], nodes[3]);
941 gr.link(nodes[2], nodes[4]);
942 gr.link(nodes[3], nodes[5]);
943 gr.link(nodes[4], nodes[6]);
944 gr.link(nodes[5], nodes[6]);
945 gr.link(nodes[6], nodes[7]);
946
947 std::vector<std::vector<ade::NodeHandle>> resPaths = {
948 {nodes[0],nodes[1],nodes[2],nodes[4],nodes[6],nodes[7]},
949 {nodes[0],nodes[1],nodes[3],nodes[5],nodes[6],nodes[7]}};
950 sort_subgraphs(resPaths);
951
952 {
953 std::vector<std::vector<ade::NodeHandle>> paths;
954 ade::findPaths(nodes[0], nodes[7], [&](const std::vector<ade::NodeHandle>& path)
955 {
956 paths.push_back(path);
957 return false;
958 });
959 ASSERT_EQ(2, paths.size());
960 sort_subgraphs(paths);
961
962 EXPECT_EQ(resPaths, paths);
963 }
964
965 {
966 std::vector<std::vector<ade::NodeHandle>> paths;
967 ade::findPaths(nodes[0], nodes[7], [&](const std::vector<ade::NodeHandle>& path)
968 {
969 paths.push_back(path);
970 return true;
971 });
972 ASSERT_EQ(1, paths.size());
973
974 EXPECT_TRUE((paths[0] == resPaths[0]) ||
975 (paths[0] == resPaths[1]));
976 }
977
978 {
979 std::vector<std::vector<ade::NodeHandle>> paths;
980 ade::findBiPaths(nodes[7], nodes[0], [&](const std::vector<ade::NodeHandle>& path)
981 {
982 paths.push_back(path);
983 return false;
984 });
985 ASSERT_EQ(2, paths.size());
986 sort_subgraphs(paths);
987
988 EXPECT_EQ(resPaths, paths);
989 }
990 }
991
TEST(Helpers,FindPaths2)992 TEST(Helpers, FindPaths2)
993 {
994 // 0
995 // |
996 // 1
997 // / \
998 // 2 3
999 // | / \
1000 // 4 5 6
1001 // \ | /
1002 // 7
1003 // |
1004 // 8
1005
1006 ade::Graph gr;
1007 ade::NodeHandle nodes[] = {
1008 gr.createNode(),
1009 gr.createNode(),
1010 gr.createNode(),
1011 gr.createNode(),
1012 gr.createNode(),
1013 gr.createNode(),
1014 gr.createNode(),
1015 gr.createNode(),
1016 gr.createNode()};
1017 gr.link(nodes[0], nodes[1]);
1018 gr.link(nodes[1], nodes[2]);
1019 gr.link(nodes[1], nodes[3]);
1020 gr.link(nodes[2], nodes[4]);
1021 gr.link(nodes[3], nodes[5]);
1022 gr.link(nodes[3], nodes[6]);
1023 gr.link(nodes[4], nodes[7]);
1024 gr.link(nodes[5], nodes[7]);
1025 gr.link(nodes[6], nodes[7]);
1026 gr.link(nodes[7], nodes[8]);
1027
1028 std::vector<std::vector<ade::NodeHandle>> resPaths = {
1029 {nodes[0],nodes[1],nodes[2],nodes[4],nodes[7],nodes[8]},
1030 {nodes[0],nodes[1],nodes[3],nodes[5],nodes[7],nodes[8]},
1031 {nodes[0],nodes[1],nodes[3],nodes[6],nodes[7],nodes[8]}};
1032 sort_subgraphs(resPaths);
1033
1034 {
1035 std::vector<std::vector<ade::NodeHandle>> paths;
1036 ade::findPaths(nodes[0], nodes[8], [&](const std::vector<ade::NodeHandle>& path)
1037 {
1038 paths.push_back(path);
1039 return false;
1040 });
1041 ASSERT_EQ(3, paths.size());
1042 sort_subgraphs(paths);
1043
1044 EXPECT_EQ(resPaths, paths);
1045 }
1046
1047 {
1048 std::vector<std::vector<ade::NodeHandle>> paths;
1049 ade::findPaths(nodes[0], nodes[8], [&](const std::vector<ade::NodeHandle>& path)
1050 {
1051 paths.push_back(path);
1052 return true;
1053 });
1054 ASSERT_EQ(1, paths.size());
1055
1056 EXPECT_TRUE((paths[0] == resPaths[0]) ||
1057 (paths[0] == resPaths[1]) ||
1058 (paths[0] == resPaths[2]));
1059 }
1060
1061 {
1062 std::vector<std::vector<ade::NodeHandle>> paths;
1063 ade::findBiPaths(nodes[8], nodes[0], [&](const std::vector<ade::NodeHandle>& path)
1064 {
1065 paths.push_back(path);
1066 return false;
1067 });
1068 ASSERT_EQ(3, paths.size());
1069 sort_subgraphs(paths);
1070
1071 EXPECT_EQ(resPaths, paths);
1072 }
1073 }
1074