src/mc/explo/udpor/Configuration_test.cpp

   1 /* Copyright (c) 2017-2023. The SimGrid Team. All rights reserved.               */
   2
   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. */
   5
   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"
  12
  13 #include <unordered_map>
  14
  15 using namespace simgrid::mc::udpor;
  16
  17 TEST_CASE("simgrid::mc::udpor::Configuration: Constructing Configurations")
  18 {
  19   // The following tests concern the given event structure:
  20   //                e1
  21   //              /
  22   //            e2
  23   //           /
  24   //          e3
  25   //         /  /
  26   //        e4   e5
  27   UnfoldingEvent e1;
  28   UnfoldingEvent e2{&e1};
  29   UnfoldingEvent e3{&e2};
  30   UnfoldingEvent e4{&e3};
  31   UnfoldingEvent e5{&e3};
  32
  33   SECTION("Creating a configuration without events")
  34   {
  35     Configuration C;
  36     REQUIRE(C.get_events().empty());
  37     REQUIRE(C.get_latest_event() == nullptr);
  38   }
  39
  40   SECTION("Creating a configuration with events")
  41   {
  42     // 5 choose 0 = 1 test
  43     REQUIRE_NOTHROW(Configuration({&e1}));
  44
  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);
  50
  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);
  62
  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);
  74
  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);
  81
  82     // 5 choose 5 = 1 test
  83     REQUIRE_NOTHROW(Configuration({&e1, &e2, &e3, &e4, &e5}));
  84   }
  85 }
  86
  87 TEST_CASE("simgrid::mc::udpor::Configuration: Adding Events")
  88 {
  89   // The following tests concern the given event structure:
  90   //                e1
  91   //              /
  92   //            e2
  93   //           /
  94   //         /  /
  95   //        e3   e4
  96   UnfoldingEvent e1;
  97   UnfoldingEvent e2{&e1};
  98   UnfoldingEvent e3{&e2};
  99   UnfoldingEvent e4{&e2};
 100
 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);
 107
 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));
 127 }
 128
 129 TEST_CASE("simgrid::mc::udpor::Configuration: Topological Sort Order")
 130 {
 131   // The following tests concern the given event structure:
 132   //               e1
 133   //              /
 134   //            e2
 135   //           /
 136   //          e3
 137   //         /
 138   //        e4
 139   UnfoldingEvent e1;
 140   UnfoldingEvent e2{&e1};
 141   UnfoldingEvent e3{&e2};
 142   UnfoldingEvent e4{&e3};
 143
 144   SECTION("Topological ordering for entire set")
 145   {
 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});
 150   }
 151
 152   SECTION("Topological ordering for subsets")
 153   {
 154     SECTION("No elements")
 155     {
 156       Configuration C;
 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*>{});
 159     }
 160
 161     SECTION("e1 only")
 162     {
 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});
 166     }
 167
 168     SECTION("e1 and e2 only")
 169     {
 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});
 173     }
 174
 175     SECTION("e1, e2, and e3 only")
 176     {
 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});
 181     }
 182   }
 183 }
 184
 185 TEST_CASE("simgrid::mc::udpor::Configuration: Topological Sort Order More Complicated")
 186 {
 187   // The following tests concern the given event structure:
 188   //                e1
 189   //              /
 190   //            e2
 191   //           /
 192   //          e3
 193   //         /  /
 194   //        e4   e6
 195   //        /
 196   //       e5
 197   UnfoldingEvent e1;
 198   UnfoldingEvent e2{&e1};
 199   UnfoldingEvent e3{&e2};
 200   UnfoldingEvent e4{&e3};
 201   UnfoldingEvent e5{&e4};
 202   UnfoldingEvent e6{&e3};
 203
 204   SECTION("Topological ordering for subsets")
 205   {
 206     SECTION("No elements")
 207     {
 208       Configuration C;
 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*>{});
 211     }
 212
 213     SECTION("e1 only")
 214     {
 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});
 218     }
 219
 220     SECTION("e1 and e2 only")
 221     {
 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});
 225     }
 226
 227     SECTION("e1, e2, and e3 only")
 228     {
 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});
 233     }
 234
 235     SECTION("e1, e2, e3, and e6 only")
 236     {
 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});
 241     }
 242
 243     SECTION("e1, e2, e3, and e4 only")
 244     {
 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});
 249     }
 250
 251     SECTION("e1, e2, e3, e4, and e5 only")
 252     {
 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});
 257     }
 258
 259     SECTION("e1, e2, e3, e4 and e6 only")
 260     {
 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}));
 270     }
 271
 272     SECTION("Topological ordering for entire set")
 273     {
 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};
 277       REQUIRE(
 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}));
 287     }
 288   }
 289 }
 290
 291 TEST_CASE("simgrid::mc::udpor::Configuration: Topological Sort Order Very Complicated")
 292 {
 293   // The following tests concern the given event structure:
 294   //                e1
 295   //              /   /
 296   //            e2    e8
 297   //           /  /    /  /
 298   //          e3   /   /    /
 299   //         /  /    /      e11
 300   //        e4  e6   e7
 301   //        /   /  /   /
 302   //       e5   e9    e10
 303   //        /   /     /
 304   //         /  /   /
 305   //         [   e12    ]
 306   UnfoldingEvent e1;
 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};
 319
 320   SECTION("Test every combination of the maximal configuration (forward graph)")
 321   {
 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();
 327
 328     std::for_each(ordered_events.begin(), ordered_events.end(), [&events_seen](const UnfoldingEvent* e) {
 329       History history(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
 335         if (e_hist == e)
 336           continue;
 337
 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));
 342       }
 343       events_seen.insert(e);
 344     });
 345   }
 346
 347   SECTION("Test every combination of the maximal configuration (reverse graph)")
 348   {
 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();
 354
 355     std::for_each(ordered_events.begin(), ordered_events.end(), [&events_seen](const UnfoldingEvent* e) {
 356       History history(e);
 357
 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
 361
 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));
 366       }
 367       events_seen.insert(e);
 368     });
 369   }
 370
 371   SECTION("Test that the topological ordering contains only the events of the configuration")
 372   {
 373     const EventSet events_seen = C.get_events();
 374
 375     SECTION("Forward direction")
 376     {
 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);
 380     }
 381
 382     SECTION("Reverse direction")
 383     {
 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);
 387     }
 388   }
 389
 390   SECTION("Test that the topological ordering is equivalent to that of the configuration's events")
 391   {
 392     REQUIRE(C.get_topologically_sorted_events() == C.get_events().get_topological_ordering());
 393     REQUIRE(C.get_topologically_sorted_events_of_reverse_graph() ==
 394             C.get_events().get_topological_ordering_of_reverse_graph());
 395   }
 396 }
 397
 398 TEST_CASE("simgrid::mc::udpor::maximal_subsets_iterator: Basic Testing of Maximal Subsets")
 399 {
 400   // The following tests concern the given event structure:
 401   //                e1
 402   //              /   /
 403   //             e2   e5
 404   //            /     /
 405   //           e3    e6
 406   //           /     / /
 407   //          e4    e7 e8
 408   UnfoldingEvent e1;
 409   UnfoldingEvent e2{&e1};
 410   UnfoldingEvent e3{&e2};
 411   UnfoldingEvent e4{&e3};
 412   UnfoldingEvent e5{&e1};
 413   UnfoldingEvent e6{&e5};
 414   UnfoldingEvent e7{&e6};
 415   UnfoldingEvent e8{&e6};
 416
 417   SECTION("Iteration over an empty configuration yields only the empty set")
 418   {
 419     Configuration C;
 420     maximal_subsets_iterator first(C);
 421     maximal_subsets_iterator last;
 422
 423     REQUIRE(*first == EventSet());
 424     ++first;
 425     REQUIRE(first == last);
 426   }
 427
 428   SECTION("Check counts of maximal event sets discovered")
 429   {
 430     std::unordered_map<int, int> maximal_subset_counts;
 431
 432     Configuration C{&e1, &e2, &e3, &e4, &e5, &e6, &e7, &e8};
 433     maximal_subsets_iterator first(C);
 434     maximal_subsets_iterator last;
 435
 436     for (; first != last; ++first) {
 437       maximal_subset_counts[(*first).size()]++;
 438     }
 439
 440     // First, ensure that there are only sets of size 0, 1, 2, and 3
 441     CHECK(maximal_subset_counts.size() == 4);
 442
 443     // The empty set should appear only once
 444     REQUIRE(maximal_subset_counts[0] == 1);
 445
 446     // 8 is the number of nodes in the graph
 447     REQUIRE(maximal_subset_counts[1] == 8);
 448
 449     // 13 = 3 * 4 (each of the left branch can combine with one in the right branch) + 1 (e7 + e8)
 450     REQUIRE(maximal_subset_counts[2] == 13);
 451
 452     // e7 + e8 must be included, so that means we can combine from the left branch
 453     REQUIRE(maximal_subset_counts[3] == 3);
 454   }
 455
 456   SECTION("Check counts of maximal event sets discovered with a filter")
 457   {
 458     std::unordered_map<int, int> maximal_subset_counts;
 459
 460     Configuration C{&e1, &e2, &e3, &e4, &e5, &e6, &e7, &e8};
 461
 462     SECTION("Filter with events part of initial maximal set")
 463     {
 464       EventSet interesting_bunch{&e2, &e4, &e7, &e8};
 465
 466       maximal_subsets_iterator first(C, [&](const UnfoldingEvent* e) { return interesting_bunch.contains(e); });
 467       maximal_subsets_iterator last;
 468
 469       for (; first != last; ++first) {
 470         const auto& event_set = *first;
 471         // Only events in `interesting_bunch` can appear: thus no set
 472         // should include anything else other than `interesting_bunch`
 473         REQUIRE(event_set.is_subset_of(interesting_bunch));
 474         REQUIRE(event_set.is_maximal());
 475         maximal_subset_counts[event_set.size()]++;
 476       }
 477
 478       // The empty set should (still) appear only once
 479       REQUIRE(maximal_subset_counts[0] == 1);
 480
 481       // 4 is the number of nodes in the `interesting_bunch`
 482       REQUIRE(maximal_subset_counts[1] == 4);
 483
 484       // 5 = 2 * 2 (each of the left branch can combine with one in the right branch) + 1 (e7 + e8)
 485       REQUIRE(maximal_subset_counts[2] == 5);
 486
 487       // e7 + e8 must be included, so that means we can combine from the left branch (only e2 and e4)
 488       REQUIRE(maximal_subset_counts[3] == 2);
 489
 490       // There are no subsets of size 4 (or higher, but that
 491       // is tested by asserting each maximal set traversed is a subset)
 492       REQUIRE(maximal_subset_counts[4] == 0);
 493     }
 494
 495     SECTION("Filter with interesting subset not initially part of the maximal set")
 496     {
 497       EventSet interesting_bunch{&e3, &e5, &e6};
 498
 499       maximal_subsets_iterator first(C, [&](const UnfoldingEvent* e) { return interesting_bunch.contains(e); });
 500       maximal_subsets_iterator last;
 501
 502       for (; first != last; ++first) {
 503         const auto& event_set = *first;
 504         // Only events in `interesting_bunch` can appear: thus no set
 505         // should include anything else other than `interesting_bunch`
 506         REQUIRE(event_set.is_subset_of(interesting_bunch));
 507         REQUIRE(event_set.is_maximal());
 508         maximal_subset_counts[event_set.size()]++;
 509       }
 510
 511       // The empty set should (still) appear only once
 512       REQUIRE(maximal_subset_counts[0] == 1);
 513
 514       // 3 is the number of nodes in the `interesting_bunch`
 515       REQUIRE(maximal_subset_counts[1] == 3);
 516
 517       // 2 = e3, e5 and e3, e6
 518       REQUIRE(maximal_subset_counts[2] == 2);
 519
 520       // There are no subsets of size 3 (or higher, but that
 521       // is tested by asserting each maximal set traversed is a subset)
 522       REQUIRE(maximal_subset_counts[3] == 0);
 523     }
 524   }
 525 }
 526
 527 TEST_CASE("simgrid::mc::udpor::maximal_subsets_iterator: Stress Test for Maximal Subsets Iteration")
 528 {
 529   // The following tests concern the given event structure:
 530   //                              e1
 531   //                            /   /
 532   //                          e2    e3
 533   //                          / /   /  /
 534   //               +------* e4 *e5 e6  e7
 535   //               |        /   ///   /  /
 536   //               |       e8   e9    e10
 537   //               |      /  /   /\      /
 538   //               |   e11 e12 e13 e14   e15
 539   //               |   /      / / /   /  /
 540   //               +-> e16     e17     e18
 541   UnfoldingEvent e1;
 542   UnfoldingEvent e2{&e1};
 543   UnfoldingEvent e3{&e1};
 544   UnfoldingEvent e4{&e2};
 545   UnfoldingEvent e5{&e2};
 546   UnfoldingEvent e6{&e3};
 547   UnfoldingEvent e7{&e3};
 548   UnfoldingEvent e8{&e4};
 549   UnfoldingEvent e9{&e4, &e5, &e6};
 550   UnfoldingEvent e10{&e6, &e7};
 551   UnfoldingEvent e11{&e8};
 552   UnfoldingEvent e12{&e8};
 553   UnfoldingEvent e13{&e9};
 554   UnfoldingEvent e14{&e9};
 555   UnfoldingEvent e15{&e10};
 556   UnfoldingEvent e16{&e5, &e11};
 557   UnfoldingEvent e17{&e12, &e13, &e14};
 558   UnfoldingEvent e18{&e14, &e15};
 559   Configuration C{&e1, &e2, &e3, &e4, &e5, &e6, &e7, &e8, &e9, &e10, &e11, &e12, &e13, &e14, &e15, &e16, &e17, &e18};
 560
 561   SECTION("Every subset iterated over is maximal")
 562   {
 563     maximal_subsets_iterator first(C);
 564     maximal_subsets_iterator last;
 565
 566     // Make sure we actually have something to iterate over
 567     REQUIRE(first != last);
 568
 569     for (; first != last; ++first) {
 570       REQUIRE((*first).size() <= C.get_events().size());
 571       REQUIRE((*first).is_maximal());
 572     }
 573   }
 574
 575   SECTION("Test that the maximal set ordering is equivalent to that of the configuration's events")
 576   {
 577     maximal_subsets_iterator first_config(C);
 578     maximal_subsets_iterator first_events(C.get_events());
 579     maximal_subsets_iterator last;
 580
 581     // Make sure we actually have something to iterate over
 582     REQUIRE(first_config != last);
 583     REQUIRE(first_config == first_events);
 584     REQUIRE(first_events != last);
 585
 586     for (; first_config != last; ++first_config, ++first_events) {
 587       // first_events and first_config should always be at the same location
 588       REQUIRE(first_events != last);
 589       const auto& first_config_set = *first_config;
 590       const auto& first_events_set = *first_events;
 591
 592       REQUIRE(first_config_set.size() <= C.get_events().size());
 593       REQUIRE(first_config_set.is_maximal());
 594       REQUIRE(first_events_set == first_config_set);
 595     }
 596
 597     // Iteration with events directly should now also be finished
 598     REQUIRE(first_events == last);
 599   }
 600 }