Version control systems are a staple of modern software development. With popular applications like Git and SVN, almost all production-level software written today is managed with version control systems. However, what is not as well-known is that at the heart of these systems is a beautiful and practical application of graph theory.
The commit history of any version control repository can be represented as a directed acyclic graph, where each node is a revision of some source code, and the edges are links in time pointing to the previous commit made. The main branch of this repository, often named master, is essentially a straight chain of commit nodes, with each edge linking commits to its previous commit dependency.
The tree-like structure of this particular repository comes from the ability to “branch” off certain nodes in the master branch, which allows parallel lines of development. The interesting part is when we consider the actions of “merging” and “rebasing”, which turns the graph from a tree to a directed acyclic graph.
Merging is the act of taking two branches and combining them together, constructing a new node in the commit history containing the combination of changes made on both branches. Note this still forms a directed acyclic graph, since every edge is only ever directed backwards in time- there is no way to form a cycle in this case.
Rebasing, on the other hand, constructs a new edge, rather than a new node. When branch A is rebased onto branch B, the head of branch A modifies its edge to point to the tail of B, essentially replaying changes made to the source code in a new order. Note this also still forms a directed acyclic graph!
While Git is infamous for its terse and confusing commands, the model behind it is quite interesting!
