deba@913: /* -*- mode: C++; indent-tabs-mode: nil; -*- deba@913: * deba@913: * This file is a part of LEMON, a generic C++ optimization library. deba@913: * alpar@1092: * Copyright (C) 2003-2013 deba@913: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport deba@913: * (Egervary Research Group on Combinatorial Optimization, EGRES). deba@913: * deba@913: * Permission to use, modify and distribute this software is granted deba@913: * provided that this copyright notice appears in all copies. For deba@913: * precise terms see the accompanying LICENSE file. deba@913: * deba@913: * This software is provided "AS IS" with no warranty of any kind, deba@913: * express or implied, and with no claim as to its suitability for any deba@913: * purpose. deba@913: * deba@913: */ deba@913: deba@913: #ifndef LEMON_NAGAMOCHI_IBARAKI_H deba@913: #define LEMON_NAGAMOCHI_IBARAKI_H deba@913: deba@913: deba@913: /// \ingroup min_cut deba@913: /// \file deba@913: /// \brief Implementation of the Nagamochi-Ibaraki algorithm. deba@913: deba@913: #include deba@913: #include deba@913: #include deba@913: #include deba@913: #include deba@913: #include deba@913: deba@913: #include deba@913: deba@913: namespace lemon { deba@913: deba@913: /// \brief Default traits class for NagamochiIbaraki class. deba@913: /// deba@913: /// Default traits class for NagamochiIbaraki class. deba@913: /// \param GR The undirected graph type. deba@913: /// \param CM Type of capacity map. deba@913: template deba@913: struct NagamochiIbarakiDefaultTraits { deba@913: /// The type of the capacity map. deba@913: typedef typename CM::Value Value; deba@913: deba@913: /// The undirected graph type the algorithm runs on. deba@913: typedef GR Graph; deba@913: deba@913: /// \brief The type of the map that stores the edge capacities. deba@913: /// deba@913: /// The type of the map that stores the edge capacities. deba@913: /// It must meet the \ref concepts::ReadMap "ReadMap" concept. deba@913: typedef CM CapacityMap; deba@913: deba@913: /// \brief Instantiates a CapacityMap. deba@913: /// deba@913: /// This function instantiates a \ref CapacityMap. deba@913: #ifdef DOXYGEN deba@913: static CapacityMap *createCapacityMap(const Graph& graph) deba@913: #else deba@913: static CapacityMap *createCapacityMap(const Graph&) deba@913: #endif deba@913: { deba@913: LEMON_ASSERT(false, "CapacityMap is not initialized"); deba@913: return 0; // ignore warnings deba@913: } deba@913: deba@913: /// \brief The cross reference type used by heap. deba@913: /// deba@913: /// The cross reference type used by heap. deba@913: /// Usually \c Graph::NodeMap. deba@913: typedef typename Graph::template NodeMap HeapCrossRef; deba@913: deba@913: /// \brief Instantiates a HeapCrossRef. deba@913: /// deba@913: /// This function instantiates a \ref HeapCrossRef. deba@913: /// \param g is the graph, to which we would like to define the deba@913: /// \ref HeapCrossRef. deba@913: static HeapCrossRef *createHeapCrossRef(const Graph& g) { deba@913: return new HeapCrossRef(g); deba@913: } deba@913: deba@913: /// \brief The heap type used by NagamochiIbaraki algorithm. deba@913: /// deba@913: /// The heap type used by NagamochiIbaraki algorithm. It has to deba@913: /// maximize the priorities. deba@913: /// deba@913: /// \sa BinHeap deba@913: /// \sa NagamochiIbaraki deba@913: typedef BinHeap > Heap; deba@913: deba@913: /// \brief Instantiates a Heap. deba@913: /// deba@913: /// This function instantiates a \ref Heap. deba@913: /// \param r is the cross reference of the heap. deba@913: static Heap *createHeap(HeapCrossRef& r) { deba@913: return new Heap(r); deba@913: } deba@913: }; deba@913: deba@913: /// \ingroup min_cut deba@913: /// deba@913: /// \brief Calculates the minimum cut in an undirected graph. deba@913: /// deba@913: /// Calculates the minimum cut in an undirected graph with the deba@913: /// Nagamochi-Ibaraki algorithm. The algorithm separates the graph's deba@913: /// nodes into two partitions with the minimum sum of edge capacities deba@913: /// between the two partitions. The algorithm can be used to test deba@913: /// the network reliability, especially to test how many links have deba@913: /// to be destroyed in the network to split it to at least two deba@913: /// distinict subnetworks. deba@913: /// deba@913: /// The complexity of the algorithm is \f$ O(nm\log(n)) \f$ but with deba@913: /// \ref FibHeap "Fibonacci heap" it can be decreased to deba@913: /// \f$ O(nm+n^2\log(n)) \f$. When the edges have unit capacities, deba@913: /// \c BucketHeap can be used which yields \f$ O(nm) \f$ time deba@913: /// complexity. deba@913: /// deba@913: /// \warning The value type of the capacity map should be able to deba@913: /// hold any cut value of the graph, otherwise the result can deba@913: /// overflow. deba@913: /// \note This capacity is supposed to be integer type. deba@913: #ifdef DOXYGEN deba@913: template deba@913: #else deba@913: template , deba@913: typename TR = NagamochiIbarakiDefaultTraits > deba@913: #endif deba@913: class NagamochiIbaraki { deba@913: public: deba@913: deba@913: typedef TR Traits; deba@913: /// The type of the underlying graph. deba@913: typedef typename Traits::Graph Graph; deba@913: deba@913: /// The type of the capacity map. deba@913: typedef typename Traits::CapacityMap CapacityMap; deba@913: /// The value type of the capacity map. deba@913: typedef typename Traits::CapacityMap::Value Value; deba@913: deba@913: /// The heap type used by the algorithm. deba@913: typedef typename Traits::Heap Heap; deba@913: /// The cross reference type used for the heap. deba@913: typedef typename Traits::HeapCrossRef HeapCrossRef; deba@913: deba@913: ///\name Named template parameters deba@913: deba@913: ///@{ deba@913: deba@913: struct SetUnitCapacityTraits : public Traits { deba@913: typedef ConstMap > CapacityMap; deba@913: static CapacityMap *createCapacityMap(const Graph&) { deba@913: return new CapacityMap(); deba@913: } deba@913: }; deba@913: deba@913: /// \brief \ref named-templ-param "Named parameter" for setting deba@913: /// the capacity map to a constMap() instance deba@913: /// deba@913: /// \ref named-templ-param "Named parameter" for setting deba@913: /// the capacity map to a constMap() instance deba@913: struct SetUnitCapacity deba@913: : public NagamochiIbaraki { deba@913: typedef NagamochiIbaraki Create; deba@913: }; deba@913: deba@913: deba@913: template deba@913: struct SetHeapTraits : public Traits { deba@913: typedef CR HeapCrossRef; deba@913: typedef H Heap; kpeter@1197: static HeapCrossRef *createHeapCrossRef(int) { deba@913: LEMON_ASSERT(false, "HeapCrossRef is not initialized"); deba@913: return 0; // ignore warnings deba@913: } deba@913: static Heap *createHeap(HeapCrossRef &) { deba@913: LEMON_ASSERT(false, "Heap is not initialized"); deba@913: return 0; // ignore warnings deba@913: } deba@913: }; deba@913: deba@913: /// \brief \ref named-templ-param "Named parameter" for setting deba@913: /// heap and cross reference type deba@913: /// deba@913: /// \ref named-templ-param "Named parameter" for setting heap and deba@913: /// cross reference type. The heap has to maximize the priorities. deba@913: template > deba@913: struct SetHeap deba@913: : public NagamochiIbaraki > { deba@913: typedef NagamochiIbaraki< Graph, CapacityMap, SetHeapTraits > deba@913: Create; deba@913: }; deba@913: deba@913: template deba@913: struct SetStandardHeapTraits : public Traits { deba@913: typedef CR HeapCrossRef; deba@913: typedef H Heap; deba@913: static HeapCrossRef *createHeapCrossRef(int size) { deba@913: return new HeapCrossRef(size); deba@913: } deba@913: static Heap *createHeap(HeapCrossRef &crossref) { deba@913: return new Heap(crossref); deba@913: } deba@913: }; deba@913: deba@913: /// \brief \ref named-templ-param "Named parameter" for setting deba@913: /// heap and cross reference type with automatic allocation deba@913: /// deba@913: /// \ref named-templ-param "Named parameter" for setting heap and deba@913: /// cross reference type with automatic allocation. They should deba@913: /// have standard constructor interfaces to be able to deba@913: /// automatically created by the algorithm (i.e. the graph should deba@913: /// be passed to the constructor of the cross reference and the deba@913: /// cross reference should be passed to the constructor of the deba@913: /// heap). However, external heap and cross reference objects deba@913: /// could also be passed to the algorithm using the \ref heap() deba@913: /// function before calling \ref run() or \ref init(). The heap deba@913: /// has to maximize the priorities. deba@913: /// \sa SetHeap deba@913: template > deba@913: struct SetStandardHeap deba@913: : public NagamochiIbaraki > { deba@913: typedef NagamochiIbaraki > Create; deba@913: }; deba@913: deba@913: ///@} deba@913: deba@913: deba@913: private: deba@913: deba@913: const Graph &_graph; deba@913: const CapacityMap *_capacity; deba@913: bool _local_capacity; // unit capacity deba@913: deba@913: struct ArcData { deba@913: typename Graph::Node target; deba@913: int prev, next; deba@913: }; deba@913: struct EdgeData { deba@913: Value capacity; deba@913: Value cut; deba@913: }; deba@913: deba@913: struct NodeData { deba@913: int first_arc; deba@913: typename Graph::Node prev, next; deba@913: int curr_arc; deba@913: typename Graph::Node last_rep; deba@913: Value sum; deba@913: }; deba@913: deba@913: typename Graph::template NodeMap *_nodes; deba@913: std::vector _arcs; deba@913: std::vector _edges; deba@913: deba@913: typename Graph::Node _first_node; deba@913: int _node_num; deba@913: deba@913: Value _min_cut; deba@913: deba@913: HeapCrossRef *_heap_cross_ref; deba@913: bool _local_heap_cross_ref; deba@913: Heap *_heap; deba@913: bool _local_heap; deba@913: deba@913: typedef typename Graph::template NodeMap NodeList; deba@913: NodeList *_next_rep; deba@913: deba@913: typedef typename Graph::template NodeMap MinCutMap; deba@913: MinCutMap *_cut_map; deba@913: deba@913: void createStructures() { deba@913: if (!_nodes) { deba@913: _nodes = new (typename Graph::template NodeMap)(_graph); deba@913: } deba@913: if (!_capacity) { deba@913: _local_capacity = true; deba@913: _capacity = Traits::createCapacityMap(_graph); deba@913: } deba@913: if (!_heap_cross_ref) { deba@913: _local_heap_cross_ref = true; deba@913: _heap_cross_ref = Traits::createHeapCrossRef(_graph); deba@913: } deba@913: if (!_heap) { deba@913: _local_heap = true; deba@913: _heap = Traits::createHeap(*_heap_cross_ref); deba@913: } deba@913: if (!_next_rep) { deba@913: _next_rep = new NodeList(_graph); deba@913: } deba@913: if (!_cut_map) { deba@913: _cut_map = new MinCutMap(_graph); deba@913: } deba@913: } deba@913: alpar@978: protected: alpar@978: //This is here to avoid a gcc-3.3 compilation error. alpar@978: //It should never be called. alpar@1092: NagamochiIbaraki() {} alpar@1092: alpar@978: public: deba@913: deba@913: typedef NagamochiIbaraki Create; deba@913: deba@913: deba@913: /// \brief Constructor. deba@913: /// deba@913: /// \param graph The graph the algorithm runs on. deba@913: /// \param capacity The capacity map used by the algorithm. deba@913: NagamochiIbaraki(const Graph& graph, const CapacityMap& capacity) deba@913: : _graph(graph), _capacity(&capacity), _local_capacity(false), deba@913: _nodes(0), _arcs(), _edges(), _min_cut(), deba@913: _heap_cross_ref(0), _local_heap_cross_ref(false), deba@913: _heap(0), _local_heap(false), deba@913: _next_rep(0), _cut_map(0) {} deba@913: deba@913: /// \brief Constructor. deba@913: /// deba@913: /// This constructor can be used only when the Traits class deba@913: /// defines how can the local capacity map be instantiated. deba@913: /// If the SetUnitCapacity used the algorithm automatically deba@913: /// constructs the capacity map. deba@913: /// deba@913: ///\param graph The graph the algorithm runs on. deba@913: NagamochiIbaraki(const Graph& graph) deba@913: : _graph(graph), _capacity(0), _local_capacity(false), deba@913: _nodes(0), _arcs(), _edges(), _min_cut(), deba@913: _heap_cross_ref(0), _local_heap_cross_ref(false), deba@913: _heap(0), _local_heap(false), deba@913: _next_rep(0), _cut_map(0) {} deba@913: deba@913: /// \brief Destructor. deba@913: /// deba@913: /// Destructor. deba@913: ~NagamochiIbaraki() { deba@913: if (_local_capacity) delete _capacity; deba@913: if (_nodes) delete _nodes; deba@913: if (_local_heap) delete _heap; deba@913: if (_local_heap_cross_ref) delete _heap_cross_ref; deba@913: if (_next_rep) delete _next_rep; deba@913: if (_cut_map) delete _cut_map; deba@913: } deba@913: deba@913: /// \brief Sets the heap and the cross reference used by algorithm. deba@913: /// deba@913: /// Sets the heap and the cross reference used by algorithm. deba@913: /// If you don't use this function before calling \ref run(), deba@913: /// it will allocate one. The destuctor deallocates this deba@913: /// automatically allocated heap and cross reference, of course. deba@913: /// \return (*this) deba@913: NagamochiIbaraki &heap(Heap& hp, HeapCrossRef &cr) deba@913: { deba@913: if (_local_heap_cross_ref) { deba@913: delete _heap_cross_ref; deba@913: _local_heap_cross_ref = false; deba@913: } deba@913: _heap_cross_ref = &cr; deba@913: if (_local_heap) { deba@913: delete _heap; deba@913: _local_heap = false; deba@913: } deba@913: _heap = &hp; deba@913: return *this; deba@913: } deba@913: deba@913: /// \name Execution control deba@913: /// The simplest way to execute the algorithm is to use deba@913: /// one of the member functions called \c run(). deba@913: /// \n deba@913: /// If you need more control on the execution, deba@913: /// first you must call \ref init() and then call the start() deba@913: /// or proper times the processNextPhase() member functions. deba@913: deba@913: ///@{ deba@913: deba@913: /// \brief Initializes the internal data structures. deba@913: /// deba@913: /// Initializes the internal data structures. deba@913: void init() { deba@913: createStructures(); deba@913: deba@913: int edge_num = countEdges(_graph); deba@913: _edges.resize(edge_num); deba@913: _arcs.resize(2 * edge_num); deba@913: deba@913: typename Graph::Node prev = INVALID; deba@913: _node_num = 0; deba@913: for (typename Graph::NodeIt n(_graph); n != INVALID; ++n) { deba@913: (*_cut_map)[n] = false; deba@913: (*_next_rep)[n] = INVALID; deba@913: (*_nodes)[n].last_rep = n; deba@913: (*_nodes)[n].first_arc = -1; deba@913: (*_nodes)[n].curr_arc = -1; deba@913: (*_nodes)[n].prev = prev; deba@913: if (prev != INVALID) { deba@913: (*_nodes)[prev].next = n; deba@913: } deba@913: (*_nodes)[n].next = INVALID; deba@913: (*_nodes)[n].sum = 0; deba@913: prev = n; deba@913: ++_node_num; deba@913: } deba@913: deba@913: _first_node = typename Graph::NodeIt(_graph); deba@913: deba@913: int index = 0; deba@913: for (typename Graph::NodeIt n(_graph); n != INVALID; ++n) { deba@913: for (typename Graph::OutArcIt a(_graph, n); a != INVALID; ++a) { deba@913: typename Graph::Node m = _graph.target(a); alpar@1092: deba@913: if (!(n < m)) continue; deba@913: deba@913: (*_nodes)[n].sum += (*_capacity)[a]; deba@913: (*_nodes)[m].sum += (*_capacity)[a]; alpar@1092: deba@913: int c = (*_nodes)[m].curr_arc; deba@913: if (c != -1 && _arcs[c ^ 1].target == n) { deba@913: _edges[c >> 1].capacity += (*_capacity)[a]; deba@913: } else { deba@913: _edges[index].capacity = (*_capacity)[a]; alpar@1092: deba@913: _arcs[index << 1].prev = -1; deba@913: if ((*_nodes)[n].first_arc != -1) { deba@913: _arcs[(*_nodes)[n].first_arc].prev = (index << 1); deba@913: } deba@913: _arcs[index << 1].next = (*_nodes)[n].first_arc; deba@913: (*_nodes)[n].first_arc = (index << 1); deba@913: _arcs[index << 1].target = m; deba@913: deba@913: (*_nodes)[m].curr_arc = (index << 1); alpar@1092: deba@913: _arcs[(index << 1) | 1].prev = -1; deba@913: if ((*_nodes)[m].first_arc != -1) { deba@913: _arcs[(*_nodes)[m].first_arc].prev = ((index << 1) | 1); deba@913: } deba@913: _arcs[(index << 1) | 1].next = (*_nodes)[m].first_arc; deba@913: (*_nodes)[m].first_arc = ((index << 1) | 1); deba@913: _arcs[(index << 1) | 1].target = n; alpar@1092: deba@913: ++index; deba@913: } deba@913: } deba@913: } deba@913: deba@913: typename Graph::Node cut_node = INVALID; deba@913: _min_cut = std::numeric_limits::max(); deba@913: alpar@1092: for (typename Graph::Node n = _first_node; deba@913: n != INVALID; n = (*_nodes)[n].next) { deba@913: if ((*_nodes)[n].sum < _min_cut) { deba@913: cut_node = n; deba@913: _min_cut = (*_nodes)[n].sum; deba@913: } deba@913: } deba@913: (*_cut_map)[cut_node] = true; deba@913: if (_min_cut == 0) { deba@913: _first_node = INVALID; deba@913: } deba@913: } deba@913: deba@913: public: deba@913: deba@913: /// \brief Processes the next phase deba@913: /// deba@913: /// Processes the next phase in the algorithm. It must be called deba@913: /// at most one less the number of the nodes in the graph. deba@913: /// deba@913: ///\return %True when the algorithm finished. deba@913: bool processNextPhase() { deba@913: if (_first_node == INVALID) return true; deba@913: deba@913: _heap->clear(); alpar@1092: for (typename Graph::Node n = _first_node; deba@913: n != INVALID; n = (*_nodes)[n].next) { deba@913: (*_heap_cross_ref)[n] = Heap::PRE_HEAP; deba@913: } deba@913: deba@913: std::vector order; deba@913: order.reserve(_node_num); deba@913: int sep = 0; deba@913: deba@913: Value alpha = 0; deba@913: Value pmc = std::numeric_limits::max(); deba@913: deba@913: _heap->push(_first_node, static_cast(0)); deba@913: while (!_heap->empty()) { deba@913: typename Graph::Node n = _heap->top(); deba@913: Value v = _heap->prio(); deba@913: deba@913: _heap->pop(); deba@913: for (int a = (*_nodes)[n].first_arc; a != -1; a = _arcs[a].next) { deba@913: switch (_heap->state(_arcs[a].target)) { alpar@1092: case Heap::PRE_HEAP: deba@913: { deba@913: Value nv = _edges[a >> 1].capacity; deba@913: _heap->push(_arcs[a].target, nv); deba@913: _edges[a >> 1].cut = nv; deba@913: } break; deba@913: case Heap::IN_HEAP: deba@913: { deba@913: Value nv = _edges[a >> 1].capacity + (*_heap)[_arcs[a].target]; deba@913: _heap->decrease(_arcs[a].target, nv); deba@913: _edges[a >> 1].cut = nv; deba@913: } break; deba@913: case Heap::POST_HEAP: deba@913: break; deba@913: } deba@913: } deba@913: deba@913: alpha += (*_nodes)[n].sum; deba@913: alpha -= 2 * v; deba@913: deba@913: order.push_back(n); deba@913: if (!_heap->empty()) { deba@913: if (alpha < pmc) { deba@913: pmc = alpha; deba@913: sep = order.size(); deba@913: } deba@913: } deba@913: } deba@913: deba@913: if (static_cast(order.size()) < _node_num) { deba@913: _first_node = INVALID; deba@913: for (typename Graph::NodeIt n(_graph); n != INVALID; ++n) { deba@913: (*_cut_map)[n] = false; deba@913: } deba@913: for (int i = 0; i < static_cast(order.size()); ++i) { deba@913: typename Graph::Node n = order[i]; deba@913: while (n != INVALID) { deba@913: (*_cut_map)[n] = true; deba@913: n = (*_next_rep)[n]; deba@913: } deba@913: } deba@913: _min_cut = 0; deba@913: return true; deba@913: } deba@913: deba@913: if (pmc < _min_cut) { deba@913: for (typename Graph::NodeIt n(_graph); n != INVALID; ++n) { deba@913: (*_cut_map)[n] = false; deba@913: } deba@913: for (int i = 0; i < sep; ++i) { deba@913: typename Graph::Node n = order[i]; deba@913: while (n != INVALID) { deba@913: (*_cut_map)[n] = true; deba@913: n = (*_next_rep)[n]; deba@913: } deba@913: } deba@913: _min_cut = pmc; deba@913: } deba@913: deba@913: for (typename Graph::Node n = _first_node; deba@913: n != INVALID; n = (*_nodes)[n].next) { deba@913: bool merged = false; deba@913: for (int a = (*_nodes)[n].first_arc; a != -1; a = _arcs[a].next) { deba@913: if (!(_edges[a >> 1].cut < pmc)) { deba@913: if (!merged) { deba@913: for (int b = (*_nodes)[n].first_arc; b != -1; b = _arcs[b].next) { alpar@1092: (*_nodes)[_arcs[b].target].curr_arc = b; deba@913: } deba@913: merged = true; deba@913: } deba@913: typename Graph::Node m = _arcs[a].target; deba@913: int nb = 0; deba@913: for (int b = (*_nodes)[m].first_arc; b != -1; b = nb) { deba@913: nb = _arcs[b].next; deba@913: if ((b ^ a) == 1) continue; deba@913: typename Graph::Node o = _arcs[b].target; alpar@1092: int c = (*_nodes)[o].curr_arc; deba@913: if (c != -1 && _arcs[c ^ 1].target == n) { deba@913: _edges[c >> 1].capacity += _edges[b >> 1].capacity; deba@913: (*_nodes)[n].sum += _edges[b >> 1].capacity; deba@913: if (_edges[b >> 1].cut < _edges[c >> 1].cut) { deba@913: _edges[b >> 1].cut = _edges[c >> 1].cut; deba@913: } deba@913: if (_arcs[b ^ 1].prev != -1) { deba@913: _arcs[_arcs[b ^ 1].prev].next = _arcs[b ^ 1].next; deba@913: } else { deba@913: (*_nodes)[o].first_arc = _arcs[b ^ 1].next; deba@913: } deba@913: if (_arcs[b ^ 1].next != -1) { deba@913: _arcs[_arcs[b ^ 1].next].prev = _arcs[b ^ 1].prev; deba@913: } deba@913: } else { deba@913: if (_arcs[a].next != -1) { deba@913: _arcs[_arcs[a].next].prev = b; deba@913: } deba@913: _arcs[b].next = _arcs[a].next; deba@913: _arcs[b].prev = a; deba@913: _arcs[a].next = b; deba@913: _arcs[b ^ 1].target = n; deba@913: deba@913: (*_nodes)[n].sum += _edges[b >> 1].capacity; deba@913: (*_nodes)[o].curr_arc = b; deba@913: } deba@913: } deba@913: deba@913: if (_arcs[a].prev != -1) { deba@913: _arcs[_arcs[a].prev].next = _arcs[a].next; deba@913: } else { deba@913: (*_nodes)[n].first_arc = _arcs[a].next; alpar@1092: } deba@913: if (_arcs[a].next != -1) { deba@913: _arcs[_arcs[a].next].prev = _arcs[a].prev; deba@913: } deba@913: deba@913: (*_nodes)[n].sum -= _edges[a >> 1].capacity; deba@913: (*_next_rep)[(*_nodes)[n].last_rep] = m; deba@913: (*_nodes)[n].last_rep = (*_nodes)[m].last_rep; alpar@1092: deba@913: if ((*_nodes)[m].prev != INVALID) { deba@913: (*_nodes)[(*_nodes)[m].prev].next = (*_nodes)[m].next; deba@913: } else{ deba@913: _first_node = (*_nodes)[m].next; deba@913: } deba@913: if ((*_nodes)[m].next != INVALID) { deba@913: (*_nodes)[(*_nodes)[m].next].prev = (*_nodes)[m].prev; deba@913: } deba@913: --_node_num; deba@913: } deba@913: } deba@913: } deba@913: deba@913: if (_node_num == 1) { deba@913: _first_node = INVALID; deba@913: return true; deba@913: } deba@913: deba@913: return false; deba@913: } deba@913: deba@913: /// \brief Executes the algorithm. deba@913: /// deba@913: /// Executes the algorithm. deba@913: /// deba@913: /// \pre init() must be called deba@913: void start() { deba@913: while (!processNextPhase()) {} deba@913: } deba@913: deba@913: deba@913: /// \brief Runs %NagamochiIbaraki algorithm. deba@913: /// deba@913: /// This method runs the %Min cut algorithm deba@913: /// deba@913: /// \note mc.run(s) is just a shortcut of the following code. deba@913: ///\code deba@913: /// mc.init(); deba@913: /// mc.start(); deba@913: ///\endcode deba@913: void run() { deba@913: init(); deba@913: start(); deba@913: } deba@913: deba@913: ///@} deba@913: deba@913: /// \name Query Functions deba@913: /// deba@913: /// The result of the %NagamochiIbaraki deba@913: /// algorithm can be obtained using these functions.\n deba@913: /// Before the use of these functions, either run() or start() deba@913: /// must be called. deba@913: deba@913: ///@{ deba@913: deba@913: /// \brief Returns the min cut value. deba@913: /// deba@913: /// Returns the min cut value if the algorithm finished. deba@913: /// After the first processNextPhase() it is a value of a deba@913: /// valid cut in the graph. deba@913: Value minCutValue() const { deba@913: return _min_cut; deba@913: } deba@913: deba@913: /// \brief Returns a min cut in a NodeMap. deba@913: /// deba@913: /// It sets the nodes of one of the two partitions to true and deba@913: /// the other partition to false. deba@913: /// \param cutMap A \ref concepts::WriteMap "writable" node map with deba@913: /// \c bool (or convertible) value type. deba@913: template deba@913: Value minCutMap(CutMap& cutMap) const { deba@913: for (typename Graph::NodeIt n(_graph); n != INVALID; ++n) { deba@913: cutMap.set(n, (*_cut_map)[n]); deba@913: } deba@913: return minCutValue(); deba@913: } deba@913: deba@913: ///@} deba@913: deba@913: }; deba@913: } deba@913: deba@913: #endif