kernel.core.topological-sort
Sorts a set of compatible operations topologically according to kernel.core.compound-operation/preceding?.
Sometimes, a site has to apply a given set of operations to a feature model. The order of operations matters, but there is a solution if the operations are pairwise compatible. In that case, it can be proven that operations commute if they are concurrent. Order of operations then only matters for causal chains of operations in the set. For example, if {A, B, C} should be sorted where A || B and B -> C, a valid order can execute A at any time, but has to execute B before C. This corresponds to a topological sorting of the operation set using the causally-preceding relation.
Topological sort is not guaranteed to be unique, but as concurrent operations commute, the resulting feature model is guaranteed to be equal for any topological sorting (and therefore across all sites).
Algorithm adapted from rosettacode.org.
apply-compatible*
(apply-compatible* CDAG HB FM CO-IDs)Applies a set of compatible compound operations to a feature model. First, sorts the operations topologically with CO-topological-sort, then applies the operations in that order.
CO-dependency-map
(CO-dependency-map CDAG CO-IDs)Constructs a dependency map from operations to their CIPs, only including direct dependencies (CIP) that are in the set of operations to be sorted.
CO-topological-sort
(CO-topological-sort CDAG CO-IDs)Sorts a set of compatible operations topologically according to the causally-preceding relation.
remove-items
(remove-items deps items)Returns a dependence map with the specified items removed from keys and from all dependence sets of remaining keys.
single-dependency-map
(single-dependency-map item items)Constructs a single-key dependence, represented as a map from item to a set of items, ensuring that item is not in the set.
sources
(sources deps)Returns all keys from the argument which have no (i.e. empty) dependencies.
topological-sort
(topological-sort deps)Given a dependence map assumed to have no cycles, returns a list of items in which each item follows all of its successors.