This group contains the algorithms for finding maximum flows and feasible circulations [CLRS01], [AMO93].

The *maximum* *flow* *problem* is to find a flow of maximum value between a single source and a single target. Formally, there is a digraph, a capacity function and source and target nodes. A maximum flow is an solution of the following optimization problem.

Preflow is an efficient implementation of Goldberg-Tarjan's preflow push-relabel algorithm [GT88] for finding maximum flows. It also provides functions to query the minimum cut, which is the dual problem of maximum flow.

Circulation is a preflow push-relabel algorithm implemented directly for finding feasible circulations, which is a somewhat different problem, but it is strongly related to maximum flow. For more information, see Circulation.

## Classes | |

class | Circulation< GR, LM, UM, SM, TR > |

Push-relabel algorithm for the network circulation problem. More... | |

class | Preflow< GR, CAP, TR > |

Preflow algorithm class. More... | |

## Files | |

file | circulation.h |

Push-relabel algorithm for finding a feasible circulation. | |

file | preflow.h |

Implementation of the preflow algorithm. |

Generated on Wed Nov 9 2011 11:44:10 by 1.7.3