Add topological sort of configuration events

Topological sorting is an important first step
in determining which groups of events in a
configuration need to be tested together when
looking at all possible subsets of maximal events
of a configuration. The idea is that you first
build a compatability graph (soon to come) whose
elements represent "chains" of the event structure
that are mutually exslcusive and whose edges
describe which chains are mutually compatible
with one another. Then, you look for all possible
cliques within the graph to determine all possible
configurations of these chains. Each of the
major components of this process will be added in
subsequent commits

diff --git a/src/mc/explo/udpor/Configuration.cpp b/src/mc/explo/udpor/Configuration.cpp
index 46bc8c5..e2e2c3a 100644 (file)
--- a/src/mc/explo/udpor/Configuration.cpp
+++ b/src/mc/explo/udpor/Configuration.cpp
@@ -5,8 +5,10 @@
 
 #include "src/mc/explo/udpor/Configuration.hpp"
 #include "src/mc/explo/udpor/History.hpp"
+#include "src/mc/explo/udpor/UnfoldingEvent.hpp"
 
 #include <algorithm>
+#include <stack>
 #include <stdexcept>
 
 namespace simgrid::mc::udpor {
@@ -43,4 +45,59 @@ void Configuration::add_event(UnfoldingEvent* e)
   }
 }
 
+std::vector<UnfoldingEvent*> Configuration::get_topogolically_sorted_events_of_reverse_graph() const
+{
+  if (events_.empty()) {
+    return std::vector<UnfoldingEvent*>();
+  }
+
+  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);
+      } else {
+
+        // Mark this event as:
+        // 1. discovered across all DFSs performed
+        // 2. part of the topological search
+        temporarily_marked_events.remove(evt);
+        permanently_marked_events.insert(evt);
+        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();
+      }
+
+      const EventSet immediate_causes = evt->get_immediate_causes();
+      if (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");
+      }
+      const EventSet undiscovered_causes = std::move(immediate_causes).subtracting(discovered_events);
+
+      for (const auto cause : undiscovered_causes) {
+        event_stack.push(cause);
+      }
+    }
+  }
+
+  return topological_ordering;
+}
+
 } // namespace simgrid::mc::udpor

diff --git a/src/mc/explo/udpor/Configuration.hpp b/src/mc/explo/udpor/Configuration.hpp
index a1d37c5..eb365d5 100644 (file)
--- a/src/mc/explo/udpor/Configuration.hpp
+++ b/src/mc/explo/udpor/Configuration.hpp
@@ -10,6 +10,7 @@
 #include "src/mc/explo/udpor/udpor_forward.hpp"
 
 #include <initializer_list>
+#include <vector>
 
 namespace simgrid::mc::udpor {
 
@@ -59,6 +60,11 @@ public:
    */
   void add_event(UnfoldingEvent* e);
 
+  /**
+   *
+   */
+  std::vector<UnfoldingEvent*> get_topogolically_sorted_events_of_reverse_graph() const;
+
 private:
   /**
    * @brief The most recent event added to the configuration