## 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)
- 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
## 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:
## 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
**Share with your friends:** |