1 /* Copyright (c) 2007-2023. The SimGrid Team. All rights reserved. */
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. */
6 #ifndef SIMGRID_MC_UDPOR_COMB_HPP
7 #define SIMGRID_MC_UDPOR_COMB_HPP
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"
13 #include <boost/iterator/function_input_iterator.hpp>
14 #include <boost/iterator/indirect_iterator.hpp>
18 namespace simgrid::mc::udpor {
21 * @brief An individual element of a `Comb`, i.e. a
22 * sequence of `const UnfoldingEvent*`s
24 using Spike = std::vector<const UnfoldingEvent*>;
27 * @brief A two-dimensional data structure that is used
28 * to compute partial alternatives in UDPOR
30 * The comb data structure is described in the paper
31 * "Quasi-Optimal DPOR" by Nguyen et al. Formally,
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.
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
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
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`
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
74 class Comb : public std::vector<Spike> {
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;
82 auto combinations_begin() const
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));
88 auto combinations_end() const { return simgrid::xbt::variable_for_loop<const Spike>(); }
91 } // namespace simgrid::mc::udpor