1 /* Copyright (c) 2017-2023. The SimGrid Team. All rights reserved. */
3 /* This program is free software; you can redistribute it and/or modify it
4 * under the terms of the license (GNU LGPL) which comes with this package. */
6 #include "src/3rd-party/catch.hpp"
7 #include "src/mc/explo/udpor/Configuration.hpp"
8 #include "src/mc/explo/udpor/EventSet.hpp"
9 #include "src/mc/explo/udpor/History.hpp"
10 #include "src/mc/explo/udpor/UnfoldingEvent.hpp"
11 #include "src/mc/explo/udpor/maximal_subsets_iterator.hpp"
13 #include <unordered_map>
15 using namespace simgrid::mc::udpor;
17 TEST_CASE("simgrid::mc::udpor::Configuration: Constructing Configurations")
19 // The following tests concern the given event structure:
28 UnfoldingEvent e2{&e1};
29 UnfoldingEvent e3{&e2};
30 UnfoldingEvent e4{&e3};
31 UnfoldingEvent e5{&e3};
33 SECTION("Creating a configuration without events")
36 REQUIRE(C.get_events().empty());
37 REQUIRE(C.get_latest_event() == nullptr);
40 SECTION("Creating a configuration with events")
42 // 5 choose 0 = 1 test
43 REQUIRE_NOTHROW(Configuration({&e1}));
45 // 5 choose 1 = 5 tests
46 REQUIRE_THROWS_AS(Configuration({&e2}), std::invalid_argument);
47 REQUIRE_THROWS_AS(Configuration({&e3}), std::invalid_argument);
48 REQUIRE_THROWS_AS(Configuration({&e4}), std::invalid_argument);
49 REQUIRE_THROWS_AS(Configuration({&e5}), std::invalid_argument);
51 // 5 choose 2 = 10 tests
52 REQUIRE_NOTHROW(Configuration({&e1, &e2}));
53 REQUIRE_THROWS_AS(Configuration({&e1, &e3}), std::invalid_argument);
54 REQUIRE_THROWS_AS(Configuration({&e1, &e4}), std::invalid_argument);
55 REQUIRE_THROWS_AS(Configuration({&e1, &e5}), std::invalid_argument);
56 REQUIRE_THROWS_AS(Configuration({&e2, &e3}), std::invalid_argument);
57 REQUIRE_THROWS_AS(Configuration({&e2, &e4}), std::invalid_argument);
58 REQUIRE_THROWS_AS(Configuration({&e2, &e5}), std::invalid_argument);
59 REQUIRE_THROWS_AS(Configuration({&e3, &e4}), std::invalid_argument);
60 REQUIRE_THROWS_AS(Configuration({&e3, &e5}), std::invalid_argument);
61 REQUIRE_THROWS_AS(Configuration({&e4, &e5}), std::invalid_argument);
63 // 5 choose 3 = 10 tests
64 REQUIRE_NOTHROW(Configuration({&e1, &e2, &e3}));
65 REQUIRE_THROWS_AS(Configuration({&e1, &e2, &e4}), std::invalid_argument);
66 REQUIRE_THROWS_AS(Configuration({&e1, &e2, &e5}), std::invalid_argument);
67 REQUIRE_THROWS_AS(Configuration({&e1, &e3, &e4}), std::invalid_argument);
68 REQUIRE_THROWS_AS(Configuration({&e1, &e3, &e5}), std::invalid_argument);
69 REQUIRE_THROWS_AS(Configuration({&e1, &e4, &e5}), std::invalid_argument);
70 REQUIRE_THROWS_AS(Configuration({&e2, &e3, &e4}), std::invalid_argument);
71 REQUIRE_THROWS_AS(Configuration({&e2, &e3, &e5}), std::invalid_argument);
72 REQUIRE_THROWS_AS(Configuration({&e2, &e4, &e5}), std::invalid_argument);
73 REQUIRE_THROWS_AS(Configuration({&e3, &e4, &e5}), std::invalid_argument);
75 // 5 choose 4 = 5 tests
76 REQUIRE_NOTHROW(Configuration({&e1, &e2, &e3, &e4}));
77 REQUIRE_NOTHROW(Configuration({&e1, &e2, &e3, &e5}));
78 REQUIRE_THROWS_AS(Configuration({&e1, &e2, &e4, &e5}), std::invalid_argument);
79 REQUIRE_THROWS_AS(Configuration({&e1, &e3, &e4, &e5}), std::invalid_argument);
80 REQUIRE_THROWS_AS(Configuration({&e2, &e3, &e4, &e5}), std::invalid_argument);
82 // 5 choose 5 = 1 test
83 REQUIRE_NOTHROW(Configuration({&e1, &e2, &e3, &e4, &e5}));
87 TEST_CASE("simgrid::mc::udpor::Configuration: Adding Events")
89 // The following tests concern the given event structure:
97 UnfoldingEvent e2{&e1};
98 UnfoldingEvent e3{&e2};
99 UnfoldingEvent e4{&e2};
101 REQUIRE_THROWS_AS(Configuration().add_event(nullptr), std::invalid_argument);
102 REQUIRE_THROWS_AS(Configuration().add_event(&e2), std::invalid_argument);
103 REQUIRE_THROWS_AS(Configuration().add_event(&e3), std::invalid_argument);
104 REQUIRE_THROWS_AS(Configuration().add_event(&e4), std::invalid_argument);
105 REQUIRE_THROWS_AS(Configuration({&e1}).add_event(&e3), std::invalid_argument);
106 REQUIRE_THROWS_AS(Configuration({&e1}).add_event(&e4), std::invalid_argument);
108 REQUIRE_NOTHROW(Configuration().add_event(&e1));
109 REQUIRE_NOTHROW(Configuration({&e1}).add_event(&e1));
110 REQUIRE_NOTHROW(Configuration({&e1}).add_event(&e2));
111 REQUIRE_NOTHROW(Configuration({&e1, &e2}).add_event(&e1));
112 REQUIRE_NOTHROW(Configuration({&e1, &e2}).add_event(&e2));
113 REQUIRE_NOTHROW(Configuration({&e1, &e2}).add_event(&e3));
114 REQUIRE_NOTHROW(Configuration({&e1, &e2}).add_event(&e4));
115 REQUIRE_NOTHROW(Configuration({&e1, &e2, &e3}).add_event(&e1));
116 REQUIRE_NOTHROW(Configuration({&e1, &e2, &e3}).add_event(&e2));
117 REQUIRE_NOTHROW(Configuration({&e1, &e2, &e3}).add_event(&e3));
118 REQUIRE_NOTHROW(Configuration({&e1, &e2, &e3}).add_event(&e4));
119 REQUIRE_NOTHROW(Configuration({&e1, &e2, &e4}).add_event(&e1));
120 REQUIRE_NOTHROW(Configuration({&e1, &e2, &e4}).add_event(&e2));
121 REQUIRE_NOTHROW(Configuration({&e1, &e2, &e4}).add_event(&e3));
122 REQUIRE_NOTHROW(Configuration({&e1, &e2, &e4}).add_event(&e4));
123 REQUIRE_NOTHROW(Configuration({&e1, &e2, &e3, &e4}).add_event(&e1));
124 REQUIRE_NOTHROW(Configuration({&e1, &e2, &e3, &e4}).add_event(&e2));
125 REQUIRE_NOTHROW(Configuration({&e1, &e2, &e3, &e4}).add_event(&e3));
126 REQUIRE_NOTHROW(Configuration({&e1, &e2, &e3, &e4}).add_event(&e4));
129 TEST_CASE("simgrid::mc::udpor::Configuration: Topological Sort Order")
131 // The following tests concern the given event structure:
140 UnfoldingEvent e2{&e1};
141 UnfoldingEvent e3{&e2};
142 UnfoldingEvent e4{&e3};
144 SECTION("Topological ordering for entire set")
146 Configuration C{&e1, &e2, &e3, &e4};
147 REQUIRE(C.get_topologically_sorted_events() == std::vector<const UnfoldingEvent*>{&e1, &e2, &e3, &e4});
148 REQUIRE(C.get_topologically_sorted_events_of_reverse_graph() ==
149 std::vector<const UnfoldingEvent*>{&e4, &e3, &e2, &e1});
152 SECTION("Topological ordering for subsets")
154 SECTION("No elements")
157 REQUIRE(C.get_topologically_sorted_events() == std::vector<const UnfoldingEvent*>{});
158 REQUIRE(C.get_topologically_sorted_events_of_reverse_graph() == std::vector<const UnfoldingEvent*>{});
163 Configuration C{&e1};
164 REQUIRE(C.get_topologically_sorted_events() == std::vector<const UnfoldingEvent*>{&e1});
165 REQUIRE(C.get_topologically_sorted_events_of_reverse_graph() == std::vector<const UnfoldingEvent*>{&e1});
168 SECTION("e1 and e2 only")
170 Configuration C{&e1, &e2};
171 REQUIRE(C.get_topologically_sorted_events() == std::vector<const UnfoldingEvent*>{&e1, &e2});
172 REQUIRE(C.get_topologically_sorted_events_of_reverse_graph() == std::vector<const UnfoldingEvent*>{&e2, &e1});
175 SECTION("e1, e2, and e3 only")
177 Configuration C{&e1, &e2, &e3};
178 REQUIRE(C.get_topologically_sorted_events() == std::vector<const UnfoldingEvent*>{&e1, &e2, &e3});
179 REQUIRE(C.get_topologically_sorted_events_of_reverse_graph() ==
180 std::vector<const UnfoldingEvent*>{&e3, &e2, &e1});
185 TEST_CASE("simgrid::mc::udpor::Configuration: Topological Sort Order More Complicated")
187 // The following tests concern the given event structure:
198 UnfoldingEvent e2{&e1};
199 UnfoldingEvent e3{&e2};
200 UnfoldingEvent e4{&e3};
201 UnfoldingEvent e5{&e4};
202 UnfoldingEvent e6{&e3};
204 SECTION("Topological ordering for subsets")
206 SECTION("No elements")
209 REQUIRE(C.get_topologically_sorted_events() == std::vector<const UnfoldingEvent*>{});
210 REQUIRE(C.get_topologically_sorted_events_of_reverse_graph() == std::vector<const UnfoldingEvent*>{});
215 Configuration C{&e1};
216 REQUIRE(C.get_topologically_sorted_events() == std::vector<const UnfoldingEvent*>{&e1});
217 REQUIRE(C.get_topologically_sorted_events_of_reverse_graph() == std::vector<const UnfoldingEvent*>{&e1});
220 SECTION("e1 and e2 only")
222 Configuration C{&e1, &e2};
223 REQUIRE(C.get_topologically_sorted_events() == std::vector<const UnfoldingEvent*>{&e1, &e2});
224 REQUIRE(C.get_topologically_sorted_events_of_reverse_graph() == std::vector<const UnfoldingEvent*>{&e2, &e1});
227 SECTION("e1, e2, and e3 only")
229 Configuration C{&e1, &e2, &e3};
230 REQUIRE(C.get_topologically_sorted_events() == std::vector<const UnfoldingEvent*>{&e1, &e2, &e3});
231 REQUIRE(C.get_topologically_sorted_events_of_reverse_graph() ==
232 std::vector<const UnfoldingEvent*>{&e3, &e2, &e1});
235 SECTION("e1, e2, e3, and e6 only")
237 Configuration C{&e1, &e2, &e3, &e6};
238 REQUIRE(C.get_topologically_sorted_events() == std::vector<const UnfoldingEvent*>{&e1, &e2, &e3, &e6});
239 REQUIRE(C.get_topologically_sorted_events_of_reverse_graph() ==
240 std::vector<const UnfoldingEvent*>{&e6, &e3, &e2, &e1});
243 SECTION("e1, e2, e3, and e4 only")
245 Configuration C{&e1, &e2, &e3, &e4};
246 REQUIRE(C.get_topologically_sorted_events() == std::vector<const UnfoldingEvent*>{&e1, &e2, &e3, &e4});
247 REQUIRE(C.get_topologically_sorted_events_of_reverse_graph() ==
248 std::vector<const UnfoldingEvent*>{&e4, &e3, &e2, &e1});
251 SECTION("e1, e2, e3, e4, and e5 only")
253 Configuration C{&e1, &e2, &e3, &e4, &e5};
254 REQUIRE(C.get_topologically_sorted_events() == std::vector<const UnfoldingEvent*>{&e1, &e2, &e3, &e4, &e5});
255 REQUIRE(C.get_topologically_sorted_events_of_reverse_graph() ==
256 std::vector<const UnfoldingEvent*>{&e5, &e4, &e3, &e2, &e1});
259 SECTION("e1, e2, e3, e4 and e6 only")
261 // In this case, e4 and e6 are interchangeable. Hence, we have to check
262 // if the sorting gives us *any* of the combinations
263 Configuration C{&e1, &e2, &e3, &e4, &e6};
264 REQUIRE((C.get_topologically_sorted_events() == std::vector<const UnfoldingEvent*>{&e1, &e2, &e3, &e4, &e6} ||
265 C.get_topologically_sorted_events() == std::vector<const UnfoldingEvent*>{&e1, &e2, &e3, &e6, &e4}));
266 REQUIRE((C.get_topologically_sorted_events_of_reverse_graph() ==
267 std::vector<const UnfoldingEvent*>{&e6, &e4, &e3, &e2, &e1} ||
268 C.get_topologically_sorted_events_of_reverse_graph() ==
269 std::vector<const UnfoldingEvent*>{&e4, &e6, &e3, &e2, &e1}));
272 SECTION("Topological ordering for entire set")
274 // In this case, e4/e5 are both interchangeable with e6. Hence, again we have to check
275 // if the sorting gives us *any* of the combinations
276 Configuration C{&e1, &e2, &e3, &e4, &e5, &e6};
278 (C.get_topologically_sorted_events() == std::vector<const UnfoldingEvent*>{&e1, &e2, &e3, &e4, &e5, &e6} ||
279 C.get_topologically_sorted_events() == std::vector<const UnfoldingEvent*>{&e1, &e2, &e3, &e4, &e6, &e5} ||
280 C.get_topologically_sorted_events() == std::vector<const UnfoldingEvent*>{&e1, &e2, &e3, &e6, &e4, &e5}));
281 REQUIRE((C.get_topologically_sorted_events_of_reverse_graph() ==
282 std::vector<const UnfoldingEvent*>{&e6, &e5, &e4, &e3, &e2, &e1} ||
283 C.get_topologically_sorted_events_of_reverse_graph() ==
284 std::vector<const UnfoldingEvent*>{&e5, &e6, &e4, &e3, &e2, &e1} ||
285 C.get_topologically_sorted_events_of_reverse_graph() ==
286 std::vector<const UnfoldingEvent*>{&e5, &e4, &e6, &e3, &e2, &e1}));
291 TEST_CASE("simgrid::mc::udpor::Configuration: Topological Sort Order Very Complicated")
293 // The following tests concern the given event structure:
307 UnfoldingEvent e2{&e1};
308 UnfoldingEvent e8{&e1};
309 UnfoldingEvent e3{&e2};
310 UnfoldingEvent e4{&e3};
311 UnfoldingEvent e5{&e4};
312 UnfoldingEvent e6{&e4};
313 UnfoldingEvent e7{&e2, &e8};
314 UnfoldingEvent e9{&e6, &e7};
315 UnfoldingEvent e10{&e7};
316 UnfoldingEvent e11{&e8};
317 UnfoldingEvent e12{&e5, &e9, &e10};
318 Configuration C{&e1, &e2, &e3, &e4, &e5, &e6, &e7, &e8, &e9, &e10, &e11, &e12};
320 SECTION("Test every combination of the maximal configuration (forward graph)")
322 // To test this, we ensure that for the `i`th event
323 // in `ordered_events`, each event in `ordered_events[0...<i]
324 // is contained in the history of `ordered_events[i]`.
325 EventSet events_seen;
326 const auto ordered_events = C.get_topologically_sorted_events();
328 std::for_each(ordered_events.begin(), ordered_events.end(), [&events_seen](const UnfoldingEvent* e) {
330 for (auto* e_hist : history) {
331 // In this demo, we want to make sure that
332 // we don't mark not yet seeing `e` as an error.
333 // The history of `e` traverses `e` itself. All
334 // other events in e's history are included in
338 // If this event has not been "seen" before,
339 // this implies that event `e` appears earlier
340 // in the list than one of its dependencies
341 REQUIRE(events_seen.contains(e_hist));
343 events_seen.insert(e);
347 SECTION("Test every combination of the maximal configuration (reverse graph)")
349 // To test this, we ensure that for the `i`th event
350 // in `ordered_events`, no event in `ordered_events[0...<i]
351 // is contained in the history of `ordered_events[i]`.
352 EventSet events_seen;
353 const auto ordered_events = C.get_topologically_sorted_events_of_reverse_graph();
355 std::for_each(ordered_events.begin(), ordered_events.end(), [&events_seen](const UnfoldingEvent* e) {
358 for (auto* e_hist : history) {
359 // Unlike the test above, we DO want to ensure
360 // that `e` itself ALSO isn't yet seen
362 // If this event has been "seen" before,
363 // this implies that event `e` appears later
364 // in the list than one of its ancestors
365 REQUIRE_FALSE(events_seen.contains(e_hist));
367 events_seen.insert(e);
371 SECTION("Test that the topological ordering contains only the events of the configuration")
373 const EventSet events_seen = C.get_events();
375 SECTION("Forward direction")
377 auto ordered_events = C.get_topologically_sorted_events();
378 const EventSet ordered_event_set = EventSet(std::move(ordered_events));
379 REQUIRE(events_seen == ordered_event_set);
382 SECTION("Reverse direction")
384 auto ordered_events = C.get_topologically_sorted_events_of_reverse_graph();
385 const EventSet ordered_event_set = EventSet(std::move(ordered_events));
386 REQUIRE(events_seen == ordered_event_set);
391 TEST_CASE("simgrid::mc::udpor::maximal_subsets_iterator: Basic Testing of Maximal Subsets")
393 // The following tests concern the given event structure:
402 UnfoldingEvent e2{&e1};
403 UnfoldingEvent e3{&e2};
404 UnfoldingEvent e4{&e3};
405 UnfoldingEvent e5{&e1};
406 UnfoldingEvent e6{&e5};
407 UnfoldingEvent e7{&e6};
408 UnfoldingEvent e8{&e6};
410 SECTION("Iteration over an empty configuration yields only the empty set")
413 maximal_subsets_iterator first(C);
414 maximal_subsets_iterator last;
416 REQUIRE(*first == EventSet());
418 REQUIRE(first == last);
421 SECTION("Check counts of maximal event sets discovered")
423 std::unordered_map<int, int> maximal_subset_counts;
425 Configuration C{&e1, &e2, &e3, &e4, &e5, &e6, &e7, &e8};
426 maximal_subsets_iterator first(C);
427 maximal_subsets_iterator last;
429 for (; first != last; ++first) {
430 maximal_subset_counts[(*first).size()]++;
433 // First, ensure that there are only sets of size 0, 1, 2, and 3
434 CHECK(maximal_subset_counts.size() == 4);
436 // The empty set should appear only once
437 REQUIRE(maximal_subset_counts[0] == 1);
439 // 8 is the number of nodes in the graph
440 REQUIRE(maximal_subset_counts[1] == 8);
442 // 13 = 3 * 4 (each of the left branch can combine with one in the right branch) + 1 (e7 + e8)
443 REQUIRE(maximal_subset_counts[2] == 13);
445 // e7 + e8 must be included, so that means we can combine from the left branch
446 REQUIRE(maximal_subset_counts[3] == 3);
449 SECTION("Check counts of maximal event sets discovered with a filter")
451 std::unordered_map<int, int> maximal_subset_counts;
453 Configuration C{&e1, &e2, &e3, &e4, &e5, &e6, &e7, &e8};
455 SECTION("Filter with events part of initial maximal set")
457 EventSet interesting_bunch{&e2, &e4, &e7, &e8};
459 maximal_subsets_iterator first(C, [&](const UnfoldingEvent* e) { return interesting_bunch.contains(e); });
460 maximal_subsets_iterator last;
462 for (; first != last; ++first) {
463 const auto& event_set = *first;
464 // Only events in `interesting_bunch` can appear: thus no set
465 // should include anything else other than `interesting_bunch`
466 REQUIRE(event_set.is_subset_of(interesting_bunch));
467 REQUIRE(event_set.is_maximal());
468 maximal_subset_counts[event_set.size()]++;
471 // The empty set should (still) appear only once
472 REQUIRE(maximal_subset_counts[0] == 1);
474 // 4 is the number of nodes in the `interesting_bunch`
475 REQUIRE(maximal_subset_counts[1] == 4);
477 // 5 = 2 * 2 (each of the left branch can combine with one in the right branch) + 1 (e7 + e8)
478 REQUIRE(maximal_subset_counts[2] == 5);
480 // e7 + e8 must be included, so that means we can combine from the left branch (only e2 and e4)
481 REQUIRE(maximal_subset_counts[3] == 2);
483 // There are no subsets of size 4 (or higher, but that
484 // is tested by asserting each maximal set traversed is a subset)
485 REQUIRE(maximal_subset_counts[4] == 0);
488 SECTION("Filter with interesting subset not initially part of the maximal set")
490 EventSet interesting_bunch{&e3, &e5, &e6};
492 maximal_subsets_iterator first(C, [&](const UnfoldingEvent* e) { return interesting_bunch.contains(e); });
493 maximal_subsets_iterator last;
495 for (; first != last; ++first) {
496 const auto& event_set = *first;
497 // Only events in `interesting_bunch` can appear: thus no set
498 // should include anything else other than `interesting_bunch`
499 REQUIRE(event_set.is_subset_of(interesting_bunch));
500 REQUIRE(event_set.is_maximal());
501 maximal_subset_counts[event_set.size()]++;
504 // The empty set should (still) appear only once
505 REQUIRE(maximal_subset_counts[0] == 1);
507 // 3 is the number of nodes in the `interesting_bunch`
508 REQUIRE(maximal_subset_counts[1] == 3);
510 // 2 = e3, e5 and e3, e6
511 REQUIRE(maximal_subset_counts[2] == 2);
513 // There are no subsets of size 3 (or higher, but that
514 // is tested by asserting each maximal set traversed is a subset)
515 REQUIRE(maximal_subset_counts[3] == 0);
520 TEST_CASE("simgrid::mc::udpor::maximal_subsets_iterator: Stress Test for Maximal Subsets Iteration")
522 // The following tests concern the given event structure:
527 // +------* e4 *e5 e6 e7
531 // | e11 e12 e13 e14 e15
535 UnfoldingEvent e2{&e1};
536 UnfoldingEvent e3{&e1};
537 UnfoldingEvent e4{&e2};
538 UnfoldingEvent e5{&e2};
539 UnfoldingEvent e6{&e3};
540 UnfoldingEvent e7{&e3};
541 UnfoldingEvent e8{&e4};
542 UnfoldingEvent e9{&e4, &e5, &e6};
543 UnfoldingEvent e10{&e6, &e7};
544 UnfoldingEvent e11{&e8};
545 UnfoldingEvent e12{&e8};
546 UnfoldingEvent e13{&e9};
547 UnfoldingEvent e14{&e9};
548 UnfoldingEvent e15{&e10};
549 UnfoldingEvent e16{&e5, &e11};
550 UnfoldingEvent e17{&e12, &e13, &e14};
551 UnfoldingEvent e18{&e14, &e15};
552 Configuration C{&e1, &e2, &e3, &e4, &e5, &e6, &e7, &e8, &e9, &e10, &e11, &e12, &e13, &e14, &e15, &e16, &e17, &e18};
554 SECTION("Every subset iterated over is maximal")
556 maximal_subsets_iterator first(C);
557 maximal_subsets_iterator last;
559 // Make sure we actually have something to iterate over
560 REQUIRE(first != last);
562 for (; first != last; ++first) {
563 REQUIRE((*first).size() <= C.get_events().size());
564 REQUIRE((*first).is_maximal());