DAG vs. tree using Git?

GitData Structures

Git Problem Overview

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?

Git Solutions

Solution 1 - Git

> 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.

Graph with merging (Image source)

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

Categories
Recommended Git Solutions
Recommended Data Structures Solutions

Previous Solution:

Trouble using ScrollableResults-backed Stream as return type in Spring MVC

JavaHibernateJava 8Spring OrmOpen Session-in-View

Next Solution:

After Windows update "The type or namespace name 'Html' does not exist in the namespace 'System.Web.Mvc'"

asp.netasp.net MvcWindows Update

Attributions

All content for this solution is sourced from the original question on Stackoverflow.

The content on this page is licensed under the Attribution-ShareAlike 4.0 International (CC BY-SA 4.0) license.

Content TypeOriginal AuthorOriginal Content on Stackoverflow
QuestionJonathan.BrinkView Question on Stackoverflow
Solution 1 - GitJohn KugelmanView Answer on Stackoverflow