Skip to content

Phase 2 of UDPOR Integration: Add topological sorting of events in a configuration

Maxwell Pirtle requested to merge maxwellpirtle/simgrid:udpor-phase2 into master

Overview

The next step is to add the ability to traverse events in a configuration in topological order. 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 compatibility graph G (which arrives with phase 3) whose elements represent "chains" of the event structure that are mutually exclusive and whose edges describe which chains are mutually incompatible with one another. The cliques of the complement of this graph G' represent "compatible" sets of events in the sense of being causally compatible (i.e. both can occur). Enumerating all possible cliques within G' thus determines all possible maximal configurations among these chains and thus of the configuration itself.

Since the topological sorting portion is rather important step, though, I've decided to make it into its own MR.

Changes

This MR adds two important methods to the Configuration class:

  1. Configuration::get_topologically_sorted_events() will give a topological ordering of the events in the configuration based on the dependency graph of the event structure (i.e. looking only at causal relations among events). Events that occur "earlier" in the causality sequence will appear earlier in the list
  2. Configuration::get_topologically_sorted_events_of_reverse_graph() does the same thing except that it considers the causal relations in the other sense: "you caused me" instead of "I cause you." The UnfoldingEvents maintain the former interpretation anyway, so the resulting ordering feels more "natural". Traversing the reverse of the causality graph is important for phase 3: constructing the compatibility graph for a configuration requires traversal of the configuration in topological order, and it is much more natural to perform the computations with traversal in the reverse sense.

What to focus on

The next phases (which I am currently working on at the moment) should be even more heavily scrutinized, as it will involve the actual determination of the compatibility graph, enumerations of its cliques, and enumerations of the events that are a part of each clique. For now, though, the idea is to be sufficiently sure in the computation of the topological sort of the configuration which will be used in subsequent phases.

Merge request reports