If you have a tree that also might merge branches, but only in a directed way, i.e. all edges are one step either towards or away from the "root", what can we call it? It's a special case of a directed graph.

Version control systems with branches such as git have these graph structures. In git you have the forward/backward in time (with the epoch as the "root") with the possibility of branches being merged.

Example from the git page on wikipedia, 1 being the "root":
git-graph from the git-page on wikipedia
( https://commons.wikimedia.org/wiki/File:Revision_controlled_project_visualization-2010-24-02.svg )

  • $\begingroup$ I feel like this question is sort of the inverse of the article Git for Computer Scientists: a "quick introduction to git internals for people who are not scared by words like Directed Acyclic Graph." $\endgroup$ – Rahul Dec 29 '14 at 12:55

This is known as a directed acyclic graph. For this type of graph no path along the directed edges can meet itself again at another point, but different paths could possibly diverge and then merge again.

Section 3.5 in the same article linked above actually mentions version control systems.

  • $\begingroup$ even if it only has one top-level node? $\endgroup$ – Filip Haglund Dec 26 '14 at 23:04
  • $\begingroup$ @FilipHaglund The situation where there is only one top-level node is a special case. If it were a tree we would say that it is "rooted." I suppose the same term could be applied to directed acyclic graphs. $\endgroup$ – Matt Samuel Dec 26 '14 at 23:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.