X-Git-Url: http://bilbo.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/blobdiff_plain/52367db30501439c2091f5dd858c8efe107e3340..50753d5f8442a47c17c4035724201a18a7ff6146:/src/mc/explo/udpor/Configuration.cpp

diff --git a/src/mc/explo/udpor/Configuration.cpp b/src/mc/explo/udpor/Configuration.cpp
index 098b70f26a..98d004b22d 100644
--- a/src/mc/explo/udpor/Configuration.cpp
+++ b/src/mc/explo/udpor/Configuration.cpp
@@ -4,7 +4,9 @@
  * under the terms of the license (GNU LGPL) which comes with this package. */
 
 #include "src/mc/explo/udpor/Configuration.hpp"
+#include "src/mc/explo/udpor/Comb.hpp"
 #include "src/mc/explo/udpor/History.hpp"
+#include "src/mc/explo/udpor/Unfolding.hpp"
 #include "src/mc/explo/udpor/UnfoldingEvent.hpp"
 #include "src/mc/explo/udpor/maximal_subsets_iterator.hpp"
 #include "xbt/asserts.h"
@@ -32,6 +34,8 @@ Configuration::Configuration(const EventSet& events) : events_(events)
   }
 }
 
+Configuration::Configuration(const History& history) : Configuration(history.get_all_events()) {}
+
 void Configuration::add_event(const UnfoldingEvent* e)
 {
   if (e == nullptr) {
@@ -59,9 +63,15 @@ void Configuration::add_event(const UnfoldingEvent* e)
   }
 }
 
+bool Configuration::is_compatible_with(const UnfoldingEvent* e) const
+{
+  return not e->conflicts_with(*this);
+}
+
 bool Configuration::is_compatible_with(const History& history) const
 {
-  return false;
+  return std::none_of(history.begin(), history.end(),
+                      [&](const UnfoldingEvent* e) { return e->conflicts_with(*this); });
 }
 
 std::vector<const UnfoldingEvent*> Configuration::get_topologically_sorted_events() const
@@ -105,4 +115,79 @@ EventSet Configuration::get_minimally_reproducible_events() const
   return minimally_reproducible_events;
 }
 
+std::optional<Configuration> Configuration::compute_alternative_to(const EventSet& D, const Unfolding& U) const
+{
+  // A full alternative can be computed by checking against everything in D
+  return compute_k_partial_alternative_to(D, U, D.size());
+}
+
+std::optional<Configuration> Configuration::compute_k_partial_alternative_to(const EventSet& D, const Unfolding& U,
+                                                                             size_t k) const
+{
+  // 1. Select k (of |D|, whichever is smaller) arbitrary events e_1, ..., e_k from D
+  const auto D_hat = [&]() {
+    const size_t size = std::min(k, D.size());
+    std::vector<const UnfoldingEvent*> D_hat(size);
+    // TODO: Since any subset suffices for computing `k`-partial alternatives,
+    // potentially select intelligently here (e.g. perhaps pick events
+    // with transitions that we know are totally independent). This may be
+    // especially important if the enumeration is the slowest part of
+    // UDPOR
+    //
+    // For now, simply pick the first `k` events
+    std::copy_n(D.begin(), size, D_hat.begin());
+    return D_hat;
+  }();
+
+  // 2. Build a U-comb <s_1, ..., s_k> of size k, where spike `s_i` contains
+  // all events in conflict with `e_i`
+  //
+  // 3. EXCEPT those events e' for which [e'] + C is not a configuration or
+  // [e'] intersects D
+  //
+  // NOTE: This is an expensive operation as we must traverse the entire unfolding
+  // and compute `C.is_compatible_with(History)` for every event in the structure :/.
+  // A later performance improvement would be to incorporate the work of Nguyen et al.
+  // into SimGrid which associated additonal data structures with each unfolding event.
+  // Since that is a rather complicated addition, we defer it to a later time...
+  Comb comb(k);
+
+  for (const auto* e : U) {
+    for (unsigned i = 0; i < k; i++) {
+      const UnfoldingEvent* e_i = D_hat[i];
+      if (const auto e_local_config = History(e);
+          e_i->conflicts_with(e) and (not D.intersects(e_local_config)) and is_compatible_with(e_local_config)) {
+        comb[i].push_back(e);
+      }
+    }
+  }
+
+  // 4. Find any such combination <e_1', ..., e_k'> in comb satisfying
+  // ~(e_i' # e_j') for i != j
+  //
+  // NOTE: This is a VERY expensive operation: it enumerates all possible
+  // ways to select an element from each spike. Unfortunately there's no
+  // way around the enumeration, as computing a full alternative in general is
+  // NP-complete (although computing the k-partial alternative is polynomial in
+  // the number of events)
+  const auto map_events = [](const std::vector<Spike::const_iterator>& spikes) {
+    std::vector<const UnfoldingEvent*> events;
+    for (const auto& event_in_spike : spikes) {
+      events.push_back(*event_in_spike);
+    }
+    return EventSet(std::move(events));
+  };
+  const auto alternative =
+      std::find_if(comb.combinations_begin(), comb.combinations_end(),
+                   [&map_events](const auto& vector) { return map_events(vector).is_conflict_free(); });
+
+  // No such alternative exists
+  if (alternative == comb.combinations_end()) {
+    return std::nullopt;
+  }
+
+  // 5. J := [e_1] + [e_2] + ... + [e_k] is a k-partial alternative
+  return Configuration(History(map_events(*alternative)));
+}
+
 } // namespace simgrid::mc::udpor