Incremental Construction of Modal Implication Graphs for Evolving Feature Models

A feature model represents a set of variants as configurable features and dependencies between them. During variant configuration, (de)selection of a feature may entail that other features must or cannot be selected. A Modal Implication Graph (MIG) enables efficient decision propagation to perform automatic (de)selection of subsequent features. In addition, it facilitates other configuration-related activities such as t-wise sampling. Evolution of a feature model may change its configuration logic, thereby invalidating an existing MIG and forcing a full recomputation. However, repeated recomputation of a MIG is expensive, and thus hampers the overall usefulness of MIGs for frequently evolving feature models. In this paper, we devise a method to incrementally compute updated MIGs after feature model evolution. We identify expensive steps in the MIG construction algorithm, enable them for incremental computation, and measure performance compared to a full rebuild of a complete MIG within the evolution histories of four real-world feature models. Results show that our incremental method can increase the speed of MIG construction by orders of magnitude, depending on the given scenario and extent of evolutionary changes.