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 a33d418..d6ed988 100644 (file)
--- 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<node_filter_function> filter)
-    : current_maximal_set({EventSet()})
+maximal_subsets_iterator::maximal_subsets_iterator(const EventSet& events, std::optional<node_filter_function> filter,
+                                                   std::optional<size_t> 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 2be3497..c36d04a 100644 (file)
--- 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 UnfoldingEvent*>::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<node_filter_function> filter)
-      : maximal_subsets_iterator(config.get_events(), filter)
+  explicit maximal_subsets_iterator(const Configuration& config,
+                                    std::optional<node_filter_function> filter = std::nullopt,
+                                    std::optional<size_t> maximum_subset_size  = std::nullopt)
+      : maximal_subsets_iterator(config.get_events(), filter, maximum_subset_size)
   {
   }
-  maximal_subsets_iterator(const EventSet& events, std::optional<node_filter_function> filter);
+  explicit maximal_subsets_iterator(const EventSet& events, std::optional<node_filter_function> filter = std::nullopt,
+                                    std::optional<size_t> maximum_subset_size = std::nullopt);
 
 private:
   std::vector<const UnfoldingEvent*> 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<size_t> maximum_subset_size               = std::nullopt;
   std::optional<EventSet> current_maximal_set             = std::nullopt;
   std::stack<topological_order_position> backtrack_points = std::stack<topological_order_position>();
 
@@ -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; }