Conflict and Dependency Graphs of Highly Configurable Software

Conflict and Dependency Graphs of Highly Configurable Software This repository contains a dataset of conflict and dependency graphs for 5,709 highly configurable software systems, along with the necessary code to replicate and validate the dataset. 1. Motivation and Purpose Software Product Lines (SPLs) enable developers to create diverse software products by combining and configuring reusable blocks of code, commonly referred to as features or configurable options. These systems are typically represented by Variability Models (VMs), which capture the relationships and constraints between options. However, VMs often fail to explicitly represent the indirect and transitive relationships that emerge from chaining direct constraints. These hidden relationships can make large-scale models, such as the Linux Kernel, difficult to reason about, validate, and manually configure. This dataset addresses these limitations by providing closure transitive graphs for 5,709 variability models from industrial and open-source systems. This graph-based representation offers several advantages: Explicit Relationships: It makes all direct and indirect "strong relationships" (dependencies and conflicts) explicit. A strong dependency means that if option A is enabled, option B must always be enabled. A strong conflict means that options A and B cannot be enabled simultaneously. Advanced Analysis: It enables the use of powerful graph analysis tools (like Gephi, Pajek, and igraph) to compute metrics, detect structural patterns (e.g., small-world), identify connected components, and find dominant features. Improved Reasoning: It helps propagate user configuration decisions automatically and simplifies reasoning about the impact of turning specific options on or off. The goal of this dataset is to facilitate advanced research on dependency patterns, feature centrality, and the evolution of configurability in complex systems by providing a curated collection of VMs transformed into a more expressive graph-based format. 2. Dataset Format The repository is organized into three main folders: graphs, replication, and validation. 2.1 summary.csv The root folder contains a summary.csv file that provides detailed metadata for each of the 5,709 variability models in the dataset. Each row corresponds to one model and includes columns such as: Identifier: A unique string to identify all files associated with a model (e.g., "LinuxX86__3-9__SystemsSoftware__Kuiter25__KMax"). NumNodes, NumDead, NumCore, NumExcludes, NumRequires: Statistics on the number of nodes, dead options, core options, conflict edges, and dependency arcs. Name: name of the model. Version: version of the model. Domain: application area of the variability model. Bibliographic and repository information (BibliographicID, BibliographicDOI, Repository). ToolToGetTheFormula: translator used to transform the variability model into a Boolean formula (e.g., “KMax”). The dataset was not generated directly from the original variability models (like Kconfig files). Instead, the starting point for building the graphs was a collection of Boolean formulas that had been previously synthesized and published by other research teams. These formulas, which logically encode the constraints of all 5,709 configurable systems, were created by the following researchers using specific tools: Sundermann et al., who used the TraVarT translator. Kuiter et al., who used the KMax and KConfigReader translators. Fernandez et al., who used the KconfigSampler tool. All these pre-existing formulas are in the /replication/formulas folder. They are written in the standard DIMACS CNF (Conjunctive Normal Form) format. The authors of this dataset then took this collection of formulas as input for their own process 2.2 /graphs Folder This folder contains the dataset itself. For each of the 5,709 models, there are four files, distinguished by their unique identifier: <identifier>__requires.net: A directed graph representing strong dependencies. An arc from node A to B means A strongly depends on B. <identifier>__excludes.net: An undirected graph representing strong conflicts. An edge between nodes A and B means they are mutually exclusive. <identifier>__core.txt: A text file listing all core options, which are options that must be enabled in every valid configuration. The file is empty if there are none. <identifier>__dead.txt: A text file listing all dead options, which are options that can never be enabled in any valid configuration. The file is empty if there are none. The dependency and conflict graphs (.net files) are in the Pajek NET format, which is widely supported by graph analysis tools like Gephi, igraph, and Pajek. These files are structured with a *Vertices section defining the nodes and an *Arcs (for dependency graphs) or *Edges (for conflict graphs) section defining the links. To simplify analysis and visualization, links related to core and dead options are omitted from the graphs, and these options are listed in separate files instead. 3. How to Replicate the Dataset All code required to regenerate the dataset from the original Boolean formulas is provided and has been tested on Linux. The process starts from the formulas located in the /replication/formulas directory. These formulas are encoded in the standard DIMACS CNF format. To replicate the entire dataset: 1. Navigate to the /replication/bin directory. 2. Run the following command in your terminal: bash get_all_transitive_graphs.sh This script internally calls the get_transitive_graph executable, which implements the algorithms to compute strong relationships from the Boolean formulas. If you wish to compile the C++ source code from scratch: 1. Navigate to the /replication/src directory. 2. Run the command: bash makegtg.sh This will compile the get_transitive_graph.cpp source code and create the executable. The implementation uses the MiniSat 2.2.0 solver via the IPASIR interface to speed up computations. 4. How to Validate the Dataset The repository includes scripts to validate the correctness of the generated dataset. The validation process checks two key aspects: (1) the lists of core and dead options, and (2) the dependency and conflict links for a sample of nodes in each graph. It uses an external tool, [MiniBones](https://github.com/MikolasJanota/minibones), to independently compute the backbone of the Boolean formulas for verification. To run the validation: 1. First, ensure you have the R interpreter installed. 2. Navigate to the /validation directory. You can then choose one of two validation options: - Validate a single model: To validate a specific model M by checking N random nodes, execute: Rscript validate_transitive_graph.R -f M -c N (Replace M with the model's DIMACS file path and N with the number of nodes to check). - Validate the entire dataset: To validate all models, run the following shell script: bash validate_all_transitive_graphs.sh By default, this script tests 1,000 nodes for each model; however, this number can be adjusted within the script. The dataset was successfully tested with N = 1,000.高可配置性软件的冲突与依赖图 本仓库收录了5709个高可配置性软件系统的冲突与依赖图数据集，以及用于复现、验证该数据集的配套代码。 1. 研究动机与目的 软件产品线（Software Product Lines, SPLs）允许开发者通过组合、配置可复用代码块（通常称为特征或可配置选项）来构建多样化的软件产品。这类系统通常通过可变模型（Variability Models, VMs）进行建模，以捕获各选项间的关联与约束关系。 然而，可变模型往往无法显式表示由直接约束链式衍生出的间接传递关系。这类隐藏关系会使得Linux内核这类大规模模型难以进行推理、验证与手动配置。 本数据集针对上述局限，为来自工业界与开源社区的5709个可变模型提供了传递闭包图。这种基于图的表示方式具备多项优势： - 显式关联关系：将所有直接与间接的强关联关系（依赖与冲突）清晰呈现。强依赖指若启用选项A，则必须同时启用选项B；强冲突指选项A与B无法同时启用。 - 高级分析能力：支持使用Gephi、Pajek、igraph等成熟图分析工具计算指标、检测结构模式（如小世界网络）、识别连通分量并找出主导特征。 - 优化推理效率：可自动传播用户的配置决策，简化针对特定选项启用/禁用所产生影响的推理过程。 本数据集的目标是，通过将精选的可变模型转换为更具表达力的图格式，推动复杂系统中依赖模式、特征中心性以及可配置性演化方向的前沿研究。 2. 数据集格式 本仓库分为三个核心文件夹：graphs、replication与validation。 2.1 summary.csv 根目录包含summary.csv文件，为数据集中的5709个可变模型提供详细元数据。每一行对应一个模型，包含以下列： - 唯一标识符：用于标识与该模型关联的所有文件的唯一字符串（例如"LinuxX86__3-9__SystemsSoftware__Kuiter25__KMax"）。 - 节点数、死选项数、核心选项数、冲突边数、依赖弧数：分别对应模型的节点总量、无法在任何有效配置中启用的选项数、所有有效配置中均需启用的核心选项数、冲突边数量与依赖弧数量。 - 模型名称：可变模型的名称。 - 模型版本：可变模型的版本号。 - 应用领域：可变模型的应用场景。 - 文献与仓库信息：包括文献ID、文献DOI、关联仓库地址。 - 公式生成工具：用于将可变模型转换为布尔公式（Boolean formula）的工具（例如"KMax"）。 本数据集并非直接从原始可变模型（如Kconfig文件）生成，而是以其他研究团队此前合成并公开的布尔公式集合作为构建基础。这5709个可配置系统的约束均通过布尔公式进行逻辑编码，这些公式由以下研究团队使用特定工具生成： - Sundermann等人，使用TraVarT工具； - Kuiter等人，使用KMax与KConfigReader工具； - Fernandez等人，使用KconfigSampler工具。 所有上述预先生成的公式均存储在/replication/formulas文件夹中，采用标准DIMACS合取范式（Conjunctive Normal Form, CNF）格式编写。本数据集的作者将这些公式集合作为自身处理流程的输入。 2.2 /graphs 文件夹 本文件夹存储数据集本体。针对5709个模型中的每一个，均包含四个以唯一标识符区分的文件： - <标识符>__requires.net：表示强依赖关系的有向图。从节点A指向节点B的弧代表A强依赖于B。 - <标识符>__excludes.net：表示强冲突关系的无向图。节点A与B之间的边代表二者互斥。 - <标识符>__core.txt：存储所有核心选项的文本文件，若不存在核心选项则该文件为空。 - <标识符>__dead.txt：存储所有死选项的文本文件，若不存在死选项则该文件为空。 依赖与冲突图（.net文件）采用Pajek NET格式，该格式被Gephi、igraph、Pajek等主流图分析工具广泛支持。文件结构包含定义节点的*Vertices段，以及定义连接关系的*Arcs（依赖图）或*Edges（冲突图）段。为简化分析与可视化流程，与核心选项及死选项相关的连接已从图中移除，这类选项将分别存储在单独的文件中。 3. 数据集复现方法 本仓库提供了从原始布尔公式重新生成数据集所需的全部代码，且已在Linux系统上完成测试。复现流程从/replication/formulas目录下的布尔公式开始，这些公式采用标准DIMACS合取范式格式编码。 若需复现完整数据集： 1. 进入/replication/bin目录。 2. 在终端执行以下命令： bash get_all_transitive_graphs.sh 该脚本内部将调用get_transitive_graph可执行文件，该文件实现了从布尔公式计算强关联关系的算法。 若需从头编译C++源代码： 1. 进入/replication/src目录。 2. 执行以下命令： bash makegtg.sh 该命令将编译get_transitive_graph.cpp源代码并生成可执行文件。本实现通过IPASIR接口调用MiniSat 2.2.0求解器以加速计算。 4. 数据集验证方法 本仓库包含用于验证生成数据集正确性的脚本。验证流程将检查两个核心维度：(1) 核心选项与死选项列表；(2) 每个图中随机采样节点的依赖与冲突连接关系。验证过程将使用外部工具MiniBones独立计算布尔公式的骨干集以完成验证。 若需运行验证流程： 1. 确保已安装R解释器。 2. 进入/validation目录。 您可选择以下两种验证方式之一： - 验证单个模型：若需验证特定模型M，通过检查N个随机节点，执行以下命令： Rscript validate_transitive_graph.R -f M -c N （将M替换为模型的DIMACS文件路径，N替换为待检查的节点数量）。 - 验证全量数据集：若需验证所有模型，运行以下shell脚本： bash validate_all_transitive_graphs.sh 默认情况下，该脚本将为每个模型测试1000个节点，该数值可在脚本内部调整。本数据集已通过N=1000的测试验证。