# These notes are intended for use by students in cs1501 at the University of Pittsburgh and no one else

 Page 23/24 Date 03.05.2017 Size 186.06 Kb. #18863

## Implementing a Heap

• Idea:
• Now we have the benefit of a tree structure with the speed of an array implementation
• Parent(i) = i/2
• LChild(i) = 2i
• RChild(i) = 2i+1

## PQ Needed for PFS

• Recall the PQ operations:
• Insert
• FindMin (or FindMax)
• DeleteMin (or DeleteMax)
• Recall operations needed for PFS:
• Insert
• DeleteMax
• Update – assign a new priority to a vertex
• How to do this one?
• Do you see why it is a problem?

## PQ Needed for PFS

• In order to allow Update in our PQ, we must be able to do a general Find() of the data
• PQ is only partially ordered, and further it is ordered on VALUES, not vertex ids
• Finding an arbitrary id will take Theta(N)
• Luckily, we can do it better with a little thought
• We can think of each entry in 2 parts:
• A vertex id (int)
• A priority value
• To update, we need to locate the id, update the priority, then reestablish the Heap property

## PQ Needed for PFS

• We can do this using indirection
• Keep an array indexed on the vertex ids which, for vertex i gives the location of i in the PQ
• When we move i in the PQ we change the value stored in our array
• This way we can always "find" a vertex in Theta(1) time
• Now, total time for update is simply time to reestablish heap priority using upheap or downheap
• See pqtest.cpp, pq.h and pq.out

## Network Flow

• Definitions:
• Consider a directed, weighted graph with set V of vertices and set E of edges, with each edge weight indicating a capacity, c(u,v) for that edge
• c(u,v) = 0 means no edge between u and v
• Consider a source vertex, s with no in-edges and a sink vertex, t with no out-edges
• A FLOW on the graph is another assignment of weights to the edges, f(u,v) such that the following rules are satisfied:

## Network Flow

• For All (u,v) in V, f(u,v) <= c(u,v)
• No flow can exceed the capacity of the edge
• For All (u,v) in V, f(u,v) = – f(v,u)
• If a positive flow is going from u to v, than an equal weight negative flow is going from v to u
• For All u in V – {s, t}, sum of (flow on edges from u) = 0
• All vertices except the source and sink have an overall "net" flow of 0 – the amount coming in is the same as the amount going out
• Problem: What is the maximum flow for a given network and how can we determine it?

## Network Flow

• Ford-Fulkerson approach:
• For a given network with a given flow, we look for an augmenting path from the source to the sink
• An augmenting path is a path from the source to the sink that provides additional flow along it
• After finding an augmenting path, we update the residual network to reflect the additional flow
• We repeat this process on the residual network until no augmenting path can be found
• At this point, the maximum flow has been determined
• See examples on board

## Backward Flow

• Note the following example:
• Let's look at 2 possible sequences of augmenting paths:
• SBT (5), SCT (5), SBCT (5)
• Total Flow is 15
• SBCT (10), ????
• We seem to be stuck, since there is no forward path from S to T
• Yet the choice of paths should not affect our answer
• S
• C
• B
• T
• 10
• 5
• 5
• 10
• 10

## Backward Flow

• How to resolve this problem?
• The augmenting paths do not represent final flow values for given edges
• They are simply a tool for determining the overall maximum flow
• A given assignment for an edge may be MORE than what the final network flow would indicate
• Backward flow is a way to lessen the flow on a given edge while increasing the overall flow in the graph
• In the example shown we can thus have the following augmenting paths:
• SBCT (10), SCBT (5)

## Backward Flow

• Augmenting path SCBT has an overall positive value of 5
• However, the link CB actually reduces the flow along that edge by 5, since it is in the backward direction on that edge
• Note that the final assignment on the edges for both sequences of augmenting paths is the same
• This is not always the case
• If the assignment of maximum flow is unique, they will be the same
• If more than one assignment gives the same value for maximum flow, difference choices for augmenting paths can result in different assignments
• But the overall flow will always be the same

## Implementing FF approach

• To implement FF, we need
• A way to represent the graph, capacity, flow, etc.
• What data structures will we need?
• See notes on board and in flownew.cpp
• Adjacency matrix (or list) in two parts:
• size[][] gives capacity of edges
• 0 if no edge
• Directed, and for edge [i][j], size[j][i] = – size[i][j] (see rule 2)
• flow[][] gives current flow on edges
• Initially 0
• flow[i][j] always less than size[i][j] (see rule 1)
• Rule 2 applies here as well