com.mhhe.clrs2e
Class EdmondsKarp

java.lang.Object
  |
  +--com.mhhe.clrs2e.MaxFlow
        |
        +--com.mhhe.clrs2e.EdmondsKarp

public class EdmondsKarp

extends MaxFlow

Implements the Edmonds-Karp algorithm for maximum flow from Section 26.2 of Introduction to Algorithms, Second edition.

Nested Class Summary

private static class

EdmondsKarp.EKInfo Inner class for the information found by a breadth-first search in the Edmonds-Karp algorithm.

Constructor Summary

EdmondsKarp()

Method Summary

EdmondsKarp.EKInfo[]	breadthFirstSearch(com.mhhe.clrs2e.FlowNetwork g, com.mhhe.clrs2e.Vertex s, com.mhhe.clrs2e.Vertex t) Performs a breadth-first search in the Edmonds-Karp algorithm.
void	computeMaxFlow(com.mhhe.clrs2e.FlowNetwork g, com.mhhe.clrs2e.Vertex s, com.mhhe.clrs2e.Vertex t) Finds a maximum flow in a flow network from a given source to a given sink.

Methods inherited from class com.mhhe.clrs2e.MaxFlow

zeroFlow

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

EdmondsKarp

public EdmondsKarp()

Method Detail

computeMaxFlow

public void computeMaxFlow(com.mhhe.clrs2e.FlowNetwork g,
                           com.mhhe.clrs2e.Vertex s,
                           com.mhhe.clrs2e.Vertex t)

Finds a maximum flow in a flow network from a given source to a given sink.

Specified by:

computeMaxFlow in class MaxFlow

Parameters:

g - The flow network.

s - The source vertex.

t - The sink vertex.

breadthFirstSearch

public EdmondsKarp.EKInfo[] breadthFirstSearch(com.mhhe.clrs2e.FlowNetwork g,
                                               com.mhhe.clrs2e.Vertex s,
                                               com.mhhe.clrs2e.Vertex t)

Performs a breadth-first search in the Edmonds-Karp algorithm.

This method is written as distinct code from the BFS.search(com.mhhe.clrs2e.AdjacencyListGraph, com.mhhe.clrs2e.Vertex) version of breadth-first search because

1. We have to maintain additional information upon visiting a vertex, namely the edge that is taken into the vertex.
2. We stop once we find the sink.

Parameters:

g - The flow network.

s - The source vertex.

t - The sink vertex.

Returns:

An array of EKInfo objects, one per vertex.