Graphs:   Directed Acyclic G's (DAGs):   Introduction

• special kind of graph
  • D - directed
  • A - acyclic, has no cycles
  • G - graph
    
    
• quite common, appropriate when vertices have a partial order:
  
  
  • if v_i < v_j and v_j < v_k then v_i < v_k, i.e. transitive
  • if v_i < v_j and v_j < v_i then v_i = v_j
    
    
  • BUT there may be incomparable vertices, i.e. neither v_i < v_j, nor v_i > v_j
  • which we can take to mean either order or even simultaneous
    
    

DAG

• A cycle is a sequence of vertices
  
  
• { v_n1, v_n2, v_n3, . . . , v_nm, v_nm+1 = v_n1 }
  
  
• such that   <v_ni, v_ni+1>,   for i = 1 . . m,   are all edges of the graph
  
  
  • (A cycle is simple if the v_n1 to v_nm are all different.)
    
    
• A   DAG   is a directed graph that does not have any cycles.
  
  
  • ( Can check with Warshall's algorithm. )
    
    

DAG

Examples of partial orders, i.e. potential DAGs:

1. sub-tasks of a project and "must finish before"
   
   
   • so, DAGs useful in project management
     
     
2. subjects for a degree and "is a prerequisite for"
   
   
3. people and "is a descendant of"
   
   
4. sets and "is a subset of"
   
   
5. other: you think of some: [___________________________]
   
   

Simplified (!) prerequisites for Computer Science, Monash University, Australia, 2000:

CSE1303 (Comp Sci): CSE1301

CSE2303 (Formal Methods I): CSE1301, MAT1830, MAT1841

CSE2304 (Alg + D S): CSE1303, MAT1830, MAT1841

CSE2302 (Op' Sys'): CSE1303, MAT1830, MAT1841

CSE2305 (OOP): CSE1303, MAT1830, MAT1841

CSE3301 (Project): CSE2304

CSE3305 (Formal Methods II): CSE2303, CSE2304

A Topological-Sort of a DAG

• is a permutation of the vertices
  
  
• v_i1, v_i2, v_i3, . . . , v_in
  
  
• such that for every edge of the DAG, <v_j,v_k>,
  
  
• v_j occurs before v_k in the topological sort
  
  

e.g. gives you an ordering of subjects for taking a degree, one subject at a time, while obeying prerequisite rules.

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 -- [class: run it!]

Critical Path Analysis of a DAG

• a topological sort (above) is a permutation of all vertices
  
  
  • sub-tasks (say) "one at a time"
    
    
• but critical path allows for parallelism in project
  
  
• overall project duration limited by the critical path(s):
  
  
  • a sequence of sub-tasks that
    
    
  • must occur in sequence
    
    
  • of longest duration
    
    
• NB. a vertex-weighted DAG

Critical path analysis of a DAG,   two equivalent strategies:

1. How soon (after start) can a sub_task finish?

• A sub_task with no pre-requisites can start at t=0
  and finish at t = sub_task's duration.
  
  
• A sub_task can start when the last of its pre-req's to finish, has finished.
  
  

2. How late (before dead-line) can a sub_task begin?

• A task that is not a pre-req' can end on the deadline `D'
  and start at   D - sub_task's duration
  
  
• A sub-task can end at the time that it's first "post-req'" to start, starts, . . .

• for each vertex
  • traverse the vertex
    
    

• if this vertex has been visited then
  • already know its end time
    
    
• else if this vertex has no pre-req's then
  • this vertex can start at t = 0 and end at . . .
    
    
• else
  • for each pre-req'
    • traverse the pre-req'
  • this vertex start_time = latest of the pre-req' end times
  • this vertex end time = start_time + duration

DAG

• [lecturer: do some critical path problem; class: take notes]

Graphs:  Directed Acyclic Graphs (DAGs):  Summary

• D - Directed
• A - Acyclic
• G - Graph.
  
  
• Topological sort:
  
  
  • permutation of vertices allowed by edges / arcs / constraints
    
    
• & critical path analysis:
  
  
  • allows possibility of parallelism
    
    
• can both be solved by versions of depth-first traversal of the DAG.