Incremental Construction of Modal Implication Graphs for Evolving Feature Models

Sebastian Krieter, Rahel Arens, Michael Nieke, Chico Sundermann, Tobias Heß, Thomas Thüm, Christoph Seidl

Research output: Conference Article in Proceeding or Book/Report chapterArticle in proceedingsResearchpeer-review


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.
Original languageEnglish
Title of host publicationProceedings of the 25th ACM International Systems and Software Product Line Conference (SPLC'21) - Volume A
PublisherAssociation for Computing Machinery
Publication date2021
Publication statusPublished - 2021


  • Feature Model
  • Variant Configuration
  • Modal Implication Graph (MIG)
  • Incremental Computation
  • Configuration Logic Evolution


Dive into the research topics of 'Incremental Construction of Modal Implication Graphs for Evolving Feature Models'. Together they form a unique fingerprint.

Cite this