thoneyvazul@1056: /* -*- mode: C++; indent-tabs-mode: nil; -*- thoneyvazul@1056: * thoneyvazul@1056: * This file is a part of LEMON, a generic C++ optimization library. thoneyvazul@1056: * thoneyvazul@1056: * Copyright (C) 2003-2010 thoneyvazul@1056: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport thoneyvazul@1056: * (Egervary Research Group on Combinatorial Optimization, EGRES). thoneyvazul@1056: * thoneyvazul@1056: * Permission to use, modify and distribute this software is granted thoneyvazul@1056: * provided that this copyright notice appears in all copies. For thoneyvazul@1056: * precise terms see the accompanying LICENSE file. thoneyvazul@1056: * thoneyvazul@1056: * This software is provided "AS IS" with no warranty of any kind, thoneyvazul@1056: * express or implied, and with no claim as to its suitability for any thoneyvazul@1056: * purpose. thoneyvazul@1056: * thoneyvazul@1056: */ thoneyvazul@1056: thoneyvazul@1056: #ifndef LEMON_EDMONDS_KARP_H thoneyvazul@1056: #define LEMON_EDMONDS_KARP_H thoneyvazul@1056: thoneyvazul@1056: /// \file thoneyvazul@1056: /// \ingroup max_flow thoneyvazul@1056: /// \brief Implementation of the Edmonds-Karp algorithm. thoneyvazul@1056: thoneyvazul@1056: #include thoneyvazul@1056: #include thoneyvazul@1056: thoneyvazul@1056: namespace lemon { thoneyvazul@1056: thoneyvazul@1056: /// \brief Default traits class of EdmondsKarp class. thoneyvazul@1056: /// thoneyvazul@1056: /// Default traits class of EdmondsKarp class. thoneyvazul@1056: /// \param GR Digraph type. thoneyvazul@1056: /// \param CAP Type of capacity map. thoneyvazul@1056: template thoneyvazul@1056: struct EdmondsKarpDefaultTraits { thoneyvazul@1056: thoneyvazul@1056: /// \brief The digraph type the algorithm runs on. thoneyvazul@1056: typedef GR Digraph; thoneyvazul@1056: thoneyvazul@1056: /// \brief The type of the map that stores the arc capacities. thoneyvazul@1056: /// thoneyvazul@1056: /// The type of the map that stores the arc capacities. thoneyvazul@1056: /// It must meet the \ref concepts::ReadMap "ReadMap" concept. thoneyvazul@1056: typedef CAP CapacityMap; thoneyvazul@1056: kpeter@1057: /// \brief The type of the flow values. thoneyvazul@1056: typedef typename CapacityMap::Value Value; thoneyvazul@1056: kpeter@1057: /// \brief The type of the map that stores the flow values. thoneyvazul@1056: /// kpeter@1057: /// The type of the map that stores the flow values. thoneyvazul@1056: /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. kpeter@1057: #ifdef DOXYGEN kpeter@1057: typedef GR::ArcMap FlowMap; kpeter@1057: #else thoneyvazul@1056: typedef typename Digraph::template ArcMap FlowMap; kpeter@1057: #endif thoneyvazul@1056: thoneyvazul@1056: /// \brief Instantiates a FlowMap. thoneyvazul@1056: /// thoneyvazul@1056: /// This function instantiates a \ref FlowMap. kpeter@1057: /// \param digraph The digraph for which we would like to define kpeter@1057: /// the flow map. thoneyvazul@1056: static FlowMap* createFlowMap(const Digraph& digraph) { thoneyvazul@1056: return new FlowMap(digraph); thoneyvazul@1056: } thoneyvazul@1056: thoneyvazul@1056: /// \brief The tolerance used by the algorithm thoneyvazul@1056: /// thoneyvazul@1056: /// The tolerance used by the algorithm to handle inexact computation. thoneyvazul@1056: typedef lemon::Tolerance Tolerance; thoneyvazul@1056: thoneyvazul@1056: }; thoneyvazul@1056: thoneyvazul@1056: /// \ingroup max_flow thoneyvazul@1056: /// thoneyvazul@1056: /// \brief Edmonds-Karp algorithms class. thoneyvazul@1056: /// thoneyvazul@1056: /// This class provides an implementation of the \e Edmonds-Karp \e kpeter@1057: /// algorithm producing a \ref max_flow "flow of maximum value" in a alpar@1074: /// digraph \cite clrs01algorithms, \cite amo93networkflows, alpar@1074: /// \cite edmondskarp72theoretical. kpeter@1057: /// The Edmonds-Karp algorithm is slower than the Preflow kpeter@1057: /// algorithm, but it has an advantage of the step-by-step execution thoneyvazul@1056: /// control with feasible flow solutions. The \e source node, the \e thoneyvazul@1056: /// target node, the \e capacity of the arcs and the \e starting \e thoneyvazul@1056: /// flow value of the arcs should be passed to the algorithm thoneyvazul@1056: /// through the constructor. thoneyvazul@1056: /// thoneyvazul@1056: /// The time complexity of the algorithm is \f$ O(nm^2) \f$ in kpeter@1057: /// worst case. Always try the Preflow algorithm instead of this if thoneyvazul@1056: /// you just want to compute the optimal flow. thoneyvazul@1056: /// kpeter@1057: /// \tparam GR The type of the digraph the algorithm runs on. kpeter@1057: /// \tparam CAP The type of the capacity map. The default map kpeter@1057: /// type is \ref concepts::Digraph::ArcMap "GR::ArcMap". kpeter@1057: /// \tparam TR The traits class that defines various types used by the kpeter@1057: /// algorithm. By default, it is \ref EdmondsKarpDefaultTraits kpeter@1057: /// "EdmondsKarpDefaultTraits". kpeter@1057: /// In most cases, this parameter should not be set directly, kpeter@1057: /// consider to use the named template parameters instead. thoneyvazul@1056: thoneyvazul@1056: #ifdef DOXYGEN thoneyvazul@1056: template thoneyvazul@1056: #else thoneyvazul@1056: template , thoneyvazul@1056: typename TR = EdmondsKarpDefaultTraits > thoneyvazul@1056: #endif thoneyvazul@1056: class EdmondsKarp { thoneyvazul@1056: public: thoneyvazul@1056: alpar@1074: /// \brief The \ref lemon::EdmondsKarpDefaultTraits "traits class" alpar@1074: /// of the algorithm. thoneyvazul@1056: typedef TR Traits; kpeter@1057: /// The type of the digraph the algorithm runs on. thoneyvazul@1056: typedef typename Traits::Digraph Digraph; kpeter@1057: /// The type of the capacity map. thoneyvazul@1056: typedef typename Traits::CapacityMap CapacityMap; kpeter@1057: /// The type of the flow values. thoneyvazul@1056: typedef typename Traits::Value Value; thoneyvazul@1056: kpeter@1057: /// The type of the flow map. thoneyvazul@1056: typedef typename Traits::FlowMap FlowMap; kpeter@1057: /// The type of the tolerance. thoneyvazul@1056: typedef typename Traits::Tolerance Tolerance; thoneyvazul@1056: thoneyvazul@1056: private: thoneyvazul@1056: thoneyvazul@1056: TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); thoneyvazul@1056: typedef typename Digraph::template NodeMap PredMap; thoneyvazul@1056: thoneyvazul@1056: const Digraph& _graph; thoneyvazul@1056: const CapacityMap* _capacity; thoneyvazul@1056: thoneyvazul@1056: Node _source, _target; thoneyvazul@1056: thoneyvazul@1056: FlowMap* _flow; thoneyvazul@1056: bool _local_flow; thoneyvazul@1056: thoneyvazul@1056: PredMap* _pred; thoneyvazul@1056: std::vector _queue; thoneyvazul@1056: thoneyvazul@1056: Tolerance _tolerance; thoneyvazul@1056: Value _flow_value; thoneyvazul@1056: thoneyvazul@1056: void createStructures() { thoneyvazul@1056: if (!_flow) { thoneyvazul@1056: _flow = Traits::createFlowMap(_graph); thoneyvazul@1056: _local_flow = true; thoneyvazul@1056: } thoneyvazul@1056: if (!_pred) { thoneyvazul@1056: _pred = new PredMap(_graph); thoneyvazul@1056: } thoneyvazul@1056: _queue.resize(countNodes(_graph)); thoneyvazul@1056: } thoneyvazul@1056: thoneyvazul@1056: void destroyStructures() { thoneyvazul@1056: if (_local_flow) { thoneyvazul@1056: delete _flow; thoneyvazul@1056: } thoneyvazul@1056: if (_pred) { thoneyvazul@1056: delete _pred; thoneyvazul@1056: } thoneyvazul@1056: } thoneyvazul@1056: thoneyvazul@1056: public: thoneyvazul@1056: kpeter@1060: typedef EdmondsKarp Create; kpeter@1060: thoneyvazul@1056: ///\name Named template parameters thoneyvazul@1056: thoneyvazul@1056: ///@{ thoneyvazul@1056: thoneyvazul@1056: template kpeter@1058: struct SetFlowMapTraits : public Traits { thoneyvazul@1056: typedef T FlowMap; thoneyvazul@1056: static FlowMap *createFlowMap(const Digraph&) { kpeter@1057: LEMON_ASSERT(false, "FlowMap is not initialized"); thoneyvazul@1056: return 0; thoneyvazul@1056: } thoneyvazul@1056: }; thoneyvazul@1056: thoneyvazul@1056: /// \brief \ref named-templ-param "Named parameter" for setting thoneyvazul@1056: /// FlowMap type thoneyvazul@1056: /// thoneyvazul@1056: /// \ref named-templ-param "Named parameter" for setting FlowMap thoneyvazul@1056: /// type thoneyvazul@1056: template kpeter@1058: struct SetFlowMap kpeter@1058: : public EdmondsKarp > { kpeter@1058: typedef EdmondsKarp > Create; thoneyvazul@1056: }; thoneyvazul@1056: thoneyvazul@1056: /// @} thoneyvazul@1056: thoneyvazul@1056: protected: thoneyvazul@1056: thoneyvazul@1056: EdmondsKarp() {} thoneyvazul@1056: thoneyvazul@1056: public: thoneyvazul@1056: thoneyvazul@1056: /// \brief The constructor of the class. thoneyvazul@1056: /// thoneyvazul@1056: /// The constructor of the class. thoneyvazul@1056: /// \param digraph The digraph the algorithm runs on. thoneyvazul@1056: /// \param capacity The capacity of the arcs. thoneyvazul@1056: /// \param source The source node. thoneyvazul@1056: /// \param target The target node. thoneyvazul@1056: EdmondsKarp(const Digraph& digraph, const CapacityMap& capacity, thoneyvazul@1056: Node source, Node target) thoneyvazul@1056: : _graph(digraph), _capacity(&capacity), _source(source), _target(target), thoneyvazul@1056: _flow(0), _local_flow(false), _pred(0), _tolerance(), _flow_value() thoneyvazul@1056: { kpeter@1057: LEMON_ASSERT(_source != _target, kpeter@1057: "Flow source and target are the same nodes."); thoneyvazul@1056: } thoneyvazul@1056: thoneyvazul@1056: /// \brief Destructor. thoneyvazul@1056: /// thoneyvazul@1056: /// Destructor. thoneyvazul@1056: ~EdmondsKarp() { thoneyvazul@1056: destroyStructures(); thoneyvazul@1056: } thoneyvazul@1056: thoneyvazul@1056: /// \brief Sets the capacity map. thoneyvazul@1056: /// thoneyvazul@1056: /// Sets the capacity map. kpeter@1057: /// \return (*this) thoneyvazul@1056: EdmondsKarp& capacityMap(const CapacityMap& map) { thoneyvazul@1056: _capacity = ↦ thoneyvazul@1056: return *this; thoneyvazul@1056: } thoneyvazul@1056: thoneyvazul@1056: /// \brief Sets the flow map. thoneyvazul@1056: /// thoneyvazul@1056: /// Sets the flow map. kpeter@1057: /// If you don't use this function before calling \ref run() or kpeter@1057: /// \ref init(), an instance will be allocated automatically. kpeter@1057: /// The destructor deallocates this automatically allocated map, kpeter@1057: /// of course. kpeter@1057: /// \return (*this) thoneyvazul@1056: EdmondsKarp& flowMap(FlowMap& map) { thoneyvazul@1056: if (_local_flow) { thoneyvazul@1056: delete _flow; thoneyvazul@1056: _local_flow = false; thoneyvazul@1056: } thoneyvazul@1056: _flow = ↦ thoneyvazul@1056: return *this; thoneyvazul@1056: } thoneyvazul@1056: thoneyvazul@1056: /// \brief Sets the source node. thoneyvazul@1056: /// thoneyvazul@1056: /// Sets the source node. kpeter@1057: /// \return (*this) thoneyvazul@1056: EdmondsKarp& source(const Node& node) { thoneyvazul@1056: _source = node; thoneyvazul@1056: return *this; thoneyvazul@1056: } thoneyvazul@1056: thoneyvazul@1056: /// \brief Sets the target node. thoneyvazul@1056: /// thoneyvazul@1056: /// Sets the target node. kpeter@1057: /// \return (*this) thoneyvazul@1056: EdmondsKarp& target(const Node& node) { thoneyvazul@1056: _target = node; thoneyvazul@1056: return *this; thoneyvazul@1056: } thoneyvazul@1056: thoneyvazul@1056: /// \brief Sets the tolerance used by algorithm. thoneyvazul@1056: /// thoneyvazul@1056: /// Sets the tolerance used by algorithm. kpeter@1057: /// \return (*this) thoneyvazul@1056: EdmondsKarp& tolerance(const Tolerance& tolerance) { thoneyvazul@1056: _tolerance = tolerance; thoneyvazul@1056: return *this; thoneyvazul@1056: } thoneyvazul@1056: kpeter@1057: /// \brief Returns a const reference to the tolerance. thoneyvazul@1056: /// kpeter@1057: /// Returns a const reference to the tolerance object used by kpeter@1057: /// the algorithm. thoneyvazul@1056: const Tolerance& tolerance() const { thoneyvazul@1056: return _tolerance; thoneyvazul@1056: } thoneyvazul@1056: thoneyvazul@1056: /// \name Execution control kpeter@1057: /// The simplest way to execute the algorithm is to use \ref run().\n kpeter@1057: /// If you need better control on the initial solution or the execution, kpeter@1057: /// you have to call one of the \ref init() functions first, then kpeter@1057: /// \ref start() or multiple times the \ref augment() function. thoneyvazul@1056: thoneyvazul@1056: ///@{ thoneyvazul@1056: kpeter@1057: /// \brief Initializes the algorithm. kpeter@1057: /// kpeter@1057: /// Initializes the internal data structures and sets the initial kpeter@1057: /// flow to zero on each arc. thoneyvazul@1056: void init() { thoneyvazul@1056: createStructures(); thoneyvazul@1056: for (ArcIt it(_graph); it != INVALID; ++it) { thoneyvazul@1056: _flow->set(it, 0); thoneyvazul@1056: } thoneyvazul@1056: _flow_value = 0; thoneyvazul@1056: } thoneyvazul@1056: kpeter@1057: /// \brief Initializes the algorithm using the given flow map. kpeter@1057: /// kpeter@1057: /// Initializes the internal data structures and sets the initial kpeter@1057: /// flow to the given \c flowMap. The \c flowMap should kpeter@1057: /// contain a feasible flow, i.e. at each node excluding the source kpeter@1057: /// and the target, the incoming flow should be equal to the thoneyvazul@1056: /// outgoing flow. thoneyvazul@1056: template kpeter@1059: void init(const FlowMap& flowMap) { thoneyvazul@1056: createStructures(); thoneyvazul@1056: for (ArcIt e(_graph); e != INVALID; ++e) { thoneyvazul@1056: _flow->set(e, flowMap[e]); thoneyvazul@1056: } thoneyvazul@1056: _flow_value = 0; thoneyvazul@1056: for (OutArcIt jt(_graph, _source); jt != INVALID; ++jt) { thoneyvazul@1056: _flow_value += (*_flow)[jt]; thoneyvazul@1056: } thoneyvazul@1056: for (InArcIt jt(_graph, _source); jt != INVALID; ++jt) { thoneyvazul@1056: _flow_value -= (*_flow)[jt]; thoneyvazul@1056: } thoneyvazul@1056: } thoneyvazul@1056: kpeter@1057: /// \brief Initializes the algorithm using the given flow map. kpeter@1057: /// kpeter@1057: /// Initializes the internal data structures and sets the initial kpeter@1057: /// flow to the given \c flowMap. The \c flowMap should kpeter@1057: /// contain a feasible flow, i.e. at each node excluding the source kpeter@1057: /// and the target, the incoming flow should be equal to the kpeter@1057: /// outgoing flow. kpeter@1057: /// \return \c false when the given \c flowMap does not contain a thoneyvazul@1056: /// feasible flow. thoneyvazul@1056: template kpeter@1059: bool checkedInit(const FlowMap& flowMap) { thoneyvazul@1056: createStructures(); thoneyvazul@1056: for (ArcIt e(_graph); e != INVALID; ++e) { thoneyvazul@1056: _flow->set(e, flowMap[e]); thoneyvazul@1056: } thoneyvazul@1056: for (NodeIt it(_graph); it != INVALID; ++it) { thoneyvazul@1056: if (it == _source || it == _target) continue; thoneyvazul@1056: Value outFlow = 0; thoneyvazul@1056: for (OutArcIt jt(_graph, it); jt != INVALID; ++jt) { thoneyvazul@1056: outFlow += (*_flow)[jt]; thoneyvazul@1056: } thoneyvazul@1056: Value inFlow = 0; thoneyvazul@1056: for (InArcIt jt(_graph, it); jt != INVALID; ++jt) { thoneyvazul@1056: inFlow += (*_flow)[jt]; thoneyvazul@1056: } thoneyvazul@1056: if (_tolerance.different(outFlow, inFlow)) { thoneyvazul@1056: return false; thoneyvazul@1056: } thoneyvazul@1056: } thoneyvazul@1056: for (ArcIt it(_graph); it != INVALID; ++it) { thoneyvazul@1056: if (_tolerance.less((*_flow)[it], 0)) return false; thoneyvazul@1056: if (_tolerance.less((*_capacity)[it], (*_flow)[it])) return false; thoneyvazul@1056: } thoneyvazul@1056: _flow_value = 0; thoneyvazul@1056: for (OutArcIt jt(_graph, _source); jt != INVALID; ++jt) { thoneyvazul@1056: _flow_value += (*_flow)[jt]; thoneyvazul@1056: } thoneyvazul@1056: for (InArcIt jt(_graph, _source); jt != INVALID; ++jt) { thoneyvazul@1056: _flow_value -= (*_flow)[jt]; thoneyvazul@1056: } thoneyvazul@1056: return true; thoneyvazul@1056: } thoneyvazul@1056: kpeter@1057: /// \brief Augments the solution along a shortest path. thoneyvazul@1056: /// kpeter@1057: /// Augments the solution along a shortest path. This function searches a kpeter@1057: /// shortest path between the source and the target kpeter@1057: /// in the residual digraph by the Bfs algoritm. thoneyvazul@1056: /// Then it increases the flow on this path with the minimal residual kpeter@1057: /// capacity on the path. If there is no such path, it gives back thoneyvazul@1056: /// false. kpeter@1057: /// \return \c false when the augmenting did not success, i.e. the thoneyvazul@1056: /// current flow is a feasible and optimal solution. thoneyvazul@1056: bool augment() { thoneyvazul@1056: for (NodeIt n(_graph); n != INVALID; ++n) { thoneyvazul@1056: _pred->set(n, INVALID); thoneyvazul@1056: } thoneyvazul@1056: thoneyvazul@1056: int first = 0, last = 1; thoneyvazul@1056: thoneyvazul@1056: _queue[0] = _source; thoneyvazul@1056: _pred->set(_source, OutArcIt(_graph, _source)); thoneyvazul@1056: thoneyvazul@1056: while (first != last && (*_pred)[_target] == INVALID) { thoneyvazul@1056: Node n = _queue[first++]; thoneyvazul@1056: thoneyvazul@1056: for (OutArcIt e(_graph, n); e != INVALID; ++e) { thoneyvazul@1056: Value rem = (*_capacity)[e] - (*_flow)[e]; thoneyvazul@1056: Node t = _graph.target(e); thoneyvazul@1056: if (_tolerance.positive(rem) && (*_pred)[t] == INVALID) { thoneyvazul@1056: _pred->set(t, e); thoneyvazul@1056: _queue[last++] = t; thoneyvazul@1056: } thoneyvazul@1056: } thoneyvazul@1056: for (InArcIt e(_graph, n); e != INVALID; ++e) { thoneyvazul@1056: Value rem = (*_flow)[e]; thoneyvazul@1056: Node t = _graph.source(e); thoneyvazul@1056: if (_tolerance.positive(rem) && (*_pred)[t] == INVALID) { thoneyvazul@1056: _pred->set(t, e); thoneyvazul@1056: _queue[last++] = t; thoneyvazul@1056: } thoneyvazul@1056: } thoneyvazul@1056: } thoneyvazul@1056: thoneyvazul@1056: if ((*_pred)[_target] != INVALID) { thoneyvazul@1056: Node n = _target; thoneyvazul@1056: Arc e = (*_pred)[n]; thoneyvazul@1056: thoneyvazul@1056: Value prem = (*_capacity)[e] - (*_flow)[e]; thoneyvazul@1056: n = _graph.source(e); thoneyvazul@1056: while (n != _source) { thoneyvazul@1056: e = (*_pred)[n]; thoneyvazul@1056: if (_graph.target(e) == n) { thoneyvazul@1056: Value rem = (*_capacity)[e] - (*_flow)[e]; thoneyvazul@1056: if (rem < prem) prem = rem; thoneyvazul@1056: n = _graph.source(e); thoneyvazul@1056: } else { thoneyvazul@1056: Value rem = (*_flow)[e]; thoneyvazul@1056: if (rem < prem) prem = rem; thoneyvazul@1056: n = _graph.target(e); thoneyvazul@1056: } thoneyvazul@1056: } thoneyvazul@1056: thoneyvazul@1056: n = _target; thoneyvazul@1056: e = (*_pred)[n]; thoneyvazul@1056: thoneyvazul@1056: _flow->set(e, (*_flow)[e] + prem); thoneyvazul@1056: n = _graph.source(e); thoneyvazul@1056: while (n != _source) { thoneyvazul@1056: e = (*_pred)[n]; thoneyvazul@1056: if (_graph.target(e) == n) { thoneyvazul@1056: _flow->set(e, (*_flow)[e] + prem); thoneyvazul@1056: n = _graph.source(e); thoneyvazul@1056: } else { thoneyvazul@1056: _flow->set(e, (*_flow)[e] - prem); thoneyvazul@1056: n = _graph.target(e); thoneyvazul@1056: } thoneyvazul@1056: } thoneyvazul@1056: thoneyvazul@1056: _flow_value += prem; thoneyvazul@1056: return true; thoneyvazul@1056: } else { thoneyvazul@1056: return false; thoneyvazul@1056: } thoneyvazul@1056: } thoneyvazul@1056: thoneyvazul@1056: /// \brief Executes the algorithm thoneyvazul@1056: /// kpeter@1057: /// Executes the algorithm by performing augmenting phases until the kpeter@1057: /// optimal solution is reached. kpeter@1057: /// \pre One of the \ref init() functions must be called before kpeter@1057: /// using this function. thoneyvazul@1056: void start() { thoneyvazul@1056: while (augment()) {} thoneyvazul@1056: } thoneyvazul@1056: thoneyvazul@1056: /// \brief Runs the algorithm. thoneyvazul@1056: /// kpeter@1057: /// Runs the Edmonds-Karp algorithm. kpeter@1057: /// \note ek.run() is just a shortcut of the following code. thoneyvazul@1056: ///\code thoneyvazul@1056: /// ek.init(); thoneyvazul@1056: /// ek.start(); thoneyvazul@1056: ///\endcode thoneyvazul@1056: void run() { thoneyvazul@1056: init(); thoneyvazul@1056: start(); thoneyvazul@1056: } thoneyvazul@1056: thoneyvazul@1056: /// @} thoneyvazul@1056: thoneyvazul@1056: /// \name Query Functions thoneyvazul@1056: /// The result of the Edmonds-Karp algorithm can be obtained using these thoneyvazul@1056: /// functions.\n kpeter@1057: /// Either \ref run() or \ref start() should be called before using them. thoneyvazul@1056: thoneyvazul@1056: ///@{ thoneyvazul@1056: thoneyvazul@1056: /// \brief Returns the value of the maximum flow. thoneyvazul@1056: /// kpeter@1057: /// Returns the value of the maximum flow found by the algorithm. kpeter@1057: /// kpeter@1057: /// \pre Either \ref run() or \ref init() must be called before kpeter@1057: /// using this function. thoneyvazul@1056: Value flowValue() const { thoneyvazul@1056: return _flow_value; thoneyvazul@1056: } thoneyvazul@1056: kpeter@1057: /// \brief Returns the flow value on the given arc. thoneyvazul@1056: /// kpeter@1057: /// Returns the flow value on the given arc. kpeter@1057: /// kpeter@1057: /// \pre Either \ref run() or \ref init() must be called before kpeter@1057: /// using this function. thoneyvazul@1056: Value flow(const Arc& arc) const { thoneyvazul@1056: return (*_flow)[arc]; thoneyvazul@1056: } thoneyvazul@1056: kpeter@1057: /// \brief Returns a const reference to the flow map. thoneyvazul@1056: /// kpeter@1057: /// Returns a const reference to the arc map storing the found flow. kpeter@1057: /// kpeter@1057: /// \pre Either \ref run() or \ref init() must be called before kpeter@1057: /// using this function. kpeter@1057: const FlowMap& flowMap() const { kpeter@1057: return *_flow; kpeter@1057: } thoneyvazul@1056: kpeter@1057: /// \brief Returns \c true when the node is on the source side of the kpeter@1057: /// minimum cut. kpeter@1057: /// kpeter@1057: /// Returns true when the node is on the source side of the found kpeter@1057: /// minimum cut. kpeter@1057: /// kpeter@1057: /// \pre Either \ref run() or \ref init() must be called before kpeter@1057: /// using this function. thoneyvazul@1056: bool minCut(const Node& node) const { kpeter@1061: return ((*_pred)[node] != INVALID) || node == _source; thoneyvazul@1056: } thoneyvazul@1056: kpeter@1057: /// \brief Gives back a minimum value cut. thoneyvazul@1056: /// kpeter@1057: /// Sets \c cutMap to the characteristic vector of a minimum value kpeter@1057: /// cut. \c cutMap should be a \ref concepts::WriteMap "writable" kpeter@1057: /// node map with \c bool (or convertible) value type. kpeter@1057: /// kpeter@1057: /// \note This function calls \ref minCut() for each node, so it runs in kpeter@1057: /// O(n) time. kpeter@1057: /// kpeter@1057: /// \pre Either \ref run() or \ref init() must be called before kpeter@1057: /// using this function. thoneyvazul@1056: template thoneyvazul@1056: void minCutMap(CutMap& cutMap) const { thoneyvazul@1056: for (NodeIt n(_graph); n != INVALID; ++n) { thoneyvazul@1056: cutMap.set(n, (*_pred)[n] != INVALID); thoneyvazul@1056: } thoneyvazul@1056: cutMap.set(_source, true); thoneyvazul@1056: } thoneyvazul@1056: thoneyvazul@1056: /// @} thoneyvazul@1056: thoneyvazul@1056: }; thoneyvazul@1056: thoneyvazul@1056: } thoneyvazul@1056: thoneyvazul@1056: #endif