From: Maxwell Pirtle Date: Tue, 7 Mar 2023 13:36:03 +0000 (+0100) Subject: Add ability to restrict maximum subset size X-Git-Tag: v3.34~350^2~11 X-Git-Url: http://bilbo.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/commitdiff_plain/fcd4590468b5d531f9e95cc9972d0c8eb775661b Add ability to restrict maximum subset size This commit adds the ability to restrict the size of the maximal subsets that are produced by the maximal_subsets_iterator. This filtering significantly reduces the number of subsets that need to be searched in more complicated graphs. The advantage of adding the filtering directly to the maximal_subsets_iterator over using a higher-order iterator such as boost::filter_iterator is that branches can be pruned immediately. Since the maximal_subsets_iterator performs its search in depth-first order, something like boost::filter_iterator, while technically equivalent, would have to actually perform the iteration over entire branches that are otherwise useless due to their size. Searching maximal subsets of a restricted size is useful when determining conflicts between sets of events: we want to look at pairs of maximal events --- diff --git a/src/mc/explo/udpor/maximal_subsets_iterator.cpp b/src/mc/explo/udpor/maximal_subsets_iterator.cpp index a33d418f69..d6ed9888e9 100644 --- a/src/mc/explo/udpor/maximal_subsets_iterator.cpp +++ b/src/mc/explo/udpor/maximal_subsets_iterator.cpp @@ -6,8 +6,9 @@ namespace simgrid::mc::udpor { -maximal_subsets_iterator::maximal_subsets_iterator(const EventSet& events, std::optional filter) - : current_maximal_set({EventSet()}) +maximal_subsets_iterator::maximal_subsets_iterator(const EventSet& events, std::optional filter, + std::optional maximum_subset_size) + : maximum_subset_size(maximum_subset_size), current_maximal_set({EventSet()}) { const auto candidate_ordering = events.get_topological_ordering_of_reverse_graph(); if (filter.has_value()) { @@ -21,12 +22,13 @@ maximal_subsets_iterator::maximal_subsets_iterator(const EventSet& events, std:: void maximal_subsets_iterator::increment() { + // Termination condition if (current_maximal_set == std::nullopt) { return; } + // Stop immediately if there's nothing to search if (topological_ordering.empty()) { - // Stop immediately if there's nothing to search current_maximal_set = std::nullopt; return; } @@ -40,6 +42,7 @@ void maximal_subsets_iterator::increment() } }(); + // Out of events: we've finished if (next_event_ref == topological_ordering.end()) { current_maximal_set = std::nullopt; return; @@ -59,9 +62,13 @@ maximal_subsets_iterator::continue_traversal_of_maximal_events_tree() return topological_ordering.end(); } + xbt_assert(current_maximal_set.has_value(), "Traversal continued even after the termination condition " + "was met. Please verify that the termination condition " + "of the iterator has not been modified"); + // 1. First, check if we can keep expanding from the // maximal set that we currently have - { + if (can_grow_maximal_set()) { // This is an iterator which points to the latest event `e` that // was added to what is currently the maximal set const auto latest_event_ref = backtrack_points.top(); @@ -113,6 +120,11 @@ bool maximal_subsets_iterator::bookkeeper::is_candidate_event(const UnfoldingEve void maximal_subsets_iterator::add_element_to_current_maximal_set(const UnfoldingEvent* e) { + xbt_assert(can_grow_maximal_set(), "Attempting to add an event to the maximal set " + "when doing so would increase the size past the " + "prescribed limit. This indicates that detecting when " + "to stop growing the maximal set when continuing the " + "search is broken"); xbt_assert(current_maximal_set.has_value(), "Attempting to add an event to the maximal set " "when iteration has completed. This indicates that " "the termination condition for the iterator is broken"); @@ -129,6 +141,17 @@ void maximal_subsets_iterator::remove_element_from_current_maximal_set(const Unf bookkeeper.mark_removed_from_maximal_set(e); } +bool maximal_subsets_iterator::can_grow_maximal_set() const +{ + if (not current_maximal_set.has_value()) { + return true; + } + if (maximum_subset_size.has_value()) { + return current_maximal_set.value().size() < maximum_subset_size.value(); + } + return true; +} + maximal_subsets_iterator::topological_order_position maximal_subsets_iterator::bookkeeper::find_next_candidate_event(topological_order_position first, topological_order_position last) const diff --git a/src/mc/explo/udpor/maximal_subsets_iterator.hpp b/src/mc/explo/udpor/maximal_subsets_iterator.hpp index 2be3497aea..c36d04a02c 100644 --- a/src/mc/explo/udpor/maximal_subsets_iterator.hpp +++ b/src/mc/explo/udpor/maximal_subsets_iterator.hpp @@ -39,14 +39,14 @@ public: using topological_order_position = std::vector::const_iterator; maximal_subsets_iterator() = default; - explicit maximal_subsets_iterator(const Configuration& config) : maximal_subsets_iterator(config.get_events()) {} - explicit maximal_subsets_iterator(const EventSet& events) : maximal_subsets_iterator(events, std::nullopt) {} - - maximal_subsets_iterator(const Configuration& config, std::optional filter) - : maximal_subsets_iterator(config.get_events(), filter) + explicit maximal_subsets_iterator(const Configuration& config, + std::optional filter = std::nullopt, + std::optional maximum_subset_size = std::nullopt) + : maximal_subsets_iterator(config.get_events(), filter, maximum_subset_size) { } - maximal_subsets_iterator(const EventSet& events, std::optional filter); + explicit maximal_subsets_iterator(const EventSet& events, std::optional filter = std::nullopt, + std::optional maximum_subset_size = std::nullopt); private: std::vector topological_ordering; @@ -56,6 +56,7 @@ private: // 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 maximum_subset_size = std::nullopt; std::optional current_maximal_set = std::nullopt; std::stack backtrack_points = std::stack(); @@ -124,6 +125,13 @@ private: */ topological_order_position continue_traversal_of_maximal_events_tree(); + /** + * @brief: Whether or not the current maximal set can + * grow based on the size limit imposed on the maximal + * sets that can be produced + */ + bool can_grow_maximal_set() 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; }