Algorithms in a Nutshell

(^238) | Chapter 8: Network Flow Algorithms
Related Algorithms
The PUSH/RELABEL algorithm introduced by Goldberg and Tarjan (1986)
improves the performance to O(VElog(V^2 /E)) and also provides an algorithm
that can be parallelized for greater gains. A variant of the problem, known as the
Multi-Commodity Flow problem, generalizes the Maximum Flow problem stated
here. Briefly, instead of having a single source and sink, consider a shared network
used by multiple sourcessiand sinkstito transmit different commodities. The
capacity of the edges is fixed, but the usage demands for each source and sink
may vary. Practical applications of algorithms that solve this problem include
routing in wireless networks (Fragouli and Tabet, 2006). Leighton and Rao (1999)
have written a widely cited reference for multi-commodity problems.
There are several slight variations to the Maximum Flow problem:
Vertex capacities
What if a flow network places a maximum capacityk(v) flowing through a
vertexvin the graph? Construct a modified flow networkG′as follows. For
each vertexvin the network, create two verticesv′andv′′. Create edge (v′′,v′)
with a flow capacity ofk(v). For each edge (x,v) in the original graph with
capacityc(x,v), create new edge (x,v′′) with capacityc(x,v) from original
graphG. For each edge (v,w) in the original graphG, create edge (v′,w)inG′
with capacityk(v). A solution inG′ determines the solution toG.
Undirected edges
What if the flow networkGhas undirected edges? Construct a modified flow
networkG′as follows. In a new graph, all vertices are the same. For each
edge (u,v) in the original graph with capacityc(u,v), construct a pair of edges
(u,v) and (v,u) each with the same capacityc(u,v). A solution inG′deter-
mines the solution toG.
int u = queue[head]; head = (head + 1) % QUEUE_SIZE;
visited[u] = 2;
// add to queue unvisited neighboring vertices of u with enough capacity.
for (int v = 0; v < numVertices; v++) {
if (visited[v] == 0 && capacity[u][v] > flow[u][v]) {
queue[tail] = v; tail = (tail + 1) % QUEUE_SIZE;
visited[v] = 1; // actively in queue.
previous[v] = u;
}
}
}
return visited[sink] != 0; // did we make it to the sink?
}
}
Example 8-4. Optimized Ford-Fulkerson implementation (continued)
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