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 partialorder '<'. An edge is drawn from a to b whenever a<b. A partial order '<' satisfies:
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 'brickwork', but the plaster cannot be applied until the walls are there for it to stick to and the roof exists to protect it. Topological SortingA topologicalsort 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 brickwork>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 DemonstrationGenerate 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 depthfirst 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 topsort
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 for
DepthFirst 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 AnalysisCriticalpath analysis is another management problem. The criticalpath of a complex task is the most timeconsuming 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>
2
Example of Critical Path Analysis.
The critical path can be found by a modification of the depthfirst search. 

↑ © L. Allison, www.allisons.org/ll/ (or as otherwise indicated). Created with "vi (Linux)", charset=iso88591, fetched Friday, 12Apr2024 13:55:25 UTC. Free: Linux, Ubuntu operatingsys, OpenOffice officesuite, The GIMP ~photoshop, Firefox webbrowser, FlashBlock flash on/off. 