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



Download 186.06 Kb.
Page23/24
Date03.05.2017
Size186.06 Kb.
#18863
1   ...   16   17   18   19   20   21   22   23   24

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

Download 186.06 Kb.

Share with your friends:
1   ...   16   17   18   19   20   21   22   23   24




The database is protected by copyright ©sckool.org 2022
send message

    Main page