Algorithms in a Nutshell

Maximum Flow | 229

Network Flow

Algorithms

Capacity constraint

The flowf(u,v) through an edge cannot be negative and cannot exceed the

capacity of the edgec(u,v), 0≤f(u,v)≤c(u,v). If an edge (u,v) doesn’t exist in

the network, thenc(u,v)=0.

Flow conservation

Aside from the source vertexsand sink vertext, each vertexu∈Vmust satisfy

the property that the sum off(v,u) for all edges (v,u)inE(the flow intou)

must equal the sum off(u,w) for all edges (u,w)∈E(the flow out ofu). This

property ensures that flow is neither produced nor consumed in the network,

except ats andt.

Skew symmetry

For consistency, the quantityf(v,u) represents the net flow from vertexutov.

This means that it must be the case thatf(u,v)=–f(v,u); this holds even if both

edges (u,v) and (v,u) exist in a directed graph (as they do in Figure 8-2).

In the ensuing algorithms we refer to a network path that is a non-cyclic path of

unique vertices <v 1 ,v 2 ,...,vn> involvingn–1 consecutive edges (vi,vj)inE. In the

directed graph shown in Figure 8-2, one possible network path is <v 3 ,v 5 ,v 2 ,v 4 >. In

a network path, the direction of the edges can be ignored. In Figure 8-3, a possible

network path is <s,v 1 ,v 4 ,v 2 ,v 3 ,t>.

Maximum Flow

Given a flow network, it is possible to compute the maximum flow (mf) between

verticessandtgiven the capacity constraintsc(u,v)≥0 for all directed edges

e=(u,v)inE. That is, compute the largest amount that can flow out of sources,

through the network, and into sinktgiven specific capacity limits on individual

edges. Starting with a feasible flow (a flow of 0 through every edge is feasible),

FORD-FULKERSON(Figure 8-3) successively locates anaugmenting paththrough

the network fromstotto which more flow can be added. The algorithm termi-

nates when no augmenting paths can be found. The Max-flow Min-cut theorem

(Ford-Fulkerson, 1962) guarantees that with non-negative flows and capacities,

FORD-FULKERSONalways terminates and identifies the maximum flow in a

network.

Input/Output

In this presentation, we describe FORD-FULKERSONusing linked lists to store

edges. Each vertexumaintains two separate lists: forward edges for the edges

emanating fromuand backward edges for the edges coming intou; thus each

edge appears in two lists, doubling the total storage. The code repository provided

with this book contains an implementation using a two-dimensional matrix to

store edges, a more appropriate data structure to use for dense flow network

graphs.

Algorithms in a Nutshell
Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
9780596516246 Publisher: O'Reilly Media, Inc.

Prepared for Ming Yi, Safari ID: [email protected]
Licensed by Ming Yi
Print Publication Date: 2008/10/21 User number: 594243
© 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use