X-Git-Url: http://bilbo.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/blobdiff_plain/3203afd846219ef8b41cadda945ea0a98103c46f..5f4fec5323389b31285cd4e19a6abda90e63a555:/src/mc/explo/udpor/Configuration.cpp

diff --git a/src/mc/explo/udpor/Configuration.cpp b/src/mc/explo/udpor/Configuration.cpp
index 46bc8c568d..70f4659f0b 100644
--- a/src/mc/explo/udpor/Configuration.cpp
+++ b/src/mc/explo/udpor/Configuration.cpp
@@ -5,24 +5,28 @@
 
 #include "src/mc/explo/udpor/Configuration.hpp"
 #include "src/mc/explo/udpor/History.hpp"
+#include "src/mc/explo/udpor/UnfoldingEvent.hpp"
+#include "xbt/asserts.h"
 
 #include <algorithm>
+#include <stack>
 #include <stdexcept>
 
 namespace simgrid::mc::udpor {
 
-Configuration::Configuration(std::initializer_list<UnfoldingEvent*> events) : Configuration(EventSet(std::move(events)))
+Configuration::Configuration(std::initializer_list<const UnfoldingEvent*> events)
+    : Configuration(EventSet(std::move(events)))
 {
 }
 
-Configuration::Configuration(EventSet events) : events_(events)
+Configuration::Configuration(const EventSet& events) : events_(events)
 {
   if (!events_.is_valid_configuration()) {
     throw std::invalid_argument("The events do not form a valid configuration");
   }
 }
 
-void Configuration::add_event(UnfoldingEvent* e)
+void Configuration::add_event(const UnfoldingEvent* e)
 {
   if (e == nullptr) {
     throw std::invalid_argument("Expected a nonnull `UnfoldingEvent*` but received NULL instead");
@@ -43,4 +47,78 @@ void Configuration::add_event(UnfoldingEvent* e)
   }
 }
 
+std::vector<const UnfoldingEvent*> Configuration::get_topologically_sorted_events() const
+{
+  if (events_.empty()) {
+    return std::vector<const UnfoldingEvent*>();
+  }
+
+  std::stack<const UnfoldingEvent*> event_stack;
+  std::vector<const UnfoldingEvent*> topological_ordering;
+  EventSet unknown_events = events_;
+  EventSet temporarily_marked_events;
+  EventSet permanently_marked_events;
+
+  while (not unknown_events.empty()) {
+    EventSet discovered_events;
+    event_stack.push(*unknown_events.begin());
+
+    while (not event_stack.empty()) {
+      const 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();
+      }
+    }
+  }
+  return topological_ordering;
+}
+
+std::vector<const UnfoldingEvent*> Configuration::get_topologically_sorted_events_of_reverse_graph() const
+{
+  // The method exploits the property that
+  // a topological sorting S^R of the reverse graph G^R
+  // of some graph G is simply the reverse of any
+  // topological sorting S of G.
+  auto topological_events = get_topologically_sorted_events();
+  std::reverse(topological_events.begin(), topological_events.end());
+  return topological_events;
+}
+
 } // namespace simgrid::mc::udpor