Consider the CPXMIP_OPTIMAL_TOL status as OPTIMAL too.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2007
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
19 #ifndef LEMON_EDMONDS_KARP_H
20 #define LEMON_EDMONDS_KARP_H
24 /// \brief Implementation of the Edmonds-Karp algorithm.
26 #include <lemon/graph_adaptor.h>
27 #include <lemon/tolerance.h>
28 #include <lemon/bfs.h>
33 /// \brief Edmonds-Karp algorithms class.
35 /// This class provides an implementation of the \e Edmonds-Karp \e
36 /// algorithm producing a flow of maximum value in a directed
37 /// graph. The Edmonds-Karp algorithm is slower than the Preflow algorithm
38 /// but it has an advantage of the step-by-step execution control with
39 /// feasible flow solutions. The \e source node, the \e target node, the \e
40 /// capacity of the edges and the \e starting \e flow value of the
41 /// edges should be passed to the algorithm through the
44 /// The time complexity of the algorithm is \f$ O(n * e^2) \f$ in
45 /// worst case. Always try the preflow algorithm instead of this if
46 /// you just want to compute the optimal flow.
48 /// \param _Graph The directed graph type the algorithm runs on.
49 /// \param _Number The number type of the capacities and the flow values.
50 /// \param _CapacityMap The capacity map type.
51 /// \param _FlowMap The flow map type.
52 /// \param _Tolerance The tolerance class to handle computation problems.
54 /// \author Balazs Dezso
56 template <typename _Graph, typename _Number,
57 typename _CapacityMap, typename _FlowMap, typename _Tolerance>
59 template <typename _Graph, typename _Number,
60 typename _CapacityMap = typename _Graph::template EdgeMap<_Number>,
61 typename _FlowMap = typename _Graph::template EdgeMap<_Number>,
62 typename _Tolerance = Tolerance<_Number> >
67 /// \brief \ref Exception for the case when the source equals the target.
69 /// \ref Exception for the case when the source equals the target.
71 class InvalidArgument : public lemon::LogicError {
73 virtual const char* what() const throw() {
74 return "lemon::EdmondsKarp::InvalidArgument";
79 /// \brief The graph type the algorithm runs on.
81 /// \brief The value type of the algorithms.
82 typedef _Number Number;
83 /// \brief The capacity map on the edges.
84 typedef _CapacityMap CapacityMap;
85 /// \brief The flow map on the edges.
86 typedef _FlowMap FlowMap;
87 /// \brief The tolerance used by the algorithm.
88 typedef _Tolerance Tolerance;
90 typedef ResGraphAdaptor<Graph, Number, CapacityMap,
91 FlowMap, Tolerance> ResGraph;
95 typedef typename Graph::Node Node;
96 typedef typename Graph::Edge Edge;
98 typedef typename Graph::NodeIt NodeIt;
99 typedef typename Graph::EdgeIt EdgeIt;
100 typedef typename Graph::InEdgeIt InEdgeIt;
101 typedef typename Graph::OutEdgeIt OutEdgeIt;
105 /// \brief The constructor of the class.
107 /// The constructor of the class.
108 /// \param graph The directed graph the algorithm runs on.
109 /// \param source The source node.
110 /// \param target The target node.
111 /// \param capacity The capacity of the edges.
112 /// \param flow The flow of the edges.
113 /// \param tolerance Tolerance class.
114 EdmondsKarp(const Graph& graph, Node source, Node target,
115 const CapacityMap& capacity, FlowMap& flow,
116 const Tolerance& tolerance = Tolerance())
117 : _graph(graph), _capacity(capacity), _flow(flow),
118 _tolerance(tolerance), _resgraph(graph, capacity, flow, tolerance),
119 _source(source), _target(target)
121 if (_source == _target) {
122 throw InvalidArgument();
126 /// \brief Initializes the algorithm
128 /// It sets the flow to empty flow.
130 for (EdgeIt it(_graph); it != INVALID; ++it) {
136 /// \brief Initializes the algorithm
138 /// If the flow map initially flow this let the flow map
139 /// unchanged but the flow value will be set by the flow
140 /// on the outedges from the source.
143 for (OutEdgeIt jt(_graph, _source); jt != INVALID; ++jt) {
146 for (InEdgeIt jt(_graph, _source); jt != INVALID; ++jt) {
151 /// \brief Initializes the algorithm
153 /// If the flow map initially flow this let the flow map
154 /// unchanged but the flow value will be set by the flow
155 /// on the outedges from the source. It also checks that
156 /// the flow map really contains a flow.
157 /// \return %True when the flow map really a flow.
158 bool checkedFlowInit() {
160 for (OutEdgeIt jt(_graph, _source); jt != INVALID; ++jt) {
163 for (InEdgeIt jt(_graph, _source); jt != INVALID; ++jt) {
166 for (NodeIt it(_graph); it != INVALID; ++it) {
167 if (it == _source || it == _target) continue;
169 for (OutEdgeIt jt(_graph, it); jt != INVALID; ++jt) {
170 outFlow += _flow[jt];
173 for (InEdgeIt jt(_graph, it); jt != INVALID; ++jt) {
176 if (_tolerance.different(outFlow, inFlow)) {
180 for (EdgeIt it(_graph); it != INVALID; ++it) {
181 if (_tolerance.less(_flow[it], 0)) return false;
182 if (_tolerance.less(_capacity[it], _flow[it])) return false;
187 /// \brief Augment the solution on an edge shortest path.
189 /// Augment the solution on an edge shortest path. It search an
190 /// edge shortest path between the source and the target
191 /// in the residual graph with the bfs algoritm.
192 /// Then it increase the flow on this path with the minimal residual
193 /// capacity on the path. If there is not such path it gives back
195 /// \return %False when the augmenting is not success so the
196 /// current flow is a feasible and optimal solution.
198 typename Bfs<ResGraph>
199 ::template DefDistMap<NullMap<Node, int> >
200 ::Create bfs(_resgraph);
202 NullMap<Node, int> distMap;
203 bfs.distMap(distMap);
206 bfs.addSource(_source);
209 if (!bfs.reached(_target)) {
212 Number min = _resgraph.rescap(bfs.predEdge(_target));
213 for (Node it = bfs.predNode(_target); it != _source;
214 it = bfs.predNode(it)) {
215 if (min > _resgraph.rescap(bfs.predEdge(it))) {
216 min = _resgraph.rescap(bfs.predEdge(it));
219 for (Node it = _target; it != _source; it = bfs.predNode(it)) {
220 _resgraph.augment(bfs.predEdge(it), min);
226 /// \brief Executes the algorithm
228 /// It runs augmenting phases until the optimal solution is reached.
233 /// \brief Gives back the current flow value.
235 /// Gives back the current flow _value.
236 Number flowValue() const {
240 /// \brief runs the algorithm.
242 /// It is just a shorthand for:
253 /// \brief Returns a minimum value cut.
255 /// Sets \c cut to the characteristic vector of a minimum value cut
256 /// It simply calls the minMinCut member.
257 /// \retval cut Write node bool map.
258 template <typename CutMap>
259 void minCut(CutMap& cut) const {
263 /// \brief Returns the inclusionwise minimum of the minimum value cuts.
265 /// Sets \c cut to the characteristic vector of the minimum value cut
266 /// which is inclusionwise minimum. It is computed by processing a
267 /// bfs from the source node \c source in the residual graph.
268 /// \retval cut Write node bool map.
269 template <typename CutMap>
270 void minMinCut(CutMap& cut) const {
272 typename Bfs<ResGraph>
273 ::template DefDistMap<NullMap<Node, int> >
274 ::template DefProcessedMap<CutMap>
275 ::Create bfs(_resgraph);
277 NullMap<Node, int> distMap;
278 bfs.distMap(distMap);
280 bfs.processedMap(cut);
285 /// \brief Returns the inclusionwise minimum of the minimum value cuts.
287 /// Sets \c cut to the characteristic vector of the minimum value cut
288 /// which is inclusionwise minimum. It is computed by processing a
289 /// bfs from the source node \c source in the residual graph.
290 /// \retval cut Write node bool map.
291 template <typename CutMap>
292 void maxMinCut(CutMap& cut) const {
294 typedef RevGraphAdaptor<const ResGraph> RevGraph;
296 RevGraph revgraph(_resgraph);
298 typename Bfs<RevGraph>
299 ::template DefDistMap<NullMap<Node, int> >
300 ::template DefPredMap<NullMap<Node, Edge> >
301 ::template DefProcessedMap<NotWriteMap<CutMap> >
302 ::Create bfs(revgraph);
304 NullMap<Node, int> distMap;
305 bfs.distMap(distMap);
307 NullMap<Node, Edge> predMap;
308 bfs.predMap(predMap);
310 NotWriteMap<CutMap> notcut(cut);
311 bfs.processedMap(notcut);
316 /// \brief Returns the source node.
318 /// Returns the source node.
320 Node source() const {
324 /// \brief Returns the target node.
326 /// Returns the target node.
328 Node target() const {
332 /// \brief Returns a reference to capacity map.
334 /// Returns a reference to capacity map.
336 const CapacityMap &capacityMap() const {
340 /// \brief Returns a reference to flow map.
342 /// Returns a reference to flow map.
344 const FlowMap &flowMap() const {
348 /// \brief Returns the tolerance used by algorithm.
350 /// Returns the tolerance used by algorithm.
351 const Tolerance& tolerance() const {
358 const CapacityMap& _capacity;
360 Tolerance _tolerance;
363 Node _source, _target;