[Subject home], [FAQ], [progress],   Bib', Alg's,  C , Java - L.A., Sunday, 28-Nov-2021 03:56:43 AEDT
Instructions: Topics discussed in these lecture notes are examinable unless otherwise indicated. You need to follow instructions, take more notes & draw diagrams especially as [indicated] or as done in lectures, work through examples, and do extra reading. Hyper-links not in [square brackets] are mainly for revision, for further reading, and for lecturers of the subject.

## 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 vi < vj and vj < vk then vi < vk, i.e. transitive
• if vi < vj and vj < vi then vi = vj

• BUT there may be incomparable vertices, i.e. neither vi < vj, nor vi > vj
• which we can take to mean either order or even simultaneous

DAG

• A cycle is a sequence of vertices

• { vn1, vn2, vn3, . . . , vnm, vnm+1 = vn1 }

• such that   <vni, vni+1>,   for i = 1 . . m,   are all edges of the graph

• (A cycle is simple if the vn1 to vnm are all different.)

• A   DAG   is a directed graph that does not have any cycles.

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: [___________________________]

DAG example:

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
[lecturer: draw the graph; class: take notes!]   Do NOT take this as course advice!

### A Topological-Sort of a DAG

• is a permutation of the vertices

• vi1, vi2, vi3, . . . , vin

• such that for every edge of the DAG, <vj,vk>,

• vj occurs before vk 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.

[lecturer: run the demo'; class: draw DAGs, take notes!]
```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.

• 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, . . .
Critical path analysis of a DAG:
• for each vertex
• traverse the vertex

traverse 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
i.e. "depth"- (pre-req'-) first traversal.   Throughout, record the lastest end time seen.
[lecturer: do examples; class: draw diagrams, take notes!]

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.
Revise sub-string searching and prepare suffix trees.
© L.Allison, Sunday, 28-Nov-2021 03:56:43 AEDT users.monash.edu.au/~lloyd/tilde/CSC2/CSE2304/Notes/18DAG.shtml
Computer Science, Software Engineering, Science (Computer Science).