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 #include "src/mc/explo/udpor/udpor_tests_private.hpp"
  13
  14 #include <unordered_map>
  15
  16 using namespace simgrid::mc::udpor;
  17
  18 TEST_CASE("simgrid::mc::udpor::Configuration: Constructing Configurations")
  19 {
  20   // The following tests concern the given event structure:
  21   //                e1
  22   //              /
  23   //            e2
  24   //           /
  25   //          e3
  26   //         /  /
  27   //        e4   e5
  28   UnfoldingEvent e1(EventSet(), std::make_shared<IndependentAction>());
  29   UnfoldingEvent e2(EventSet({&e1}), std::make_shared<IndependentAction>());
  30   UnfoldingEvent e3(EventSet({&e2}), std::make_shared<IndependentAction>());
  31   UnfoldingEvent e4(EventSet({&e3}), std::make_shared<IndependentAction>());
  32   UnfoldingEvent e5(EventSet({&e3}), std::make_shared<IndependentAction>());
  33
  34   SECTION("Creating a configuration without events")
  35   {
  36     Configuration C;
  37     REQUIRE(C.get_events().empty());
  38     REQUIRE(C.get_latest_event() == nullptr);
  39   }
  40
  41   SECTION("Creating a configuration with events (test violation of being causally closed)")
  42   {
  43     // 5 choose 0 = 1 test
  44     REQUIRE_NOTHROW(Configuration({&e1}));
  45
  46     // 5 choose 1 = 5 tests
  47     REQUIRE_THROWS_AS(Configuration({&e2}), std::invalid_argument);
  48     REQUIRE_THROWS_AS(Configuration({&e3}), std::invalid_argument);
  49     REQUIRE_THROWS_AS(Configuration({&e4}), std::invalid_argument);
  50     REQUIRE_THROWS_AS(Configuration({&e5}), std::invalid_argument);
  51
  52     // 5 choose 2 = 10 tests
  53     REQUIRE_NOTHROW(Configuration({&e1, &e2}));
  54     REQUIRE_THROWS_AS(Configuration({&e1, &e3}), std::invalid_argument);
  55     REQUIRE_THROWS_AS(Configuration({&e1, &e4}), std::invalid_argument);
  56     REQUIRE_THROWS_AS(Configuration({&e1, &e5}), std::invalid_argument);
  57     REQUIRE_THROWS_AS(Configuration({&e2, &e3}), std::invalid_argument);
  58     REQUIRE_THROWS_AS(Configuration({&e2, &e4}), std::invalid_argument);
  59     REQUIRE_THROWS_AS(Configuration({&e2, &e5}), std::invalid_argument);
  60     REQUIRE_THROWS_AS(Configuration({&e3, &e4}), std::invalid_argument);
  61     REQUIRE_THROWS_AS(Configuration({&e3, &e5}), std::invalid_argument);
  62     REQUIRE_THROWS_AS(Configuration({&e4, &e5}), std::invalid_argument);
  63
  64     // 5 choose 3 = 10 tests
  65     REQUIRE_NOTHROW(Configuration({&e1, &e2, &e3}));
  66     REQUIRE_THROWS_AS(Configuration({&e1, &e2, &e4}), std::invalid_argument);
  67     REQUIRE_THROWS_AS(Configuration({&e1, &e2, &e5}), std::invalid_argument);
  68     REQUIRE_THROWS_AS(Configuration({&e1, &e3, &e4}), std::invalid_argument);
  69     REQUIRE_THROWS_AS(Configuration({&e1, &e3, &e5}), std::invalid_argument);
  70     REQUIRE_THROWS_AS(Configuration({&e1, &e4, &e5}), std::invalid_argument);
  71     REQUIRE_THROWS_AS(Configuration({&e2, &e3, &e4}), std::invalid_argument);
  72     REQUIRE_THROWS_AS(Configuration({&e2, &e3, &e5}), std::invalid_argument);
  73     REQUIRE_THROWS_AS(Configuration({&e2, &e4, &e5}), std::invalid_argument);
  74     REQUIRE_THROWS_AS(Configuration({&e3, &e4, &e5}), std::invalid_argument);
  75
  76     // 5 choose 4 = 5 tests
  77     REQUIRE_NOTHROW(Configuration({&e1, &e2, &e3, &e4}));
  78     REQUIRE_NOTHROW(Configuration({&e1, &e2, &e3, &e5}));
  79     REQUIRE_THROWS_AS(Configuration({&e1, &e2, &e4, &e5}), std::invalid_argument);
  80     REQUIRE_THROWS_AS(Configuration({&e1, &e3, &e4, &e5}), std::invalid_argument);
  81     REQUIRE_THROWS_AS(Configuration({&e2, &e3, &e4, &e5}), std::invalid_argument);
  82
  83     // 5 choose 5 = 1 test
  84     REQUIRE_NOTHROW(Configuration({&e1, &e2, &e3, &e4, &e5}));
  85   }
  86 }
  87
  88 TEST_CASE("simgrid::mc::udpor::Configuration: Adding Events")
  89 {
  90   // The following tests concern the given event structure:
  91   //                e1
  92   //              /
  93   //            e2
  94   //           /
  95   //         /  /
  96   //        e3   e4
  97   UnfoldingEvent e1(EventSet(), std::make_shared<IndependentAction>());
  98   UnfoldingEvent e2(EventSet({&e1}), std::make_shared<IndependentAction>());
  99   UnfoldingEvent e3(EventSet({&e2}), std::make_shared<IndependentAction>());
 100   UnfoldingEvent e4(EventSet({&e2}), std::make_shared<IndependentAction>());
 101
 102   REQUIRE_THROWS_AS(Configuration().add_event(nullptr), std::invalid_argument);
 103   REQUIRE_THROWS_AS(Configuration().add_event(&e2), std::invalid_argument);
 104   REQUIRE_THROWS_AS(Configuration().add_event(&e3), std::invalid_argument);
 105   REQUIRE_THROWS_AS(Configuration().add_event(&e4), std::invalid_argument);
 106   REQUIRE_THROWS_AS(Configuration({&e1}).add_event(&e3), std::invalid_argument);
 107   REQUIRE_THROWS_AS(Configuration({&e1}).add_event(&e4), std::invalid_argument);
 108
 109   REQUIRE_NOTHROW(Configuration().add_event(&e1));
 110   REQUIRE_NOTHROW(Configuration({&e1}).add_event(&e1));
 111   REQUIRE_NOTHROW(Configuration({&e1}).add_event(&e2));
 112   REQUIRE_NOTHROW(Configuration({&e1, &e2}).add_event(&e1));
 113   REQUIRE_NOTHROW(Configuration({&e1, &e2}).add_event(&e2));
 114   REQUIRE_NOTHROW(Configuration({&e1, &e2}).add_event(&e3));
 115   REQUIRE_NOTHROW(Configuration({&e1, &e2}).add_event(&e4));
 116   REQUIRE_NOTHROW(Configuration({&e1, &e2, &e3}).add_event(&e1));
 117   REQUIRE_NOTHROW(Configuration({&e1, &e2, &e3}).add_event(&e2));
 118   REQUIRE_NOTHROW(Configuration({&e1, &e2, &e3}).add_event(&e3));
 119   REQUIRE_NOTHROW(Configuration({&e1, &e2, &e3}).add_event(&e4));
 120   REQUIRE_NOTHROW(Configuration({&e1, &e2, &e4}).add_event(&e1));
 121   REQUIRE_NOTHROW(Configuration({&e1, &e2, &e4}).add_event(&e2));
 122   REQUIRE_NOTHROW(Configuration({&e1, &e2, &e4}).add_event(&e3));
 123   REQUIRE_NOTHROW(Configuration({&e1, &e2, &e4}).add_event(&e4));
 124   REQUIRE_NOTHROW(Configuration({&e1, &e2, &e3, &e4}).add_event(&e1));
 125   REQUIRE_NOTHROW(Configuration({&e1, &e2, &e3, &e4}).add_event(&e2));
 126   REQUIRE_NOTHROW(Configuration({&e1, &e2, &e3, &e4}).add_event(&e3));
 127   REQUIRE_NOTHROW(Configuration({&e1, &e2, &e3, &e4}).add_event(&e4));
 128 }
 129
 130 TEST_CASE("simgrid::mc::udpor::Configuration: Topological Sort Order")
 131 {
 132   // The following tests concern the given event structure:
 133   //               e1
 134   //              /
 135   //            e2
 136   //           /
 137   //          e3
 138   //         /
 139   //        e4
 140   UnfoldingEvent e1(EventSet(), std::make_shared<IndependentAction>());
 141   UnfoldingEvent e2(EventSet({&e1}), std::make_shared<IndependentAction>());
 142   UnfoldingEvent e3(EventSet({&e2}), std::make_shared<IndependentAction>());
 143   UnfoldingEvent e4(EventSet({&e3}), std::make_shared<IndependentAction>());
 144
 145   SECTION("Topological ordering for entire set")
 146   {
 147     Configuration C{&e1, &e2, &e3, &e4};
 148     REQUIRE(C.get_topologically_sorted_events() == std::vector<const UnfoldingEvent*>{&e1, &e2, &e3, &e4});
 149     REQUIRE(C.get_topologically_sorted_events_of_reverse_graph() ==
 150             std::vector<const UnfoldingEvent*>{&e4, &e3, &e2, &e1});
 151   }
 152
 153   SECTION("Topological ordering for subsets")
 154   {
 155     SECTION("No elements")
 156     {
 157       Configuration C;
 158       REQUIRE(C.get_topologically_sorted_events() == std::vector<const UnfoldingEvent*>{});
 159       REQUIRE(C.get_topologically_sorted_events_of_reverse_graph() == std::vector<const UnfoldingEvent*>{});
 160     }
 161
 162     SECTION("e1 only")
 163     {
 164       Configuration C{&e1};
 165       REQUIRE(C.get_topologically_sorted_events() == std::vector<const UnfoldingEvent*>{&e1});
 166       REQUIRE(C.get_topologically_sorted_events_of_reverse_graph() == std::vector<const UnfoldingEvent*>{&e1});
 167     }
 168
 169     SECTION("e1 and e2 only")
 170     {
 171       Configuration C{&e1, &e2};
 172       REQUIRE(C.get_topologically_sorted_events() == std::vector<const UnfoldingEvent*>{&e1, &e2});
 173       REQUIRE(C.get_topologically_sorted_events_of_reverse_graph() == std::vector<const UnfoldingEvent*>{&e2, &e1});
 174     }
 175
 176     SECTION("e1, e2, and e3 only")
 177     {
 178       Configuration C{&e1, &e2, &e3};
 179       REQUIRE(C.get_topologically_sorted_events() == std::vector<const UnfoldingEvent*>{&e1, &e2, &e3});
 180       REQUIRE(C.get_topologically_sorted_events_of_reverse_graph() ==
 181               std::vector<const UnfoldingEvent*>{&e3, &e2, &e1});
 182     }
 183   }
 184 }
 185
 186 TEST_CASE("simgrid::mc::udpor::Configuration: Topological Sort Order More Complicated")
 187 {
 188   // The following tests concern the given event structure:
 189   //                e1
 190   //              /
 191   //            e2
 192   //           /
 193   //          e3
 194   //         /  /
 195   //        e4   e6
 196   //        /
 197   //       e5
 198   UnfoldingEvent e1(EventSet(), std::make_shared<IndependentAction>());
 199   UnfoldingEvent e2(EventSet({&e1}), std::make_shared<IndependentAction>());
 200   UnfoldingEvent e3(EventSet({&e2}), std::make_shared<IndependentAction>());
 201   UnfoldingEvent e4(EventSet({&e3}), std::make_shared<IndependentAction>());
 202   UnfoldingEvent e5(EventSet({&e4}), std::make_shared<IndependentAction>());
 203   UnfoldingEvent e6(EventSet({&e3}), std::make_shared<IndependentAction>());
 204
 205   SECTION("Topological ordering for subsets")
 206   {
 207     SECTION("No elements")
 208     {
 209       Configuration C;
 210       REQUIRE(C.get_topologically_sorted_events() == std::vector<const UnfoldingEvent*>{});
 211       REQUIRE(C.get_topologically_sorted_events_of_reverse_graph() == std::vector<const UnfoldingEvent*>{});
 212     }
 213
 214     SECTION("e1 only")
 215     {
 216       Configuration C{&e1};
 217       REQUIRE(C.get_topologically_sorted_events() == std::vector<const UnfoldingEvent*>{&e1});
 218       REQUIRE(C.get_topologically_sorted_events_of_reverse_graph() == std::vector<const UnfoldingEvent*>{&e1});
 219     }
 220
 221     SECTION("e1 and e2 only")
 222     {
 223       Configuration C{&e1, &e2};
 224       REQUIRE(C.get_topologically_sorted_events() == std::vector<const UnfoldingEvent*>{&e1, &e2});
 225       REQUIRE(C.get_topologically_sorted_events_of_reverse_graph() == std::vector<const UnfoldingEvent*>{&e2, &e1});
 226     }
 227
 228     SECTION("e1, e2, and e3 only")
 229     {
 230       Configuration C{&e1, &e2, &e3};
 231       REQUIRE(C.get_topologically_sorted_events() == std::vector<const UnfoldingEvent*>{&e1, &e2, &e3});
 232       REQUIRE(C.get_topologically_sorted_events_of_reverse_graph() ==
 233               std::vector<const UnfoldingEvent*>{&e3, &e2, &e1});
 234     }
 235
 236     SECTION("e1, e2, e3, and e6 only")
 237     {
 238       Configuration C{&e1, &e2, &e3, &e6};
 239       REQUIRE(C.get_topologically_sorted_events() == std::vector<const UnfoldingEvent*>{&e1, &e2, &e3, &e6});
 240       REQUIRE(C.get_topologically_sorted_events_of_reverse_graph() ==
 241               std::vector<const UnfoldingEvent*>{&e6, &e3, &e2, &e1});
 242     }
 243
 244     SECTION("e1, e2, e3, and e4 only")
 245     {
 246       Configuration C{&e1, &e2, &e3, &e4};
 247       REQUIRE(C.get_topologically_sorted_events() == std::vector<const UnfoldingEvent*>{&e1, &e2, &e3, &e4});
 248       REQUIRE(C.get_topologically_sorted_events_of_reverse_graph() ==
 249               std::vector<const UnfoldingEvent*>{&e4, &e3, &e2, &e1});
 250     }
 251
 252     SECTION("e1, e2, e3, e4, and e5 only")
 253     {
 254       Configuration C{&e1, &e2, &e3, &e4, &e5};
 255       REQUIRE(C.get_topologically_sorted_events() == std::vector<const UnfoldingEvent*>{&e1, &e2, &e3, &e4, &e5});
 256       REQUIRE(C.get_topologically_sorted_events_of_reverse_graph() ==
 257               std::vector<const UnfoldingEvent*>{&e5, &e4, &e3, &e2, &e1});
 258     }
 259
 260     SECTION("e1, e2, e3, e4 and e6 only")
 261     {
 262       // In this case, e4 and e6 are interchangeable. Hence, we have to check
 263       // if the sorting gives us *any* of the combinations
 264       Configuration C{&e1, &e2, &e3, &e4, &e6};
 265       REQUIRE((C.get_topologically_sorted_events() == std::vector<const UnfoldingEvent*>{&e1, &e2, &e3, &e4, &e6} ||
 266                C.get_topologically_sorted_events() == std::vector<const UnfoldingEvent*>{&e1, &e2, &e3, &e6, &e4}));
 267       REQUIRE((C.get_topologically_sorted_events_of_reverse_graph() ==
 268                    std::vector<const UnfoldingEvent*>{&e6, &e4, &e3, &e2, &e1} ||
 269                C.get_topologically_sorted_events_of_reverse_graph() ==
 270                    std::vector<const UnfoldingEvent*>{&e4, &e6, &e3, &e2, &e1}));
 271     }
 272
 273     SECTION("Topological ordering for entire set")
 274     {
 275       // In this case, e4/e5 are both interchangeable with e6. Hence, again we have to check
 276       // if the sorting gives us *any* of the combinations
 277       Configuration C{&e1, &e2, &e3, &e4, &e5, &e6};
 278       REQUIRE(
 279           (C.get_topologically_sorted_events() == std::vector<const UnfoldingEvent*>{&e1, &e2, &e3, &e4, &e5, &e6} ||
 280            C.get_topologically_sorted_events() == std::vector<const UnfoldingEvent*>{&e1, &e2, &e3, &e4, &e6, &e5} ||
 281            C.get_topologically_sorted_events() == std::vector<const UnfoldingEvent*>{&e1, &e2, &e3, &e6, &e4, &e5}));
 282       REQUIRE((C.get_topologically_sorted_events_of_reverse_graph() ==
 283                    std::vector<const UnfoldingEvent*>{&e6, &e5, &e4, &e3, &e2, &e1} ||
 284                C.get_topologically_sorted_events_of_reverse_graph() ==
 285                    std::vector<const UnfoldingEvent*>{&e5, &e6, &e4, &e3, &e2, &e1} ||
 286                C.get_topologically_sorted_events_of_reverse_graph() ==
 287                    std::vector<const UnfoldingEvent*>{&e5, &e4, &e6, &e3, &e2, &e1}));
 288     }
 289   }
 290 }
 291
 292 TEST_CASE("simgrid::mc::udpor::Configuration: Topological Sort Order Very Complicated")
 293 {
 294   // The following tests concern the given event structure:
 295   //                e1
 296   //              /   /
 297   //            e2    e8
 298   //           /  /    /  /
 299   //          e3   /   /    /
 300   //         /  /    /      e11
 301   //        e4  e6   e7
 302   //        /   /  /   /
 303   //       e5   e9    e10
 304   //        /   /     /
 305   //         /  /   /
 306   //         [   e12    ]
 307   UnfoldingEvent e1(EventSet(), std::make_shared<IndependentAction>());
 308   UnfoldingEvent e2(EventSet({&e1}), std::make_shared<IndependentAction>());
 309   UnfoldingEvent e8(EventSet({&e1}), std::make_shared<IndependentAction>());
 310   UnfoldingEvent e3(EventSet({&e2}), std::make_shared<IndependentAction>());
 311   UnfoldingEvent e4(EventSet({&e3}), std::make_shared<IndependentAction>());
 312   UnfoldingEvent e5(EventSet({&e4}), std::make_shared<IndependentAction>());
 313   UnfoldingEvent e6(EventSet({&e4}), std::make_shared<IndependentAction>());
 314   UnfoldingEvent e7(EventSet({&e2, &e8}), std::make_shared<IndependentAction>());
 315   UnfoldingEvent e9(EventSet({&e6, &e7}), std::make_shared<IndependentAction>());
 316   UnfoldingEvent e10(EventSet({&e7}), std::make_shared<IndependentAction>());
 317   UnfoldingEvent e11(EventSet({&e8}), std::make_shared<IndependentAction>());
 318   UnfoldingEvent e12(EventSet({&e5, &e9, &e10}), std::make_shared<IndependentAction>());
 319   Configuration C{&e1, &e2, &e3, &e4, &e5, &e6, &e7, &e8, &e9, &e10, &e11, &e12};
 320
 321   SECTION("Test every combination of the maximal configuration (forward graph)")
 322   {
 323     // To test this, we ensure that for the `i`th event
 324     // in `ordered_events`, each event in `ordered_events[0...<i]
 325     // is contained in the history of `ordered_events[i]`.
 326     EventSet events_seen;
 327     const auto ordered_events = C.get_topologically_sorted_events();
 328
 329     std::for_each(ordered_events.begin(), ordered_events.end(), [&events_seen](const UnfoldingEvent* e) {
 330       History history(e);
 331       for (auto* e_hist : history) {
 332         // In this demo, we want to make sure that
 333         // we don't mark not yet seeing `e` as an error.
 334         // The history of `e` traverses `e` itself. All
 335         // other events in e's history are included in
 336         if (e_hist == e)
 337           continue;
 338
 339         // If this event has not been "seen" before,
 340         // this implies that event `e` appears earlier
 341         // in the list than one of its dependencies
 342         REQUIRE(events_seen.contains(e_hist));
 343       }
 344       events_seen.insert(e);
 345     });
 346   }
 347
 348   SECTION("Test every combination of the maximal configuration (reverse graph)")
 349   {
 350     // To test this, we ensure that for the `i`th event
 351     // in `ordered_events`, no event in `ordered_events[0...<i]
 352     // is contained in the history of `ordered_events[i]`.
 353     EventSet events_seen;
 354     const auto ordered_events = C.get_topologically_sorted_events_of_reverse_graph();
 355
 356     std::for_each(ordered_events.begin(), ordered_events.end(), [&events_seen](const UnfoldingEvent* e) {
 357       History history(e);
 358
 359       for (auto* e_hist : history) {
 360         // Unlike the test above, we DO want to ensure
 361         // that `e` itself ALSO isn't yet seen
 362
 363         // If this event has been "seen" before,
 364         // this implies that event `e` appears later
 365         // in the list than one of its ancestors
 366         REQUIRE_FALSE(events_seen.contains(e_hist));
 367       }
 368       events_seen.insert(e);
 369     });
 370   }
 371
 372   SECTION("Test that the topological ordering contains only the events of the configuration")
 373   {
 374     const EventSet events_seen = C.get_events();
 375
 376     SECTION("Forward direction")
 377     {
 378       auto ordered_events              = C.get_topologically_sorted_events();
 379       const EventSet ordered_event_set = EventSet(std::move(ordered_events));
 380       REQUIRE(events_seen == ordered_event_set);
 381     }
 382
 383     SECTION("Reverse direction")
 384     {
 385       auto ordered_events              = C.get_topologically_sorted_events_of_reverse_graph();
 386       const EventSet ordered_event_set = EventSet(std::move(ordered_events));
 387       REQUIRE(events_seen == ordered_event_set);
 388     }
 389   }
 390
 391   SECTION("Test that the topological ordering is equivalent to that of the configuration's events")
 392   {
 393     REQUIRE(C.get_topologically_sorted_events() == C.get_events().get_topological_ordering());
 394     REQUIRE(C.get_topologically_sorted_events_of_reverse_graph() ==
 395             C.get_events().get_topological_ordering_of_reverse_graph());
 396   }
 397 }
 398
 399 TEST_CASE("simgrid::mc::udpor::maximal_subsets_iterator: Basic Testing of Maximal Subsets")
 400 {
 401   // The following tests concern the given event structure:
 402   //                e1
 403   //              /   /
 404   //             e2   e5
 405   //            /     /
 406   //           e3    e6
 407   //           /     / /
 408   //          e4    e7 e8
 409   UnfoldingEvent e1(EventSet(), std::make_shared<IndependentAction>());
 410   UnfoldingEvent e2(EventSet({&e1}), std::make_shared<IndependentAction>());
 411   UnfoldingEvent e3(EventSet({&e2}), std::make_shared<IndependentAction>());
 412   UnfoldingEvent e4(EventSet({&e3}), std::make_shared<IndependentAction>());
 413   UnfoldingEvent e5(EventSet({&e1}), std::make_shared<IndependentAction>());
 414   UnfoldingEvent e6(EventSet({&e5}), std::make_shared<IndependentAction>());
 415   UnfoldingEvent e7(EventSet({&e6}), std::make_shared<IndependentAction>());
 416   UnfoldingEvent e8(EventSet({&e6}), std::make_shared<IndependentAction>());
 417
 418   SECTION("Iteration over an empty configuration yields only the empty set")
 419   {
 420     Configuration C;
 421     maximal_subsets_iterator first(C);
 422     maximal_subsets_iterator last;
 423
 424     REQUIRE(*first == EventSet());
 425     ++first;
 426     REQUIRE(first == last);
 427   }
 428
 429   SECTION("Check counts of maximal event sets discovered")
 430   {
 431     std::unordered_map<int, int> maximal_subset_counts;
 432
 433     Configuration C{&e1, &e2, &e3, &e4, &e5, &e6, &e7, &e8};
 434     maximal_subsets_iterator first(C);
 435     maximal_subsets_iterator last;
 436
 437     for (; first != last; ++first) {
 438       maximal_subset_counts[(*first).size()]++;
 439     }
 440
 441     // First, ensure that there are only sets of size 0, 1, 2, and 3
 442     CHECK(maximal_subset_counts.size() == 4);
 443
 444     // The empty set should appear only once
 445     REQUIRE(maximal_subset_counts[0] == 1);
 446
 447     // 8 is the number of nodes in the graph
 448     REQUIRE(maximal_subset_counts[1] == 8);
 449
 450     // 13 = 3 * 4 (each of the left branch can combine with one in the right branch) + 1 (e7 + e8)
 451     REQUIRE(maximal_subset_counts[2] == 13);
 452
 453     // e7 + e8 must be included, so that means we can combine from the left branch
 454     REQUIRE(maximal_subset_counts[3] == 3);
 455   }
 456
 457   SECTION("Check counts of maximal event sets discovered with a filter")
 458   {
 459     std::unordered_map<int, int> maximal_subset_counts;
 460
 461     Configuration C{&e1, &e2, &e3, &e4, &e5, &e6, &e7, &e8};
 462
 463     SECTION("Filter with events part of initial maximal set")
 464     {
 465       EventSet interesting_bunch{&e2, &e4, &e7, &e8};
 466
 467       maximal_subsets_iterator first(C, [&](const UnfoldingEvent* e) { return interesting_bunch.contains(e); });
 468       maximal_subsets_iterator last;
 469
 470       for (; first != last; ++first) {
 471         const auto& event_set = *first;
 472         // Only events in `interesting_bunch` can appear: thus no set
 473         // should include anything else other than `interesting_bunch`
 474         REQUIRE(event_set.is_subset_of(interesting_bunch));
 475         REQUIRE(event_set.is_maximal());
 476         maximal_subset_counts[event_set.size()]++;
 477       }
 478
 479       // The empty set should (still) appear only once
 480       REQUIRE(maximal_subset_counts[0] == 1);
 481
 482       // 4 is the number of nodes in the `interesting_bunch`
 483       REQUIRE(maximal_subset_counts[1] == 4);
 484
 485       // 5 = 2 * 2 (each of the left branch can combine with one in the right branch) + 1 (e7 + e8)
 486       REQUIRE(maximal_subset_counts[2] == 5);
 487
 488       // e7 + e8 must be included, so that means we can combine from the left branch (only e2 and e4)
 489       REQUIRE(maximal_subset_counts[3] == 2);
 490
 491       // There are no subsets of size 4 (or higher, but that
 492       // is tested by asserting each maximal set traversed is a subset)
 493       REQUIRE(maximal_subset_counts[4] == 0);
 494     }
 495
 496     SECTION("Filter with interesting subset not initially part of the maximal set")
 497     {
 498       EventSet interesting_bunch{&e3, &e5, &e6};
 499
 500       maximal_subsets_iterator first(C, [&](const UnfoldingEvent* e) { return interesting_bunch.contains(e); });
 501       maximal_subsets_iterator last;
 502
 503       for (; first != last; ++first) {
 504         const auto& event_set = *first;
 505         // Only events in `interesting_bunch` can appear: thus no set
 506         // should include anything else other than `interesting_bunch`
 507         REQUIRE(event_set.is_subset_of(interesting_bunch));
 508         REQUIRE(event_set.is_maximal());
 509         maximal_subset_counts[event_set.size()]++;
 510       }
 511
 512       // The empty set should (still) appear only once
 513       REQUIRE(maximal_subset_counts[0] == 1);
 514
 515       // 3 is the number of nodes in the `interesting_bunch`
 516       REQUIRE(maximal_subset_counts[1] == 3);
 517
 518       // 2 = e3, e5 and e3, e6
 519       REQUIRE(maximal_subset_counts[2] == 2);
 520
 521       // There are no subsets of size 3 (or higher, but that
 522       // is tested by asserting each maximal set traversed is a subset)
 523       REQUIRE(maximal_subset_counts[3] == 0);
 524     }
 525   }
 526 }
 527
 528 TEST_CASE("simgrid::mc::udpor::maximal_subsets_iterator: Stress Test for Maximal Subsets Iteration")
 529 {
 530   // The following tests concern the given event structure:
 531   //                              e1
 532   //                            /   /
 533   //                          e2    e3
 534   //                          / /   /  /
 535   //               +------* e4 *e5 e6  e7
 536   //               |        /   ///   /  /
 537   //               |       e8   e9    e10
 538   //               |      /  /   /\      /
 539   //               |   e11 e12 e13 e14   e15
 540   //               |   /      / / /   /  /
 541   //               +-> e16     e17     e18
 542   UnfoldingEvent e1(EventSet(), std::make_shared<IndependentAction>());
 543   UnfoldingEvent e2(EventSet({&e1}), std::make_shared<IndependentAction>());
 544   UnfoldingEvent e3(EventSet({&e1}), std::make_shared<IndependentAction>());
 545   UnfoldingEvent e4(EventSet({&e2}), std::make_shared<IndependentAction>());
 546   UnfoldingEvent e5(EventSet({&e2}), std::make_shared<IndependentAction>());
 547   UnfoldingEvent e6(EventSet({&e3}), std::make_shared<IndependentAction>());
 548   UnfoldingEvent e7(EventSet({&e3}), std::make_shared<IndependentAction>());
 549   UnfoldingEvent e8(EventSet({&e4}), std::make_shared<IndependentAction>());
 550   UnfoldingEvent e9(EventSet({&e4, &e5, &e6}), std::make_shared<IndependentAction>());
 551   UnfoldingEvent e10(EventSet({&e6, &e7}), std::make_shared<IndependentAction>());
 552   UnfoldingEvent e11(EventSet({&e8}), std::make_shared<IndependentAction>());
 553   UnfoldingEvent e12(EventSet({&e8}), std::make_shared<IndependentAction>());
 554   UnfoldingEvent e13(EventSet({&e9}), std::make_shared<IndependentAction>());
 555   UnfoldingEvent e14(EventSet({&e9}), std::make_shared<IndependentAction>());
 556   UnfoldingEvent e15(EventSet({&e10}), std::make_shared<IndependentAction>());
 557   UnfoldingEvent e16(EventSet({&e5, &e11}), std::make_shared<IndependentAction>());
 558   UnfoldingEvent e17(EventSet({&e12, &e13, &e14}), std::make_shared<IndependentAction>());
 559   UnfoldingEvent e18(EventSet({&e14, &e15}), std::make_shared<IndependentAction>());
 560   Configuration C{&e1, &e2, &e3, &e4, &e5, &e6, &e7, &e8, &e9, &e10, &e11, &e12, &e13, &e14, &e15, &e16, &e17, &e18};
 561
 562   SECTION("Every subset iterated over is maximal")
 563   {
 564     maximal_subsets_iterator first(C);
 565     maximal_subsets_iterator last;
 566
 567     // Make sure we actually have something to iterate over
 568     REQUIRE(first != last);
 569
 570     for (; first != last; ++first) {
 571       REQUIRE((*first).size() <= C.get_events().size());
 572       REQUIRE((*first).is_maximal());
 573     }
 574   }
 575
 576   SECTION("Test that the maximal set ordering is equivalent to that of the configuration's events")
 577   {
 578     maximal_subsets_iterator first_config(C);
 579     maximal_subsets_iterator first_events(C.get_events());
 580     maximal_subsets_iterator last;
 581
 582     // Make sure we actually have something to iterate over
 583     REQUIRE(first_config != last);
 584     REQUIRE(first_config == first_events);
 585     REQUIRE(first_events != last);
 586
 587     for (; first_config != last; ++first_config, ++first_events) {
 588       // first_events and first_config should always be at the same location
 589       REQUIRE(first_events != last);
 590       const auto& first_config_set = *first_config;
 591       const auto& first_events_set = *first_events;
 592
 593       REQUIRE(first_config_set.size() <= C.get_events().size());
 594       REQUIRE(first_config_set.is_maximal());
 595       REQUIRE(first_events_set == first_config_set);
 596     }
 597
 598     // Iteration with events directly should now also be finished
 599     REQUIRE(first_events == last);
 600   }
 601 }