99 public: |
99 public: |
100 |
100 |
101 /// \brief The constructor of the class. |
101 /// \brief The constructor of the class. |
102 /// |
102 /// |
103 /// The constructor of the class. |
103 /// The constructor of the class. |
104 /// \param _graph The directed graph the algorithm runs on. |
104 /// \param graph The directed graph the algorithm runs on. |
105 /// \param _source The source node. |
105 /// \param source The source node. |
106 /// \param _target The target node. |
106 /// \param target The target node. |
107 /// \param _capacity The capacity of the edges. |
107 /// \param capacity The capacity of the edges. |
108 /// \param _flow The flow of the edges. |
108 /// \param flow The flow of the edges. |
109 /// \param _tolerance Tolerance class. |
109 /// \param tolerance Tolerance class. |
110 /// Except the graph, all of these parameters can be reset by |
110 /// Except the graph, all of these parameters can be reset by |
111 /// calling \ref source, \ref target, \ref capacityMap and \ref |
111 /// calling \ref source, \ref target, \ref capacityMap and \ref |
112 /// flowMap, resp. |
112 /// flowMap, resp. |
113 EdmondsKarp(const Graph& graph, Node source, Node target, |
113 EdmondsKarp(const Graph& graph, Node source, Node target, |
114 const CapacityMap& capacity, FlowMap& flow, |
114 const CapacityMap& capacity, FlowMap& flow, |
250 |
250 |
251 /// \brief Returns a minimum value cut. |
251 /// \brief Returns a minimum value cut. |
252 /// |
252 /// |
253 /// Sets \c cut to the characteristic vector of a minimum value cut |
253 /// Sets \c cut to the characteristic vector of a minimum value cut |
254 /// It simply calls the minMinCut member. |
254 /// It simply calls the minMinCut member. |
|
255 /// \retval cut Write node bool map. |
255 template <typename CutMap> |
256 template <typename CutMap> |
256 void minCut(CutMap& cut) const { |
257 void minCut(CutMap& cut) const { |
257 minMinCut(cut); |
258 minMinCut(cut); |
258 } |
259 } |
259 |
260 |
260 /// \brief Returns the inclusionwise minimum of the minimum value cuts. |
261 /// \brief Returns the inclusionwise minimum of the minimum value cuts. |
261 /// |
262 /// |
262 /// Sets \c cut to the characteristic vector of the minimum value cut |
263 /// Sets \c cut to the characteristic vector of the minimum value cut |
263 /// which is inclusionwise minimum. It is computed by processing a |
264 /// which is inclusionwise minimum. It is computed by processing a |
264 /// bfs from the source node \c source in the residual graph. |
265 /// bfs from the source node \c source in the residual graph. |
|
266 /// \retval cut Write node bool map. |
265 template <typename CutMap> |
267 template <typename CutMap> |
266 void minMinCut(CutMap& cut) const { |
268 void minMinCut(CutMap& cut) const { |
267 |
269 |
268 typename Bfs<ResGraph> |
270 typename Bfs<ResGraph> |
269 ::template DefDistMap<NullMap<Node, int> > |
271 ::template DefDistMap<NullMap<Node, int> > |
281 /// \brief Returns the inclusionwise minimum of the minimum value cuts. |
283 /// \brief Returns the inclusionwise minimum of the minimum value cuts. |
282 /// |
284 /// |
283 /// Sets \c cut to the characteristic vector of the minimum value cut |
285 /// Sets \c cut to the characteristic vector of the minimum value cut |
284 /// which is inclusionwise minimum. It is computed by processing a |
286 /// which is inclusionwise minimum. It is computed by processing a |
285 /// bfs from the source node \c source in the residual graph. |
287 /// bfs from the source node \c source in the residual graph. |
|
288 /// \retval cut Write node bool map. |
286 template <typename CutMap> |
289 template <typename CutMap> |
287 void maxMinCut(CutMap& cut) const { |
290 void maxMinCut(CutMap& cut) const { |
288 |
291 |
289 typedef RevGraphAdaptor<const ResGraph> RevGraph; |
292 typedef RevGraphAdaptor<const ResGraph> RevGraph; |
290 |
293 |