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/Unfolding.hpp"
  11 #include "src/mc/explo/udpor/UnfoldingEvent.hpp"
  12 #include "src/mc/explo/udpor/maximal_subsets_iterator.hpp"
  13 #include "src/mc/explo/udpor/udpor_tests_private.hpp"
  14
  15 #include <unordered_map>
  16
  17 using namespace simgrid::mc::udpor;
  18
  19 TEST_CASE("simgrid::mc::udpor::Configuration: Constructing Configurations")
  20 {
  21   // The following tests concern the given event structure:
  22   //                e1
  23   //              /
  24   //            e2
  25   //           /
  26   //          e3
  27   //         /  /
  28   //        e4   e5
  29   UnfoldingEvent e1(EventSet(), std::make_shared<IndependentAction>());
  30   UnfoldingEvent e2(EventSet({&e1}), std::make_shared<IndependentAction>());
  31   UnfoldingEvent e3(EventSet({&e2}), std::make_shared<IndependentAction>());
  32   UnfoldingEvent e4(EventSet({&e3}), std::make_shared<IndependentAction>());
  33   UnfoldingEvent e5(EventSet({&e3}), std::make_shared<IndependentAction>());
  34
  35   SECTION("Creating a configuration without events")
  36   {
  37     Configuration C;
  38     REQUIRE(C.get_events().empty());
  39     REQUIRE(C.get_latest_event() == nullptr);
  40   }
  41
  42   SECTION("Creating a configuration with events (test violation of being causally closed)")
  43   {
  44     // 5 choose 0 = 1 test
  45     REQUIRE_NOTHROW(Configuration({&e1}));
  46
  47     // 5 choose 1 = 5 tests
  48     REQUIRE_THROWS_AS(Configuration({&e2}), std::invalid_argument);
  49     REQUIRE_THROWS_AS(Configuration({&e3}), std::invalid_argument);
  50     REQUIRE_THROWS_AS(Configuration({&e4}), std::invalid_argument);
  51     REQUIRE_THROWS_AS(Configuration({&e5}), std::invalid_argument);
  52
  53     // 5 choose 2 = 10 tests
  54     REQUIRE_NOTHROW(Configuration({&e1, &e2}));
  55     REQUIRE_THROWS_AS(Configuration({&e1, &e3}), std::invalid_argument);
  56     REQUIRE_THROWS_AS(Configuration({&e1, &e4}), std::invalid_argument);
  57     REQUIRE_THROWS_AS(Configuration({&e1, &e5}), std::invalid_argument);
  58     REQUIRE_THROWS_AS(Configuration({&e2, &e3}), std::invalid_argument);
  59     REQUIRE_THROWS_AS(Configuration({&e2, &e4}), std::invalid_argument);
  60     REQUIRE_THROWS_AS(Configuration({&e2, &e5}), std::invalid_argument);
  61     REQUIRE_THROWS_AS(Configuration({&e3, &e4}), std::invalid_argument);
  62     REQUIRE_THROWS_AS(Configuration({&e3, &e5}), std::invalid_argument);
  63     REQUIRE_THROWS_AS(Configuration({&e4, &e5}), std::invalid_argument);
  64
  65     // 5 choose 3 = 10 tests
  66     REQUIRE_NOTHROW(Configuration({&e1, &e2, &e3}));
  67     REQUIRE_THROWS_AS(Configuration({&e1, &e2, &e4}), std::invalid_argument);
  68     REQUIRE_THROWS_AS(Configuration({&e1, &e2, &e5}), std::invalid_argument);
  69     REQUIRE_THROWS_AS(Configuration({&e1, &e3, &e4}), std::invalid_argument);
  70     REQUIRE_THROWS_AS(Configuration({&e1, &e3, &e5}), std::invalid_argument);
  71     REQUIRE_THROWS_AS(Configuration({&e1, &e4, &e5}), std::invalid_argument);
  72     REQUIRE_THROWS_AS(Configuration({&e2, &e3, &e4}), std::invalid_argument);
  73     REQUIRE_THROWS_AS(Configuration({&e2, &e3, &e5}), std::invalid_argument);
  74     REQUIRE_THROWS_AS(Configuration({&e2, &e4, &e5}), std::invalid_argument);
  75     REQUIRE_THROWS_AS(Configuration({&e3, &e4, &e5}), std::invalid_argument);
  76
  77     // 5 choose 4 = 5 tests
  78     REQUIRE_NOTHROW(Configuration({&e1, &e2, &e3, &e4}));
  79     REQUIRE_NOTHROW(Configuration({&e1, &e2, &e3, &e5}));
  80     REQUIRE_THROWS_AS(Configuration({&e1, &e2, &e4, &e5}), std::invalid_argument);
  81     REQUIRE_THROWS_AS(Configuration({&e1, &e3, &e4, &e5}), std::invalid_argument);
  82     REQUIRE_THROWS_AS(Configuration({&e2, &e3, &e4, &e5}), std::invalid_argument);
  83
  84     // 5 choose 5 = 1 test
  85     REQUIRE_NOTHROW(Configuration({&e1, &e2, &e3, &e4, &e5}));
  86   }
  87 }
  88
  89 TEST_CASE("simgrid::mc::udpor::Configuration: Adding Events")
  90 {
  91   // The following tests concern the given event structure:
  92   //                e1
  93   //              /
  94   //            e2
  95   //           /
  96   //         /  /
  97   //        e3   e4
  98   UnfoldingEvent e1(EventSet(), std::make_shared<IndependentAction>());
  99   UnfoldingEvent e2(EventSet({&e1}), std::make_shared<IndependentAction>());
 100   UnfoldingEvent e3(EventSet({&e2}), std::make_shared<IndependentAction>());
 101   UnfoldingEvent e4(EventSet({&e2}), std::make_shared<IndependentAction>());
 102
 103   REQUIRE_THROWS_AS(Configuration().add_event(nullptr), std::invalid_argument);
 104   REQUIRE_THROWS_AS(Configuration().add_event(&e2), std::invalid_argument);
 105   REQUIRE_THROWS_AS(Configuration().add_event(&e3), std::invalid_argument);
 106   REQUIRE_THROWS_AS(Configuration().add_event(&e4), std::invalid_argument);
 107   REQUIRE_THROWS_AS(Configuration({&e1}).add_event(&e3), std::invalid_argument);
 108   REQUIRE_THROWS_AS(Configuration({&e1}).add_event(&e4), std::invalid_argument);
 109
 110   REQUIRE_NOTHROW(Configuration().add_event(&e1));
 111   REQUIRE_NOTHROW(Configuration({&e1}).add_event(&e1));
 112   REQUIRE_NOTHROW(Configuration({&e1}).add_event(&e2));
 113   REQUIRE_NOTHROW(Configuration({&e1, &e2}).add_event(&e1));
 114   REQUIRE_NOTHROW(Configuration({&e1, &e2}).add_event(&e2));
 115   REQUIRE_NOTHROW(Configuration({&e1, &e2}).add_event(&e3));
 116   REQUIRE_NOTHROW(Configuration({&e1, &e2}).add_event(&e4));
 117   REQUIRE_NOTHROW(Configuration({&e1, &e2, &e3}).add_event(&e1));
 118   REQUIRE_NOTHROW(Configuration({&e1, &e2, &e3}).add_event(&e2));
 119   REQUIRE_NOTHROW(Configuration({&e1, &e2, &e3}).add_event(&e3));
 120   REQUIRE_NOTHROW(Configuration({&e1, &e2, &e3}).add_event(&e4));
 121   REQUIRE_NOTHROW(Configuration({&e1, &e2, &e4}).add_event(&e1));
 122   REQUIRE_NOTHROW(Configuration({&e1, &e2, &e4}).add_event(&e2));
 123   REQUIRE_NOTHROW(Configuration({&e1, &e2, &e4}).add_event(&e3));
 124   REQUIRE_NOTHROW(Configuration({&e1, &e2, &e4}).add_event(&e4));
 125   REQUIRE_NOTHROW(Configuration({&e1, &e2, &e3, &e4}).add_event(&e1));
 126   REQUIRE_NOTHROW(Configuration({&e1, &e2, &e3, &e4}).add_event(&e2));
 127   REQUIRE_NOTHROW(Configuration({&e1, &e2, &e3, &e4}).add_event(&e3));
 128   REQUIRE_NOTHROW(Configuration({&e1, &e2, &e3, &e4}).add_event(&e4));
 129 }
 130
 131 TEST_CASE("simgrid::mc::udpor::Configuration: Topological Sort Order")
 132 {
 133   // The following tests concern the given event structure:
 134   //               e1
 135   //              /
 136   //            e2
 137   //           /
 138   //          e3
 139   //         /
 140   //        e4
 141   UnfoldingEvent e1(EventSet(), std::make_shared<IndependentAction>());
 142   UnfoldingEvent e2(EventSet({&e1}), std::make_shared<IndependentAction>());
 143   UnfoldingEvent e3(EventSet({&e2}), std::make_shared<IndependentAction>());
 144   UnfoldingEvent e4(EventSet({&e3}), std::make_shared<IndependentAction>());
 145
 146   SECTION("Topological ordering for entire set")
 147   {
 148     Configuration C{&e1, &e2, &e3, &e4};
 149     REQUIRE(C.get_topologically_sorted_events() == std::vector<const UnfoldingEvent*>{&e1, &e2, &e3, &e4});
 150     REQUIRE(C.get_topologically_sorted_events_of_reverse_graph() ==
 151             std::vector<const UnfoldingEvent*>{&e4, &e3, &e2, &e1});
 152   }
 153
 154   SECTION("Topological ordering for subsets")
 155   {
 156     SECTION("No elements")
 157     {
 158       Configuration C;
 159       REQUIRE(C.get_topologically_sorted_events() == std::vector<const UnfoldingEvent*>{});
 160       REQUIRE(C.get_topologically_sorted_events_of_reverse_graph() == std::vector<const UnfoldingEvent*>{});
 161     }
 162
 163     SECTION("e1 only")
 164     {
 165       Configuration C{&e1};
 166       REQUIRE(C.get_topologically_sorted_events() == std::vector<const UnfoldingEvent*>{&e1});
 167       REQUIRE(C.get_topologically_sorted_events_of_reverse_graph() == std::vector<const UnfoldingEvent*>{&e1});
 168     }
 169
 170     SECTION("e1 and e2 only")
 171     {
 172       Configuration C{&e1, &e2};
 173       REQUIRE(C.get_topologically_sorted_events() == std::vector<const UnfoldingEvent*>{&e1, &e2});
 174       REQUIRE(C.get_topologically_sorted_events_of_reverse_graph() == std::vector<const UnfoldingEvent*>{&e2, &e1});
 175     }
 176
 177     SECTION("e1, e2, and e3 only")
 178     {
 179       Configuration C{&e1, &e2, &e3};
 180       REQUIRE(C.get_topologically_sorted_events() == std::vector<const UnfoldingEvent*>{&e1, &e2, &e3});
 181       REQUIRE(C.get_topologically_sorted_events_of_reverse_graph() ==
 182               std::vector<const UnfoldingEvent*>{&e3, &e2, &e1});
 183     }
 184   }
 185 }
 186
 187 TEST_CASE("simgrid::mc::udpor::Configuration: Topological Sort Order More Complicated")
 188 {
 189   // The following tests concern the given event structure:
 190   //                e1
 191   //              /
 192   //            e2
 193   //           /
 194   //          e3
 195   //         /  /
 196   //        e4   e6
 197   //        /
 198   //       e5
 199   UnfoldingEvent e1(EventSet(), std::make_shared<IndependentAction>());
 200   UnfoldingEvent e2(EventSet({&e1}), std::make_shared<IndependentAction>());
 201   UnfoldingEvent e3(EventSet({&e2}), std::make_shared<IndependentAction>());
 202   UnfoldingEvent e4(EventSet({&e3}), std::make_shared<IndependentAction>());
 203   UnfoldingEvent e5(EventSet({&e4}), std::make_shared<IndependentAction>());
 204   UnfoldingEvent e6(EventSet({&e3}), std::make_shared<IndependentAction>());
 205
 206   SECTION("Topological ordering for subsets")
 207   {
 208     SECTION("No elements")
 209     {
 210       Configuration C;
 211       REQUIRE(C.get_topologically_sorted_events() == std::vector<const UnfoldingEvent*>{});
 212       REQUIRE(C.get_topologically_sorted_events_of_reverse_graph() == std::vector<const UnfoldingEvent*>{});
 213     }
 214
 215     SECTION("e1 only")
 216     {
 217       Configuration C{&e1};
 218       REQUIRE(C.get_topologically_sorted_events() == std::vector<const UnfoldingEvent*>{&e1});
 219       REQUIRE(C.get_topologically_sorted_events_of_reverse_graph() == std::vector<const UnfoldingEvent*>{&e1});
 220     }
 221
 222     SECTION("e1 and e2 only")
 223     {
 224       Configuration C{&e1, &e2};
 225       REQUIRE(C.get_topologically_sorted_events() == std::vector<const UnfoldingEvent*>{&e1, &e2});
 226       REQUIRE(C.get_topologically_sorted_events_of_reverse_graph() == std::vector<const UnfoldingEvent*>{&e2, &e1});
 227     }
 228
 229     SECTION("e1, e2, and e3 only")
 230     {
 231       Configuration C{&e1, &e2, &e3};
 232       REQUIRE(C.get_topologically_sorted_events() == std::vector<const UnfoldingEvent*>{&e1, &e2, &e3});
 233       REQUIRE(C.get_topologically_sorted_events_of_reverse_graph() ==
 234               std::vector<const UnfoldingEvent*>{&e3, &e2, &e1});
 235     }
 236
 237     SECTION("e1, e2, e3, and e6 only")
 238     {
 239       Configuration C{&e1, &e2, &e3, &e6};
 240       REQUIRE(C.get_topologically_sorted_events() == std::vector<const UnfoldingEvent*>{&e1, &e2, &e3, &e6});
 241       REQUIRE(C.get_topologically_sorted_events_of_reverse_graph() ==
 242               std::vector<const UnfoldingEvent*>{&e6, &e3, &e2, &e1});
 243     }
 244
 245     SECTION("e1, e2, e3, and e4 only")
 246     {
 247       Configuration C{&e1, &e2, &e3, &e4};
 248       REQUIRE(C.get_topologically_sorted_events() == std::vector<const UnfoldingEvent*>{&e1, &e2, &e3, &e4});
 249       REQUIRE(C.get_topologically_sorted_events_of_reverse_graph() ==
 250               std::vector<const UnfoldingEvent*>{&e4, &e3, &e2, &e1});
 251     }
 252
 253     SECTION("e1, e2, e3, e4, and e5 only")
 254     {
 255       Configuration C{&e1, &e2, &e3, &e4, &e5};
 256       REQUIRE(C.get_topologically_sorted_events() == std::vector<const UnfoldingEvent*>{&e1, &e2, &e3, &e4, &e5});
 257       REQUIRE(C.get_topologically_sorted_events_of_reverse_graph() ==
 258               std::vector<const UnfoldingEvent*>{&e5, &e4, &e3, &e2, &e1});
 259     }
 260
 261     SECTION("e1, e2, e3, e4 and e6 only")
 262     {
 263       // In this case, e4 and e6 are interchangeable. Hence, we have to check
 264       // if the sorting gives us *any* of the combinations
 265       Configuration C{&e1, &e2, &e3, &e4, &e6};
 266       REQUIRE((C.get_topologically_sorted_events() == std::vector<const UnfoldingEvent*>{&e1, &e2, &e3, &e4, &e6} ||
 267                C.get_topologically_sorted_events() == std::vector<const UnfoldingEvent*>{&e1, &e2, &e3, &e6, &e4}));
 268       REQUIRE((C.get_topologically_sorted_events_of_reverse_graph() ==
 269                    std::vector<const UnfoldingEvent*>{&e6, &e4, &e3, &e2, &e1} ||
 270                C.get_topologically_sorted_events_of_reverse_graph() ==
 271                    std::vector<const UnfoldingEvent*>{&e4, &e6, &e3, &e2, &e1}));
 272     }
 273
 274     SECTION("Topological ordering for entire set")
 275     {
 276       // In this case, e4/e5 are both interchangeable with e6. Hence, again we have to check
 277       // if the sorting gives us *any* of the combinations
 278       Configuration C{&e1, &e2, &e3, &e4, &e5, &e6};
 279       REQUIRE(
 280           (C.get_topologically_sorted_events() == std::vector<const UnfoldingEvent*>{&e1, &e2, &e3, &e4, &e5, &e6} ||
 281            C.get_topologically_sorted_events() == std::vector<const UnfoldingEvent*>{&e1, &e2, &e3, &e4, &e6, &e5} ||
 282            C.get_topologically_sorted_events() == std::vector<const UnfoldingEvent*>{&e1, &e2, &e3, &e6, &e4, &e5}));
 283       REQUIRE((C.get_topologically_sorted_events_of_reverse_graph() ==
 284                    std::vector<const UnfoldingEvent*>{&e6, &e5, &e4, &e3, &e2, &e1} ||
 285                C.get_topologically_sorted_events_of_reverse_graph() ==
 286                    std::vector<const UnfoldingEvent*>{&e5, &e6, &e4, &e3, &e2, &e1} ||
 287                C.get_topologically_sorted_events_of_reverse_graph() ==
 288                    std::vector<const UnfoldingEvent*>{&e5, &e4, &e6, &e3, &e2, &e1}));
 289     }
 290   }
 291 }
 292
 293 TEST_CASE("simgrid::mc::udpor::Configuration: Topological Sort Order Very Complicated")
 294 {
 295   // The following tests concern the given event structure:
 296   //                e1
 297   //              /   /
 298   //            e2    e8
 299   //           /  /    /  /
 300   //          e3   /   /    /
 301   //         /  /    /      e11
 302   //        e4  e6   e7
 303   //        /   /  /   /
 304   //       e5   e9    e10
 305   //        /   /     /
 306   //         /  /   /
 307   //         [   e12    ]
 308   UnfoldingEvent e1(EventSet(), std::make_shared<IndependentAction>());
 309   UnfoldingEvent e2(EventSet({&e1}), std::make_shared<IndependentAction>());
 310   UnfoldingEvent e8(EventSet({&e1}), std::make_shared<IndependentAction>());
 311   UnfoldingEvent e3(EventSet({&e2}), std::make_shared<IndependentAction>());
 312   UnfoldingEvent e4(EventSet({&e3}), std::make_shared<IndependentAction>());
 313   UnfoldingEvent e5(EventSet({&e4}), std::make_shared<IndependentAction>());
 314   UnfoldingEvent e6(EventSet({&e4}), std::make_shared<IndependentAction>());
 315   UnfoldingEvent e7(EventSet({&e2, &e8}), std::make_shared<IndependentAction>());
 316   UnfoldingEvent e9(EventSet({&e6, &e7}), std::make_shared<IndependentAction>());
 317   UnfoldingEvent e10(EventSet({&e7}), std::make_shared<IndependentAction>());
 318   UnfoldingEvent e11(EventSet({&e8}), std::make_shared<IndependentAction>());
 319   UnfoldingEvent e12(EventSet({&e5, &e9, &e10}), std::make_shared<IndependentAction>());
 320   Configuration C{&e1, &e2, &e3, &e4, &e5, &e6, &e7, &e8, &e9, &e10, &e11, &e12};
 321
 322   SECTION("Test every combination of the maximal configuration (forward graph)")
 323   {
 324     // To test this, we ensure that for the `i`th event
 325     // in `ordered_events`, each event in `ordered_events[0...<i]
 326     // is contained in the history of `ordered_events[i]`.
 327     EventSet events_seen;
 328     const auto ordered_events = C.get_topologically_sorted_events();
 329
 330     std::for_each(ordered_events.begin(), ordered_events.end(), [&events_seen](const UnfoldingEvent* e) {
 331       History history(e);
 332       for (auto* e_hist : history) {
 333         // In this demo, we want to make sure that
 334         // we don't mark not yet seeing `e` as an error.
 335         // The history of `e` traverses `e` itself. All
 336         // other events in e's history are included in
 337         if (e_hist == e)
 338           continue;
 339
 340         // If this event has not been "seen" before,
 341         // this implies that event `e` appears earlier
 342         // in the list than one of its dependencies
 343         REQUIRE(events_seen.contains(e_hist));
 344       }
 345       events_seen.insert(e);
 346     });
 347   }
 348
 349   SECTION("Test every combination of the maximal configuration (reverse graph)")
 350   {
 351     // To test this, we ensure that for the `i`th event
 352     // in `ordered_events`, no event in `ordered_events[0...<i]
 353     // is contained in the history of `ordered_events[i]`.
 354     EventSet events_seen;
 355     const auto ordered_events = C.get_topologically_sorted_events_of_reverse_graph();
 356
 357     std::for_each(ordered_events.begin(), ordered_events.end(), [&events_seen](const UnfoldingEvent* e) {
 358       History history(e);
 359
 360       for (auto* e_hist : history) {
 361         // Unlike the test above, we DO want to ensure
 362         // that `e` itself ALSO isn't yet seen
 363
 364         // If this event has been "seen" before,
 365         // this implies that event `e` appears later
 366         // in the list than one of its ancestors
 367         REQUIRE_FALSE(events_seen.contains(e_hist));
 368       }
 369       events_seen.insert(e);
 370     });
 371   }
 372
 373   SECTION("Test that the topological ordering contains only the events of the configuration")
 374   {
 375     const EventSet events_seen = C.get_events();
 376
 377     SECTION("Forward direction")
 378     {
 379       auto ordered_events              = C.get_topologically_sorted_events();
 380       const EventSet ordered_event_set = EventSet(std::move(ordered_events));
 381       REQUIRE(events_seen == ordered_event_set);
 382     }
 383
 384     SECTION("Reverse direction")
 385     {
 386       auto ordered_events              = C.get_topologically_sorted_events_of_reverse_graph();
 387       const EventSet ordered_event_set = EventSet(std::move(ordered_events));
 388       REQUIRE(events_seen == ordered_event_set);
 389     }
 390   }
 391
 392   SECTION("Test that the topological ordering is equivalent to that of the configuration's events")
 393   {
 394     REQUIRE(C.get_topologically_sorted_events() == C.get_events().get_topological_ordering());
 395     REQUIRE(C.get_topologically_sorted_events_of_reverse_graph() ==
 396             C.get_events().get_topological_ordering_of_reverse_graph());
 397   }
 398 }
 399
 400 TEST_CASE("simgrid::mc::udpor::maximal_subsets_iterator: Basic Testing of Maximal Subsets")
 401 {
 402   // The following tests concern the given event structure:
 403   //                e1
 404   //              /   /
 405   //             e2   e5
 406   //            /     /
 407   //           e3    e6
 408   //           /     / /
 409   //          e4    e7 e8
 410   UnfoldingEvent e1(EventSet(), std::make_shared<IndependentAction>());
 411   UnfoldingEvent e2(EventSet({&e1}), std::make_shared<IndependentAction>());
 412   UnfoldingEvent e3(EventSet({&e2}), std::make_shared<IndependentAction>());
 413   UnfoldingEvent e4(EventSet({&e3}), std::make_shared<IndependentAction>());
 414   UnfoldingEvent e5(EventSet({&e1}), std::make_shared<IndependentAction>());
 415   UnfoldingEvent e6(EventSet({&e5}), std::make_shared<IndependentAction>());
 416   UnfoldingEvent e7(EventSet({&e6}), std::make_shared<IndependentAction>());
 417   UnfoldingEvent e8(EventSet({&e6}), std::make_shared<IndependentAction>());
 418
 419   SECTION("Iteration over an empty configuration yields only the empty set")
 420   {
 421     Configuration C;
 422     maximal_subsets_iterator first(C);
 423     maximal_subsets_iterator last;
 424
 425     REQUIRE(*first == EventSet());
 426     ++first;
 427     REQUIRE(first == last);
 428   }
 429
 430   SECTION("Check counts of maximal event sets discovered")
 431   {
 432     std::unordered_map<int, int> maximal_subset_counts;
 433
 434     Configuration C{&e1, &e2, &e3, &e4, &e5, &e6, &e7, &e8};
 435     maximal_subsets_iterator first(C);
 436     maximal_subsets_iterator last;
 437
 438     for (; first != last; ++first) {
 439       maximal_subset_counts[(*first).size()]++;
 440     }
 441
 442     // First, ensure that there are only sets of size 0, 1, 2, and 3
 443     CHECK(maximal_subset_counts.size() == 4);
 444
 445     // The empty set should appear only once
 446     REQUIRE(maximal_subset_counts[0] == 1);
 447
 448     // 8 is the number of nodes in the graph
 449     REQUIRE(maximal_subset_counts[1] == 8);
 450
 451     // 13 = 3 * 4 (each of the left branch can combine with one in the right branch) + 1 (e7 + e8)
 452     REQUIRE(maximal_subset_counts[2] == 13);
 453
 454     // e7 + e8 must be included, so that means we can combine from the left branch
 455     REQUIRE(maximal_subset_counts[3] == 3);
 456   }
 457
 458   SECTION("Check counts of maximal event sets discovered with a filter")
 459   {
 460     std::unordered_map<int, int> maximal_subset_counts;
 461
 462     Configuration C{&e1, &e2, &e3, &e4, &e5, &e6, &e7, &e8};
 463
 464     SECTION("Filter with events part of initial maximal set")
 465     {
 466       EventSet interesting_bunch{&e2, &e4, &e7, &e8};
 467
 468       maximal_subsets_iterator first(C, [&](const UnfoldingEvent* e) { return interesting_bunch.contains(e); });
 469       maximal_subsets_iterator last;
 470
 471       for (; first != last; ++first) {
 472         const auto& event_set = *first;
 473         // Only events in `interesting_bunch` can appear: thus no set
 474         // should include anything else other than `interesting_bunch`
 475         REQUIRE(event_set.is_subset_of(interesting_bunch));
 476         REQUIRE(event_set.is_maximal());
 477         maximal_subset_counts[event_set.size()]++;
 478       }
 479
 480       // The empty set should (still) appear only once
 481       REQUIRE(maximal_subset_counts[0] == 1);
 482
 483       // 4 is the number of nodes in the `interesting_bunch`
 484       REQUIRE(maximal_subset_counts[1] == 4);
 485
 486       // 5 = 2 * 2 (each of the left branch can combine with one in the right branch) + 1 (e7 + e8)
 487       REQUIRE(maximal_subset_counts[2] == 5);
 488
 489       // e7 + e8 must be included, so that means we can combine from the left branch (only e2 and e4)
 490       REQUIRE(maximal_subset_counts[3] == 2);
 491
 492       // There are no subsets of size 4 (or higher, but that
 493       // is tested by asserting each maximal set traversed is a subset)
 494       REQUIRE(maximal_subset_counts[4] == 0);
 495     }
 496
 497     SECTION("Filter with interesting subset not initially part of the maximal set")
 498     {
 499       EventSet interesting_bunch{&e3, &e5, &e6};
 500
 501       maximal_subsets_iterator first(C, [&](const UnfoldingEvent* e) { return interesting_bunch.contains(e); });
 502       maximal_subsets_iterator last;
 503
 504       for (; first != last; ++first) {
 505         const auto& event_set = *first;
 506         // Only events in `interesting_bunch` can appear: thus no set
 507         // should include anything else other than `interesting_bunch`
 508         REQUIRE(event_set.is_subset_of(interesting_bunch));
 509         REQUIRE(event_set.is_maximal());
 510         maximal_subset_counts[event_set.size()]++;
 511       }
 512
 513       // The empty set should (still) appear only once
 514       REQUIRE(maximal_subset_counts[0] == 1);
 515
 516       // 3 is the number of nodes in the `interesting_bunch`
 517       REQUIRE(maximal_subset_counts[1] == 3);
 518
 519       // 2 = e3, e5 and e3, e6
 520       REQUIRE(maximal_subset_counts[2] == 2);
 521
 522       // There are no subsets of size 3 (or higher, but that
 523       // is tested by asserting each maximal set traversed is a subset)
 524       REQUIRE(maximal_subset_counts[3] == 0);
 525     }
 526   }
 527 }
 528
 529 TEST_CASE("simgrid::mc::udpor::maximal_subsets_iterator: Stress Test for Maximal Subsets Iteration")
 530 {
 531   // The following tests concern the given event structure:
 532   //                              e1
 533   //                            /   /
 534   //                          e2    e3
 535   //                          / /   /  /
 536   //               +------* e4 *e5 e6  e7
 537   //               |        /   ///   /  /
 538   //               |       e8   e9    e10
 539   //               |      /  /   /\      /
 540   //               |   e11 e12 e13 e14   e15
 541   //               |   /      / / /   /  /
 542   //               +-> e16     e17     e18
 543   UnfoldingEvent e1(EventSet(), std::make_shared<IndependentAction>());
 544   UnfoldingEvent e2(EventSet({&e1}), std::make_shared<IndependentAction>());
 545   UnfoldingEvent e3(EventSet({&e1}), std::make_shared<IndependentAction>());
 546   UnfoldingEvent e4(EventSet({&e2}), std::make_shared<IndependentAction>());
 547   UnfoldingEvent e5(EventSet({&e2}), std::make_shared<IndependentAction>());
 548   UnfoldingEvent e6(EventSet({&e3}), std::make_shared<IndependentAction>());
 549   UnfoldingEvent e7(EventSet({&e3}), std::make_shared<IndependentAction>());
 550   UnfoldingEvent e8(EventSet({&e4}), std::make_shared<IndependentAction>());
 551   UnfoldingEvent e9(EventSet({&e4, &e5, &e6}), std::make_shared<IndependentAction>());
 552   UnfoldingEvent e10(EventSet({&e6, &e7}), std::make_shared<IndependentAction>());
 553   UnfoldingEvent e11(EventSet({&e8}), std::make_shared<IndependentAction>());
 554   UnfoldingEvent e12(EventSet({&e8}), std::make_shared<IndependentAction>());
 555   UnfoldingEvent e13(EventSet({&e9}), std::make_shared<IndependentAction>());
 556   UnfoldingEvent e14(EventSet({&e9}), std::make_shared<IndependentAction>());
 557   UnfoldingEvent e15(EventSet({&e10}), std::make_shared<IndependentAction>());
 558   UnfoldingEvent e16(EventSet({&e5, &e11}), std::make_shared<IndependentAction>());
 559   UnfoldingEvent e17(EventSet({&e12, &e13, &e14}), std::make_shared<IndependentAction>());
 560   UnfoldingEvent e18(EventSet({&e14, &e15}), std::make_shared<IndependentAction>());
 561   Configuration C{&e1, &e2, &e3, &e4, &e5, &e6, &e7, &e8, &e9, &e10, &e11, &e12, &e13, &e14, &e15, &e16, &e17, &e18};
 562
 563   SECTION("Every subset iterated over is maximal")
 564   {
 565     maximal_subsets_iterator first(C);
 566     maximal_subsets_iterator last;
 567
 568     // Make sure we actually have something to iterate over
 569     REQUIRE(first != last);
 570
 571     for (; first != last; ++first) {
 572       REQUIRE((*first).size() <= C.get_events().size());
 573       REQUIRE((*first).is_maximal());
 574     }
 575   }
 576
 577   SECTION("Test that the maximal set ordering is equivalent to that of the configuration's events")
 578   {
 579     maximal_subsets_iterator first_config(C);
 580     maximal_subsets_iterator first_events(C.get_events());
 581     maximal_subsets_iterator last;
 582
 583     // Make sure we actually have something to iterate over
 584     REQUIRE(first_config != last);
 585     REQUIRE(first_config == first_events);
 586     REQUIRE(first_events != last);
 587
 588     for (; first_config != last; ++first_config, ++first_events) {
 589       // first_events and first_config should always be at the same location
 590       REQUIRE(first_events != last);
 591       const auto& first_config_set = *first_config;
 592       const auto& first_events_set = *first_events;
 593
 594       REQUIRE(first_config_set.size() <= C.get_events().size());
 595       REQUIRE(first_config_set.is_maximal());
 596       REQUIRE(first_events_set == first_config_set);
 597     }
 598
 599     // Iteration with events directly should now also be finished
 600     REQUIRE(first_events == last);
 601   }
 602 }
 603
 604 TEST_CASE("simgrid::mc::udpor:Configuration: Computing Full Alternatives in Reader/Writer Example")
 605 {
 606   // The following tests concern the given event structure that is given as
 607   // an example in figure 1 of the original UDPOR paper.
 608   //                  e0
 609   //              /  /   /
 610   //            e1   e4   e7
 611   //           /     /  //   /
 612   //         /  /   e5  e8   e9
 613   //        e2 e3   /        /
 614   //               e6       e10
 615   //
 616   // Theses tests walk through exactly the configurations and sets of `D` that
 617   // UDPOR COULD encounter as it walks through the unfolding. Note that
 618   // if there are multiple alternatives to any given configuration, UDPOR can
 619   // continue searching any one of them. The sequence assumes UDPOR first picks `e1`,
 620   // then `e4`, and then `e7`
 621   Unfolding U;
 622
 623   auto e0        = std::make_unique<UnfoldingEvent>(EventSet(), std::make_shared<ConditionallyDependentAction>());
 624   auto e0_handle = e0.get();
 625
 626   auto e1        = std::make_unique<UnfoldingEvent>(EventSet({e0_handle}), std::make_shared<DependentAction>());
 627   auto e1_handle = e1.get();
 628
 629   auto e2 = std::make_unique<UnfoldingEvent>(EventSet({e1_handle}), std::make_shared<ConditionallyDependentAction>());
 630   auto e2_handle = e2.get();
 631
 632   auto e3 = std::make_unique<UnfoldingEvent>(EventSet({e1_handle}), std::make_shared<ConditionallyDependentAction>());
 633   auto e3_handle = e3.get();
 634
 635   auto e4 = std::make_unique<UnfoldingEvent>(EventSet({e0_handle}), std::make_shared<ConditionallyDependentAction>());
 636   auto e4_handle = e4.get();
 637
 638   auto e5        = std::make_unique<UnfoldingEvent>(EventSet({e4_handle}), std::make_shared<DependentAction>());
 639   auto e5_handle = e5.get();
 640
 641   auto e6 = std::make_unique<UnfoldingEvent>(EventSet({e5_handle}), std::make_shared<ConditionallyDependentAction>());
 642   auto e6_handle = e6.get();
 643
 644   auto e7 = std::make_unique<UnfoldingEvent>(EventSet({e0_handle}), std::make_shared<ConditionallyDependentAction>());
 645   auto e7_handle = e7.get();
 646
 647   auto e8 = std::make_unique<UnfoldingEvent>(EventSet({e4_handle, e7_handle}), std::make_shared<DependentAction>());
 648   auto e8_handle = e8.get();
 649
 650   auto e9        = std::make_unique<UnfoldingEvent>(EventSet({e7_handle}), std::make_shared<DependentAction>());
 651   auto e9_handle = e9.get();
 652
 653   auto e10 = std::make_unique<UnfoldingEvent>(EventSet({e9_handle}), std::make_shared<ConditionallyDependentAction>());
 654   auto e10_handle = e10.get();
 655
 656   SECTION("Alternative computation call 1")
 657   {
 658     // During the first call to Alt(C, D + {e}),
 659     // UDPOR believes `U` to be the following:
 660     //
 661     //                  e0
 662     //              /  /   /
 663     //            e1   e4   e7
 664     //           /
 665     //         /  /
 666     //        e2 e3
 667     //
 668     // C := {e0, e1, e2} and `Explore(C, D, A)` picked `e3`
 669     // (since en(C') where C' := {e0, e1, e2, e3} is empty
 670     // [so UDPOR will simply return when C' is reached])
 671     //
 672     // Thus the computation is (since D is empty at first)
 673     //
 674     // Alt(C, D + {e}) --> Alt({e0, e1, e2}, {e3})
 675     //
 676     // where U is given above. There are no alternatives in
 677     // this case since `e4` and `e7` conflict with `e1` (so
 678     // they cannot be added to C to form a configuration)
 679     const Configuration C{e0_handle, e1_handle, e2_handle};
 680     const EventSet D_plus_e{e3_handle};
 681
 682     REQUIRE(U.empty());
 683     U.insert(std::move(e0));
 684     U.insert(std::move(e1));
 685     U.insert(std::move(e2));
 686     U.insert(std::move(e3));
 687     U.insert(std::move(e4));
 688     U.insert(std::move(e7));
 689
 690     const auto alternative = C.compute_alternative_to(D_plus_e, U);
 691     REQUIRE_FALSE(alternative.has_value());
 692   }
 693
 694   SECTION("Alternative computation call 2")
 695   {
 696     // During the second call to Alt(C, D + {e}),
 697     // UDPOR believes `U` to be the following:
 698     //
 699     //                  e0
 700     //              /  /   /
 701     //            e1   e4   e7
 702     //           /
 703     //         /  /
 704     //        e2 e3
 705     //
 706     // C := {e0, e1} and `Explore(C, D, A)` picked `e2`.
 707     //
 708     // Thus the computation is (since D is still empty)
 709     //
 710     // Alt(C, D + {e}) --> Alt({e0, e1}, {e2})
 711     //
 712     // where U is given above. There are no alternatives in
 713     // this case since `e4` and `e7` conflict with `e1` (so
 714     // they cannot be added to C to form a configuration) and
 715     // e3 is NOT in conflict with either e0 or e1
 716     const Configuration C{e0_handle, e1_handle};
 717     const EventSet D_plus_e{e2_handle};
 718
 719     REQUIRE(U.empty());
 720     U.insert(std::move(e0));
 721     U.insert(std::move(e1));
 722     U.insert(std::move(e2));
 723     U.insert(std::move(e3));
 724     U.insert(std::move(e4));
 725     U.insert(std::move(e7));
 726
 727     const auto alternative = C.compute_alternative_to(D_plus_e, U);
 728     REQUIRE_FALSE(alternative.has_value());
 729   }
 730
 731   SECTION("Alternative computation call 3")
 732   {
 733     // During the thrid call to Alt(C, D + {e}),
 734     // UDPOR believes `U` to be the following:
 735     //
 736     //                 e0
 737     //              /  /   /
 738     //            e1   e4   e7
 739     //           /
 740     //         /  /
 741     //        e2 e3
 742     //
 743     // C := {e0} and `Explore(C, D, A)` picked `e1`.
 744     //
 745     // Thus the computation is (since D is still empty)
 746     //
 747     // Alt(C, D + {e}) --> Alt({e0}, {e1})
 748     //
 749     // where U is given above. There are two alternatives in this case:
 750     // {e0, e4} and {e0, e7}. Either one would be a valid choice for
 751     // UDPOR, so we must check for the precense of either
 752     const Configuration C{e0_handle};
 753     const EventSet D_plus_e{e1_handle};
 754
 755     REQUIRE(U.empty());
 756     U.insert(std::move(e0));
 757     U.insert(std::move(e1));
 758     U.insert(std::move(e2));
 759     U.insert(std::move(e3));
 760     U.insert(std::move(e4));
 761     U.insert(std::move(e7));
 762
 763     const auto alternative = C.compute_alternative_to(D_plus_e, U);
 764     REQUIRE(alternative.has_value());
 765
 766     // The first alternative that is found is the one that is chosen. Since
 767     // traversal over the elements of an unordered_set<> are not guaranteed,
 768     // both {e0, e4} and {e0, e7} are valid alternatives
 769     REQUIRE((alternative.value().get_events() == EventSet({e0_handle, e4_handle}) or
 770              alternative.value().get_events() == EventSet({e0_handle, e7_handle})));
 771   }
 772
 773   SECTION("Alternative computation call 4")
 774   {
 775     // During the fourth call to Alt(C, D + {e}),
 776     // UDPOR believes `U` to be the following:
 777     //
 778     //                  e0
 779     //              /  /   /
 780     //            e1   e4   e7
 781     //           /     /  //
 782     //         /  /   e5  e8
 783     //        e2 e3   /
 784     //               e6
 785     //
 786     // C := {e0, e4, e5} and `Explore(C, D, A)` picked `e6`
 787     // (since en(C') where C' := {e0, e4, e5, e6} is empty
 788     // [so UDPOR will simply return when C' is reached])
 789     //
 790     // Thus the computation is (since D is {e1})
 791     //
 792     // Alt(C, D + {e}) --> Alt({e0, e4, e5}, {e1, e6})
 793     //
 794     // where U is given above. There are no alternatives in this
 795     // case, since:
 796     //
 797     // 1.`e2/e3` are eliminated since their histories contain `e1`
 798     // 2. `e7/e8` are eliminated because they conflict with `e5`
 799     const Configuration C{e0_handle, e4_handle, e5_handle};
 800     const EventSet D_plus_e{e1_handle, e6_handle};
 801
 802     REQUIRE(U.empty());
 803     U.insert(std::move(e0));
 804     U.insert(std::move(e1));
 805     U.insert(std::move(e2));
 806     U.insert(std::move(e3));
 807     U.insert(std::move(e4));
 808     U.insert(std::move(e6));
 809     U.insert(std::move(e7));
 810     U.insert(std::move(e8));
 811
 812     const auto alternative = C.compute_alternative_to(D_plus_e, U);
 813     REQUIRE_FALSE(alternative.has_value());
 814   }
 815
 816   SECTION("Alternative computation call 5")
 817   {
 818     // During the fifth call to Alt(C, D + {e}),
 819     // UDPOR believes `U` to be the following:
 820     //
 821     //                  e0
 822     //              /  /   /
 823     //            e1   e4   e7
 824     //           /     /  //
 825     //         /  /   e5  e8
 826     //        e2 e3   /
 827     //               e6
 828     //
 829     // C := {e0, e4} and `Explore(C, D, A)` picked `e5`
 830     // (since en(C') where C' := {e0, e4, e5, e6} is empty
 831     // [so UDPOR will simply return when C' is reached])
 832     //
 833     // Thus the computation is (since D is {e1})
 834     //
 835     // Alt(C, D + {e}) --> Alt({e0, e4}, {e1, e5})
 836     //
 837     // where U is given above. There are THREE alternatives in this case,
 838     // viz. {e0, e7}, {e0, e4, e7} and {e0, e4, e7, e8}.
 839     //
 840     // To continue the search, UDPOR computes J / C which in this
 841     // case gives {e7, e8}. Since `e8` is not in en(C), UDPOR will
 842     // choose `e7` next and add `e5` to `D`
 843     const Configuration C{e0_handle, e4_handle};
 844     const EventSet D_plus_e{e1_handle, e5_handle};
 845
 846     REQUIRE(U.empty());
 847     U.insert(std::move(e0));
 848     U.insert(std::move(e1));
 849     U.insert(std::move(e2));
 850     U.insert(std::move(e3));
 851     U.insert(std::move(e4));
 852     U.insert(std::move(e6));
 853     U.insert(std::move(e7));
 854     U.insert(std::move(e8));
 855     REQUIRE(U.size() == 8);
 856
 857     const auto alternative = C.compute_alternative_to(D_plus_e, U);
 858     REQUIRE(alternative.has_value());
 859     REQUIRE((alternative.value().get_events() == EventSet({e0_handle, e7_handle}) or
 860              alternative.value().get_events() == EventSet({e0_handle, e4_handle, e7_handle}) or
 861              alternative.value().get_events() == EventSet({e0_handle, e4_handle, e7_handle, e8_handle})));
 862   }
 863
 864   SECTION("Alternative computation call 6")
 865   {
 866     // During the sixth call to Alt(C, D + {e}),
 867     // UDPOR believes `U` to be the following:
 868     //
 869     //                 e0
 870     //              /  /   /
 871     //            e1   e4   e7
 872     //           /     /  //   /
 873     //         /  /   e5  e8   e9
 874     //        e2 e3   /
 875     //               e6
 876     //
 877     // C := {e0, e4, e7} and `Explore(C, D, A)` picked `e8`
 878     // (since en(C') where C' := {e0, e4, e7, e8} is empty
 879     // [so UDPOR will simply return when C' is reached])
 880     //
 881     // Thus the computation is (since D is {e1, e5} [see the last step])
 882     //
 883     // Alt(C, D + {e}) --> Alt({e0, e4, e7}, {e1, e5, e8})
 884     //
 885     // where U is given above. There are no alternatives in this case
 886     // since all `e9` conflicts with `e4` and all other events of `U`
 887     // are eliminated since their history intersects `D`
 888     const Configuration C{e0_handle, e4_handle, e7_handle};
 889     const EventSet D_plus_e{e1_handle, e5_handle, e8_handle};
 890
 891     REQUIRE(U.empty());
 892     U.insert(std::move(e0));
 893     U.insert(std::move(e1));
 894     U.insert(std::move(e2));
 895     U.insert(std::move(e3));
 896     U.insert(std::move(e4));
 897     U.insert(std::move(e6));
 898     U.insert(std::move(e7));
 899     U.insert(std::move(e8));
 900     U.insert(std::move(e9));
 901
 902     const auto alternative = C.compute_alternative_to(D_plus_e, U);
 903     REQUIRE_FALSE(alternative.has_value());
 904   }
 905
 906   SECTION("Alternative computation call 7")
 907   {
 908     // During the seventh call to Alt(C, D + {e}),
 909     // UDPOR believes `U` to be the following:
 910     //
 911     //                 e0
 912     //              /  /   /
 913     //            e1   e4   e7
 914     //           /     /  //   /
 915     //         /  /   e5  e8   e9
 916     //        e2 e3   /
 917     //               e6
 918     //
 919     // C := {e0, e4} and `Explore(C, D, A)` picked `e7`
 920     //
 921     // Thus the computation is (since D is {e1, e5} [see call 5])
 922     //
 923     // Alt(C, D + {e}) --> Alt({e0, e4}, {e1, e5, e7})
 924     //
 925     // where U is given above. There are no alternatives again in this case
 926     // since all `e9` conflicts with `e4` and all other events of `U`
 927     // are eliminated since their history intersects `D`
 928     const Configuration C{e0_handle, e4_handle};
 929     const EventSet D_plus_e{e1_handle, e5_handle, e7_handle};
 930
 931     REQUIRE(U.empty());
 932     U.insert(std::move(e0));
 933     U.insert(std::move(e1));
 934     U.insert(std::move(e2));
 935     U.insert(std::move(e3));
 936     U.insert(std::move(e4));
 937     U.insert(std::move(e6));
 938     U.insert(std::move(e7));
 939     U.insert(std::move(e8));
 940     U.insert(std::move(e9));
 941
 942     const auto alternative = C.compute_alternative_to(D_plus_e, U);
 943     REQUIRE_FALSE(alternative.has_value());
 944   }
 945
 946   SECTION("Alternative computation call 8")
 947   {
 948     // During the eigth call to Alt(C, D + {e}),
 949     // UDPOR believes `U` to be the following:
 950     //
 951     //                 e0
 952     //              /  /   /
 953     //            e1   e4   e7
 954     //           /     /  //   /
 955     //         /  /   e5  e8   e9
 956     //        e2 e3   /
 957     //               e6
 958     //
 959     // C := {e0} and `Explore(C, D, A)` picked `e4`. At this
 960     // point, UDPOR finished its recursive search of {e0, e4}
 961     // after having finished {e0, e1} prior.
 962     //
 963     // Thus the computation is (since D = {e1})
 964     //
 965     // Alt(C, D + {e}) --> Alt({e0}, {e1, e4})
 966     //
 967     // where U is given above. There is one alternative in this
 968     // case, viz {e0, e7, e9} since
 969     // 1. e9 conflicts with e4 in D
 970     // 2. e7 conflicts with e1 in D
 971     // 3. the set {e7, e9} is conflict-free since `e7 < e9`
 972     // 4. all other events are eliminated since their histories
 973     // intersect D
 974     //
 975     // UDPOR will continue its recursive search following `e7`
 976     // and add `e4` to D
 977     const Configuration C{e0_handle};
 978     const EventSet D_plus_e{e1_handle, e4_handle};
 979
 980     REQUIRE(U.empty());
 981     U.insert(std::move(e0));
 982     U.insert(std::move(e1));
 983     U.insert(std::move(e2));
 984     U.insert(std::move(e3));
 985     U.insert(std::move(e4));
 986     U.insert(std::move(e6));
 987     U.insert(std::move(e7));
 988     U.insert(std::move(e8));
 989     U.insert(std::move(e9));
 990
 991     const auto alternative = C.compute_alternative_to(D_plus_e, U);
 992     REQUIRE(alternative.has_value());
 993     REQUIRE(alternative.value().get_events() == EventSet({e0_handle, e7_handle, e9_handle}));
 994   }
 995
 996   SECTION("Alternative computation call 9")
 997   {
 998     // During the ninth call to Alt(C, D + {e}),
 999     // UDPOR believes `U` to be the following:
1000     //
1001     //                  e0
1002     //              /  /   /
1003     //            e1   e4   e7
1004     //           /     /  //   /
1005     //         /  /   e5  e8   e9
1006     //        e2 e3   /        /
1007     //               e6       e10
1008     //
1009     // C := {e0, e7, e9} and `Explore(C, D, A)` picked `e10`.
1010     // (since en(C') where C' := {e0, e7, e9, e10} is empty
1011     // [so UDPOR will simply return when C' is reached]).
1012     //
1013     // Thus the computation is (since D = {e1, e4} [see the previous step])
1014     //
1015     // Alt(C, D + {e}) --> Alt({e0}, {e1, e4, e10})
1016     //
1017     // where U is given above. There are no alternatives in this case
1018     const Configuration C{e0_handle, e7_handle, e9_handle};
1019     const EventSet D_plus_e{e1_handle, e4_handle, e10_handle};
1020
1021     REQUIRE(U.empty());
1022     U.insert(std::move(e0));
1023     U.insert(std::move(e1));
1024     U.insert(std::move(e2));
1025     U.insert(std::move(e3));
1026     U.insert(std::move(e4));
1027     U.insert(std::move(e6));
1028     U.insert(std::move(e7));
1029     U.insert(std::move(e8));
1030     U.insert(std::move(e9));
1031     U.insert(std::move(e10));
1032
1033     const auto alternative = C.compute_alternative_to(D_plus_e, U);
1034     REQUIRE_FALSE(alternative.has_value());
1035   }
1036
1037   SECTION("Alternative computation call 10")
1038   {
1039     // During the tenth call to Alt(C, D + {e}),
1040     // UDPOR believes `U` to be the following:
1041     //
1042     //                  e0
1043     //              /  /   /
1044     //            e1   e4   e7
1045     //           /     /  //   /
1046     //         /  /   e5  e8   e9
1047     //        e2 e3   /        /
1048     //               e6       e10
1049     //
1050     // C := {e0, e7} and `Explore(C, D, A)` picked `e9`.
1051     //
1052     // Thus the computation is (since D = {e1, e4} [see call 8])
1053     //
1054     // Alt(C, D + {e}) --> Alt({e0}, {e1, e4, e9})
1055     //
1056     // where U is given above. There are no alternatives in this case
1057     const Configuration C{e0_handle, e7_handle};
1058     const EventSet D_plus_e{e1_handle, e4_handle, e9_handle};
1059
1060     REQUIRE(U.empty());
1061     U.insert(std::move(e0));
1062     U.insert(std::move(e1));
1063     U.insert(std::move(e2));
1064     U.insert(std::move(e3));
1065     U.insert(std::move(e4));
1066     U.insert(std::move(e6));
1067     U.insert(std::move(e7));
1068     U.insert(std::move(e8));
1069     U.insert(std::move(e9));
1070     U.insert(std::move(e10));
1071
1072     const auto alternative = C.compute_alternative_to(D_plus_e, U);
1073     REQUIRE_FALSE(alternative.has_value());
1074   }
1075
1076   SECTION("Alternative computation call 11 (final call)")
1077   {
1078     // During the eleventh and final call to Alt(C, D + {e}),
1079     // UDPOR believes `U` to be the following:
1080     //
1081     //                  e0
1082     //              /  /   /
1083     //            e1   e4   e7
1084     //           /     /  //   /
1085     //         /  /   e5  e8   e9
1086     //        e2 e3   /        /
1087     //               e6       e10
1088     //
1089     // C := {e0} and `Explore(C, D, A)` picked `e7`.
1090     //
1091     // Thus the computation is (since D = {e1, e4} [see call 8])
1092     //
1093     // Alt(C, D + {e}) --> Alt({e0}, {e1, e4, e7})
1094     //
1095     // where U is given above. There are no alternatives in this case:
1096     // everyone is eliminated!
1097     const Configuration C{e0_handle, e7_handle};
1098     const EventSet D_plus_e{e1_handle, e4_handle, e9_handle};
1099
1100     REQUIRE(U.empty());
1101     U.insert(std::move(e0));
1102     U.insert(std::move(e1));
1103     U.insert(std::move(e2));
1104     U.insert(std::move(e3));
1105     U.insert(std::move(e4));
1106     U.insert(std::move(e6));
1107     U.insert(std::move(e7));
1108     U.insert(std::move(e8));
1109     U.insert(std::move(e9));
1110     U.insert(std::move(e10));
1111
1112     const auto alternative = C.compute_alternative_to(D_plus_e, U);
1113     REQUIRE_FALSE(alternative.has_value());
1114   }
1115
1116   SECTION("Alternative computation next")
1117   {
1118     SECTION("Followed {e0, e7} first")
1119     {
1120       const EventSet D{e1_handle, e7_handle};
1121       const Configuration C{e0_handle};
1122
1123       REQUIRE(U.empty());
1124       U.insert(std::move(e0));
1125       U.insert(std::move(e1));
1126       U.insert(std::move(e2));
1127       U.insert(std::move(e3));
1128       U.insert(std::move(e4));
1129       U.insert(std::move(e5));
1130       U.insert(std::move(e7));
1131       U.insert(std::move(e8));
1132       U.insert(std::move(e9));
1133       U.insert(std::move(e10));
1134
1135       const auto alternative = C.compute_alternative_to(D, U);
1136       REQUIRE(alternative.has_value());
1137
1138       // In this case, only {e0, e4} is a valid alternative
1139       REQUIRE(alternative.value().get_events() == EventSet({e0_handle, e4_handle, e5_handle}));
1140     }
1141
1142     SECTION("Followed {e0, e4} first")
1143     {
1144       const EventSet D{e1_handle, e4_handle};
1145       const Configuration C{e0_handle};
1146
1147       REQUIRE(U.empty());
1148       U.insert(std::move(e0));
1149       U.insert(std::move(e1));
1150       U.insert(std::move(e2));
1151       U.insert(std::move(e3));
1152       U.insert(std::move(e4));
1153       U.insert(std::move(e5));
1154       U.insert(std::move(e6));
1155       U.insert(std::move(e7));
1156       U.insert(std::move(e8));
1157       U.insert(std::move(e9));
1158
1159       const auto alternative = C.compute_alternative_to(D, U);
1160       REQUIRE(alternative.has_value());
1161
1162       // In this case, only {e0, e7} is a valid alternative
1163       REQUIRE(alternative.value().get_events() == EventSet({e0_handle, e7_handle, e9_handle}));
1164     }
1165   }
1166 }