- std::stack<UnfoldingEvent*> event_stack;
- std::vector<UnfoldingEvent*> topological_ordering;
- EventSet unknown_events = events_, temporarily_marked_events, permanently_marked_events;
-
- while (not unknown_events.empty()) {
- EventSet discovered_events;
- event_stack.push(*unknown_events.begin());
-
- while (not event_stack.empty()) {
- UnfoldingEvent* evt = event_stack.top();
- discovered_events.insert(evt);
-
- if (not temporarily_marked_events.contains(evt)) {
- // If this event hasn't yet been marked, do
- // so now so that if we see it again in a child we can
- // detect a cycle and if we see it again here
- // we can detect that the node is re-processed
- temporarily_marked_events.insert(evt);
-
- EventSet immediate_causes = evt->get_immediate_causes();
- if (!immediate_causes.empty() && immediate_causes.is_subset_of(temporarily_marked_events)) {
- throw std::invalid_argument("Attempted to perform a topological sort on a configuration "
- "whose contents contain a cycle. The configuration (and the graph "
- "connecting all of the events) is an invalid event structure");
- }
- immediate_causes.subtract(discovered_events);
- immediate_causes.subtract(permanently_marked_events);
- const EventSet undiscovered_causes = std::move(immediate_causes);
-
- for (const auto cause : undiscovered_causes) {
- event_stack.push(cause);
- }
- } else {
- // Mark this event as:
- // 1. discovered across all DFSs performed
- // 2. permanently marked
- // 3. part of the topological search
- unknown_events.remove(evt);
- temporarily_marked_events.remove(evt);
- permanently_marked_events.insert(evt);
-
- // In moving this event to the end of the list,
- // we are saying this events "happens before" other
- // events that are added later.
- topological_ordering.push_back(evt);
-
- // Only now do we remove the event, i.e. once
- // we've processed the same event again
- event_stack.pop();
+ // Now we need only ensure that there are no conflicts
+ // between events of the configuration and the events
+ // that lie outside of the configuration. There is no
+ // need to check if there are conflicts in `C`: we already
+ // know that it's conflict free
+ const auto begin = simgrid::xbt::variable_for_loop<const EventSet>{{event_diff}, {this->events_}};
+ const auto end = simgrid::xbt::variable_for_loop<const EventSet>();
+ return std::none_of(begin, end, [=](const auto event_pair) {
+ const UnfoldingEvent* e1 = *event_pair[0];
+ const UnfoldingEvent* e2 = *event_pair[1];
+ return e1->conflicts_with(e2);
+ });
+}
+
+std::vector<const UnfoldingEvent*> Configuration::get_topologically_sorted_events() const
+{
+ return this->events_.get_topological_ordering();
+}
+
+std::vector<const UnfoldingEvent*> Configuration::get_topologically_sorted_events_of_reverse_graph() const
+{
+ return this->events_.get_topological_ordering_of_reverse_graph();
+}
+
+EventSet Configuration::get_minimally_reproducible_events() const
+{
+ // The implementation exploits the following observations:
+ //
+ // To select the smallest reproducible set of events, we want
+ // to pick events that "knock out" a lot of others. Furthermore,
+ // we need to ensure that the events furthest down in the
+ // causality graph are also selected. If you combine these ideas,
+ // you're basically left with traversing the set of maximal
+ // subsets of C! And we have an iterator for that already!
+ //
+ // The next observation is that the moment we don't increase in size
+ // the current maximal set (or decrease the number of events),
+ // we know that the prior set `S` covered the entire history of C and
+ // was maximal. Subsequent sets will miss events earlier in the
+ // topological ordering that appear in `S`
+ EventSet minimally_reproducible_events = EventSet();
+
+ for (const auto& maximal_set : maximal_subsets_iterator_wrapper<Configuration>(*this)) {
+ if (maximal_set.size() > minimally_reproducible_events.size()) {
+ minimally_reproducible_events = maximal_set;
+ } else {
+ // The moment we see the iterator generate a set of size
+ // that is not monotonically increasing, we can stop:
+ // the set prior was the minimally-reproducible one
+ return minimally_reproducible_events;
+ }
+ }
+ 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 size_t k_alt_size = std::min(k, D.size());
+ const auto D_hat = [&k_alt_size, &D]() {
+ std::vector<const UnfoldingEvent*> D_hat(k_alt_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(), k_alt_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 (size_t i = 0; i < k_alt_size; 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);