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: thoneyvazul@1056: /// \brief The type of the length of the arcs. thoneyvazul@1056: typedef typename CapacityMap::Value Value; thoneyvazul@1056: thoneyvazul@1056: /// \brief The map type that stores the flow values. thoneyvazul@1056: /// thoneyvazul@1056: /// The map type that stores the flow values. thoneyvazul@1056: /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. thoneyvazul@1056: typedef typename Digraph::template ArcMap FlowMap; thoneyvazul@1056: thoneyvazul@1056: /// \brief Instantiates a FlowMap. thoneyvazul@1056: /// thoneyvazul@1056: /// This function instantiates a \ref FlowMap. thoneyvazul@1056: /// \param digraph The digraph, to which we would like to define 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 thoneyvazul@1056: /// algorithm producing a flow of maximum value in directed thoneyvazul@1056: /// digraphs. The Edmonds-Karp algorithm is slower than the Preflow thoneyvazul@1056: /// 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 thoneyvazul@1056: /// worst case. Always try the preflow algorithm instead of this if thoneyvazul@1056: /// you just want to compute the optimal flow. thoneyvazul@1056: /// thoneyvazul@1056: /// \param GR The digraph type the algorithm runs on. thoneyvazul@1056: /// \param CAP The capacity map type. thoneyvazul@1056: /// \param TR Traits class to set various data types used by thoneyvazul@1056: /// the algorithm. The default traits class is \ref thoneyvazul@1056: /// EdmondsKarpDefaultTraits. See \ref EdmondsKarpDefaultTraits for the thoneyvazul@1056: /// documentation of a Edmonds-Karp traits class. 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: thoneyvazul@1056: typedef TR Traits; thoneyvazul@1056: typedef typename Traits::Digraph Digraph; thoneyvazul@1056: typedef typename Traits::CapacityMap CapacityMap; thoneyvazul@1056: typedef typename Traits::Value Value; thoneyvazul@1056: thoneyvazul@1056: typedef typename Traits::FlowMap FlowMap; 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: thoneyvazul@1056: ///\name Named template parameters thoneyvazul@1056: thoneyvazul@1056: ///@{ thoneyvazul@1056: thoneyvazul@1056: template thoneyvazul@1056: struct DefFlowMapTraits : public Traits { thoneyvazul@1056: typedef T FlowMap; thoneyvazul@1056: static FlowMap *createFlowMap(const Digraph&) { thoneyvazul@1056: LEMON_ASSERT(false,"Uninitialized parameter."); 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 thoneyvazul@1056: struct DefFlowMap thoneyvazul@1056: : public EdmondsKarp > { thoneyvazul@1056: typedef EdmondsKarp > thoneyvazul@1056: Create; thoneyvazul@1056: }; 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: { thoneyvazul@1056: LEMON_ASSERT(_source != _target,"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. thoneyvazul@1056: /// \return \c (*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. thoneyvazul@1056: /// \return \c (*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 Returns the flow map. thoneyvazul@1056: /// thoneyvazul@1056: /// \return The flow map. thoneyvazul@1056: const FlowMap& flowMap() const { thoneyvazul@1056: return *_flow; thoneyvazul@1056: } thoneyvazul@1056: thoneyvazul@1056: /// \brief Sets the source node. thoneyvazul@1056: /// thoneyvazul@1056: /// Sets the source node. thoneyvazul@1056: /// \return \c (*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. thoneyvazul@1056: /// \return \c (*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. thoneyvazul@1056: EdmondsKarp& tolerance(const Tolerance& tolerance) { thoneyvazul@1056: _tolerance = tolerance; thoneyvazul@1056: return *this; thoneyvazul@1056: } thoneyvazul@1056: thoneyvazul@1056: /// \brief Returns the tolerance used by algorithm. thoneyvazul@1056: /// thoneyvazul@1056: /// Returns the tolerance used by algorithm. thoneyvazul@1056: const Tolerance& tolerance() const { thoneyvazul@1056: return _tolerance; thoneyvazul@1056: } thoneyvazul@1056: thoneyvazul@1056: /// \name Execution control thoneyvazul@1056: /// The simplest way to execute the thoneyvazul@1056: /// algorithm is to use the \c run() member functions. thoneyvazul@1056: /// \n thoneyvazul@1056: /// If you need more control on initial solution or thoneyvazul@1056: /// execution then you have to call one \ref init() function and then thoneyvazul@1056: /// the start() or multiple times the \c augment() member function. thoneyvazul@1056: thoneyvazul@1056: ///@{ thoneyvazul@1056: thoneyvazul@1056: /// \brief Initializes the algorithm thoneyvazul@1056: /// thoneyvazul@1056: /// Sets the flow to empty flow. 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: thoneyvazul@1056: /// \brief Initializes the algorithm thoneyvazul@1056: /// thoneyvazul@1056: /// Initializes the flow to the \c flowMap. The \c flowMap should thoneyvazul@1056: /// contain a feasible flow, ie. in each node excluding the source thoneyvazul@1056: /// and the target the incoming flow should be equal to the thoneyvazul@1056: /// outgoing flow. thoneyvazul@1056: template thoneyvazul@1056: void flowInit(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: thoneyvazul@1056: /// \brief Initializes the algorithm thoneyvazul@1056: /// thoneyvazul@1056: /// Initializes the flow to the \c flowMap. The \c flowMap should thoneyvazul@1056: /// contain a feasible flow, ie. in each node excluding the source thoneyvazul@1056: /// and the target the incoming flow should be equal to the thoneyvazul@1056: /// outgoing flow. thoneyvazul@1056: /// \return %False when the given flowMap does not contain thoneyvazul@1056: /// feasible flow. thoneyvazul@1056: template thoneyvazul@1056: bool checkedFlowInit(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: thoneyvazul@1056: /// \brief Augment the solution on an arc shortest path. thoneyvazul@1056: /// thoneyvazul@1056: /// Augment the solution on an arc shortest path. It searches an thoneyvazul@1056: /// arc shortest path between the source and the target thoneyvazul@1056: /// in the residual digraph by the bfs algoritm. thoneyvazul@1056: /// Then it increases the flow on this path with the minimal residual thoneyvazul@1056: /// capacity on the path. If there is no such path it gives back thoneyvazul@1056: /// false. thoneyvazul@1056: /// \return %False when the augmenting didn't success so 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: /// thoneyvazul@1056: /// It runs augmenting phases until the optimal solution is reached. thoneyvazul@1056: void start() { thoneyvazul@1056: while (augment()) {} thoneyvazul@1056: } thoneyvazul@1056: thoneyvazul@1056: /// \brief Runs the algorithm. thoneyvazul@1056: /// thoneyvazul@1056: /// It is just a shorthand for: thoneyvazul@1056: /// 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 thoneyvazul@1056: /// Before the use of these functions, thoneyvazul@1056: /// either run() or start() must be called. thoneyvazul@1056: thoneyvazul@1056: ///@{ thoneyvazul@1056: thoneyvazul@1056: /// \brief Returns the value of the maximum flow. thoneyvazul@1056: /// thoneyvazul@1056: /// Returns the value of the maximum flow by returning the excess thoneyvazul@1056: /// of the target node \c t. thoneyvazul@1056: thoneyvazul@1056: Value flowValue() const { thoneyvazul@1056: return _flow_value; thoneyvazul@1056: } thoneyvazul@1056: thoneyvazul@1056: thoneyvazul@1056: /// \brief Returns the flow on the arc. thoneyvazul@1056: /// thoneyvazul@1056: /// Sets the \c flowMap to the flow on the arcs. thoneyvazul@1056: Value flow(const Arc& arc) const { thoneyvazul@1056: return (*_flow)[arc]; thoneyvazul@1056: } thoneyvazul@1056: thoneyvazul@1056: /// \brief Returns true when the node is on the source side of minimum cut. thoneyvazul@1056: /// thoneyvazul@1056: thoneyvazul@1056: /// Returns true when the node is on the source side of minimum thoneyvazul@1056: /// cut. thoneyvazul@1056: thoneyvazul@1056: bool minCut(const Node& node) const { thoneyvazul@1056: return ((*_pred)[node] != INVALID) or node == _source; thoneyvazul@1056: } thoneyvazul@1056: thoneyvazul@1056: /// \brief Returns a minimum value cut. thoneyvazul@1056: /// thoneyvazul@1056: /// Sets \c cutMap to the characteristic vector of a minimum value cut. thoneyvazul@1056: 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