Directed Acyclic Graphs

LA home
Computing
Algorithms
 glossary
 Graphs
  Directed
  DAG
  Undirected
  Canonical
  Isomorphism
  Subg. Iso.
  Stable mrrg.
  DAGs

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 v1<v2<...<vn<v1 would imply that v1<v1. 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 vi appears before vj whenever there is an edge <vi,vj> (or whenever vi<vj).



                 ------->          ---------->       -------->
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:

L
.
A
l
l
i
s
o
n
|V|=[  ] pr=[  ]
G=

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 for

Depth-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---->|
                                          2

Example of Critical Path Analysis.

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

www:


© L. Allison   http://www.allisons.org/ll/   (or as otherwise indicated),
Created with "vi (Linux or Solaris)",  charset=iso-8859-1,  fetched Thursday, 30-Oct-2014 23:56:58 AEDT.

free: Linux, Ubuntu operating-sys, OpenOffice office-suite, The GIMP ~photoshop,
Firefox web-browser, FlashBlock flash on/off.