src/mc/explo/udpor/Comb.hpp

   1 /* Copyright (c) 2007-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 #ifndef SIMGRID_MC_UDPOR_COMB_HPP
   7 #define SIMGRID_MC_UDPOR_COMB_HPP
   8
   9 #include "src/mc/explo/udpor/UnfoldingEvent.hpp"
  10 #include "src/mc/explo/udpor/udpor_forward.hpp"
  11 #include "src/xbt/utils/iter/variable_for_loop.hpp"
  12
  13 #include <boost/iterator/function_input_iterator.hpp>
  14 #include <boost/iterator/indirect_iterator.hpp>
  15 #include <functional>
  16 #include <vector>
  17
  18 namespace simgrid::mc::udpor {
  19
  20 /**
  21  * @brief  An individual element of a `Comb`, i.e. a
  22  * sequence of `const UnfoldingEvent*`s
  23  */
  24 using Spike = std::vector<const UnfoldingEvent*>;
  25
  26 /**
  27  * @brief A two-dimensional data structure that is used
  28  * to compute partial alternatives in UDPOR
  29  *
  30  * The comb data structure is described in the paper
  31  * "Quasi-Optimal DPOR" by Nguyen et al. Formally,
  32  * if `A` is a set:
  33  *
  34  * """
  35  * An **A-Comb C of size `n` (`n` a natural number)**
  36  * is an *ordered* collection of spikes <s_1, s_2, ..., s_n>,
  37  * where each spike is a sequence of elements over A.
  38  *
  39  * Furthermore, a **combination over C** is any tuple
  40  * <a_1, a_2, ..., a_n> where a_i is a member of s_i
  41  * """
  42  *
  43  * The name probably comes from what the structure looks
  44  * like if you draw it out. For example, if `A = {1, 2, 3, ..., 10}`,
  45  * then a possible `A-comb` of size 8 might look like
  46  *
  47  * 1 2 3 4 5 6
  48  * 2 4 5 9 8
  49  * 10 9 2 1 1
  50  * 8 9 10 5
  51  * 1
  52  * 3 4 5
  53  * 1 4 4 5 1 6
  54  * 8 8 9
  55  *
  56  * which, if you squint a bit, looks like a comb (albeit with some
  57  * broken bristles [or spikes]). A combination is any selection of
  58  * one element within each spike; e.g. (where _x_ denotes element `x`
  59  * is selected)
  60  *
  61  * 1 2 _3_ 4 5 6
  62  * 2 _4_ 5 9 8
  63  * 10 9 2 _1_ 1
  64  * 8 _9_ 10 5
  65  * _1_
  66  * 3 4 _5_
  67  * 1 _4_ 4 5 1 6
  68  * _8_ 8 9
  69  *
  70  * A `Comb` as described by this C++ class is a `U-comb`, where
  71  * `U` is the set of events that UDPOR has explored. That is,
  72  * the comb is over a set of events
  73  */
  74 class Comb : public std::vector<Spike> {
  75 public:
  76   explicit Comb(unsigned k) : std::vector<Spike>(k) {}
  77   Comb(const Comb& other)            = default;
  78   Comb(Comb&& other)                 = default;
  79   Comb& operator=(const Comb& other) = default;
  80   Comb& operator=(Comb&& other)      = default;
  81
  82   auto combinations_begin() const
  83   {
  84     std::vector<std::reference_wrapper<const Spike>> references;
  85     std::transform(begin(), end(), std::back_inserter(references), [](const Spike& spike) { return std::cref(spike); });
  86     return simgrid::xbt::variable_for_loop<const Spike>(std::move(references));
  87   }
  88   auto combinations_end() const { return simgrid::xbt::variable_for_loop<const Spike>(); }
  89 };
  90
  91 } // namespace simgrid::mc::udpor
  92 #endif