DAG vs. tree using Git?

Question

I've often read that Git uses the directed acyclic graph (DAG) data structure, with each commit as a node, and things like branches and tags as pointers to nodes.

But when I try to visualize my commit history using tools like gitk, it looks more like a tree than a graph since every parent-child relationship is directed one way.

So, what's the difference between a DAG and a tree, specifically with regards to Git?

Geesey

Answer 1

But when I try to visualize my commit history using tools like gitk, it looks more like a tree than a graph since every parent-child relationship is directed one way.

A DAG, like a tree, can be laid out such that all parent-child relationships are one-way. The difference between them is that nodes in a DAG can have multiple parents. The most common case of this in Git is when you do a merge. A merge commit will have all of the commits that were merged as parents. A tree doesn't allow nodes to have multiple parents.

(Image source)

Notice how the merge commit C6 has two parents, C4 and C5.

Grampositive

@Geesey Also, a tree can have at most only one root, whereas a DAG can contain several roots, and even multiple disconnected subgraphs. – Jacobite

@Jacobite Sorry, but I cannot imagine how Git repository can have several roots as well as how there could be a disconnected subgraph – Brueghel

@Brueghel It certainly can. In the graph above, what if C3 did not have C2 had no parent? It could have no parent. Then both it and C0 would be roots. Furthermore, if C6 did not have C5 as a parent then master and iss53 would be disconnected from each other with no common commits. – Grampositive

Most git repositories that I've worked with only have a single root commit. Although it's technically possible to create multiple root commits, and there are circumstances when this can be useful, it won't happen by accident in your day-to-day dev work. – Laborious