Optimizing product orders using graph algorithms for improving incremental product-line analysis
Sascha Lity, Mustafa Al‐Hajjaji, Thomas Thüm, Ina Schaefer · 2017
The individual analysis of each product of a software product line (SPL) leads to redundant analysis steps due to the inherent commonality. Therefore, incremental SPL analyses exploit commonalities and focus on the differences between products to reduce the analysis effort. However, existing techniques are influenced by the order in which products are analyzed. The more similar subsequently analyzed products are, the greater is the potential reduction of the overall analysis effort as similar products imply less differences to be analyzed. Hence, an order of products, where the total number of differences is minimized, facilitates incremental SPL analyses. In this paper, we apply graph algorithms to determine optimized product orders. We capture products as nodes in a graph, where solution-space information defines edge weights between product nodes. We adopt existing heuristics for finding an optimal solution of the traveling salesperson problem to determine a path in the product graph with minimal costs. A path represents an optimized product order w.r.t. minimized differences between all products. We realize a prototype of our approach and evaluate its applicability and performance showing a significant optimization compared to standard and random orders.