// e7 + e8 must be included, so that means we can combine from the left branch
REQUIRE(maximal_subset_counts[3] == 3);
}
+
+ SECTION("Check counts of maximal event sets discovered with a filter")
+ {
+ std::unordered_map<int, int> maximal_subset_counts;
+
+ Configuration C{&e1, &e2, &e3, &e4, &e5, &e6, &e7, &e8};
+
+ SECTION("Filter with events part of initial maximal set")
+ {
+ EventSet interesting_bunch{&e2, &e4, &e7, &e8};
+
+ maximal_subsets_iterator first(C, [&](const UnfoldingEvent* e) { return interesting_bunch.contains(e); });
+ maximal_subsets_iterator last;
+
+ for (; first != last; ++first) {
+ const auto& event_set = *first;
+ // Only events in `interesting_bunch` can appear: thus no set
+ // should include anything else other than `interesting_bunch`
+ REQUIRE(event_set.is_subset_of(interesting_bunch));
+ REQUIRE(event_set.is_maximal_event_set());
+ maximal_subset_counts[event_set.size()]++;
+ }
+
+ // The empty set should (still) appear only once
+ REQUIRE(maximal_subset_counts[0] == 1);
+
+ // 4 is the number of nodes in the `interesting_bunch`
+ REQUIRE(maximal_subset_counts[1] == 4);
+
+ // 5 = 2 * 2 (each of the left branch can combine with one in the right branch) + 1 (e7 + e8)
+ REQUIRE(maximal_subset_counts[2] == 5);
+
+ // e7 + e8 must be included, so that means we can combine from the left branch (only e2 and e4)
+ REQUIRE(maximal_subset_counts[3] == 2);
+
+ // There are no subsets of size 4 (or higher, but that
+ // is tested by asserting each maximal set traversed is a subset)
+ REQUIRE(maximal_subset_counts[4] == 0);
+ }
+
+ SECTION("Filter with interesting subset not initially part of the maximal set")
+ {
+ EventSet interesting_bunch{&e3, &e5, &e6};
+
+ maximal_subsets_iterator first(C, [&](const UnfoldingEvent* e) { return interesting_bunch.contains(e); });
+ maximal_subsets_iterator last;
+
+ for (; first != last; ++first) {
+ const auto& event_set = *first;
+ // Only events in `interesting_bunch` can appear: thus no set
+ // should include anything else other than `interesting_bunch`
+ REQUIRE(event_set.is_subset_of(interesting_bunch));
+ REQUIRE(event_set.is_maximal_event_set());
+ maximal_subset_counts[event_set.size()]++;
+ }
+
+ // The empty set should (still) appear only once
+ REQUIRE(maximal_subset_counts[0] == 1);
+
+ // 3 is the number of nodes in the `interesting_bunch`
+ REQUIRE(maximal_subset_counts[1] == 3);
+
+ // 2 = e3, e5 and e3, e6
+ REQUIRE(maximal_subset_counts[2] == 2);
+
+ // There are no subsets of size 3 (or higher, but that
+ // is tested by asserting each maximal set traversed is a subset)
+ REQUIRE(maximal_subset_counts[3] == 0);
+ }
+ }
}
TEST_CASE("simgrid::mc::udpor::maximal_subsets_iterator: Stress Test for Maximal Subsets Iteration")
return;
}
- // The initial step simply allows us to move past the initial empty set correctly
- if (!has_started_searching) {
- has_started_searching = true;
-
- // Otherwise, the very first step is to push the very first
- // element of the topological ordering
- add_element_to_current_maximal_set(*topological_ordering.begin());
- backtrack_points.push(topological_ordering.begin());
- } else {
-
- const auto next_event_ref = continue_traversal_of_maximal_events_tree();
- if (next_event_ref == topological_ordering.end()) {
- current_maximal_set = std::nullopt;
- return;
+ const auto next_event_ref = [&]() {
+ if (!has_started_searching) {
+ has_started_searching = true;
+ return bookkeeper.find_next_candidate_event(topological_ordering.begin(), topological_ordering.end());
+ } else {
+ return continue_traversal_of_maximal_events_tree();
}
+ }();
- // We found some other event `e'` which is not in causally related with anything
- // that currently exists in `current_maximal_set`. Add it in
- add_element_to_current_maximal_set(*next_event_ref);
- backtrack_points.push(next_event_ref);
+ if (next_event_ref == topological_ordering.end()) {
+ current_maximal_set = std::nullopt;
+ return;
}
+
+ // We found some other event `e'` which is not in causally related with anything
+ // that currently exists in `current_maximal_set`, so add it in
+ add_element_to_current_maximal_set(*next_event_ref);
+ backtrack_points.push(next_event_ref);
}
maximal_subsets_iterator::topological_order_position
const auto next_event_ref = bookkeeper.find_next_candidate_event(latest_event_ref, topological_ordering.end());
// If we can expand from what we currently have, we can stop
- if (next_event_ref != topological_ordering.end() and should_consider_event(*next_event_ref)) {
+ if (next_event_ref != topological_ordering.end()) {
return next_event_ref;
}
}
// Otherwise, we backtrack: we repeatedly pop off events that we know we
// are finished with
while (not backtrack_points.empty()) {
- // Otherwise, if we can't find another event to add after `e` that
- // we need to consider, we retry after first removing the latest event.
- // This effectively tests "check now with all combinations that3
- // exclude the latest event".
- //
// Note: it is important to remove the element FIRST before performing
- // the second search, as removal may enable dependencies of `e` to be selected
+ // the search, as removal may enable dependencies of `e` to be selected
const auto latest_event_ref = backtrack_points.top();
remove_element_from_current_maximal_set(*latest_event_ref);
backtrack_points.pop();
// to consider those events that could be added AFTER `e` and
// not `e` itself again
const auto next_event_ref = bookkeeper.find_next_candidate_event(latest_event_ref + 1, topological_ordering.end());
-
- // If we finally found some event AFTER removal, we can stop
- if (next_event_ref != topological_ordering.end() and should_consider_event(*next_event_ref)) {
+ if (next_event_ref != topological_ordering.end()) {
return next_event_ref;
}
}
return topological_ordering.end();
}
-bool maximal_subsets_iterator::should_consider_event(const UnfoldingEvent* e) const
+bool maximal_subsets_iterator::bookkeeper::is_candidate_event(const UnfoldingEvent* e) const
{
- if (filter_function.has_value()) {
- return filter_function.value()(e);
+ // The event must pass the filter, if it exists
+ if (filter_function.has_value() && not filter_function.value()(e)) {
+ return false;
}
- return true; // If nobody specified a filter, we default to considering the event
-}
-bool maximal_subsets_iterator::bookkeeper::is_candidate_event(const UnfoldingEvent* e) const
-{
if (const auto e_count = event_counts.find(e); e_count != event_counts.end()) {
return e_count->second == 0;
}
maximal_subsets_iterator(const Configuration& config, std::optional<node_filter_function> filter)
: config({config})
, topological_ordering(config.get_topologically_sorted_events_of_reverse_graph())
- , filter_function(filter)
, current_maximal_set({EventSet()})
+ , bookkeeper(filter)
{
}
private:
const std::optional<std::reference_wrapper<const Configuration>> config;
const std::vector<const UnfoldingEvent*> topological_ordering;
- const std::optional<node_filter_function> filter_function = std::nullopt;
// The boolean is a bit of an annoyance, but it works. Effectively,
// there's no way to distinguish between "we're starting the search
// after the empty set" and "we've finished the search" since the resulting
// maximal set and backtracking point stack will both be empty in both cases
- bool has_started_searching = false;
- std::optional<EventSet> current_maximal_set = std::nullopt;
- std::stack<topological_order_position> backtrack_points;
+ bool has_started_searching = false;
+ std::optional<EventSet> current_maximal_set = std::nullopt;
+ std::stack<topological_order_position> backtrack_points = std::stack<topological_order_position>();
/**
* @brief A small class which provides functionality for managing
struct bookkeeper {
public:
using topological_order_position = maximal_subsets_iterator::topological_order_position;
+ explicit bookkeeper(std::optional<node_filter_function> filter = std::nullopt) : filter_function(filter) {}
+
void mark_included_in_maximal_set(const UnfoldingEvent*);
void mark_removed_from_maximal_set(const UnfoldingEvent*);
topological_order_position find_next_candidate_event(topological_order_position first,
private:
std::unordered_map<const UnfoldingEvent*, unsigned> event_counts;
+ const std::optional<node_filter_function> filter_function;
/// @brief Whether or not the given event, according to the
/// bookkeeping that has been done thus far, can be added to the
*/
topological_order_position continue_traversal_of_maximal_events_tree();
- /// @brief Whether or not we should even consider cases where the given
- /// event `e` is included in the maximal configurations
- bool should_consider_event(const UnfoldingEvent*) const;
-
// boost::iterator_facade<...> interface to implement
void increment();
bool equal(const maximal_subsets_iterator& other) const { return current_maximal_set == other.current_maximal_set; }
