학술논문
Random Generation of Git Graphs
Document Type
Working Paper
Author
Source
GASCom 2024, Jun 2024, Talence, France, France
Subject
Language
Abstract
Version Control Systems, such as Git and Mercurial, manage the history of a project as a Directed Acyclic Graph encoding the various divergences and synchronizations happening in its life cycle. A popular workflow in the industry, called the feature branch workflow, constrains these graphs to be of a particular shape: a unique main branch, and non-interfering feature branches. Here we focus on the uniform random generation of those graphs with n vertices, including k on the main branch, for which we provide three algorithms, for three different use-cases. The first, based on rejection, is efficient when aiming for small values of k (more precisely whenever k = O($\sqrt$ n)). The second takes as input any number k of commits in the main branch, but requires costly precalculation. The last one is a Boltzmann generator and enables us to generate very large graphs while targeting a constant k/n ratio. All these algorithms are linear in the size of their outputs.