### Directed Acyclic Graphs

A *directed acyclic graph* (DAG!) is a directed graph that
contains no cycles.
A rooted tree is a special kind of DAG and a DAG is a special kind of
directed graph.
For example,
a DAG may be used to represent common subexpressions
in an optimising compiler.

+ + . . . . . . . . * apply *<---- apply . . . . . . | . . . . . . . . | . | a b f * a b | f | . . ^ v . . | | a b |--<---- Tree DAG expression: a*b+f(a*b)Example of Common Subexpression.

The common subexpression a*b need only be compiled once but its value can be used twice.

A DAG can be used to represent prerequisites in a university course, constraints on operations to be carried out in building construction, in fact an arbitrary partial-order '<'. An edge is drawn from a to b whenever a<b. A partial order '<' satisfies:

- (i) transitivity, a<b and b<c implies a<c
- (ii) non-reflexive, not(a < a)

These condition prevent cycles because
v_{1}<v_{2}<...<v_{n}<v_{1} would imply that v_{1}<v_{1}.
The word 'partial' indicates that not every pair or values
are ordered.
Examples of partial orders are numerical less-than (also a total order)
and 'subset-of';
note that {1,2} is a subset of {1,2,3} but that {1,2} and {2,3}
are *incomparable*,
i.e. there is no order relationship between them.

Constraints for a small building example are given below.

|-->roof--->--->plaster----->| foundation-->frame-->| ^ |-->paint | | |-->windows->| |-->brickwork-->| | |-->doors--->|Simplified Construction Constraints.

Note that no order is imposed between 'roof' and 'brick-work', but the plaster cannot be applied until the walls are there for it to stick to and the roof exists to protect it.

#### Topological Sorting

A *topological-sort* of a DAG is a (total) linear ordering
of the vertices such that v_{i} appears before v_{j}
whenever there is an edge <v_{i},v_{j}> (or whenever v_{i}<v_{j}).

-------> ----------> --------> foundation->frame->roof brick-work->windows plaster doors->paint -----------------> ----------------------> ------------------->Example Topological Sort.

Topological sorting can obviously be useful in the management of construction and manufacturing tasks. It gives an allowable (total) order for carrying out the basic operations one at a time. There may be several different topological sorts for a given DAG, but there must be at least one. Note that there may be reasons to prefer one ordering to another and even to do some tasks simultaneously.

#### Topological Sorting Demonstration

Generate a DAG using the HTML FORM below
and see the topological sort that results.
`|V|` is the number of vertices in the DAG.
The probability, `pr`, determines how
dense the DAG is, on average:

There are two obvious strategies for topological sorting.
One is to find an initial vertex, print it and remove it and repeat
for the reduced DAG.
The other is to find a final vertex, remove and *save* it, repeat
and finally print the vertices saved in *reverse* order.
These strategies are equivalent as can be seen by reversing every
edge and interchanging 'initial' and 'final'.
An initial vertex has no edges arriving at it
and a final vertex has no edges leaving from it.

A final vertex can be found by following a path
from an initial vertex until it is not possible to extend the path.
In fact, a final vertex can be found by following a path
from *any* vertex.
If the final edge is <x,z>, z is a final vertex and can be saved.
For every other edge <x,y>,
the process must be repeated from all such y.
Vertex x then precedes y & z and so on back up to the start vertex.
This is a familiar backtracking process
effected by a depth-first traversal
(see Tree traversal),
but here performed on a graph:

// visited[] is an array of Boolean procedure Depth_First(i :Vertex)// Note similarities if not visited[i] then // with Tree traversals. visited[i] := true; for all edge <i,j> // j must follow i in top-sort Depth_First(j) end for; save(i) // record or process Vertex i end if end Depth_First; for all i :Vertex // initialise visited[]; been nowhere! visited[i] := false end for; for all i :Vertex // try all possible starting points Depth_First(i) end forDepth-First Traversal of a Graph from a given Vertex.

This algorithm will also traverse an arbitrary graph. It should be compared with the various tree traversal algorithms. The exact coding of the algorithm, in particular the selection of 'each edge', depends on the method of implementing the graph.

#### Critical Path Analysis

*Critical-path analysis* is another management problem.
The *critical-path* of a complex task is the most time-consuming sequence
of basic operations that must be carried out sequentially even allowing for
all possible parallelism.
It defines the minimum time that the total task must take
even if no expense is spared with the maximum allowed
amount of activity going on simultaneously.

-->roof------>plaster--------| | 8 ^ 3 | foundations-->frame--| | | 10* 7* | | v -->brickwork--| | 7* | -->paint |--->windows-->| 5* | 5* | | | ---->doors---->| 2Example of Critical Path Analysis.

The critical path can be found by a modification of the depth-first search.