Suppose that you need to perform many tasks, but some of them cannot begin until certain others are completed (you have to wake up before you can get out of bed; you have to be out of bed, but not yet dressed, to take a shower; and so on). The question then is, what is a valid order in which to perform the tasks?

Such constraints are conveniently represented by a directed graph in which each task is
a node, and there is an edge from *linearize* (or *topologically sort*) it, to order the vertices one after
the other in such a way that each edge goes from an earlier vertex to a later vertex, so that
all precedence constraints are satisfied. In the following figure, for instance, one valid ordering is

What types of dags can be linearized? Simple: *All of them*. And once again depth-first search
tells us exactly how to do it: simply perform tasks in decreasing order of their

**Property** In a dag, every edge leads to a vertex with a lower

This gives us a linear-time algorithm for ordering the nodes of a dag. And, together with our earlier observations, it tells us that three rather different-sounding properties—acyclicity, linearizability, and the absence of back edges during a depth-first search—are in fact one and the same thing.

Since a dag is linearized by decreasing

**Property** Every dag has at least one source and at least one sink.

The guaranteed existence of a source suggests an alternative approach to linearization:

- Find a source, output it, and delete it from the graph.
- Repeat until the graph is empty.

Source: Algorithms by Dasgupta, Papadimitriou, Vazirani. McGraw-Hill. 2006.