src/mc/explo/udpor/EventSet_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/EventSet.hpp"
   8 #include "src/mc/explo/udpor/UnfoldingEvent.hpp"
   9
  10 using namespace simgrid::mc::udpor;
  11
  12 TEST_CASE("simgrid::mc::udpor::EventSet: Initial conditions when creating sets")
  13 {
  14   SECTION("Initialization with no elements")
  15   {
  16     SECTION("Default initializer")
  17     {
  18       EventSet event_set;
  19       REQUIRE(event_set.size() == 0);
  20       REQUIRE(event_set.empty());
  21     }
  22
  23     SECTION("Set initializer")
  24     {
  25       EventSet event_set({});
  26       REQUIRE(event_set.size() == 0);
  27       REQUIRE(event_set.empty());
  28     }
  29
  30     SECTION("List initialization")
  31     {
  32       EventSet event_set{};
  33       REQUIRE(event_set.size() == 0);
  34       REQUIRE(event_set.empty());
  35     }
  36   }
  37
  38   SECTION("Initialization with one or more elements")
  39   {
  40     UnfoldingEvent e1, e2, e3;
  41
  42     SECTION("Set initializer")
  43     {
  44       EventSet event_set({&e1, &e2, &e3});
  45       REQUIRE(event_set.size() == 3);
  46       REQUIRE(event_set.contains(&e1));
  47       REQUIRE(event_set.contains(&e2));
  48       REQUIRE(event_set.contains(&e3));
  49       REQUIRE_FALSE(event_set.empty());
  50     }
  51
  52     SECTION("List initialization")
  53     {
  54       EventSet event_set{&e1, &e2, &e3};
  55       REQUIRE(event_set.size() == 3);
  56       REQUIRE(event_set.contains(&e1));
  57       REQUIRE(event_set.contains(&e2));
  58       REQUIRE(event_set.contains(&e3));
  59       REQUIRE_FALSE(event_set.empty());
  60     }
  61   }
  62 }
  63
  64 TEST_CASE("simgrid::mc::udpor::EventSet: Insertions")
  65 {
  66   EventSet event_set;
  67   UnfoldingEvent e1, e2, e3;
  68
  69   SECTION("Inserting unique elements")
  70   {
  71     event_set.insert(&e1);
  72     REQUIRE(event_set.size() == 1);
  73     REQUIRE(event_set.contains(&e1));
  74     REQUIRE_FALSE(event_set.empty());
  75
  76     event_set.insert(&e2);
  77     REQUIRE(event_set.size() == 2);
  78     REQUIRE(event_set.contains(&e2));
  79     REQUIRE_FALSE(event_set.empty());
  80
  81     SECTION("Check contains inserted elements")
  82     {
  83       REQUIRE(event_set.contains(&e1));
  84       REQUIRE(event_set.contains(&e2));
  85       REQUIRE_FALSE(event_set.contains(&e3));
  86     }
  87   }
  88
  89   SECTION("Inserting duplicate elements")
  90   {
  91     event_set.insert(&e1);
  92     REQUIRE(event_set.size() == 1);
  93     REQUIRE(event_set.contains(&e1));
  94     REQUIRE_FALSE(event_set.empty());
  95
  96     event_set.insert(&e1);
  97     REQUIRE(event_set.size() == 1);
  98     REQUIRE(event_set.contains(&e1));
  99     REQUIRE_FALSE(event_set.empty());
 100
 101     SECTION("Check contains inserted elements")
 102     {
 103       REQUIRE(event_set.contains(&e1));
 104       REQUIRE_FALSE(event_set.contains(&e2));
 105       REQUIRE_FALSE(event_set.contains(&e3));
 106     }
 107   }
 108 }
 109
 110 TEST_CASE("simgrid::mc::udpor::EventSet: Deletions")
 111 {
 112   UnfoldingEvent e1;
 113   UnfoldingEvent e2;
 114   UnfoldingEvent e3;
 115   UnfoldingEvent e4;
 116   EventSet event_set({&e1, &e2, &e3});
 117
 118   SECTION("Remove an element already present")
 119   {
 120     REQUIRE(event_set.contains(&e1));
 121
 122     // Recall that event_set = {e2, e3}
 123     event_set.remove(&e1);
 124
 125     // Check that
 126     // 1. the size decreases by exactly 1
 127     // 2. the set remains unempty
 128     // 3. the other elements are still contained in the set
 129     REQUIRE(event_set.size() == 2);
 130     REQUIRE_FALSE(event_set.contains(&e1));
 131     REQUIRE(event_set.contains(&e2));
 132     REQUIRE(event_set.contains(&e3));
 133     REQUIRE_FALSE(event_set.empty());
 134
 135     SECTION("Remove a single element more than once")
 136     {
 137       // Recall that event_set = {e2, e3}
 138       event_set.remove(&e1);
 139       REQUIRE(event_set.size() == 2);
 140       REQUIRE_FALSE(event_set.contains(&e1));
 141       REQUIRE(event_set.contains(&e2));
 142       REQUIRE(event_set.contains(&e3));
 143       REQUIRE_FALSE(event_set.empty());
 144     }
 145
 146     SECTION("Remove more than one element")
 147     {
 148       // Recall that event_set = {e3}
 149       event_set.remove(&e2);
 150
 151       REQUIRE(event_set.size() == 1);
 152       REQUIRE_FALSE(event_set.contains(&e1));
 153       REQUIRE_FALSE(event_set.contains(&e2));
 154       REQUIRE(event_set.contains(&e3));
 155       REQUIRE_FALSE(event_set.empty());
 156
 157       // Recall that event_set = {}
 158       event_set.remove(&e3);
 159
 160       REQUIRE(event_set.size() == 0);
 161       REQUIRE_FALSE(event_set.contains(&e1));
 162       REQUIRE_FALSE(event_set.contains(&e2));
 163       REQUIRE_FALSE(event_set.contains(&e3));
 164       REQUIRE(event_set.empty());
 165     }
 166   }
 167
 168   SECTION("Remove an element absent from the set")
 169   {
 170     REQUIRE_FALSE(event_set.contains(&e4));
 171
 172     // Recall that event_set = {e1, e2, e3}
 173     event_set.remove(&e4);
 174     REQUIRE(event_set.size() == 3);
 175     REQUIRE(event_set.contains(&e1));
 176     REQUIRE(event_set.contains(&e2));
 177     REQUIRE(event_set.contains(&e3));
 178
 179     // Ensure e4 isn't somehow added
 180     REQUIRE_FALSE(event_set.contains(&e4));
 181     REQUIRE_FALSE(event_set.empty());
 182   }
 183 }
 184
 185 TEST_CASE("simgrid::mc::udpor::EventSet: Set Equality")
 186 {
 187   UnfoldingEvent e1;
 188   UnfoldingEvent e2;
 189   UnfoldingEvent e3;
 190   UnfoldingEvent e4;
 191   EventSet A{&e1, &e2, &e3}, B{&e1, &e2, &e3}, C{&e1, &e2, &e3};
 192
 193   SECTION("Equality implies containment")
 194   {
 195     REQUIRE(A == B);
 196
 197     for (const auto& e : A) {
 198       REQUIRE(B.contains(e));
 199     }
 200
 201     for (const auto& e : B) {
 202       REQUIRE(A.contains(e));
 203     }
 204   }
 205
 206   SECTION("Containment implies equality")
 207   {
 208     for (const auto& e : A) {
 209       REQUIRE(B.contains(e));
 210     }
 211
 212     for (const auto& e : C) {
 213       REQUIRE(C.contains(e));
 214     }
 215
 216     REQUIRE(A == C);
 217   }
 218
 219   SECTION("Equality is an equivalence relation")
 220   {
 221     // Reflexive
 222     REQUIRE(A == A);
 223     REQUIRE(B == B);
 224     REQUIRE(C == C);
 225
 226     // Symmetric
 227     REQUIRE(A == B);
 228     REQUIRE(B == A);
 229     REQUIRE(A == C);
 230     REQUIRE(C == A);
 231     REQUIRE(B == C);
 232     REQUIRE(C == B);
 233
 234     // Transitive
 235     REQUIRE(A == B);
 236     REQUIRE(B == C);
 237     REQUIRE(A == C);
 238   }
 239
 240   SECTION("Equality after copy (assignment + constructor)")
 241   {
 242     EventSet A_copy = A;
 243     EventSet A_copy2(A);
 244
 245     REQUIRE(A == A_copy);
 246     REQUIRE(A == A_copy2);
 247   }
 248
 249   SECTION("Equality after move constructor")
 250   {
 251     EventSet A_copy = A;
 252     EventSet A_move(std::move(A));
 253     REQUIRE(A_move == A_copy);
 254   }
 255
 256   SECTION("Equality after move-assignment")
 257   {
 258     EventSet A_copy = A;
 259     EventSet A_move = std::move(A);
 260     REQUIRE(A_move == A_copy);
 261   }
 262 }
 263
 264 TEST_CASE("simgrid::mc::udpor::EventSet: Set Union Tests")
 265 {
 266   UnfoldingEvent e1, e2, e3, e4;
 267
 268   // C = A + B
 269   EventSet A{&e1, &e2, &e3}, B{&e2, &e3, &e4}, C{&e1, &e2, &e3, &e4}, D{&e1, &e3};
 270
 271   SECTION("Unions with no effect")
 272   {
 273     EventSet A_copy = A;
 274
 275     SECTION("Self union")
 276     {
 277       // A = A union A
 278       EventSet A_union = A.make_union(A);
 279       REQUIRE(A == A_copy);
 280
 281       A.form_union(A);
 282       REQUIRE(A == A_copy);
 283     }
 284
 285     SECTION("Union with empty set")
 286     {
 287       // A = A union empty set
 288       EventSet A_union = A.make_union(EventSet());
 289       REQUIRE(A == A_union);
 290
 291       A.form_union(EventSet());
 292       REQUIRE(A == A_copy);
 293     }
 294
 295     SECTION("Union with an equivalent set")
 296     {
 297       // A = A union B if B == A
 298       EventSet A_equiv{&e1, &e2, &e3};
 299       REQUIRE(A == A_equiv);
 300
 301       EventSet A_union = A.make_union(A_equiv);
 302       REQUIRE(A_union == A_copy);
 303
 304       A.form_union(A_equiv);
 305       REQUIRE(A == A_copy);
 306     }
 307
 308     SECTION("Union with a subset")
 309     {
 310       // A = A union D if D is a subset of A
 311       EventSet A_union = A.make_union(D);
 312       REQUIRE(A == A_union);
 313
 314       A.form_union(D);
 315       REQUIRE(A == A_copy);
 316     }
 317   }
 318
 319   SECTION("Unions with partial overlaps")
 320   {
 321     EventSet A_union_B = A.make_union(B);
 322     REQUIRE(A_union_B == C);
 323
 324     A.form_union(B);
 325     REQUIRE(A == C);
 326
 327     EventSet B_union_D = B.make_union(D);
 328     REQUIRE(B_union_D == C);
 329
 330     B.form_union(D);
 331     REQUIRE(B == C);
 332   }
 333
 334   SECTION("Set union properties")
 335   {
 336     SECTION("Union operator is symmetric")
 337     {
 338       EventSet A_union_B = A.make_union(B);
 339       EventSet B_union_A = B.make_union(A);
 340       REQUIRE(A_union_B == B_union_A);
 341     }
 342
 343     SECTION("Union operator commutes")
 344     {
 345       // The last SECTION tested pair-wise
 346       // equivalence, so we only check
 347       // one of each pai
 348       EventSet AD = A.make_union(D);
 349       EventSet AC = A.make_union(C);
 350       EventSet CD = D.make_union(C);
 351
 352       EventSet ADC = AD.make_union(C);
 353       EventSet ACD = AC.make_union(D);
 354       EventSet CDA = CD.make_union(A);
 355
 356       REQUIRE(ADC == ACD);
 357       REQUIRE(ACD == CDA);
 358
 359       // Test `form_union()` in the same way
 360
 361       EventSet A_copy = A;
 362       EventSet C_copy = C;
 363       EventSet D_copy = D;
 364
 365       A.form_union(C_copy);
 366       A.form_union(D_copy);
 367
 368       D.form_union(A_copy);
 369       D.form_union(C_copy);
 370
 371       C.form_union(A);
 372       C.form_union(D);
 373
 374       REQUIRE(A == D);
 375       REQUIRE(C == D);
 376       REQUIRE(A == C);
 377     }
 378   }
 379 }
 380
 381 TEST_CASE("simgrid::mc::udpor::EventSet: Set Difference Tests")
 382 {
 383   UnfoldingEvent e1, e2, e3, e4;
 384
 385   // C = A + B
 386   // A is a subset of C
 387   // B is a subset of C
 388   // D is a subset of A and C
 389   // E is a subset of B and C
 390   // F is a subset of A, C, and D
 391   EventSet A{&e1, &e2, &e3}, B{&e2, &e3, &e4}, C{&e1, &e2, &e3, &e4}, D{&e1, &e3}, E{&e4}, F{&e1};
 392
 393   SECTION("Difference with no effect")
 394   {
 395     SECTION("Difference with empty set")
 396     {
 397       EventSet A_copy = A.subtracting(EventSet());
 398       REQUIRE(A == A_copy);
 399
 400       A.subtract(EventSet());
 401       REQUIRE(A == A_copy);
 402     }
 403
 404     SECTION("Difference with empty intersection")
 405     {
 406       // A intersection E = empty set
 407       EventSet A_copy = A.subtracting(E);
 408       REQUIRE(A == A_copy);
 409
 410       A.subtract(E);
 411       REQUIRE(A == A_copy);
 412
 413       EventSet D_copy = D.subtracting(E);
 414       REQUIRE(D == D_copy);
 415
 416       D.subtract(E);
 417       REQUIRE(D == D_copy);
 418     }
 419   }
 420
 421   SECTION("Difference with some overlap")
 422   {
 423     // A - B = {&e1} = F
 424     EventSet A_minus_B = A.subtracting(B);
 425     REQUIRE(A_minus_B == F);
 426
 427     // B - D = {&e2, &e4}
 428     EventSet B_minus_D = B.subtracting(D);
 429     REQUIRE(B_minus_D == EventSet({&e2, &e4}));
 430   }
 431
 432   SECTION("Difference with complete overlap")
 433   {
 434     SECTION("Difference with same set gives empty set")
 435     {
 436       REQUIRE(A.subtracting(A) == EventSet());
 437       REQUIRE(B.subtracting(B) == EventSet());
 438       REQUIRE(C.subtracting(C) == EventSet());
 439       REQUIRE(D.subtracting(D) == EventSet());
 440       REQUIRE(E.subtracting(E) == EventSet());
 441       REQUIRE(F.subtracting(F) == EventSet());
 442     }
 443
 444     SECTION("Difference with superset gives empty set")
 445     {
 446       REQUIRE(A.subtracting(C) == EventSet());
 447       REQUIRE(B.subtracting(C) == EventSet());
 448       REQUIRE(D.subtracting(A) == EventSet());
 449       REQUIRE(D.subtracting(C) == EventSet());
 450       REQUIRE(E.subtracting(B) == EventSet());
 451       REQUIRE(E.subtracting(C) == EventSet());
 452       REQUIRE(F.subtracting(A) == EventSet());
 453       REQUIRE(F.subtracting(C) == EventSet());
 454       REQUIRE(F.subtracting(D) == EventSet());
 455     }
 456   }
 457 }
 458
 459 TEST_CASE("simgrid::mc::udpor::EventSet: Subset Tests")
 460 {
 461   UnfoldingEvent e1, e2, e3, e4;
 462
 463   // A is a subset of C only
 464   // B is a subset of C only
 465   // D is a subset of C and A
 466   // D is NOT a subset of B
 467   // B is NOT a subset of D
 468   // ...
 469   EventSet A{&e1, &e2, &e3}, B{&e2, &e3, &e4}, C{&e1, &e2, &e3, &e4}, D{&e1, &e3}, E{&e2, &e3}, F{&e1, &e2, &e3};
 470
 471   SECTION("Subset operator properties")
 472   {
 473     SECTION("Subset operator is not commutative")
 474     {
 475       REQUIRE(A.is_subset_of(C));
 476       REQUIRE_FALSE(C.is_subset_of(A));
 477
 478       SECTION("Commutativity implies equality and vice versa")
 479       {
 480         REQUIRE(A.is_subset_of(F));
 481         REQUIRE(F.is_subset_of(A));
 482         REQUIRE(A == F);
 483
 484         REQUIRE(C == C);
 485         REQUIRE(A.is_subset_of(F));
 486         REQUIRE(F.is_subset_of(A));
 487       }
 488     }
 489
 490     SECTION("Subset operator is transitive")
 491     {
 492       REQUIRE(D.is_subset_of(A));
 493       REQUIRE(A.is_subset_of(C));
 494       REQUIRE(D.is_subset_of(C));
 495       REQUIRE(E.is_subset_of(B));
 496       REQUIRE(B.is_subset_of(C));
 497       REQUIRE(E.is_subset_of(C));
 498     }
 499
 500     SECTION("Subset operator is reflexive")
 501     {
 502       REQUIRE(A.is_subset_of(A));
 503       REQUIRE(B.is_subset_of(B));
 504       REQUIRE(C.is_subset_of(C));
 505       REQUIRE(D.is_subset_of(D));
 506       REQUIRE(E.is_subset_of(E));
 507       REQUIRE(F.is_subset_of(F));
 508     }
 509   }
 510 }
 511
 512 TEST_CASE("simgrid::mc::udpor::EventSet: Testing Configurations")
 513 {
 514   // The following tests concern the given event structure:
 515   //                e1
 516   //              /    /
 517   //            e2      e5
 518   //           /  /      /
 519   //          e3  e4     e6
 520   // The tests enumerate all possible subsets of the events
 521   // in the structure and test whether those subsets are
 522   // maximal and/or valid configurations
 523   UnfoldingEvent e1;
 524   UnfoldingEvent e2{&e1};
 525   UnfoldingEvent e3{&e2};
 526   UnfoldingEvent e4{&e2};
 527   UnfoldingEvent e5{&e1};
 528   UnfoldingEvent e6{&e5};
 529
 530   SECTION("Valid Configurations")
 531   {
 532     SECTION("The empty set is valid")
 533     {
 534       REQUIRE(EventSet().is_valid_configuration());
 535     }
 536
 537     SECTION("The set with only the root event is valid")
 538     {
 539       REQUIRE(EventSet({&e1}).is_valid_configuration());
 540     }
 541
 542     SECTION("All sets of maximal events are valid configurations")
 543     {
 544       REQUIRE(EventSet({&e1}).is_valid_configuration());
 545       REQUIRE(EventSet({&e1, &e2}).is_valid_configuration());
 546       REQUIRE(EventSet({&e1, &e2, &e3}).is_valid_configuration());
 547       REQUIRE(EventSet({&e1, &e2, &e4}).is_valid_configuration());
 548       REQUIRE(EventSet({&e1, &e5}).is_valid_configuration());
 549       REQUIRE(EventSet({&e1, &e5, &e6}).is_valid_configuration());
 550       REQUIRE(EventSet({&e1, &e2, &e5}).is_valid_configuration());
 551       REQUIRE(EventSet({&e1, &e2, &e5, &e6}).is_valid_configuration());
 552       REQUIRE(EventSet({&e1, &e2, &e3, &e4}).is_valid_configuration());
 553       REQUIRE(EventSet({&e1, &e2, &e3, &e5}).is_valid_configuration());
 554       REQUIRE(EventSet({&e1, &e2, &e4, &e5}).is_valid_configuration());
 555       REQUIRE(EventSet({&e1, &e2, &e4, &e5, &e6}).is_valid_configuration());
 556       REQUIRE(EventSet({&e1, &e2, &e3, &e4, &e5}).is_valid_configuration());
 557       REQUIRE(EventSet({&e1, &e2, &e3, &e4, &e5, &e6}).is_valid_configuration());
 558     }
 559   }
 560
 561   SECTION("Configuration checks")
 562   {
 563     // 6 choose 0 = 1 test
 564     REQUIRE(EventSet().is_valid_configuration());
 565
 566     // 6 choose 1 = 6 tests
 567     REQUIRE(EventSet({&e1}).is_valid_configuration());
 568     REQUIRE_FALSE(EventSet({&e2}).is_valid_configuration());
 569     REQUIRE_FALSE(EventSet({&e3}).is_valid_configuration());
 570     REQUIRE_FALSE(EventSet({&e4}).is_valid_configuration());
 571     REQUIRE_FALSE(EventSet({&e5}).is_valid_configuration());
 572     REQUIRE_FALSE(EventSet({&e6}).is_valid_configuration());
 573
 574     // 6 choose 2 = 15 tests
 575     REQUIRE(EventSet({&e1, &e2}).is_valid_configuration());
 576     REQUIRE_FALSE(EventSet({&e1, &e3}).is_valid_configuration());
 577     REQUIRE_FALSE(EventSet({&e1, &e4}).is_valid_configuration());
 578     REQUIRE(EventSet({&e1, &e5}).is_valid_configuration());
 579     REQUIRE_FALSE(EventSet({&e1, &e6}).is_valid_configuration());
 580     REQUIRE_FALSE(EventSet({&e2, &e3}).is_valid_configuration());
 581     REQUIRE_FALSE(EventSet({&e2, &e4}).is_valid_configuration());
 582     REQUIRE_FALSE(EventSet({&e2, &e5}).is_valid_configuration());
 583     REQUIRE_FALSE(EventSet({&e2, &e6}).is_valid_configuration());
 584     REQUIRE_FALSE(EventSet({&e3, &e4}).is_valid_configuration());
 585     REQUIRE_FALSE(EventSet({&e3, &e5}).is_valid_configuration());
 586     REQUIRE_FALSE(EventSet({&e3, &e6}).is_valid_configuration());
 587     REQUIRE_FALSE(EventSet({&e4, &e5}).is_valid_configuration());
 588     REQUIRE_FALSE(EventSet({&e4, &e6}).is_valid_configuration());
 589     REQUIRE_FALSE(EventSet({&e5, &e6}).is_valid_configuration());
 590
 591     // 6 choose 3 = 20 tests
 592     REQUIRE(EventSet({&e1, &e2, &e3}).is_valid_configuration());
 593     REQUIRE(EventSet({&e1, &e2, &e4}).is_valid_configuration());
 594     REQUIRE(EventSet({&e1, &e2, &e5}).is_valid_configuration());
 595     REQUIRE_FALSE(EventSet({&e1, &e2, &e6}).is_valid_configuration());
 596     REQUIRE_FALSE(EventSet({&e1, &e3, &e4}).is_valid_configuration());
 597     REQUIRE_FALSE(EventSet({&e1, &e3, &e5}).is_valid_configuration());
 598     REQUIRE_FALSE(EventSet({&e1, &e3, &e6}).is_valid_configuration());
 599     REQUIRE_FALSE(EventSet({&e1, &e4, &e5}).is_valid_configuration());
 600     REQUIRE_FALSE(EventSet({&e1, &e4, &e6}).is_valid_configuration());
 601     REQUIRE(EventSet({&e1, &e5, &e6}).is_valid_configuration());
 602     REQUIRE_FALSE(EventSet({&e2, &e3, &e4}).is_valid_configuration());
 603     REQUIRE_FALSE(EventSet({&e2, &e3, &e5}).is_valid_configuration());
 604     REQUIRE_FALSE(EventSet({&e2, &e3, &e6}).is_valid_configuration());
 605     REQUIRE_FALSE(EventSet({&e2, &e4, &e5}).is_valid_configuration());
 606     REQUIRE_FALSE(EventSet({&e2, &e4, &e6}).is_valid_configuration());
 607     REQUIRE_FALSE(EventSet({&e2, &e5, &e6}).is_valid_configuration());
 608     REQUIRE_FALSE(EventSet({&e3, &e4, &e5}).is_valid_configuration());
 609     REQUIRE_FALSE(EventSet({&e3, &e4, &e6}).is_valid_configuration());
 610     REQUIRE_FALSE(EventSet({&e3, &e5, &e6}).is_valid_configuration());
 611     REQUIRE_FALSE(EventSet({&e4, &e5, &e6}).is_valid_configuration());
 612
 613     // 6 choose 4 = 15 tests
 614     REQUIRE(EventSet({&e1, &e2, &e3, &e4}).is_valid_configuration());
 615     REQUIRE(EventSet({&e1, &e2, &e3, &e5}).is_valid_configuration());
 616     REQUIRE_FALSE(EventSet({&e1, &e2, &e3, &e6}).is_valid_configuration());
 617     REQUIRE(EventSet({&e1, &e2, &e4, &e5}).is_valid_configuration());
 618     REQUIRE_FALSE(EventSet({&e1, &e2, &e4, &e6}).is_valid_configuration());
 619     REQUIRE(EventSet({&e1, &e2, &e5, &e6}).is_valid_configuration());
 620     REQUIRE_FALSE(EventSet({&e1, &e3, &e4, &e5}).is_valid_configuration());
 621     REQUIRE_FALSE(EventSet({&e1, &e3, &e4, &e6}).is_valid_configuration());
 622     REQUIRE_FALSE(EventSet({&e1, &e3, &e5, &e6}).is_valid_configuration());
 623     REQUIRE_FALSE(EventSet({&e1, &e4, &e5, &e6}).is_valid_configuration());
 624     REQUIRE_FALSE(EventSet({&e2, &e3, &e4, &e5}).is_valid_configuration());
 625     REQUIRE_FALSE(EventSet({&e2, &e3, &e4, &e6}).is_valid_configuration());
 626     REQUIRE_FALSE(EventSet({&e2, &e3, &e5, &e6}).is_valid_configuration());
 627     REQUIRE_FALSE(EventSet({&e2, &e4, &e5, &e6}).is_valid_configuration());
 628     REQUIRE_FALSE(EventSet({&e3, &e4, &e5, &e6}).is_valid_configuration());
 629
 630     // 6 choose 5 = 6 tests
 631     REQUIRE(EventSet({&e1, &e2, &e3, &e4, &e5}).is_valid_configuration());
 632     REQUIRE_FALSE(EventSet({&e1, &e2, &e3, &e4, &e6}).is_valid_configuration());
 633     REQUIRE(EventSet({&e1, &e2, &e3, &e5, &e6}).is_valid_configuration());
 634     REQUIRE(EventSet({&e1, &e2, &e4, &e5, &e6}).is_valid_configuration());
 635     REQUIRE_FALSE(EventSet({&e1, &e3, &e4, &e5, &e6}).is_valid_configuration());
 636     REQUIRE_FALSE(EventSet({&e2, &e3, &e4, &e5, &e6}).is_valid_configuration());
 637
 638     // 6 choose 6 = 1 test
 639     REQUIRE(EventSet({&e1, &e2, &e3, &e4, &e5, &e6}).is_valid_configuration());
 640   }
 641
 642   SECTION("Maximal event sets")
 643   {
 644     // 6 choose 0 = 1 test
 645     REQUIRE(EventSet().is_maximal_event_set());
 646
 647     // 6 choose 1 = 6 tests
 648     REQUIRE(EventSet({&e1}).is_maximal_event_set());
 649     REQUIRE(EventSet({&e2}).is_maximal_event_set());
 650     REQUIRE(EventSet({&e3}).is_maximal_event_set());
 651     REQUIRE(EventSet({&e4}).is_maximal_event_set());
 652     REQUIRE(EventSet({&e5}).is_maximal_event_set());
 653     REQUIRE(EventSet({&e6}).is_maximal_event_set());
 654
 655     // 6 choose 2 = 15 tests
 656     REQUIRE_FALSE(EventSet({&e1, &e2}).is_maximal_event_set());
 657     REQUIRE_FALSE(EventSet({&e1, &e3}).is_maximal_event_set());
 658     REQUIRE_FALSE(EventSet({&e1, &e4}).is_maximal_event_set());
 659     REQUIRE_FALSE(EventSet({&e1, &e5}).is_maximal_event_set());
 660     REQUIRE_FALSE(EventSet({&e1, &e6}).is_maximal_event_set());
 661     REQUIRE_FALSE(EventSet({&e2, &e3}).is_maximal_event_set());
 662     REQUIRE_FALSE(EventSet({&e2, &e4}).is_maximal_event_set());
 663     REQUIRE(EventSet({&e2, &e5}).is_maximal_event_set());
 664     REQUIRE(EventSet({&e2, &e6}).is_maximal_event_set());
 665     REQUIRE(EventSet({&e3, &e4}).is_maximal_event_set());
 666     REQUIRE(EventSet({&e3, &e5}).is_maximal_event_set());
 667     REQUIRE(EventSet({&e3, &e6}).is_maximal_event_set());
 668     REQUIRE(EventSet({&e4, &e5}).is_maximal_event_set());
 669     REQUIRE(EventSet({&e4, &e6}).is_maximal_event_set());
 670     REQUIRE_FALSE(EventSet({&e5, &e6}).is_maximal_event_set());
 671
 672     // 6 choose 3 = 20 tests
 673     REQUIRE_FALSE(EventSet({&e1, &e2, &e3}).is_maximal_event_set());
 674     REQUIRE_FALSE(EventSet({&e1, &e2, &e4}).is_maximal_event_set());
 675     REQUIRE_FALSE(EventSet({&e1, &e2, &e5}).is_maximal_event_set());
 676     REQUIRE_FALSE(EventSet({&e1, &e2, &e6}).is_maximal_event_set());
 677     REQUIRE_FALSE(EventSet({&e1, &e3, &e4}).is_maximal_event_set());
 678     REQUIRE_FALSE(EventSet({&e1, &e3, &e5}).is_maximal_event_set());
 679     REQUIRE_FALSE(EventSet({&e1, &e3, &e6}).is_maximal_event_set());
 680     REQUIRE_FALSE(EventSet({&e1, &e4, &e5}).is_maximal_event_set());
 681     REQUIRE_FALSE(EventSet({&e1, &e4, &e6}).is_maximal_event_set());
 682     REQUIRE_FALSE(EventSet({&e1, &e5, &e6}).is_maximal_event_set());
 683     REQUIRE_FALSE(EventSet({&e2, &e3, &e4}).is_maximal_event_set());
 684     REQUIRE_FALSE(EventSet({&e2, &e3, &e5}).is_maximal_event_set());
 685     REQUIRE_FALSE(EventSet({&e2, &e3, &e6}).is_maximal_event_set());
 686     REQUIRE_FALSE(EventSet({&e2, &e4, &e5}).is_maximal_event_set());
 687     REQUIRE_FALSE(EventSet({&e2, &e4, &e6}).is_maximal_event_set());
 688     REQUIRE_FALSE(EventSet({&e2, &e5, &e6}).is_maximal_event_set());
 689     REQUIRE(EventSet({&e3, &e4, &e5}).is_maximal_event_set());
 690     REQUIRE(EventSet({&e3, &e4, &e6}).is_maximal_event_set());
 691     REQUIRE_FALSE(EventSet({&e3, &e5, &e6}).is_maximal_event_set());
 692     REQUIRE_FALSE(EventSet({&e4, &e5, &e6}).is_maximal_event_set());
 693
 694     // 6 choose 4 = 15 tests
 695     REQUIRE_FALSE(EventSet({&e1, &e2, &e3, &e4}).is_maximal_event_set());
 696     REQUIRE_FALSE(EventSet({&e1, &e2, &e3, &e5}).is_maximal_event_set());
 697     REQUIRE_FALSE(EventSet({&e1, &e2, &e3, &e6}).is_maximal_event_set());
 698     REQUIRE_FALSE(EventSet({&e1, &e2, &e4, &e5}).is_maximal_event_set());
 699     REQUIRE_FALSE(EventSet({&e1, &e2, &e4, &e6}).is_maximal_event_set());
 700     REQUIRE_FALSE(EventSet({&e1, &e2, &e5, &e6}).is_maximal_event_set());
 701     REQUIRE_FALSE(EventSet({&e1, &e3, &e4, &e5}).is_maximal_event_set());
 702     REQUIRE_FALSE(EventSet({&e1, &e3, &e4, &e6}).is_maximal_event_set());
 703     REQUIRE_FALSE(EventSet({&e1, &e3, &e5, &e6}).is_maximal_event_set());
 704     REQUIRE_FALSE(EventSet({&e1, &e4, &e5, &e6}).is_maximal_event_set());
 705     REQUIRE_FALSE(EventSet({&e2, &e3, &e4, &e5}).is_maximal_event_set());
 706     REQUIRE_FALSE(EventSet({&e2, &e3, &e4, &e6}).is_maximal_event_set());
 707     REQUIRE_FALSE(EventSet({&e2, &e3, &e5, &e6}).is_maximal_event_set());
 708     REQUIRE_FALSE(EventSet({&e2, &e4, &e5, &e6}).is_maximal_event_set());
 709     REQUIRE_FALSE(EventSet({&e3, &e4, &e5, &e6}).is_maximal_event_set());
 710
 711     // 6 choose 5 = 6 tests
 712     REQUIRE_FALSE(EventSet({&e1, &e2, &e3, &e4, &e5}).is_maximal_event_set());
 713     REQUIRE_FALSE(EventSet({&e1, &e2, &e3, &e4, &e6}).is_maximal_event_set());
 714     REQUIRE_FALSE(EventSet({&e1, &e2, &e3, &e5, &e6}).is_maximal_event_set());
 715     REQUIRE_FALSE(EventSet({&e1, &e2, &e4, &e5, &e6}).is_maximal_event_set());
 716     REQUIRE_FALSE(EventSet({&e1, &e3, &e4, &e5, &e6}).is_maximal_event_set());
 717     REQUIRE_FALSE(EventSet({&e2, &e3, &e4, &e5, &e6}).is_maximal_event_set());
 718
 719     // 6 choose 6 = 1 test
 720     REQUIRE_FALSE(EventSet({&e1, &e2, &e3, &e4, &e5, &e6}).is_maximal_event_set());
 721   }
 722 }