The PushRelabelMaximumFlowAlgorithm class calculates the maximum flow of a network. The calculated maximum flow will be the return value of the Compute(IVertex, IVertex)function. The function also calculates the flow values f(u,v) for all (u,v) in E, which are returned in the form of the residual capacity r(u,v) = c(u,v) - f(u,v).

There are several special requirements on the input graph and property map parameters for this algorithm. First, the directed graph G=(V,E) that represents the network must be augmented to include the reverse edge for every edge in E. That is, the input graph should be Gin = (V,{E U E^T}). The reversedEdges argument must map each edge in the original graph to its reverse edge, that is (u,v) -> (v,u) for all (u,v) in E. The capacities argument must map each edge in E to a positive number, and each edge in E^T to 0.

This algorithm was developed by Goldberg.