}
}
-std::vector<UnfoldingEvent*> Configuration::get_topogolically_sorted_events_of_reverse_graph() const
+std::vector<UnfoldingEvent*> Configuration::get_topologically_sorted_events() const
{
if (events_.empty()) {
return std::vector<UnfoldingEvent*>();
// 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 {
+ 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. part of the topological search
+ // 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();
}
-
- 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;
}
+std::vector<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
void add_event(UnfoldingEvent* e);
/**
+ * @brief Orders the events of the configuration such that
+ * "more recent" events (i.e. those that are farther down in
+ * the event structure's dependency chain) come after those
+ * that appeared "farther in the past"
*
+ * @returns a vector `V` with the following property:
+ *
+ * 1. Let i(e) := C -> I map events to their indices in `V`.
+ * For every pair of events e, e' in C, if e < e' then i(e) < i(e')
+ *
+ * Intuitively, events that are closer to the "bottom" of the event
+ * structure appear farther along in the list than those that appear
+ * closer to the "top"
+ */
+ std::vector<UnfoldingEvent*> get_topologically_sorted_events() const;
+
+ /**
+ * @brief Orders the events of the configuration such that
+ * "more recent" events (i.e. those that are farther down in
+ * the event structure's dependency chain) come before those
+ * that appear "farther in the past"
+ *
+ * @note The events of the event structure are arranged such that
+ * e < e' implies a directed edge from e to e'. However, it is
+ * also useful to be able to traverse the *reverse* graph (for
+ * example when computing the compatibility graph of a configuration),
+ * hence the distinction between "reversed" and the method
+ * "Configuration::get_topologically_sorted_events()"
+ *
+ * @returns a vector `V` with the following property:
+ *
+ * 1. Let i(e) := C -> I map events to their indices in `V`.
+ * For every pair of events e, e' in C, if e < e' then i(e) > i(e')
+ *
+ * Intuitively, events that are closer to the "top" of the event
+ * structure appear farther along in the list than those that appear
+ * closer to the "bottom"
*/
- std::vector<UnfoldingEvent*> get_topogolically_sorted_events_of_reverse_graph() const;
+ std::vector<UnfoldingEvent*> get_topologically_sorted_events_of_reverse_graph() const;
private:
/**
REQUIRE_NOTHROW(Configuration({&e1, &e2, &e3, &e4}).add_event(&e3));
REQUIRE_NOTHROW(Configuration({&e1, &e2, &e3, &e4}).add_event(&e4));
}
+
+TEST_CASE("simgrid::mc::udpor::Configuration: Topological Sort Order")
+{
+ // The following tests concern the given event structure:
+ // e1
+ // /
+ // e2
+ // /
+ // e3
+ // /
+ // e4
+ UnfoldingEvent e1;
+ UnfoldingEvent e2{&e1};
+ UnfoldingEvent e3{&e2};
+ UnfoldingEvent e4{&e3};
+
+ SECTION("Topological ordering for entire set")
+ {
+ Configuration C{&e1, &e2, &e3, &e4};
+ REQUIRE(C.get_topologically_sorted_events() == std::vector<UnfoldingEvent*>{&e1, &e2, &e3, &e4});
+ REQUIRE(C.get_topologically_sorted_events_of_reverse_graph() == std::vector<UnfoldingEvent*>{&e4, &e3, &e2, &e1});
+ }
+
+ SECTION("Topological ordering for subsets")
+ {
+ SECTION("No elements")
+ {
+ Configuration C;
+ REQUIRE(C.get_topologically_sorted_events() == std::vector<UnfoldingEvent*>{});
+ REQUIRE(C.get_topologically_sorted_events_of_reverse_graph() == std::vector<UnfoldingEvent*>{});
+ }
+
+ SECTION("e1 only")
+ {
+ Configuration C{&e1};
+ REQUIRE(C.get_topologically_sorted_events() == std::vector<UnfoldingEvent*>{&e1});
+ REQUIRE(C.get_topologically_sorted_events_of_reverse_graph() == std::vector<UnfoldingEvent*>{&e1});
+ }
+
+ SECTION("e1 and e2 only")
+ {
+ Configuration C{&e1, &e2};
+ REQUIRE(C.get_topologically_sorted_events() == std::vector<UnfoldingEvent*>{&e1, &e2});
+ REQUIRE(C.get_topologically_sorted_events_of_reverse_graph() == std::vector<UnfoldingEvent*>{&e2, &e1});
+ }
+
+ SECTION("e1, e2, and e3 only")
+ {
+ Configuration C{&e1, &e2, &e3};
+ REQUIRE(C.get_topologically_sorted_events() == std::vector<UnfoldingEvent*>{&e1, &e2, &e3});
+ REQUIRE(C.get_topologically_sorted_events_of_reverse_graph() == std::vector<UnfoldingEvent*>{&e3, &e2, &e1});
+ }
+ }
+}
+
+TEST_CASE("simgrid::mc::udpor::Configuration: Topological Sort Order More Complicated")
+{
+ // The following tests concern the given event structure:
+ // e1
+ // /
+ // e2
+ // /
+ // e3
+ // / /
+ // e4 e6
+ // /
+ // e5
+ UnfoldingEvent e1;
+ UnfoldingEvent e2{&e1};
+ UnfoldingEvent e3{&e2};
+ UnfoldingEvent e4{&e3}, e6{&e3};
+ UnfoldingEvent e5{&e4};
+
+ SECTION("Topological ordering for subsets")
+ {
+ SECTION("No elements")
+ {
+ Configuration C;
+ REQUIRE(C.get_topologically_sorted_events() == std::vector<UnfoldingEvent*>{});
+ REQUIRE(C.get_topologically_sorted_events_of_reverse_graph() == std::vector<UnfoldingEvent*>{});
+ }
+
+ SECTION("e1 only")
+ {
+ Configuration C{&e1};
+ REQUIRE(C.get_topologically_sorted_events() == std::vector<UnfoldingEvent*>{&e1});
+ REQUIRE(C.get_topologically_sorted_events_of_reverse_graph() == std::vector<UnfoldingEvent*>{&e1});
+ }
+
+ SECTION("e1 and e2 only")
+ {
+ Configuration C{&e1, &e2};
+ REQUIRE(C.get_topologically_sorted_events() == std::vector<UnfoldingEvent*>{&e1, &e2});
+ REQUIRE(C.get_topologically_sorted_events_of_reverse_graph() == std::vector<UnfoldingEvent*>{&e2, &e1});
+ }
+
+ SECTION("e1, e2, and e3 only")
+ {
+ Configuration C{&e1, &e2, &e3};
+ REQUIRE(C.get_topologically_sorted_events() == std::vector<UnfoldingEvent*>{&e1, &e2, &e3});
+ REQUIRE(C.get_topologically_sorted_events_of_reverse_graph() == std::vector<UnfoldingEvent*>{&e3, &e2, &e1});
+ }
+
+ SECTION("e1, e2, e3, and e6 only")
+ {
+ Configuration C{&e1, &e2, &e3, &e6};
+ REQUIRE(C.get_topologically_sorted_events() == std::vector<UnfoldingEvent*>{&e1, &e2, &e3, &e6});
+ REQUIRE(C.get_topologically_sorted_events_of_reverse_graph() == std::vector<UnfoldingEvent*>{&e6, &e3, &e2, &e1});
+ }
+
+ SECTION("e1, e2, e3, and e4 only")
+ {
+ Configuration C{&e1, &e2, &e3, &e4};
+ REQUIRE(C.get_topologically_sorted_events() == std::vector<UnfoldingEvent*>{&e1, &e2, &e3, &e4});
+ REQUIRE(C.get_topologically_sorted_events_of_reverse_graph() == std::vector<UnfoldingEvent*>{&e4, &e3, &e2, &e1});
+ }
+
+ SECTION("e1, e2, e3, e4, and e5 only")
+ {
+ Configuration C{&e1, &e2, &e3, &e4, &e5};
+ REQUIRE(C.get_topologically_sorted_events() == std::vector<UnfoldingEvent*>{&e1, &e2, &e3, &e4, &e5});
+ REQUIRE(C.get_topologically_sorted_events_of_reverse_graph() ==
+ std::vector<UnfoldingEvent*>{&e5, &e4, &e3, &e2, &e1});
+ }
+
+ SECTION("e1, e2, e3, e4 and e6 only")
+ {
+ // In this case, e4 and e6 are interchangeable. Hence, we have to check
+ // if the sorting gives us *any* of the combinations
+ Configuration C{&e1, &e2, &e3, &e4, &e6};
+ REQUIRE((C.get_topologically_sorted_events() == std::vector<UnfoldingEvent*>{&e1, &e2, &e3, &e4, &e6} ||
+ C.get_topologically_sorted_events() == std::vector<UnfoldingEvent*>{&e1, &e2, &e3, &e6, &e4}));
+ REQUIRE((C.get_topologically_sorted_events_of_reverse_graph() ==
+ std::vector<UnfoldingEvent*>{&e6, &e4, &e3, &e2, &e1} ||
+ C.get_topologically_sorted_events_of_reverse_graph() ==
+ std::vector<UnfoldingEvent*>{&e4, &e6, &e3, &e2, &e1}));
+ }
+
+ SECTION("Topological ordering for entire set")
+ {
+ // In this case, e4/e5 are both interchangeable with e6. Hence, again we have to check
+ // if the sorting gives us *any* of the combinations
+ Configuration C{&e1, &e2, &e3, &e4, &e5, &e6};
+ REQUIRE((C.get_topologically_sorted_events() == std::vector<UnfoldingEvent*>{&e1, &e2, &e3, &e4, &e5, &e6} ||
+ C.get_topologically_sorted_events() == std::vector<UnfoldingEvent*>{&e1, &e2, &e3, &e4, &e6, &e5} ||
+ C.get_topologically_sorted_events() == std::vector<UnfoldingEvent*>{&e1, &e2, &e3, &e6, &e4, &e5}));
+ REQUIRE((C.get_topologically_sorted_events_of_reverse_graph() ==
+ std::vector<UnfoldingEvent*>{&e6, &e5, &e4, &e3, &e2, &e1} ||
+ C.get_topologically_sorted_events_of_reverse_graph() ==
+ std::vector<UnfoldingEvent*>{&e5, &e6, &e4, &e3, &e2, &e1} ||
+ C.get_topologically_sorted_events_of_reverse_graph() ==
+ std::vector<UnfoldingEvent*>{&e5, &e4, &e6, &e3, &e2, &e1}));
+ }
+ }
+}
\ No newline at end of file
