Editing Directed acyclic graph (section)

=== Genealogy and version history ===
[[File:EgyptianPtolemies2.jpg|thumb|upright=1.5|Family tree of the [[Ptolemaic dynasty]], with many marriages between [[Consanguinity|close relatives]] causing [[pedigree collapse]].]]
[[Family tree]]s may be seen as directed acyclic graphs, with a vertex for each family member and an edge for each parent-child relationship.<ref>{{citation|journal=Algorithms for Molecular Biology|date=April 2011|volume=6|issue=10|pages=10|title=Haplotypes versus genotypes on pedigrees|first=Bonnie B.|last=Kirkpatrick|doi=10.1186/1748-7188-6-10|pmc=3102622|pmid=21504603 |doi-access=free }}.</ref> Despite the name, these graphs are not necessarily trees because of the possibility of marriages between relatives (so a child has a common ancestor on both the mother's and father's side) causing [[pedigree collapse]].<ref>{{citation
 | last1 = McGuffin | first1 = M. J.
 | last2 = Balakrishnan | first2 = R.
 | contribution = Interactive visualization of genealogical graphs
 | contribution-url = http://profs.etsmtl.ca/mMcGuffin/research/genealogyVis/genealogyVis.pdf
 | doi = 10.1109/INFVIS.2005.1532124
 | pages = 16–23
 | title = IEEE Symposium on Information Visualization (INFOVIS 2005)
 | year = 2005| isbn = 978-0-7803-9464-3
 | s2cid = 15449409
 }}.</ref> The graphs of [[matrilineal]] descent (mother-daughter relationships) and [[patrilineal]] descent (father-son relationships) are trees within this graph. Because no one can become their own ancestor, family trees are acyclic.<ref>{{citation
 | last1 = Bender | first1 = Michael A.
 | last2 = Pemmasani | first2 = Giridhar
 | last3 = Skiena | first3 = Steven
 | last4 = Sumazin | first4 = Pavel
 | contribution = Finding least common ancestors in directed acyclic graphs
 | contribution-url = http://dl.acm.org/citation.cfm?id=365411.365795
 | isbn = 978-0-89871-490-6
 | location = Philadelphia, PA, USA
 | pages = 845–854
 | publisher = Society for Industrial and Applied Mathematics
 | title = Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '01)
 | year = 2001}}.</ref>

The version history of a [[distributed revision control]] system, such as [[Git]], generally has the structure of a directed acyclic graph, in which there is a vertex for each revision and an edge connecting pairs of revisions that were directly derived from each other. These are not trees in general due to merges.<ref>{{citation|title=Architecture and Methods for Flexible Content Management in Peer-to-Peer Systems|first=Udo|last=Bartlang|publisher=Springer|year=2010|isbn=978-3-8348-9645-2|page=59|bibcode=2010aamf.book.....B|url=https://books.google.com/books?id=vXdEAAAAQBAJ&pg=PA59}}.</ref>

In many [[randomization|randomized]] [[algorithm]]s in [[computational geometry]], the algorithm maintains a ''history DAG'' representing the version history of a geometric structure over the course of a sequence of changes to the structure. For instance in a [[Randomized algorithm#Randomized incremental constructions in geometry|randomized incremental]] algorithm for [[Delaunay triangulation]], the triangulation changes by replacing one triangle by three smaller triangles when each point is added, and by "flip" operations that replace pairs of triangles by a different pair of triangles. The history DAG for this algorithm has a vertex for each triangle constructed as part of the algorithm, and edges from each triangle to the two or three other triangles that replace it. This structure allows [[point location]] queries to be answered efficiently: to find the location of a query point {{mvar|q}} in the Delaunay triangulation, follow a path in the history DAG, at each step moving to the replacement triangle that contains {{mvar|q}}. The final triangle reached in this path must be the Delaunay triangle that contains {{mvar|q}}.<ref>{{citation|title=Combinatorial Geometry and Its Algorithmic Applications: The Alcalá Lectures|volume=152|series=Mathematical surveys and monographs|first1=János|last1=Pach|author1-link=János Pach|first2=Micha|last2=Sharir|date=2008 |author2-link=Micha Sharir|publisher=American Mathematical Society|isbn=978-0-8218-7533-9|pages=93–94|url=https://books.google.com/books?id=-fguzNaYoqcC&pg=PA93}}.</ref>