}
std::unique_ptr<CompatibilityGraph>
-Configuration::make_compatibility_graph_filtered_on(std::function<bool(UnfoldingEvent*)> pred) const
+Configuration::make_compatibility_graph_filtered_on(std::function<bool(const UnfoldingEvent*)> pred) const
{
auto G = std::make_unique<CompatibilityGraph>();
const auto& e_potential_placement = e_search_data.potential_placement;
const auto e_child_count = e_search_data.immediate_children_count;
+ const bool e_should_appear = pred(e);
CompatibilityGraphNode* e_placement = nullptr;
- // The justification is as follows:
- //
- // e_has_no_search_data:
- // If nobody told us about a placement, we must either be a leaf event
- // OR be the cause of an event that itself has more than one cause.
- //
- // child_count >= 2:
- // If there are two or more events that this event causes,
- // then we certainly must be part of a different compatibility
- // graph node since
- const bool new_placement_required = e_has_no_search_data || e_child_count >= 2;
-
- if (new_placement_required) {
- auto new_graph_node = std::make_unique<CompatibilityGraphNode>(e_conflicts, EventSet({e}));
- e_placement = new_graph_node.get();
- G->insert(std::move(new_graph_node));
- } else {
- xbt_assert(e_child_count == 1, "An event was informed by an immediate child of placement in "
- "the same compatibility graph node, yet the child did not inform "
- "the parent about its precense");
- // A child event told us this node can be in the
- // same compatibility node in the graph G. Add ourselves now
- e_placement = e_potential_placement;
- e_placement->add_event(e);
+ if (e_should_appear) {
+ // The justification is as follows:
+ //
+ // e_has_no_search_data:
+ // The event `e` is a leaf node, so there are no prior
+ // nodes in `G` to join
+ //
+ // child_count >= 2:
+ // If there are two or more events that this event causes,
+ // then we certainly must be part of a compatibility
+ // graph node that conflicts with each of our children
+ //
+ // e_potential_placement == nullptr:
+ // If nobody told us about a placement and yet still have search
+ // data, this means means that our child `C` had more than one child itself,
+ // so it we could not have moved into `C`'s _potential_ placement.
+ const bool new_placement_required =
+ e_has_no_search_data || e_child_count >= 2 || e_potential_placement == nullptr;
+
+ if (new_placement_required) {
+ auto new_graph_node = std::make_unique<CompatibilityGraphNode>(e_conflicts, EventSet({e}));
+ e_placement = new_graph_node.get();
+ G->insert(std::move(new_graph_node));
+ } else {
+ xbt_assert(e_child_count == 1, "An event was informed by an immediate child of placement in "
+ "the same compatibility graph node, yet the child did not inform "
+ "the parent about its presence");
+ // A child event told us this node can be in the
+ // same compatibility node in the graph G. Add ourselves now
+ e_placement = e_potential_placement;
+ e_placement->add_event(e);
+ }
}
// 2. Update the children of `e`
const EventSet& e_immediate_causes = e->get_immediate_causes();
+
+ // If there is only a single ancestor, then it MAY BE in
+ // the same "chain" of events as us. Note that the ancestor must
+ // also have only a single child (see the note on `new_placement_required`).
+ //
+ // If there is more than one child, then each child is in conflict with `e`
+ // so we don't potentially place it
if (e_immediate_causes.size() == 1) {
- // If there is only a single ancestor, then it MAY BE in
- // the same "chain" of events as us. Note that the ancestor must
- // also have only a single child (see the note on `new_placement_required`)
- UnfoldingEvent* only_ancestor = *e_immediate_causes.begin();
- search_data[only_ancestor].potential_placement = e_placement;
+ UnfoldingEvent* only_ancestor = *e_immediate_causes.begin();
+
+ // If `e` is included in the graph, forward its placement on to
+ // the sole child. Otherwise attempt to forward `e`'s _potential_
+ // (potential is stressed) placement. We can only forward `e`'s
+ // potential placement iff `e` has only a single child; for if
+ // `e` had more children, then our sole ancestor would conflict with
+ // each one of `e`'s children and thus couldn't be in the same group
+ // as any of them
+ if (e_should_appear) {
+ search_data[only_ancestor].potential_placement = e_placement;
+ } else {
+ search_data[only_ancestor].potential_placement = e_child_count == 1 ? e_potential_placement : nullptr;
+ }
}
// Our ancestors conflict with everyone `e` does else PLUS `e` itself
+ // ONLY IF e actually was placed
auto parent_conflicts = std::move(e_conflicts);
- parent_conflicts.insert(e_placement);
+ if (e_should_appear) {
+ parent_conflicts.insert(e_placement);
+ }
for (auto* cause : e_immediate_causes) {
search_data[cause].immediate_children_count += 1;