#include <lemon/edmonds_karp.h>
The time complexity of the algorithm is in worst case. Always try the preflow algorithm instead of this if you just want to compute the optimal flow.
_Graph | The directed graph type the algorithm runs on. | |
_Number | The number type of the capacities and the flow values. | |
_CapacityMap | The capacity map type. | |
_FlowMap | The flow map type. | |
_Tolerance | The tolerance class to handle computation problems. |
Public Types | |
typedef _Graph | Graph |
The graph type the algorithm runs on. | |
typedef _Number | Number |
The value type of the algorithms. | |
typedef _CapacityMap | CapacityMap |
The capacity map on the edges. | |
typedef _FlowMap | FlowMap |
The flow map on the edges. | |
typedef _Tolerance | Tolerance |
The tolerance used by the algorithm. | |
Public Member Functions | |
EdmondsKarp (const Graph &graph, Node source, Node target, const CapacityMap &capacity, FlowMap &flow, const Tolerance &tolerance=Tolerance()) | |
The constructor of the class. | |
void | init () |
Initializes the algorithm. | |
void | flowInit () |
Initializes the algorithm. | |
bool | checkedFlowInit () |
Initializes the algorithm. | |
bool | augment () |
Augment the solution on an edge shortest path. | |
void | start () |
Executes the algorithm. | |
Number | flowValue () const |
Gives back the current flow value. | |
void | run () |
runs the algorithm. | |
template<typename CutMap> | |
void | minCut (CutMap &cut) const |
Returns a minimum value cut. | |
template<typename CutMap> | |
void | minMinCut (CutMap &cut) const |
Returns the inclusionwise minimum of the minimum value cuts. | |
template<typename CutMap> | |
void | maxMinCut (CutMap &cut) const |
Returns the inclusionwise minimum of the minimum value cuts. | |
Node | source () const |
Returns the source node. | |
Node | target () const |
Returns the target node. | |
const CapacityMap & | capacityMap () const |
Returns a reference to capacity map. | |
const FlowMap & | flowMap () const |
Returns a reference to flow map. | |
const Tolerance & | tolerance () const |
Returns the tolerance used by algorithm. | |
Classes | |
class | InvalidArgument |
Exception for the case when the source equals the target. More... |
EdmondsKarp | ( | const Graph & | graph, | |
Node | source, | |||
Node | target, | |||
const CapacityMap & | capacity, | |||
FlowMap & | flow, | |||
const Tolerance & | tolerance = Tolerance() | |||
) | [inline] |
The constructor of the class.
graph | The directed graph the algorithm runs on. | |
source | The source node. | |
target | The target node. | |
capacity | The capacity of the edges. | |
flow | The flow of the edges. | |
tolerance | Tolerance class. |
void init | ( | ) | [inline] |
It sets the flow to empty flow.
void flowInit | ( | ) | [inline] |
If the flow map initially flow this let the flow map unchanged but the flow value will be set by the flow on the outedges from the source.
bool checkedFlowInit | ( | ) | [inline] |
If the flow map initially flow this let the flow map unchanged but the flow value will be set by the flow on the outedges from the source. It also checks that the flow map really contains a flow.
bool augment | ( | ) | [inline] |
Augment the solution on an edge shortest path. It search an edge shortest path between the source and the target in the residual graph with the bfs algoritm. Then it increase the flow on this path with the minimal residual capacity on the path. If there is not such path it gives back false.
void start | ( | ) | [inline] |
It runs augmenting phases until the optimal solution is reached.
Number flowValue | ( | ) | const [inline] |
Gives back the current flow _value.
void run | ( | ) | [inline] |
It is just a shorthand for:
ek.init(); ek.start();
void minCut | ( | CutMap & | cut | ) | const [inline] |
Sets cut
to the characteristic vector of a minimum value cut It simply calls the minMinCut member.
cut | Write node bool map. |
void minMinCut | ( | CutMap & | cut | ) | const [inline] |
Sets cut
to the characteristic vector of the minimum value cut which is inclusionwise minimum. It is computed by processing a bfs from the source node source
in the residual graph.
cut | Write node bool map. |
void maxMinCut | ( | CutMap & | cut | ) | const [inline] |
Sets cut
to the characteristic vector of the minimum value cut which is inclusionwise minimum. It is computed by processing a bfs from the source node source
in the residual graph.
cut | Write node bool map. |
Node source | ( | ) | const [inline] |
Returns the source node.
Node target | ( | ) | const [inline] |
Returns the target node.
const CapacityMap& capacityMap | ( | ) | const [inline] |
Returns a reference to capacity map.
const FlowMap& flowMap | ( | ) | const [inline] |
Returns a reference to flow map.
const Tolerance& tolerance | ( | ) | const [inline] |
Returns the tolerance used by algorithm.