Algorithms in a Nutshell

Maximum Flow | 233

Network Flow

Algorithms

The flow network example in Figure 8-3 shows the results of using DEPTH-FIRST

SEARCH to locate an augmenting path; the implementation is listed in

Example 8-2. Thepathstructure contains a stack of vertices during its search. A

potential augmenting path is expanded by popping a vertexufrom the stack and

expanding to an adjacent unvisited vertexvthat satisfies one of two constraints:

(i) edge (u,v) is a forward edge with unfilled capacity; (ii) edge (v,u) is a forward

edge with flow that can be reduced. Eventually, the sink vertextis visited orpath

becomes empty, in which case no augmenting path is possible.

Figure 8-4. Modeling information for Ford-Fulkerson

Figure 8-5. Search capability

Example 8-2. Using Depth-First Search to locate augmenting path

public boolean findAugmentingPath (VertexInfo[] vertices) {

// Begin potential augmenting path at source.

vertices[sourceIndex] = new VertexInfo (-1);

Stack<Integer> path = new Stack<Integer>( );

path.push (sourceIndex);

// Process forward edges from u; then try backward edges

VertexStructure struct[] = network.getEdgeStructure( );

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