Program Analysis
Graphs Traversal and Topological Sort
David Weir (U of Sussex) Program Analysis Term 1, 2017 140 / 606
Traversing Graphs
Goal: visit each node in a graph in a systematic way
Non trivial because:
Non-linear
Non-hierarchical
David Weir (U of Sussex) Program Analysis Term 1, 2017 141 / 606
Breadth-first Search
Exploring one layer at a time
Nodes are visited in order of increasing distance from s
First visit nodes at distance 1 from s
Then visit nodes at distance 2 from s
Continue until all nodes have been visited.
How can this be achieved?
Put nodes that have been discovered but not yet explored in a
queue
Keep a record of which nodes have been discovered
Construct a search tree that records search
David Weir (U of Sussex) Program Analysis Term 1, 2017 142 / 606
Breadth-first Search
BFS(G, s) :
let Q be a queue containing just the node s
let discovered(s) = true
let discovered(v) = false for all v ∈ V − {s}
let T = (V , {})
while Q is not empty
remove v from the front of Q
for each edge {v ,w} in E where not discovered(w)
let discovered(w) = true
add w to the back of Q
add edge {v ,w} to edges in T
David Weir (U of Sussex) Program Analysis Term 1, 2017 143 / 606
Illustration of BFS
v1v2
v3v4
v5
v6
v7v8
Run BFS starting at v7
David Weir (U of Sussex) Program Analysis Term 1, 2017 144 / 606
Illustration of BFS
v1v2
v3v4
v5
v6
v7v8
Initialize Q
David Weir (U of Sussex) Program Analysis Term 1, 2017 144 / 606
Illustration of BFS
v1v2
v3v4
v5
v6
v7v8
Q = [v7]
Let discovered(v7) = true
David Weir (U of Sussex) Program Analysis Term 1, 2017 144 / 606
Illustration of BFS
v1v2
v3v4
v5
v6
v7v8
Q = [v7]
v7
Remove v7 from front of Q
David Weir (U of Sussex) Program Analysis Term 1, 2017 144 / 606
Illustration of BFS
v1v2
v3v4
v5
v6
v7v8 v7v7
Q = [ ]
Consider edge {v7, v4} since v4 not yet discovered
David Weir (U of Sussex) Program Analysis Term 1, 2017 144 / 606
Illustration of BFS
v1v2
v3v4
v5
v6
v7v8 v7v7
Q = [ ]
Let discovered(v4) = true, add {v7, v4} to T and v4 to Q
David Weir (U of Sussex) Program Analysis Term 1, 2017 144 / 606
Illustration of BFS
v1v2
v3v4
v5
v6
v7v8 v7v7v4
Q = [v4]
Consider edge {v7, v5} since v5 not yet discovered
David Weir (U of Sussex) Program Analysis Term 1, 2017 144 / 606
Illustration of BFS
v1v2
v3v4
v5
v6
v7v8 v7v7v4
Q = [v4]
Let discovered(v5) = true, add {v7, v5} to T and v5 to Q
David Weir (U of Sussex) Program Analysis Term 1, 2017 144 / 606
Illustration of BFS
v1v2
v3v4
v5
v6
v7v8 v7v7v4
v5
Q = [v4, v5]
No more edges from v7
David Weir (U of Sussex) Program Analysis Term 1, 2017 144 / 606
Illustration of BFS
v1v2
v3v4
v5
v6
v7v8 v7v4
v5
Q = [v4, v5]
Remove v4 from front of Q
David Weir (U of Sussex) Program Analysis Term 1, 2017 144 / 606
Illustration of BFS
v1v2
v3v4
v5
v6
v7v8 v7v4
v5
v4
Q = [v5]
Consider edge {v4, v6} because v6 not yet discovered
David Weir (U of Sussex) Program Analysis Term 1, 2017 144 / 606
Illustration of BFS
v1v2
v3v4
v5
v6
v7v8 v7v4
v5
v4
Q = [v5]
Let discovered(v6) = true, add {v4, v6} to T and v6 to Q
David Weir (U of Sussex) Program Analysis Term 1, 2017 144 / 606
Illustration of BFS
v1v2
v3v4
v5
v6
v7v8 v7v4
v5
v4
v6
Q = [v5, v6]
Don’t consider {v4, v7} because v7 already discovered
David Weir (U of Sussex) Program Analysis Term 1, 2017 144 / 606
Illustration of BFS
v1v2
v3v4
v5
v6
v7v8 v7v4
v5
v4
v6
Q = [v5, v6]
No more edges from v4
David Weir (U of Sussex) Program Analysis Term 1, 2017 144 / 606
Illustration of BFS
v1v2
v3v4
v5
v6
v7v8 v7v4
v5
v6
Q = [v5, v6]
Remove v5 from front of Q
David Weir (U of Sussex) Program Analysis Term 1, 2017 144 / 606
Illustration of BFS
v1v2
v3v4
v5
v6
v7v8 v7v4
v5
v6
v5
Q = [v6]
Consider edge {v5, v2} because v2 not yet discovered
David Weir (U of Sussex) Program Analysis Term 1, 2017 144 / 606
Illustration of BFS
v1v2
v3v4
v5
v6
v7v8 v7v4
v5
v6
v5
Q = [v6]
Let discovered(v2) = true, add {v5, v2} to T and v2 to Q
David Weir (U of Sussex) Program Analysis Term 1, 2017 144 / 606
Illustration of BFS
v1v2
v3v4
v5
v6
v7v8 v7v4
v5
v6
v5 v2
Q = [v6, v2]
Consider {v5, v8} because v8 not yet discovered
David Weir (U of Sussex) Program Analysis Term 1, 2017 144 / 606
Illustration of BFS
v1v2
v3v4
v5
v6
v7v8 v7v4
v5
v6
v5 v2
Q = [v6, v2]
Let discovered(v8) = true, add {v5, v8} to T and v8 to Q
David Weir (U of Sussex) Program Analysis Term 1, 2017 144 / 606
Illustration of BFS
v1v2
v3v4
v5
v6
v7v8 v7v4
v5
v6
v5 v2
v8
Q = [v6, v2, v8]
Don’t consider {v5, v7} because v7 already discovered
David Weir (U of Sussex) Program Analysis Term 1, 2017 144 / 606
Illustration of BFS
v1v2
v3v4
v5
v6
v7v8 v7v4
v5
v6
v5 v2
v8
Q = [v6, v2, v8]
No more edges from v5
David Weir (U of Sussex) Program Analysis Term 1, 2017 144 / 606
Illustration of BFS
v1v2
v3v4
v5
v6
v7v8 v7v4
v5
v6
v2
v8
Q = [v6, v2, v8]
Remove v6 from front of Q
David Weir (U of Sussex) Program Analysis Term 1, 2017 144 / 606
Illustration of BFS
v1v2
v3v4
v5
v6
v7v8 v7v4
v5
v6
v2
v8
v6
Q = [v2, v8]
Consider edge {v6, v3} because v3 not yet discovered
David Weir (U of Sussex) Program Analysis Term 1, 2017 144 / 606
Illustration of BFS
v1v2
v3v4
v5
v6
v7v8 v7v4
v5
v6
v2
v8
v6
Q = [v2, v8]
Let discovered(v3) = true, add {v6, v3} to T and v3 to Q
David Weir (U of Sussex) Program Analysis Term 1, 2017 144 / 606
Illustration of BFS
v1v2
v3v4
v5
v6
v7v8 v7v4
v5
v6
v2
v8
v6
v3
Q = [v2, v8, v3]
Don’t consider {v6, v4} because v4 already discovered
David Weir (U of Sussex) Program Analysis Term 1, 2017 144 / 606
Illustration of BFS
v1v2
v3v4
v5
v6
v7v8 v7v4
v5
v6
v2
v8
v6
v3
Q = [v2, v8, v3]
Don’t consider {v6, v8} because v8 already discovered
David Weir (U of Sussex) Program Analysis Term 1, 2017 144 / 606
Illustration of BFS
v1v2
v3v4
v5
v6
v7v8 v7v4
v5
v6
v2
v8
v6
v3
Q = [v2, v8, v3]
No more edges from v6
David Weir (U of Sussex) Program Analysis Term 1, 2017 144 / 606
Illustration of BFS
v1v2
v3v4
v5
v6
v7v8 v7v4
v5
v6
v2
v8 v3
Q = [v2, v8, v3]
Remove v2 from front of Q
David Weir (U of Sussex) Program Analysis Term 1, 2017 144 / 606
Illustration of BFS
v1v2
v3v4
v5
v6
v7v8 v7v4
v5
v6
v2
v8 v3
v2
Q = [v8, v3]
Consider edge {v2, v1} because v1 not yet discovered
David Weir (U of Sussex) Program Analysis Term 1, 2017 144 / 606
Illustration of BFS
v1v2
v3v4
v5
v6
v7v8 v7v4
v5
v6
v2
v8 v3
v2
Q = [v8, v3]
Let discovered(v1) = true, add {v2, v1} to T and v1 to Q
David Weir (U of Sussex) Program Analysis Term 1, 2017 144 / 606
Illustration of BFS
v1v2
v3v4
v5
v6
v7v8 v7v4
v5
v6
v2
v8 v3
v2 v1
Q = [v8, v3, v1]
Don’t consider {v2, v3} because v3 already discovered
David Weir (U of Sussex) Program Analysis Term 1, 2017 144 / 606
Illustration of BFS
v1v2
v3v4
v5
v6
v7v8 v7v4
v5
v6
v2
v8 v3
v2 v1
Q = [v8, v3, v1]
Don’t consider {v2, v5} because v5 already discovered
David Weir (U of Sussex) Program Analysis Term 1, 2017 144 / 606
Illustration of BFS
v1v2
v3v4
v5
v6
v7v8 v7v4
v5
v6
v2
v8 v3
v2 v1
Q = [v8, v3, v1]
No more edges from v2
David Weir (U of Sussex) Program Analysis Term 1, 2017 144 / 606
Illustration of BFS
v1v2
v3v4
v5
v6
v7v8 v7v4
v5
v6
v2
v8 v3
v1
Q = [v8, v3, v1]
Remove v8 from front of Q
David Weir (U of Sussex) Program Analysis Term 1, 2017 144 / 606
Illustration of BFS
v1v2
v3v4
v5
v6
v7v8 v7v4
v5
v6
v2
v8 v3
v1
v8
Q = [v3, v1]
Don’t consider {v8, v5} because v5 already discovered
David Weir (U of Sussex) Program Analysis Term 1, 2017 144 / 606
Illustration of BFS
v1v2
v3v4
v5
v6
v7v8 v7v4
v5
v6
v2
v8 v3
v1
v8
Q = [v3, v1]
Don’t consider {v8, v6} because v6 already discovered
David Weir (U of Sussex) Program Analysis Term 1, 2017 144 / 606
Illustration of BFS
v1v2
v3v4
v5
v6
v7v8 v7v4
v5
v6
v2
v8 v3
v1
v8
Q = [v3, v1]
No more edges from v8
David Weir (U of Sussex) Program Analysis Term 1, 2017 144 / 606
Illustration of BFS
v1v2
v3v4
v5
v6
v7v8 v7v4
v5
v6
v2
v8 v3
v1
Q = [v3, v1]
Remove v3 from front of Q
David Weir (U of Sussex) Program Analysis Term 1, 2017 144 / 606
Illustration of BFS
v1v2
v3v4
v5
v6
v7v8 v7v4
v5
v6
v2
v8 v3
v1
v3
Q = [v1]
Don’t consider {v3, v1} because v1 already discovered
David Weir (U of Sussex) Program Analysis Term 1, 2017 144 / 606
Illustration of BFS
v1v2
v3v4
v5
v6
v7v8 v7v4
v5
v6
v2
v8 v3
v1
v3
Q = [v1]
Don’t consider {v3, v2} because v2 already discovered
David Weir (U of Sussex) Program Analysis Term 1, 2017 144 / 606
Illustration of BFS
v1v2
v3v4
v5
v6
v7v8 v7v4
v5
v6
v2
v8 v3
v1
v3
Q = [v1]
No more edges from v3
David Weir (U of Sussex) Program Analysis Term 1, 2017 144 / 606
Illustration of BFS
v1v2
v3v4
v5
v6
v7v8 v7v4
v5
v6
v2
v8 v3
v1
Q = [v1]
Remove v1 from front of Q
David Weir (U of Sussex) Program Analysis Term 1, 2017 144 / 606
Illustration of BFS
v1v2
v3v4
v5
v6
v7v8 v7v4
v5
v6
v2
v8 v3
v1v1
Q = [ ]
Don’t consider {v1, v2} because v2 already discovered
David Weir (U of Sussex) Program Analysis Term 1, 2017 144 / 606
Illustration of BFS
v1v2
v3v4
v5
v6
v7v8 v7v4
v5
v6
v2
v8 v3
v1v1
Q = [ ]
Don’t consider {v1, v3} because v3 already discovered
David Weir (U of Sussex) Program Analysis Term 1, 2017 144 / 606
Illustration of BFS
v1v2
v3v4
v5
v6
v7v8 v7v4
v5
v6
v2
v8 v3
v1v1
Q = [ ]
No more edges from v1
David Weir (U of Sussex) Program Analysis Term 1, 2017 144 / 606
Illustration of BFS
v1v2
v3v4
v5
v6
v7v8 v7v4
v5
v6
v2
v8 v3
v1
Q is empty so traversal complete
David Weir (U of Sussex) Program Analysis Term 1, 2017 144 / 606
Illustration of BFS
v7v4
v5
v6
v2
v8 v3
v1
Here is the breadth first search tree for this run
David Weir (U of Sussex) Program Analysis Term 1, 2017 144 / 606
Illustration of BFS
Same tree, but arranged in more usual way
v1
v2
v3
v4 v5
v6
v7
v8
David Weir (U of Sussex) Program Analysis Term 1, 2017 144 / 606
Example for You
Draw the breadth-first search tree
Consider vertices in order of subscript
Begin traversal at v1
v1
v2
v3
v4
David Weir (U of Sussex) Program Analysis Term 1, 2017 145 / 606
Example for You
Draw the breadth-first search tree
Consider vertices in order of subscript
Begin traversal at v1
v1
v2
v3
v4
v1
v2
v3
v4
David Weir (U of Sussex) Program Analysis Term 1, 2017 145 / 606
Breadth-first Search
BFS(G, s) :
let Q be a queue containing just the node s
let discovered(s) = true
let discovered(v) = false for all v ∈ V − {s}
let T = (V , {})
while Q is not empty
remove v from the front of Q
for each edge {v ,w} in E where not discovered(w)
let discovered(w) = true
add w to the back of Q
add edge {v ,w} to edges in T
David Weir (U of Sussex) Program Analysis Term 1, 2017 146 / 606
Components of Graphs
v1
v2
v3
v4
v5
v6
v7
Is this one or two graphs?
David Weir (U of Sussex) Program Analysis Term 1, 2017 147 / 606
Components of Graphs
v1
v2
v3
v4
v5
v6
v7
This is one of the components
David Weir (U of Sussex) Program Analysis Term 1, 2017 147 / 606
Components of Graphs
v1
v2
v3
v4
v5
v6
v7
And this is the other components
David Weir (U of Sussex) Program Analysis Term 1, 2017 147 / 606
Components of Graphs
v1
v2
v3
v4
v5
v6
v7
But remember, its all one graph
David Weir (U of Sussex) Program Analysis Term 1, 2017 147 / 606
Components of Graphs (cont.)
Definition of a component of a graph G = (V ,E)
A subset of the vertices in G and all associated edges from G
Must be connected
— path between any pair of vertices
Must be maximal
— cannot be enlarged and remain connected
David Weir (U of Sussex) Program Analysis Term 1, 2017 148 / 606
BFS and Multiple Component Graphs
v1
v2
v3
v4
v5
v6
v7
Question: Suppose BFS run on this graph starting at v3?
David Weir (U of Sussex) Program Analysis Term 1, 2017 149 / 606
Components of Graphs (cont.)
v1
v2
v3
v4
v5
v6
v7
Answer: BFS would find only nodes in the component containing v3
David Weir (U of Sussex) Program Analysis Term 1, 2017 150 / 606
Revised BFS Algorithm
BFS(G) :
let discovered(v) = false for all v ∈ V
let T = (V , {})
for each v ∈ V
if not discovered(v)
BFS(G, v)
David Weir (U of Sussex) Program Analysis Term 1, 2017 151 / 606
Revised BFS Algorithm (cont.)
BFS(G, s) :
let Q be a queue containing just the node s
let discovered(s) = true
while Q is not empty
remove v from the front of Q
for each edge {v ,w} in E where not discovered(w)
let discovered(w) = true
add w to the back of Q
add edge {v ,w} to edges in T
David Weir (U of Sussex) Program Analysis Term 1, 2017 152 / 606
BFS Forest
T can consist of more than one tree
One tree in T for each component of G
T is actually Breadth-First Search Forest
Number of edges in T will be n − k
— where G contains k components
David Weir (U of Sussex) Program Analysis Term 1, 2017 153 / 606
Running Time of BFS
What is a good measure of progress?
Number of vertices whose edges have been considered
Increases by 1 on each iteration of the while loop
This means that there n iterations of the loop
How much time spent on each iteration?
Depends on number of edges to be considered
David Weir (U of Sussex) Program Analysis Term 1, 2017 154 / 606
Running Time of BFS (cont.)
Number of steps within loop is Θ(max(1,outdegree(v)))
outdegree(v) is number of edges from v to some other vertex w
We know that in total there are m edges to consider
Total across all iterations of loop:
∑
v∈V
max(1,outdegree(v)) = Θ(n + m)
David Weir (U of Sussex) Program Analysis Term 1, 2017 155 / 606
Depth-first Search
A different strategy for systematic exploration of a graph.
Uses a stack to hold discovered nodes
Record nodes as explored once popped from stack
Only explore nodes taken from stack that haven’t already been
explored
Record edges in search tree by remembering the latest parent of
each node
Parent of a node can change up to the point it is explored
David Weir (U of Sussex) Program Analysis Term 1, 2017 156 / 606
Depth-first Search
DFS(G, s) :
let S be a stack containing just the node s
let explored(v) = false for all v ∈ V
while S is not empty
pop v from the top of S
if not explored(v) then
for each edge {v ,w} in E where not explored(w)
push w onto S
let parent(w) = v
let explored(v) = true
David Weir (U of Sussex) Program Analysis Term 1, 2017 157 / 606
Illustration of DFS
v1v2
v3v4
v5
v6
v7v8
Run DFS starting at v7
David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606
Illustration of DFS
v1v2
v3v4
v5
v6
v7v8
Initialize S
David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606
Illustration of DFS
v1v2
v3v4
v5
v6
v7v8
S = [v7]
Pop v7 from top of S
David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606
Illustration of DFS
v1v2
v3v4
v5
v6
v7v8
S = [ ]
v7 not yet explored so let’s explore it
David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606
Illustration of DFS
v1v2
v3v4
v5
v6
v7v8
S = [ ]
v7
Consider edge {v7, v4} since v4 not yet explored
David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606
Illustration of DFS
v1v2
v3v4
v5
v6
v7v8
S = [ ]
v7
Push v4 onto S and let parent(v4) = v7
David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606
Illustration of DFS
v1v2
v3v4
v5
v6
v7v8 v7
S = [v4]
Consider edge {v7, v5} since v5 not yet explored
David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606
Illustration of DFS
v1v2
v3v4
v5
v6
v7v8 v7
S = [v4]
Push v5 onto S and let parent(v5) = v7
David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606
Illustration of DFS
v1v2
v3v4
v5
v6
v7v8 v7
S = [v5, v4]
No more edges from v7
David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606
Illustration of DFS
v1v2
v3v4
v5
v6
v7v8 v7
S = [v5, v4]
Let explored(v7) = true
David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606
Illustration of DFS
v1v2
v3v4
v5
v6
v7v8
S = [v5, v4]
v7
Pop v5 from top of S
David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606
Illustration of DFS
v1v2
v3v4
v5
v6
v7v8 v7
S = [v4]
v5 not yet explored so let’s explore it
David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606
Illustration of DFS
v1v2
v3v4
v5
v6
v7v8 v7
S = [v4]
v5
Consider edge {v5, v2} since v2 not yet explored
David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606
Illustration of DFS
v1v2
v3v4
v5
v6
v7v8 v7
S = [v4]
v5
Push v2 onto S and let parent(v2) = v5
David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606
Illustration of DFS
v1v2
v3v4
v5
v6
v7v8 v7
v5
S = [v2, v4]
Consider {v5, v8} since v8 not yet explored
David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606
Illustration of DFS
v1v2
v3v4
v5
v6
v7v8 v7
v5
S = [v2, v4]
Push v8 onto S and let parent(v8) = v5
David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606
Illustration of DFS
v1v2
v3v4
v5
v6
v7v8 v7
v5
S = [v8, v2, v4]
Don’t consider {v5, v7} because v7 already explored
David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606
Illustration of DFS
v1v2
v3v4
v5
v6
v7v8 v7
v5
S = [v8, v2, v4]
No more edges from v5
David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606
Illustration of DFS
v1v2
v3v4
v5
v6
v7v8 v7
v5
S = [v8, v2, v4]
Let explored(v5) = true
David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606
Illustration of DFS
v1v2
v3v4
v5
v6
v7v8 v7
S = [v8, v2, v4]
v5
Pop v8 from top of S
David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606
Illustration of DFS
v1v2
v3v4
v5
v6
v7v8 v7
v5
S = [v2, v4]
v8 not yet explored so let’s explore it
David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606
Illustration of DFS
v1v2
v3v4
v5
v6
v7v8 v7
v5
S = [v2, v4]
v8
Don’t consider {v8, v5} because v5 already explored
David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606
Illustration of DFS
v1v2
v3v4
v5
v6
v7v8 v7
v5
S = [v2, v4]
v8
Consider edge {v8, v6} since v6 not yet explored
David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606
Illustration of DFS
v1v2
v3v4
v5
v6
v7v8 v7
v5
S = [v2, v4]
v8
Push v6 onto S and let parent(v6) = v8
David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606
Illustration of DFS
v1v2
v3v4
v5
v6
v7v8 v7
v5
v8
S = [v6, v2, v4]
No more edges from v8
David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606
Illustration of DFS
v1v2
v3v4
v5
v6
v7v8 v7
v5
v8
S = [v6, v2, v4]
Let explored(v8) = true
David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606
Illustration of DFS
v1v2
v3v4
v5
v6
v7v8 v7
v5
S = [v6, v2, v4]
v8
Pop v6 from top of S
David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606
Illustration of DFS
v1v2
v3v4
v5
v6
v7v8 v7
v5
v8
S = [v2, v4]
v6 not yet explored so let’s explore it
David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606
Illustration of DFS
v1v2
v3v4
v5
v6
v7v8 v7
v5
v8
S = [v2, v4]
v6
Consider edge {v6, v4} since v4 not yet explored
David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606
Illustration of DFS
v1v2
v3v4
v5
v6
v7v8 v7
v5
v8
S = [v2, v4]
v6
Push v4 onto S and let parent(v4) = v6
David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606
Illustration of DFS
v1v2
v3v4
v5
v6
v7v8 v7
v5
v8
v6
S = [v4, v2, v4]
Don’t consider {v6, v8} because v8 already explored
David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606
Illustration of DFS
v1v2
v3v4
v5
v6
v7v8 v7
v5
v8
v6
S = [v4, v2, v4]
No more edges from v6
David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606
Illustration of DFS
v1v2
v3v4
v5
v6
v7v8 v7
v5
v8
v6
S = [v4, v2, v4]
Let explored(v6) = true
David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606
Illustration of DFS
v1v2
v3v4
v5
v6
v7v8 v7
v5
v8
S = [v4, v2, v4]
v6
Pop v4 from top of S
David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606
Illustration of DFS
v1v2
v3v4
v5
v6
v7v8 v7
v5
v8
v6
S = [v2, v4]
v4 not yet explored so let’s explore it
David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606
Illustration of DFS
v1v2
v3v4
v5
v6
v7v8 v7
v5
v8
v6
S = [v2, v4]
v4
Don’t consider {v4, v6} because v6 already explored
David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606
Illustration of DFS
v1v2
v3v4
v5
v6
v7v8 v7
v5
v8
v6
S = [v2, v4]
v4
Don’t consider {v4, v7} because v7 already explored
David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606
Illustration of DFS
v1v2
v3v4
v5
v6
v7v8 v7
v5
v8
v6
S = [v2, v4]
v4
No more edges from v4
David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606
Illustration of DFS
v1v2
v3v4
v5
v6
v7v8 v7
v5
v8
v6
S = [v2, v4]
v4
Let explored(v4) = true
David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606
Illustration of DFS
v1v2
v3v4
v5
v6
v7v8 v7
v5
v8
v6
S = [v2, v4]
v4
Pop v2 from top of S
David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606
Illustration of DFS
v1v2
v3v4
v5
v6
v7v8 v7
v5
v8
v6
v4
S = [v4]
v2 not yet explored so let’s explore it
David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606
Illustration of DFS
v1v2
v3v4
v5
v6
v7v8 v7
v5
v8
v6
v4
S = [v4]
v2
Consider edge {v2, v1} since v1 not yet explored
David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606
Illustration of DFS
v1v2
v3v4
v5
v6
v7v8 v7
v5
v8
v6
v4
S = [v4]
v2
Push v1 onto S and let parent(v1) = v2
David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606
Illustration of DFS
v1v2
v3v4
v5
v6
v7v8 v7
v5
v8
v6
v4
v2
S = [v1, v4]
Consider edge {v2, v3} since v3 not yet explored
David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606
Illustration of DFS
v1v2
v3v4
v5
v6
v7v8 v7
v5
v8
v6
v4
v2
S = [v1, v4]
Push v3 onto S and let parent(v3) = v2
David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606
Illustration of DFS
v1v2
v3v4
v5
v6
v7v8 v7
v5
v8
v6
v4
v2
S = [v3, v1, v4]
Don’t consider {v2, v5} because v5 already explored
David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606
Illustration of DFS
v1v2
v3v4
v5
v6
v7v8 v7
v5
v8
v6
v4
v2
S = [v3, v1, v4]
No more edges from v2
David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606
Illustration of DFS
v1v2
v3v4
v5
v6
v7v8 v7
v5
v8
v6
v4
v2
S = [v3, v1, v4]
Let explored(v2) = true
David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606
Illustration of DFS
v1v2
v3v4
v5
v6
v7v8 v7
v5
v8
v6
v4
S = [v3, v1, v4]
v2
Pop v3 from top of S
David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606
Illustration of DFS
v1v2
v3v4
v5
v6
v7v8 v7
v5
v8
v6
v4
v2
S = [v1, v4]
v3 not yet explored so let’s explore it
David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606
Illustration of DFS
v1v2
v3v4
v5
v6
v7v8 v7
v5
v8
v6
v4
v2
S = [v1, v4]
v3
Consider edge {v3, v1} since v1 not yet explored
David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606
Illustration of DFS
v1v2
v3v4
v5
v6
v7v8 v7
v5
v8
v6
v4
v2
S = [v1, v4]
v3
Push v1 onto S and let parent(v1) = v3
David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606
Illustration of DFS
v1v2
v3v4
v5
v6
v7v8 v7
v5
v8
v6
v4
v2
v3
S = [v1, v1, v4]
Don’t consider {v3, v2} because v2 already explored
David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606
Illustration of DFS
v1v2
v3v4
v5
v6
v7v8 v7
v5
v8
v6
v4
v2
v3
S = [v1, v1, v4]
No more edges from v3
David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606
Illustration of DFS
v1v2
v3v4
v5
v6
v7v8 v7
v5
v8
v6
v4
v2
S = [v1, v1, v4]
Let explored(v3) = true
David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606
Illustration of DFS
v1v2
v3v4
v5
v6
v7v8 v7
v5
v8
v6
v4
v2
S = [v1, v1, v4]
v3
Pop v1 from top of S
David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606
Illustration of DFS
v1v2
v3v4
v5
v6
v7v8 v7
v5
v8
v6
v4
v2
v3
S = [v1, v4]
v1 not yet explored so let’s explore it
David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606
Illustration of DFS
v1v2
v3v4
v5
v6
v7v8 v7
v5
v8
v6
v4
v2
v3
S = [v1, v4]
v1
Don’t consider {v1, v2} because v2 already explored
David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606
Illustration of DFS
v1v2
v3v4
v5
v6
v7v8 v7
v5
v8
v6
v4
v2
v3
S = [v1, v4]
v1
Don’t consider {v1, v3} because v3 already explored
David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606
Illustration of DFS
v1v2
v3v4
v5
v6
v7v8 v7
v5
v8
v6
v4
v2
v3
S = [v1, v4]
v1
No more edges from v1
David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606
Illustration of DFS
v1v2
v3v4
v5
v6
v7v8 v7
v5
v8
v6
v4
v2
v3
S = [v1, v4]
v1
Let explored(v1) = true
David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606
Illustration of DFS
v1v2
v3v4
v5
v6
v7v8 v7
v5
v8
v6
v4
v2
v3
S = [v1, v4]
v1
Pop v1 from top of S
David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606
Illustration of DFS
v1v2
v3v4
v5
v6
v7v8 v7
v5
v8
v6
v4
v2
v3
v1
S = [v4]
v1 already explored so no need to consider it
David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606
Illustration of DFS
v1v2
v3v4
v5
v6
v7v8 v7
v5
v8
v6
v4
v2
v3
v1
S = [v4]
Pop v4 from top of S
David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606
Illustration of DFS
v1v2
v3v4
v5
v6
v7v8 v7
v5
v8
v6
v4
v2
v3
v1
S = [ ]
v4 already explored so no need to consider it
David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606
Illustration of DFS
v1v2
v3v4
v5
v6
v7v8 v7
v5
v8
v6
v4
v2
v3
v1
S = [ ]
S is empty so search is complete
David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606
Illustration of DFS
v1v2
v3v4
v5
v6
v7v8 v7
v5
v8
v6
v4
v2
v3
v1
Obtain tree by reversing directionality of all parent edges
David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606
Illustration of DFS
v1v2
v3v4
v5
v6
v7v8 v7
v5
v8
v6
v4
v2
v3
v1
Re-position nodes for clarity
David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606
Illustration of DFS
v1
v2
v3
v4
v5
v6
v7
v8
David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606
Example for You
Draw the depth-first search tree
Consider vertices in order of subscript
Begin traversal at v1
v1
v2
v3
v4
David Weir (U of Sussex) Program Analysis Term 1, 2017 159 / 606
Example for You
Draw the depth-first search tree
Consider vertices in order of subscript
Begin traversal at v1
v1
v2
v3
v4
v1
v2
v3
v4
David Weir (U of Sussex) Program Analysis Term 1, 2017 159 / 606
DFS Algorithm
DFS(G, s) :
let S be a stack containing just the node s
let explored(v) = false for all v ∈ V
while S is not empty
pop v from the top of S
if not explored(v) then
for each edge {v ,w} in E where not explored(w)
push w onto S
let parent(w) = v
let explored(v) = true
David Weir (U of Sussex) Program Analysis Term 1, 2017 160 / 606
Running Time of DFS
What is a good measure of progress?
Number of vertices whose edges have been considered not
adequate
For some iterations this will not increase
— when explored vertex removed from stack
Number of edge destinations considered always increases
Each directed edge is directed into the destination vertex
Increases by at least 1 on each iteration of the while loop
David Weir (U of Sussex) Program Analysis Term 1, 2017 161 / 606
Running Time of DFS (cont.)
This means that there O(m) iterations of the loop
How much time spent on each iteration?
Depends on number of edges to be considered
Number of steps within loop is Θ(max(1,outdegree(v)))
We know that in total there are m edges to consider
Total across all iterations of loop:
∑
v∈V
max(1,outdegree(v)) = Θ(n + m)
David Weir (U of Sussex) Program Analysis Term 1, 2017 162 / 606
Topological Sorting
David Weir (U of Sussex) Program Analysis Term 1, 2017 163 / 606
Working with Dependencies
AB
CD
E
F
GH
Directed Graphs often used to encode dependencies
David Weir (U of Sussex) Program Analysis Term 1, 2017 164 / 606
Working with Dependencies
AB
CD
E
F
GH
Nodes correspond to tasks
David Weir (U of Sussex) Program Analysis Term 1, 2017 164 / 606
Working with Dependencies
AB
CD
E
F
GH
Edges encode constraints on order in which tasks can be scheduled
David Weir (U of Sussex) Program Analysis Term 1, 2017 164 / 606
Working with Dependencies
AB
CD
E
F
GH
Task E must be completed before task G is started
E
G
David Weir (U of Sussex) Program Analysis Term 1, 2017 164 / 606
Working with Dependencies
AB
CD
E
F
GH
Cycles are undesirable
David Weir (U of Sussex) Program Analysis Term 1, 2017 164 / 606
Working with Dependencies
AB
CD
E
F
GH
No scheduling would be possible that satisfies constraints
David Weir (U of Sussex) Program Analysis Term 1, 2017 164 / 606
Topological Sorting of DAGs
Topological Sorting Problem:
Given a DAG, G = (V ,E), find a topological sort of G.
Topological Ordering:
A topological ordering of a DAG, G = (V ,E), is a permutation
of the vertices in V that is compatible with each edge in E
A permutation (v1, . . . , vn) is compatible with edge (v ,w) if
v = vi , w = vj and i < j David Weir (U of Sussex) Program Analysis Term 1, 2017 165 / 606 Examples of Topological Sorts AB CD E F GH Let’s find a topological sort of this DAG David Weir (U of Sussex) Program Analysis Term 1, 2017 166 / 606 Examples of Topological Sorts AB CD E F GH We could schedule C or E , let’s choose to schedule E David Weir (U of Sussex) Program Analysis Term 1, 2017 166 / 606 Examples of Topological Sorts AB CD E F GH EE 1 David Weir (U of Sussex) Program Analysis Term 1, 2017 166 / 606 Examples of Topological Sorts AB CD E F GH E 1 Now we could schedule G or C, let’s choose G GG 2 David Weir (U of Sussex) Program Analysis Term 1, 2017 166 / 606 Examples of Topological Sorts AB CD E F GH E 1 G 2 Now let’s schedule C CC 3 David Weir (U of Sussex) Program Analysis Term 1, 2017 166 / 606 Examples of Topological Sorts AB CD E F GH E 1 G 2 C 3 Now let’s schedule A AA 4 David Weir (U of Sussex) Program Analysis Term 1, 2017 166 / 606 Examples of Topological Sorts AB CD E F GH E 1 G 2 C 3 A 4 Now let’s schedule B BB 5 David Weir (U of Sussex) Program Analysis Term 1, 2017 166 / 606 Examples of Topological Sorts AB CD E F GH E 1 G 2 C 3 A 4 B 5 Now let’s schedule F FF 6 David Weir (U of Sussex) Program Analysis Term 1, 2017 166 / 606 Examples of Topological Sorts AB CD E F GH E 1 G 2 C 3 A 4 B 5 F 6 Now let’s schedule D DD 7 David Weir (U of Sussex) Program Analysis Term 1, 2017 166 / 606 Examples of Topological Sorts AB CD E F GH E 1 G 2 C 3 A 4 B 5 F 6 D 7 Finally, let’s schedule H HH 8 David Weir (U of Sussex) Program Analysis Term 1, 2017 166 / 606 Examples of Topological Sorts AB CD E F GH E 1 G 2 C 3 A 4 B 5 F 6 D 7 H 8 So the topological sort is: (E ,G,C,A,B,F ,D,H) David Weir (U of Sussex) Program Analysis Term 1, 2017 166 / 606 Question for you Give all topological sorts of this graph. A B C David Weir (U of Sussex) Program Analysis Term 1, 2017 167 / 606 Question for you Give all topological sorts of this graph. A B C ◮ (A,B,C) ◮ (B,A,C) David Weir (U of Sussex) Program Analysis Term 1, 2017 167 / 606 Question for you Give a graph containing 5 vertices with exactly one topological sort David Weir (U of Sussex) Program Analysis Term 1, 2017 168 / 606 Question for you Give a graph containing 5 vertices with exactly one topological sort A B C D E David Weir (U of Sussex) Program Analysis Term 1, 2017 168 / 606 Question for you Give a graph containing 3 vertices with no topological sorts David Weir (U of Sussex) Program Analysis Term 1, 2017 169 / 606 Question for you Give a graph containing 3 vertices with no topological sorts A B C David Weir (U of Sussex) Program Analysis Term 1, 2017 169 / 606 Topological Sorting Algorithm Question: When can a task be safely scheduled? Answer: when everything that it depends on has already been scheduled We need to start with a task that depends on nothing This corresponds to a node without any incoming edges David Weir (U of Sussex) Program Analysis Term 1, 2017 170 / 606 The Incoming Edge Count For each node the total incoming edge count is a measure of how “close” it is to a task that is ready to be scheduled Once a task X is scheduled, can reduce incoming edge count for all tasks that depend on X . In effect, the edges out of X are deleted once X has been scheduled. Once incoming edge count for a node reduces to 0 it can be scheduled David Weir (U of Sussex) Program Analysis Term 1, 2017 171 / 606 Topological Sort Algorithm TopologicalSort(G) : let S be an empty stack for each vertex v ∈ V compute indegree(v) if indegree(v) = 0 then push v onto S while S is not empty pop u from S schedule u for each (u,w) ∈ E decrement indegree(w) by 1 if indegree(w) = 0 then push w onto S David Weir (U of Sussex) Program Analysis Term 1, 2017 172 / 606 Illustration of Topological Sort Algorithm AB CD E F GH Compute indegree of each vertex David Weir (U of Sussex) Program Analysis Term 1, 2017 173 / 606 Illustration of Topological Sort Algorithm A1B3 C0D2 E0 F1 G1H2 Push vertices with 0 indegree on stack David Weir (U of Sussex) Program Analysis Term 1, 2017 173 / 606 Illustration of Topological Sort Algorithm A1B3 C0D2 E0 F1 G1H2 Push vertices with 0 indegree on stack S = (E ,C) David Weir (U of Sussex) Program Analysis Term 1, 2017 173 / 606 Illustration of Topological Sort Algorithm A1B3 C0D2 E0 F1 G1H2 S = (E ,C) Pop E from stack David Weir (U of Sussex) Program Analysis Term 1, 2017 173 / 606 Illustration of Topological Sort Algorithm A1B3 C0D2 E0 F1 G1H2 S = (C) E0 Schedule E David Weir (U of Sussex) Program Analysis Term 1, 2017 173 / 606 Illustration of Topological Sort Algorithm A1B3 C0D2 E0 F1 G1H2 S = (C) E0 1 “Remove” all edges out of E , updating indegree values David Weir (U of Sussex) Program Analysis Term 1, 2017 173 / 606 Illustration of Topological Sort Algorithm S = (C) 1 A1B2 C0D2 E0 F1 G0H1 Push G onto stack David Weir (U of Sussex) Program Analysis Term 1, 2017 173 / 606 Illustration of Topological Sort Algorithm 1 A1B2 C0D2 E0 F1 G0H1 S = (G,C) Pop G from stack David Weir (U of Sussex) Program Analysis Term 1, 2017 173 / 606 Illustration of Topological Sort Algorithm 1 A1B2 C0D2 E0 F1 G0H1 S = (C) G0 Schedule G David Weir (U of Sussex) Program Analysis Term 1, 2017 173 / 606 Illustration of Topological Sort Algorithm 1 A1B2 C0D2 E0 F1 G0H1 S = (C) G0 2 “Remove” all edges out of G, updating indegree values David Weir (U of Sussex) Program Analysis Term 1, 2017 173 / 606 Illustration of Topological Sort Algorithm 1 S = (C) 2 A1B2 C0D1 E0 F1 G0H1 Pop C from stack David Weir (U of Sussex) Program Analysis Term 1, 2017 173 / 606 Illustration of Topological Sort Algorithm 1 2 A1B2 C0D1 E0 F1 G0H1 S = () C0 Schedule C David Weir (U of Sussex) Program Analysis Term 1, 2017 173 / 606 Illustration of Topological Sort Algorithm 1 2 A1B2 C0D1 E0 F1 G0H1 S = () C0 3 “Remove” all edges out of C, updating indegree values David Weir (U of Sussex) Program Analysis Term 1, 2017 173 / 606 Illustration of Topological Sort Algorithm 1 2 S = () 3 A0B1 C0D1 E0 F0 G0H1 Push both A and F onto stack David Weir (U of Sussex) Program Analysis Term 1, 2017 173 / 606 Illustration of Topological Sort Algorithm 1 2 3 A0B1 C0D1 E0 F0 G0H1 S = (F ,A) Pop F from stack David Weir (U of Sussex) Program Analysis Term 1, 2017 173 / 606 Illustration of Topological Sort Algorithm 1 2 3 A0B1 C0D1 E0 F0 G0H1 S = (A)F0 Schedule F David Weir (U of Sussex) Program Analysis Term 1, 2017 173 / 606 Illustration of Topological Sort Algorithm 1 2 3 A0B1 C0D1 E0 F0 G0H1 S = (A)F04 “Remove” all edges out of F , updating indegree values David Weir (U of Sussex) Program Analysis Term 1, 2017 173 / 606 Illustration of Topological Sort Algorithm 1 2 3 4 A0B1 C0D0 E0 F0 G0H0 Push both D and H onto stack David Weir (U of Sussex) Program Analysis Term 1, 2017 173 / 606 Illustration of Topological Sort Algorithm 1 2 3 4 A0B1 C0D0 E0 F0 G0H0 S = (H,D,A) Pop H from stack David Weir (U of Sussex) Program Analysis Term 1, 2017 173 / 606 Illustration of Topological Sort Algorithm 1 2 3 4 A0B1 C0D0 E0 F0 G0H0 S = (D,A) H0 Schedule H David Weir (U of Sussex) Program Analysis Term 1, 2017 173 / 606 Illustration of Topological Sort Algorithm 1 2 3 4 A0B1 C0D0 E0 F0 G0H0 S = (D,A) H05 No edges out of H to “remove” — no indegree values to update David Weir (U of Sussex) Program Analysis Term 1, 2017 173 / 606 Illustration of Topological Sort Algorithm 1 2 3 4 S = (D,A) 5 A0B1 C0D0 E0 F0 G0H0 Pop D from stack David Weir (U of Sussex) Program Analysis Term 1, 2017 173 / 606 Illustration of Topological Sort Algorithm 1 2 3 4 5 A0B1 C0D0 E0 F0 G0H0 S = (A) D0 Schedule D David Weir (U of Sussex) Program Analysis Term 1, 2017 173 / 606 Illustration of Topological Sort Algorithm 1 2 3 4 5 A0B1 C0D0 E0 F0 G0H0 S = (A) D06 No edges out of D to “remove” — no indegree values to update David Weir (U of Sussex) Program Analysis Term 1, 2017 173 / 606 Illustration of Topological Sort Algorithm 1 2 3 4 5 S = (A) 6 A0B1 C0D0 E0 F0 G0H0 Pop A from stack David Weir (U of Sussex) Program Analysis Term 1, 2017 173 / 606 Illustration of Topological Sort Algorithm 1 2 3 4 5 6 A0B1 C0D0 E0 F0 G0H0 S = () A0 Schedule A David Weir (U of Sussex) Program Analysis Term 1, 2017 173 / 606 Illustration of Topological Sort Algorithm 1 2 3 4 5 6 A0B1 C0D0 E0 F0 G0H0 S = () A0 7 “Remove” all edges out of A and update indegree values David Weir (U of Sussex) Program Analysis Term 1, 2017 173 / 606 Illustration of Topological Sort Algorithm 1 2 3 4 5 6 S = () 7A0B0 C0D0 E0 F0 G0H0 Push B onto stack David Weir (U of Sussex) Program Analysis Term 1, 2017 173 / 606 Illustration of Topological Sort Algorithm 1 2 3 4 5 6 7A0B0 C0D0 E0 F0 G0H0 S = (B) Pop B from stack David Weir (U of Sussex) Program Analysis Term 1, 2017 173 / 606 Illustration of Topological Sort Algorithm 1 2 3 4 5 6 7A0B0 C0D0 E0 F0 G0H0 S = () B0 Schedule B David Weir (U of Sussex) Program Analysis Term 1, 2017 173 / 606 Illustration of Topological Sort Algorithm 1 2 3 4 5 6 7A0B0 C0D0 E0 F0 G0H0 S = () B0 8 No edges out of B to “remove” — no indegree values to update David Weir (U of Sussex) Program Analysis Term 1, 2017 173 / 606 Illustration of Topological Sort Algorithm 1 2 3 4 5 6 7 S = () 8 A0B0 C0D0 E0 F0 G0H0 All done! David Weir (U of Sussex) Program Analysis Term 1, 2017 173 / 606 Question for you What would happen if this topological sort algorithm was given a cyclic graph as input? David Weir (U of Sussex) Program Analysis Term 1, 2017 174 / 606 Question for you What would happen if this topological sort algorithm was given a cyclic graph as input? The algorithm would terminate without scheduling any of the edges within a cycle. David Weir (U of Sussex) Program Analysis Term 1, 2017 174 / 606 Question for you What would happen when the algorithm is run on a graph with just one topological sort? David Weir (U of Sussex) Program Analysis Term 1, 2017 175 / 606 Question for you What would happen when the algorithm is run on a graph with just one topological sort? Throughout the execution of the algorithm, the stack would contain no more than one element. David Weir (U of Sussex) Program Analysis Term 1, 2017 175 / 606 Topological Sort Algorithm (again) TopologicalSort(G) : let S be an empty stack for each vertex v ∈ V compute indegree(v) if indegree(v) = 0 then push v onto S while S is not empty pop u from S schedule u for each (u,w) ∈ E decrement indegree(w) by 1 if indegree(w) = 0 then push w onto S David Weir (U of Sussex) Program Analysis Term 1, 2017 176 / 606 Running Time Time to compute initial indegree values is Θ(n + m) — traverse all adjacency lists How many times is the while loop executed? Measure of progress is number of scheduled vertices — always increases by 1 for each iteration Number of steps within loop is Θ(max(1,outdegree(v))) We know that in total there are m edges to consider Total across all iterations of loop: ∑ v∈V max(1,outdegree(v)) = Θ(n + m) David Weir (U of Sussex) Program Analysis Term 1, 2017 177 / 606 Question for you Would the algorithm be correct if a queue rather than a stack was used to hold the schedulable vertices? David Weir (U of Sussex) Program Analysis Term 1, 2017 178 / 606 Question for you Would the algorithm be correct if a queue rather than a stack was used to hold the schedulable vertices? Yes, the order of elements within the stack (or the queue) is irrelevant David Weir (U of Sussex) Program Analysis Term 1, 2017 178 / 606 Question for you Would the use of queues rather than stacks have an impact on the asymptotic running time of the algorithm? David Weir (U of Sussex) Program Analysis Term 1, 2017 179 / 606 Question for you Would the use of queues rather than stacks have an impact on the asymptotic running time of the algorithm? No, though stacks are slightly more efficient to implement. David Weir (U of Sussex) Program Analysis Term 1, 2017 179 / 606 Question for you How could the algorithm be adpated to cater for a scenario where some jobs are more urgent than others? David Weir (U of Sussex) Program Analysis Term 1, 2017 180 / 606 Question for you How could the algorithm be adpated to cater for a scenario where some jobs are more urgent than others? Use a priority queue rather than a stack. David Weir (U of Sussex) Program Analysis Term 1, 2017 180 / 606