Editing Directed acyclic graph (section)

=== Scheduling ===
Directed acyclic graph representations of partial orderings have many applications in [[Schedule|scheduling]] for systems of tasks with ordering constraints.<ref>{{harvtxt|Skiena|2009}}, p. 469.</ref>
An important class of problems of this type concern collections of objects that need to be updated, such as the cells of a [[spreadsheet]] after one of the cells has been changed, or the [[object file]]s of a piece of computer software after its [[source code]] has been changed.
In this context, a [[dependency graph]] is a graph that has a vertex for each object to be updated, and an edge connecting two objects whenever one of them needs to be updated earlier than the other. A cycle in this graph is called a [[circular dependency]], and is generally not allowed, because there would be no way to consistently schedule the tasks involved in the cycle.
Dependency graphs without circular dependencies form DAGs.<ref>{{citation | last1=Al-Mutawa | first1=H. A. | last2=Dietrich | first2=J. | last3=Marsland | first3=S. | last4=McCartin | first4=C. | contribution=On the shape of circular dependencies in Java programs | doi=10.1109/ASWEC.2014.15 | pages=48–57 | publisher=IEEE | title=23rd Australian Software Engineering Conference | year=2014| isbn=978-1-4799-3149-1 | s2cid=17570052 }}.</ref>

For instance, when one cell of a [[spreadsheet]] changes, it is necessary to recalculate the values of other cells that depend directly or indirectly on the changed cell. For this problem, the tasks to be scheduled are the recalculations of the values of individual cells of the spreadsheet. Dependencies arise when an expression in one cell uses a value from another cell. In such a case, the value that is used must be recalculated earlier than the expression that uses it. Topologically ordering the dependency graph, and using this topological order to schedule the cell updates, allows the whole spreadsheet to be updated with only a single evaluation per cell.<ref name="hgt1181">{{citation |title=Handbook of Graph Theory |first1=Jonathan L. |last1=Gross |first2=Jay |last2=Yellen |first3=Ping |last3=Zhang  | author3-link = Ping Zhang (graph theorist)|edition=2nd |publisher=CRC Press |year=2013 |isbn=978-1-4398-8018-0 |page=1181 |url=https://books.google.com/books?id=cntcAgAAQBAJ&pg=PA1181}}.</ref> Similar problems of task ordering arise in [[makefile]]s for program compilation<ref name="hgt1181" /> and [[instruction scheduling]] for low-level computer program optimization.<ref>{{citation |title=The Compiler Design Handbook: Optimizations and Machine Code Generation |first1=Y. N. |last1=Srikant |first2=Priti |last2=Shankar |edition=2nd |publisher=CRC Press|year=2007 |isbn=978-1-4200-4383-9 |pages=19–39 |url=https://books.google.com/books?id=1kqAv-uDEPEC&pg=SA19-PA39}}.</ref>

[[File:Pert chart colored.svg|thumb|PERT chart for a project with five milestones (labeled 10–50) and six tasks (labeled A–F). There are two critical paths, ADF and BC.]]
A somewhat different DAG-based formulation of scheduling constraints is used by the [[program evaluation and review technique]] (PERT), a method for management of large human projects that was one of the first applications of DAGs. In this method, the vertices of a DAG represent [[Milestone (project management)|milestones]] of a project rather than specific tasks to be performed. Instead, a task or activity is represented by an edge of a DAG, connecting two milestones that mark the beginning and completion of the task. Each such edge is labeled with an estimate for the amount of time that it will take a team of workers to perform the task. The [[Longest path problem|longest path]] in this DAG represents the [[Critical path method|critical path]] of the project, the one that controls the total time for the project. Individual milestones can be scheduled according to the lengths of the longest paths ending at their vertices.<ref>{{citation |title=What Every Engineer Should Know About Decision Making Under Uncertainty |first=John X. |last=Wang |publisher=CRC Press |year=2002 |isbn=978-0-8247-4373-4 |page=160 |url=https://books.google.com/books?id=C3yKML0dUVIC&pg=PA160}}.</ref>