modernize cycle detection in DAGs

diff --git a/include/simgrid/s4u/Activity.hpp b/include/simgrid/s4u/Activity.hpp
index 4ef19c2..6b4ceae 100644 (file)
--- a/include/simgrid/s4u/Activity.hpp
+++ b/include/simgrid/s4u/Activity.hpp
@@ -168,6 +168,8 @@ public:
 
   double get_start_time() const;
   double get_finish_time() const;
+  void mark() { marked_ = true; }
+  bool is_marked() const { return marked_; }
 
   /** Returns the internal implementation of this Activity */
   kernel::activity::ActivityImpl* get_impl() const { return pimpl_.get(); }
@@ -194,6 +196,7 @@ private:
   Activity::State state_                   = Activity::State::INITED;
   double remains_                          = 0;
   bool suspended_                          = false;
+  bool marked_                             = false;
   std::vector<ActivityPtr> successors_;
   std::set<ActivityPtr> dependencies_;
   std::atomic_int_fast32_t refcount_{0};

diff --git a/src/simdag/sd_daxloader.cpp b/src/simdag/sd_daxloader.cpp
index a3afbcb..91ffa11 100644 (file)
--- a/src/simdag/sd_daxloader.cpp
+++ b/src/simdag/sd_daxloader.cpp
@@ -5,6 +5,8 @@
  * under the terms of the license (GNU LGPL) which comes with this package. */
 
 #include "simdag_private.hpp"
+#include "simgrid/s4u/Comm.hpp"
+#include "simgrid/s4u/Exec.hpp"
 #include "simgrid/simdag.h"
 #include "xbt/file.hpp"
 #include "xbt/log.h"
@@ -126,6 +128,40 @@ bool acyclic_graph_detail(const_xbt_dynar_t dag)
   return all_marked;
 }
 
+bool check_for_cycle(const std::vector<simgrid::s4u::ActivityPtr>& dag)
+{
+  std::vector<simgrid::s4u::ActivityPtr> current;
+
+  for (const auto& a : dag)
+    if (dynamic_cast<simgrid::s4u::Exec*>(a.get()) != nullptr && a->is_waited_by() == 0)
+      current.push_back(a);
+
+  while (not current.empty()) {
+    std::vector<simgrid::s4u::ActivityPtr> next;
+    for (auto const& a : current) {
+      a->mark();
+      for (auto const& pred : a->get_dependencies()) {
+        if (dynamic_cast<simgrid::s4u::Comm*>(pred.get()) != nullptr) {
+          pred->mark();
+          // Comms have only one predecessor
+          auto pred_pred = *(pred->get_dependencies().begin());
+          if (std::none_of(pred_pred->get_successors().begin(), pred_pred->get_successors().end(),
+                           [](const simgrid::s4u::ActivityPtr& a) { return not a->is_marked(); }))
+            next.push_back(pred_pred);
+        } else {
+          if (std::none_of(pred->get_successors().begin(), pred->get_successors().end(),
+                           [](const simgrid::s4u::ActivityPtr& a) { return not a->is_marked(); }))
+            next.push_back(pred);
+        }
+      }
+    }
+    current.clear();
+    current = next;
+  }
+
+  return not std::any_of(dag.begin(), dag.end(), [](const simgrid::s4u::ActivityPtr& a) { return not a->is_marked(); });
+}
+
 static YY_BUFFER_STATE input_buffer;
 
 static xbt_dynar_t result;

diff --git a/src/simdag/sd_dotloader.cpp b/src/simdag/sd_dotloader.cpp
index 860f409..cfecfe6 100644 (file)
--- a/src/simdag/sd_dotloader.cpp
+++ b/src/simdag/sd_dotloader.cpp
@@ -120,6 +120,12 @@ std::vector<ActivityPtr> create_DAG_from_dot(const std::string& filename)
   agclose(dag_dot);
   fclose(in_file);
 
+  if (not check_for_cycle(dag)) {
+    std::string base = simgrid::xbt::Path(filename).get_base_name();
+    XBT_ERROR("The DOT described in %s is not a DAG. It contains a cycle.", base.c_str());
+    dag.clear();
+  }
+
   return dag;
 }
 

diff --git a/src/simdag/simdag_private.hpp b/src/simdag/simdag_private.hpp
index d373b76..ef9e87d 100644 (file)
--- a/src/simdag/simdag_private.hpp
+++ b/src/simdag/simdag_private.hpp
@@ -172,6 +172,7 @@ public:
 extern XBT_PRIVATE std::unique_ptr<simgrid::sd::Global> sd_global;
 
 /* SimDag private functions */
+XBT_PRIVATE bool check_for_cycle(const std::vector<simgrid::s4u::ActivityPtr>& dag);
 XBT_PRIVATE bool acyclic_graph_detail(const_xbt_dynar_t dag);
 XBT_PRIVATE void uniq_transfer_task_name(SD_task_t task);
 XBT_PRIVATE const char *__get_state_name(e_SD_task_state_t state);