程序代写代做代考 algorithm Program Analysis

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

v7v8

Run BFS starting at v7

David Weir (U of Sussex) Program Analysis Term 1, 2017 144 / 606

Illustration of BFS

v1v2

v3v4

v7v8

Initialize Q

David Weir (U of Sussex) Program Analysis Term 1, 2017 144 / 606

Illustration of BFS

v1v2

v3v4

v7v8

Q = [v7]

Let discovered(v7) = true

David Weir (U of Sussex) Program Analysis Term 1, 2017 144 / 606

Illustration of BFS

v1v2

v3v4

v7v8

Q = [v7]

Remove v7 from front of Q

David Weir (U of Sussex) Program Analysis Term 1, 2017 144 / 606

Illustration of BFS

v1v2

v3v4

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

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

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

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

v7v8 v7v7v4

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

v7v8 v7v4

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

v7v8 v7v4

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

v7v8 v7v4

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

v7v8 v7v4

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

v7v8 v7v4

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

v7v8 v7v4

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

v7v8 v7v4

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

v7v8 v7v4

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

v7v8 v7v4

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

v7v8 v7v4

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

v7v8 v7v4

v5 v2

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

v7v8 v7v4

v5 v2

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

v7v8 v7v4

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

v7v8 v7v4

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

v7v8 v7v4

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

v7v8 v7v4

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

v7v8 v7v4

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

v7v8 v7v4

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

v7v8 v7v4

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

v7v8 v7v4

v8 v3

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

v7v8 v7v4

v8 v3

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

v7v8 v7v4

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

v7v8 v7v4

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

v7v8 v7v4

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

v7v8 v7v4

v8 v3

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

v7v8 v7v4

v8 v3

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

v7v8 v7v4

v8 v3

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

v7v8 v7v4

v8 v3

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

v7v8 v7v4

v8 v3

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

v7v8 v7v4

v8 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

v7v8 v7v4

v8 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

v7v8 v7v4

v8 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

v7v8 v7v4

v8 v3

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

v7v8 v7v4

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

v7v8 v7v4

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

v7v8 v7v4

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

v7v8 v7v4

v8 v3

Q is empty so traversal complete

David Weir (U of Sussex) Program Analysis Term 1, 2017 144 / 606

Illustration of BFS

v7v4

v8 v3

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

v4 v5

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

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

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

Is this one or two graphs?

David Weir (U of Sussex) Program Analysis Term 1, 2017 147 / 606

Components of Graphs

This is one of the components

David Weir (U of Sussex) Program Analysis Term 1, 2017 147 / 606

Components of Graphs

And this is the other components

David Weir (U of Sussex) Program Analysis Term 1, 2017 147 / 606

Components of Graphs

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

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.)

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

v7v8

Run DFS starting at v7

David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606

Illustration of DFS

v1v2

v3v4

v7v8

Initialize S

David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606

Illustration of DFS

v1v2

v3v4

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

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

v7v8

S = [ ]

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

v7v8

S = [ ]

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

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

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

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

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

v7v8

S = [v5, v4]

Pop v5 from top of S

David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606

Illustration of DFS

v1v2

v3v4

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

v7v8 v7

S = [v4]

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

v7v8 v7

S = [v4]

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

v7v8 v7

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

v7v8 v7

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

v7v8 v7

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

v7v8 v7

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

v7v8 v7

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

v7v8 v7

S = [v8, v2, v4]

Pop v8 from top of S

David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606

Illustration of DFS

v1v2

v3v4

v7v8 v7

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

v7v8 v7

S = [v2, v4]

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

v7v8 v7

S = [v2, v4]

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

v7v8 v7

S = [v2, v4]

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

v7v8 v7

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

v7v8 v7

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

v7v8 v7

S = [v6, v2, v4]

Pop v6 from top of S

David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606

Illustration of DFS

v1v2

v3v4

v7v8 v7

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

v7v8 v7

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

v7v8 v7

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

v7v8 v7

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

v7v8 v7

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

v7v8 v7

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

v7v8 v7

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

v7v8 v7

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

v7v8 v7

S = [v2, 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

v7v8 v7

S = [v2, 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

v7v8 v7

S = [v2, v4]

No more edges from v4

David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606

Illustration of DFS

v1v2

v3v4

v7v8 v7

S = [v2, v4]

Let explored(v4) = true

David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606

Illustration of DFS

v1v2

v3v4

v7v8 v7

S = [v2, v4]

Pop v2 from top of S

David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606

Illustration of DFS

v1v2

v3v4

v7v8 v7

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

v7v8 v7

S = [v4]

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

v7v8 v7

S = [v4]

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

v7v8 v7

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

v7v8 v7

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

v7v8 v7

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

v7v8 v7

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

v7v8 v7

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

v7v8 v7

S = [v3, v1, v4]

Pop v3 from top of S

David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606

Illustration of DFS

v1v2

v3v4

v7v8 v7

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

v7v8 v7

S = [v1, v4]

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

v7v8 v7

S = [v1, v4]

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

v7v8 v7

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

v7v8 v7

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

v7v8 v7

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

v7v8 v7

S = [v1, v1, v4]

Pop v1 from top of S

David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606

Illustration of DFS

v1v2

v3v4

v7v8 v7

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

v7v8 v7

S = [v1, v4]

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

v7v8 v7

S = [v1, v4]

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

v7v8 v7

S = [v1, v4]

No more edges from v1

David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606

Illustration of DFS

v1v2

v3v4

v7v8 v7

S = [v1, v4]

Let explored(v1) = true

David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606

Illustration of DFS

v1v2

v3v4

v7v8 v7

S = [v1, v4]

Pop v1 from top of S

David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606

Illustration of DFS

v1v2

v3v4

v7v8 v7

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

v7v8 v7

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

v7v8 v7

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

v7v8 v7

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

v7v8 v7

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

v7v8 v7

Re-position nodes for clarity

David Weir (U of Sussex) Program Analysis Term 1, 2017 158 / 606

Illustration of DFS

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

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

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

Directed Graphs often used to encode dependencies

David Weir (U of Sussex) Program Analysis Term 1, 2017 164 / 606

Working with Dependencies

Nodes correspond to tasks

David Weir (U of Sussex) Program Analysis Term 1, 2017 164 / 606

Working with Dependencies

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

Task E must be completed before task G is started

David Weir (U of Sussex) Program Analysis Term 1, 2017 164 / 606

Working with Dependencies

Cycles are undesirable

David Weir (U of Sussex) Program Analysis Term 1, 2017 164 / 606

Working with Dependencies

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

Published by admin

Leave a Reply Cancel reply