1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/min_cut.h Mon Feb 20 09:40:07 2006 +0000
1.3 @@ -0,0 +1,1351 @@
1.4 +/* -*- C++ -*-
1.5 + * lemon/min_cut.h - Part of LEMON, a generic C++ optimization library
1.6 + *
1.7 + * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.8 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.9 + *
1.10 + * Permission to use, modify and distribute this software is granted
1.11 + * provided that this copyright notice appears in all copies. For
1.12 + * precise terms see the accompanying LICENSE file.
1.13 + *
1.14 + * This software is provided "AS IS" with no warranty of any kind,
1.15 + * express or implied, and with no claim as to its suitability for any
1.16 + * purpose.
1.17 + *
1.18 + */
1.19 +
1.20 +#ifndef LEMON_MIN_CUT_H
1.21 +#define LEMON_MIN_CUT_H
1.22 +
1.23 +
1.24 +/// \ingroup topology
1.25 +/// \file
1.26 +/// \brief Maximum cardinality search and min cut in undirected graphs.
1.27 +
1.28 +#include <lemon/list_graph.h>
1.29 +#include <lemon/bin_heap.h>
1.30 +#include <lemon/linear_heap.h>
1.31 +
1.32 +#include <lemon/invalid.h>
1.33 +#include <lemon/error.h>
1.34 +#include <lemon/maps.h>
1.35 +
1.36 +#include <functional>
1.37 +
1.38 +namespace lemon {
1.39 +
1.40 + namespace _min_cut_bits {
1.41 +
1.42 + template <typename CapacityMap>
1.43 + struct HeapSelector {
1.44 + template <typename Key, typename Value, typename Ref>
1.45 + struct Selector {
1.46 + typedef BinHeap<Key, Value, Ref, std::greater<Value> > Heap;
1.47 + };
1.48 + };
1.49 +
1.50 + template <typename CapacityKey>
1.51 + struct HeapSelector<ConstMap<CapacityKey, Const<int, 1> > > {
1.52 + template <typename Key, typename Value, typename Ref>
1.53 + struct Selector {
1.54 + typedef LinearHeap<Key, Ref, false > Heap;
1.55 + };
1.56 + };
1.57 +
1.58 + }
1.59 +
1.60 + /// \brief Default traits class of MaxCardinalitySearch class.
1.61 + ///
1.62 + /// Default traits class of MaxCardinalitySearch class.
1.63 + /// \param Graph Graph type.
1.64 + /// \param CapacityMap Type of length map.
1.65 + template <typename _Graph, typename _CapacityMap>
1.66 + struct MaxCardinalitySearchDefaultTraits {
1.67 + /// The graph type the algorithm runs on.
1.68 + typedef _Graph Graph;
1.69 +
1.70 + /// \brief The type of the map that stores the edge capacities.
1.71 + ///
1.72 + /// The type of the map that stores the edge capacities.
1.73 + /// It must meet the \ref concept::ReadMap "ReadMap" concept.
1.74 + typedef _CapacityMap CapacityMap;
1.75 +
1.76 + /// \brief The type of the capacity of the edges.
1.77 + typedef typename CapacityMap::Value Value;
1.78 +
1.79 + /// \brief The cross reference type used by heap.
1.80 + ///
1.81 + /// The cross reference type used by heap.
1.82 + /// Usually it is \c Graph::NodeMap<int>.
1.83 + typedef typename Graph::template NodeMap<int> HeapCrossRef;
1.84 +
1.85 + /// \brief Instantiates a HeapCrossRef.
1.86 + ///
1.87 + /// This function instantiates a \ref HeapCrossRef.
1.88 + /// \param graph is the graph, to which we would like to define the
1.89 + /// HeapCrossRef.
1.90 + static HeapCrossRef *createHeapCrossRef(const Graph &graph) {
1.91 + return new HeapCrossRef(graph);
1.92 + }
1.93 +
1.94 + /// \brief The heap type used by MaxCardinalitySearch algorithm.
1.95 + ///
1.96 + /// The heap type used by MaxCardinalitySearch algorithm. It should
1.97 + /// maximalize the priorities. The default heap type is
1.98 + /// the \ref BinHeap, but it is specialized when the
1.99 + /// CapacityMap is ConstMap<Graph::Node, Const<int, 1> >
1.100 + /// to LinearHeap.
1.101 + ///
1.102 + /// \sa MaxCardinalitySearch
1.103 + typedef typename _min_cut_bits
1.104 + ::HeapSelector<CapacityMap>
1.105 + ::template Selector<typename Graph::Node, Value, HeapCrossRef>
1.106 + ::Heap Heap;
1.107 +
1.108 + /// \brief Instantiates a Heap.
1.109 + ///
1.110 + /// This function instantiates a \ref Heap.
1.111 + /// \param crossref The cross reference of the heap.
1.112 + static Heap *createHeap(HeapCrossRef& crossref) {
1.113 + return new Heap(crossref);
1.114 + }
1.115 +
1.116 + /// \brief The type of the map that stores whether a nodes is processed.
1.117 + ///
1.118 + /// The type of the map that stores whether a nodes is processed.
1.119 + /// It must meet the \ref concept::WriteMap "WriteMap" concept.
1.120 + /// By default it is a NullMap.
1.121 + typedef NullMap<typename Graph::Node, bool> ProcessedMap;
1.122 +
1.123 + /// \brief Instantiates a ProcessedMap.
1.124 + ///
1.125 + /// This function instantiates a \ref ProcessedMap.
1.126 + /// \param g is the graph, to which
1.127 + /// we would like to define the \ref ProcessedMap
1.128 +#ifdef DOXYGEN
1.129 + static ProcessedMap *createProcessedMap(const Graph &graph)
1.130 +#else
1.131 + static ProcessedMap *createProcessedMap(const Graph &)
1.132 +#endif
1.133 + {
1.134 + return new ProcessedMap();
1.135 + }
1.136 +
1.137 + /// \brief The type of the map that stores the cardinalties of the nodes.
1.138 + ///
1.139 + /// The type of the map that stores the cardinalities of the nodes.
1.140 + /// It must meet the \ref concept::WriteMap "WriteMap" concept.
1.141 + typedef typename Graph::template NodeMap<Value> CardinalityMap;
1.142 +
1.143 + /// \brief Instantiates a CardinalityMap.
1.144 + ///
1.145 + /// This function instantiates a \ref CardinalityMap.
1.146 + /// \param graph is the graph, to which we would like to define the \ref
1.147 + /// CardinalityMap
1.148 + static CardinalityMap *createCardinalityMap(const Graph &graph) {
1.149 + return new CardinalityMap(graph);
1.150 + }
1.151 +
1.152 + };
1.153 +
1.154 + /// \ingroup topology
1.155 + ///
1.156 + /// \brief Maximum Cardinality Search algorithm class.
1.157 + ///
1.158 + /// This class provides an efficient implementation of Maximum Cardinality
1.159 + /// Search algorithm. The maximum cardinality search chooses first time any
1.160 + /// node of the graph. Then every time it chooses the node which is connected
1.161 + /// to the processed nodes at most in the sum of capacities on the out
1.162 + /// edges. If there is a cut in the graph the algorithm should choose
1.163 + /// again any unprocessed node of the graph. Each node cardinality is
1.164 + /// the sum of capacities on the out edges to the nodes which are processed
1.165 + /// before the given node.
1.166 + ///
1.167 + /// The edge capacities are passed to the algorithm using a
1.168 + /// \ref concept::ReadMap "ReadMap", so it is easy to change it to any
1.169 + /// kind of capacity.
1.170 + ///
1.171 + /// The type of the capacity is determined by the \ref
1.172 + /// concept::ReadMap::Value "Value" of the capacity map.
1.173 + ///
1.174 + /// It is also possible to change the underlying priority heap.
1.175 + ///
1.176 + ///
1.177 + /// \param _Graph The graph type the algorithm runs on. The default value
1.178 + /// is \ref ListGraph. The value of Graph is not used directly by
1.179 + /// the search algorithm, it is only passed to
1.180 + /// \ref MaxCardinalitySearchDefaultTraits.
1.181 + /// \param _CapacityMap This read-only EdgeMap determines the capacities of
1.182 + /// the edges. It is read once for each edge, so the map may involve in
1.183 + /// relatively time consuming process to compute the edge capacity if
1.184 + /// it is necessary. The default map type is \ref
1.185 + /// concept::StaticGraph::EdgeMap "Graph::EdgeMap<int>". The value
1.186 + /// of CapacityMap is not used directly by search algorithm, it is only
1.187 + /// passed to \ref MaxCardinalitySearchDefaultTraits.
1.188 + /// \param _Traits Traits class to set various data types used by the
1.189 + /// algorithm. The default traits class is
1.190 + /// \ref MaxCardinalitySearchDefaultTraits
1.191 + /// "MaxCardinalitySearchDefaultTraits<_Graph, _CapacityMap>".
1.192 + /// See \ref MaxCardinalitySearchDefaultTraits
1.193 + /// for the documentation of a MaxCardinalitySearch traits class.
1.194 + ///
1.195 + /// \author Balazs Dezso
1.196 +
1.197 +#ifdef DOXYGEN
1.198 + template <typename _Graph, typename _CapacityMap, typename _Traits>
1.199 +#else
1.200 + template <typename _Graph = ListUGraph,
1.201 + typename _CapacityMap = typename _Graph::template EdgeMap<int>,
1.202 + typename _Traits =
1.203 + MaxCardinalitySearchDefaultTraits<_Graph, _CapacityMap> >
1.204 +#endif
1.205 + class MaxCardinalitySearch {
1.206 + public:
1.207 + /// \brief \ref Exception for uninitialized parameters.
1.208 + ///
1.209 + /// This error represents problems in the initialization
1.210 + /// of the parameters of the algorithms.
1.211 + class UninitializedParameter : public lemon::UninitializedParameter {
1.212 + public:
1.213 + virtual const char* exceptionName() const {
1.214 + return "lemon::MaxCardinalitySearch::UninitializedParameter";
1.215 + }
1.216 + };
1.217 +
1.218 + typedef _Traits Traits;
1.219 + ///The type of the underlying graph.
1.220 + typedef typename Traits::Graph Graph;
1.221 +
1.222 + ///The type of the capacity of the edges.
1.223 + typedef typename Traits::CapacityMap::Value Value;
1.224 + ///The type of the map that stores the edge capacities.
1.225 + typedef typename Traits::CapacityMap CapacityMap;
1.226 + ///The type of the map indicating if a node is processed.
1.227 + typedef typename Traits::ProcessedMap ProcessedMap;
1.228 + ///The type of the map that stores the cardinalities of the nodes.
1.229 + typedef typename Traits::CardinalityMap CardinalityMap;
1.230 + ///The cross reference type used for the current heap.
1.231 + typedef typename Traits::HeapCrossRef HeapCrossRef;
1.232 + ///The heap type used by the algorithm. It maximize the priorities.
1.233 + typedef typename Traits::Heap Heap;
1.234 + private:
1.235 + /// Pointer to the underlying graph.
1.236 + const Graph *_graph;
1.237 + /// Pointer to the capacity map
1.238 + const CapacityMap *_capacity;
1.239 + ///Pointer to the map of cardinality.
1.240 + CardinalityMap *_cardinality;
1.241 + ///Indicates if \ref _cardinality is locally allocated (\c true) or not.
1.242 + bool local_cardinality;
1.243 + ///Pointer to the map of processed status of the nodes.
1.244 + ProcessedMap *_processed;
1.245 + ///Indicates if \ref _processed is locally allocated (\c true) or not.
1.246 + bool local_processed;
1.247 + ///Pointer to the heap cross references.
1.248 + HeapCrossRef *_heap_cross_ref;
1.249 + ///Indicates if \ref _heap_cross_ref is locally allocated (\c true) or not.
1.250 + bool local_heap_cross_ref;
1.251 + ///Pointer to the heap.
1.252 + Heap *_heap;
1.253 + ///Indicates if \ref _heap is locally allocated (\c true) or not.
1.254 + bool local_heap;
1.255 +
1.256 + public :
1.257 +
1.258 + typedef MaxCardinalitySearch Create;
1.259 +
1.260 + ///\name Named template parameters
1.261 +
1.262 + ///@{
1.263 +
1.264 + template <class T>
1.265 + struct DefCardinalityMapTraits : public Traits {
1.266 + typedef T CardinalityMap;
1.267 + static CardinalityMap *createCardinalityMap(const Graph &)
1.268 + {
1.269 + throw UninitializedParameter();
1.270 + }
1.271 + };
1.272 + /// \brief \ref named-templ-param "Named parameter" for setting
1.273 + /// CardinalityMap type
1.274 + ///
1.275 + /// \ref named-templ-param "Named parameter" for setting CardinalityMap
1.276 + /// type
1.277 + template <class T>
1.278 + struct DefCardinalityMap
1.279 + : public MaxCardinalitySearch<Graph, CapacityMap,
1.280 + DefCardinalityMapTraits<T> > {
1.281 + typedef MaxCardinalitySearch<Graph, CapacityMap,
1.282 + DefCardinalityMapTraits<T> > Create;
1.283 + };
1.284 +
1.285 + template <class T>
1.286 + struct DefProcessedMapTraits : public Traits {
1.287 + typedef T ProcessedMap;
1.288 + static ProcessedMap *createProcessedMap(const Graph &) {
1.289 + throw UninitializedParameter();
1.290 + }
1.291 + };
1.292 + /// \brief \ref named-templ-param "Named parameter" for setting
1.293 + /// ProcessedMap type
1.294 + ///
1.295 + /// \ref named-templ-param "Named parameter" for setting ProcessedMap type
1.296 + ///
1.297 + template <class T>
1.298 + struct DefProcessedMap
1.299 + : public MaxCardinalitySearch<Graph, CapacityMap,
1.300 + DefProcessedMapTraits<T> > {
1.301 + typedef MaxCardinalitySearch<Graph, CapacityMap,
1.302 + DefProcessedMapTraits<T> > Create;
1.303 + };
1.304 +
1.305 + template <class H, class CR>
1.306 + struct DefHeapTraits : public Traits {
1.307 + typedef CR HeapCrossRef;
1.308 + typedef H Heap;
1.309 + static HeapCrossRef *createHeapCrossRef(const Graph &) {
1.310 + throw UninitializedParameter();
1.311 + }
1.312 + static Heap *createHeap(HeapCrossRef &) {
1.313 + throw UninitializedParameter();
1.314 + }
1.315 + };
1.316 + /// \brief \ref named-templ-param "Named parameter" for setting heap
1.317 + /// and cross reference type
1.318 + ///
1.319 + /// \ref named-templ-param "Named parameter" for setting heap and cross
1.320 + /// reference type
1.321 + template <class H, class CR = typename Graph::template NodeMap<int> >
1.322 + struct DefHeap
1.323 + : public MaxCardinalitySearch<Graph, CapacityMap,
1.324 + DefHeapTraits<H, CR> > {
1.325 + typedef MaxCardinalitySearch< Graph, CapacityMap,
1.326 + DefHeapTraits<H, CR> > Create;
1.327 + };
1.328 +
1.329 + template <class H, class CR>
1.330 + struct DefStandardHeapTraits : public Traits {
1.331 + typedef CR HeapCrossRef;
1.332 + typedef H Heap;
1.333 + static HeapCrossRef *createHeapCrossRef(const Graph &graph) {
1.334 + return new HeapCrossRef(graph);
1.335 + }
1.336 + static Heap *createHeap(HeapCrossRef &crossref) {
1.337 + return new Heap(crossref);
1.338 + }
1.339 + };
1.340 +
1.341 + /// \brief \ref named-templ-param "Named parameter" for setting heap and
1.342 + /// cross reference type with automatic allocation
1.343 + ///
1.344 + /// \ref named-templ-param "Named parameter" for setting heap and cross
1.345 + /// reference type. It can allocate the heap and the cross reference
1.346 + /// object if the cross reference's constructor waits for the graph as
1.347 + /// parameter and the heap's constructor waits for the cross reference.
1.348 + template <class H, class CR = typename Graph::template NodeMap<int> >
1.349 + struct DefStandardHeap
1.350 + : public MaxCardinalitySearch<Graph, CapacityMap,
1.351 + DefStandardHeapTraits<H, CR> > {
1.352 + typedef MaxCardinalitySearch<Graph, CapacityMap,
1.353 + DefStandardHeapTraits<H, CR> >
1.354 + Create;
1.355 + };
1.356 +
1.357 + ///@}
1.358 +
1.359 +
1.360 + protected:
1.361 +
1.362 + MaxCardinalitySearch() {}
1.363 +
1.364 + public:
1.365 +
1.366 + /// \brief Constructor.
1.367 + ///
1.368 + ///\param _graph the graph the algorithm will run on.
1.369 + ///\param _capacity the capacity map used by the algorithm.
1.370 + MaxCardinalitySearch(const Graph& graph, const CapacityMap& capacity) :
1.371 + _graph(&graph), _capacity(&capacity),
1.372 + _cardinality(0), local_cardinality(false),
1.373 + _processed(0), local_processed(false),
1.374 + _heap_cross_ref(0), local_heap_cross_ref(false),
1.375 + _heap(0), local_heap(false)
1.376 + { }
1.377 +
1.378 + /// \brief Destructor.
1.379 + ~MaxCardinalitySearch() {
1.380 + if(local_cardinality) delete _cardinality;
1.381 + if(local_processed) delete _processed;
1.382 + if(local_heap_cross_ref) delete _heap_cross_ref;
1.383 + if(local_heap) delete _heap;
1.384 + }
1.385 +
1.386 + /// \brief Sets the capacity map.
1.387 + ///
1.388 + /// Sets the capacity map.
1.389 + /// \return <tt> (*this) </tt>
1.390 + MaxCardinalitySearch &capacityMap(const CapacityMap &m) {
1.391 + _capacity = &m;
1.392 + return *this;
1.393 + }
1.394 +
1.395 + /// \brief Sets the map storing the cardinalities calculated by the
1.396 + /// algorithm.
1.397 + ///
1.398 + /// Sets the map storing the cardinalities calculated by the algorithm.
1.399 + /// If you don't use this function before calling \ref run(),
1.400 + /// it will allocate one. The destuctor deallocates this
1.401 + /// automatically allocated map, of course.
1.402 + /// \return <tt> (*this) </tt>
1.403 + MaxCardinalitySearch &cardinalityMap(CardinalityMap &m) {
1.404 + if(local_cardinality) {
1.405 + delete _cardinality;
1.406 + local_cardinality=false;
1.407 + }
1.408 + _cardinality = &m;
1.409 + return *this;
1.410 + }
1.411 +
1.412 + /// \brief Sets the map storing the processed nodes.
1.413 + ///
1.414 + /// Sets the map storing the processed nodes.
1.415 + /// If you don't use this function before calling \ref run(),
1.416 + /// it will allocate one. The destuctor deallocates this
1.417 + /// automatically allocated map, of course.
1.418 + /// \return <tt> (*this) </tt>
1.419 + MaxCardinalitySearch &processedMap(ProcessedMap &m)
1.420 + {
1.421 + if(local_processed) {
1.422 + delete _processed;
1.423 + local_processed=false;
1.424 + }
1.425 + _processed = &m;
1.426 + return *this;
1.427 + }
1.428 +
1.429 + /// \brief Sets the heap and the cross reference used by algorithm.
1.430 + ///
1.431 + /// Sets the heap and the cross reference used by algorithm.
1.432 + /// If you don't use this function before calling \ref run(),
1.433 + /// it will allocate one. The destuctor deallocates this
1.434 + /// automatically allocated map, of course.
1.435 + /// \return <tt> (*this) </tt>
1.436 + MaxCardinalitySearch &heap(Heap& heap, HeapCrossRef &crossRef) {
1.437 + if(local_heap_cross_ref) {
1.438 + delete _heap_cross_ref;
1.439 + local_heap_cross_ref = false;
1.440 + }
1.441 + _heap_cross_ref = &crossRef;
1.442 + if(local_heap) {
1.443 + delete _heap;
1.444 + local_heap = false;
1.445 + }
1.446 + _heap = &heap;
1.447 + return *this;
1.448 + }
1.449 +
1.450 + private:
1.451 +
1.452 + typedef typename Graph::Node Node;
1.453 + typedef typename Graph::NodeIt NodeIt;
1.454 + typedef typename Graph::Edge Edge;
1.455 + typedef typename Graph::InEdgeIt InEdgeIt;
1.456 +
1.457 + void create_maps() {
1.458 + if(!_cardinality) {
1.459 + local_cardinality = true;
1.460 + _cardinality = Traits::createCardinalityMap(*_graph);
1.461 + }
1.462 + if(!_processed) {
1.463 + local_processed = true;
1.464 + _processed = Traits::createProcessedMap(*_graph);
1.465 + }
1.466 + if (!_heap_cross_ref) {
1.467 + local_heap_cross_ref = true;
1.468 + _heap_cross_ref = Traits::createHeapCrossRef(*_graph);
1.469 + }
1.470 + if (!_heap) {
1.471 + local_heap = true;
1.472 + _heap = Traits::createHeap(*_heap_cross_ref);
1.473 + }
1.474 + }
1.475 +
1.476 + void finalizeNodeData(Node node, Value capacity) {
1.477 + _processed->set(node, true);
1.478 + _cardinality->set(node, capacity);
1.479 + }
1.480 +
1.481 + public:
1.482 + /// \name Execution control
1.483 + /// The simplest way to execute the algorithm is to use
1.484 + /// one of the member functions called \c run(...).
1.485 + /// \n
1.486 + /// If you need more control on the execution,
1.487 + /// first you must call \ref init(), then you can add several source nodes
1.488 + /// with \ref addSource().
1.489 + /// Finally \ref start() will perform the actual path
1.490 + /// computation.
1.491 +
1.492 + ///@{
1.493 +
1.494 + /// \brief Initializes the internal data structures.
1.495 + ///
1.496 + /// Initializes the internal data structures.
1.497 + void init() {
1.498 + create_maps();
1.499 + _heap->clear();
1.500 + for (NodeIt it(*_graph) ; it != INVALID ; ++it) {
1.501 + _processed->set(it, false);
1.502 + _heap_cross_ref->set(it, Heap::PRE_HEAP);
1.503 + }
1.504 + }
1.505 +
1.506 + /// \brief Adds a new source node.
1.507 + ///
1.508 + /// Adds a new source node to the priority heap.
1.509 + ///
1.510 + /// It checks if the node has not yet been added to the heap.
1.511 + void addSource(Node source, Value capacity = 0) {
1.512 + if(_heap->state(source) == Heap::PRE_HEAP) {
1.513 + _heap->push(source, capacity);
1.514 + }
1.515 + }
1.516 +
1.517 + /// \brief Processes the next node in the priority heap
1.518 + ///
1.519 + /// Processes the next node in the priority heap.
1.520 + ///
1.521 + /// \return The processed node.
1.522 + ///
1.523 + /// \warning The priority heap must not be empty!
1.524 + Node processNextNode() {
1.525 + Node node = _heap->top();
1.526 + finalizeNodeData(node, _heap->prio());
1.527 + _heap->pop();
1.528 +
1.529 + for (InEdgeIt it(*_graph, node); it != INVALID; ++it) {
1.530 + Node source = _graph->source(it);
1.531 + switch (_heap->state(source)) {
1.532 + case Heap::PRE_HEAP:
1.533 + _heap->push(source, (*_capacity)[it]);
1.534 + break;
1.535 + case Heap::IN_HEAP:
1.536 + _heap->decrease(source, (*_heap)[source] + (*_capacity)[it]);
1.537 + break;
1.538 + case Heap::POST_HEAP:
1.539 + break;
1.540 + }
1.541 + }
1.542 + return node;
1.543 + }
1.544 +
1.545 + /// \brief Next node to be processed.
1.546 + ///
1.547 + /// Next node to be processed.
1.548 + ///
1.549 + /// \return The next node to be processed or INVALID if the
1.550 + /// priority heap is empty.
1.551 + Node nextNode() {
1.552 + return _heap->empty() ? _heap->top() : INVALID;
1.553 + }
1.554 +
1.555 + /// \brief Returns \c false if there are nodes
1.556 + /// to be processed in the priority heap
1.557 + ///
1.558 + /// Returns \c false if there are nodes
1.559 + /// to be processed in the priority heap
1.560 + bool emptyQueue() { return _heap->empty(); }
1.561 + /// \brief Returns the number of the nodes to be processed
1.562 + /// in the priority heap
1.563 + ///
1.564 + /// Returns the number of the nodes to be processed in the priority heap
1.565 + int queueSize() { return _heap->size(); }
1.566 +
1.567 + /// \brief Executes the algorithm.
1.568 + ///
1.569 + /// Executes the algorithm.
1.570 + ///
1.571 + ///\pre init() must be called and at least one node should be added
1.572 + /// with addSource() before using this function.
1.573 + ///
1.574 + /// This method runs the Maximum Cardinality Search algorithm from the
1.575 + /// source node(s).
1.576 + void start() {
1.577 + while ( !_heap->empty() ) processNextNode();
1.578 + }
1.579 +
1.580 + /// \brief Executes the algorithm until \c dest is reached.
1.581 + ///
1.582 + /// Executes the algorithm until \c dest is reached.
1.583 + ///
1.584 + /// \pre init() must be called and at least one node should be added
1.585 + /// with addSource() before using this function.
1.586 + ///
1.587 + /// This method runs the %MaxCardinalitySearch algorithm from the source
1.588 + /// nodes.
1.589 + void start(Node dest) {
1.590 + while ( !_heap->empty() && _heap->top()!=dest ) processNextNode();
1.591 + if ( !_heap->empty() ) finalizeNodeData(_heap->top(), _heap->prio());
1.592 + }
1.593 +
1.594 + /// \brief Executes the algorithm until a condition is met.
1.595 + ///
1.596 + /// Executes the algorithm until a condition is met.
1.597 + ///
1.598 + /// \pre init() must be called and at least one node should be added
1.599 + /// with addSource() before using this function.
1.600 + ///
1.601 + /// \param nm must be a bool (or convertible) node map. The algorithm
1.602 + /// will stop when it reaches a node \c v with <tt>nm[v]==true</tt>.
1.603 + template <typename NodeBoolMap>
1.604 + void start(const NodeBoolMap &nm) {
1.605 + while ( !_heap->empty() && !nm[_heap->top()] ) processNextNode();
1.606 + if ( !_heap->empty() ) finalizeNodeData(_heap->top(),_heap->prio());
1.607 + }
1.608 +
1.609 + /// \brief Runs the maximal cardinality search algorithm from node \c s.
1.610 + ///
1.611 + /// This method runs the %MaxCardinalitySearch algorithm from a root
1.612 + /// node \c s.
1.613 + ///
1.614 + ///\note d.run(s) is just a shortcut of the following code.
1.615 + ///\code
1.616 + /// d.init();
1.617 + /// d.addSource(s);
1.618 + /// d.start();
1.619 + ///\endcode
1.620 + void run(Node s) {
1.621 + init();
1.622 + addSource(s);
1.623 + start();
1.624 + }
1.625 +
1.626 + /// \brief Runs the maximal cardinality search algorithm for the
1.627 + /// whole graph.
1.628 + ///
1.629 + /// This method runs the %MaxCardinalitySearch algorithm from all
1.630 + /// unprocessed node of the graph.
1.631 + ///
1.632 + ///\note d.run(s) is just a shortcut of the following code.
1.633 + ///\code
1.634 + /// d.init();
1.635 + /// for (NodeIt it(graph); it != INVALID; ++it) {
1.636 + /// if (!d.reached(it)) {
1.637 + /// d.addSource(s);
1.638 + /// d.start();
1.639 + /// }
1.640 + /// }
1.641 + ///\endcode
1.642 + void run() {
1.643 + init();
1.644 + for (NodeIt it(*_graph); it != INVALID; ++it) {
1.645 + if (!reached(it)) {
1.646 + addSource(it);
1.647 + start();
1.648 + }
1.649 + }
1.650 + }
1.651 +
1.652 + ///@}
1.653 +
1.654 + /// \name Query Functions
1.655 + /// The result of the maximum cardinality search algorithm can be
1.656 + /// obtained using these functions.
1.657 + /// \n
1.658 + /// Before the use of these functions, either run() or start() must be
1.659 + /// called.
1.660 +
1.661 + ///@{
1.662 +
1.663 + /// \brief The cardinality of a node.
1.664 + ///
1.665 + /// Returns the cardinality of a node.
1.666 + /// \pre \ref run() must be called before using this function.
1.667 + /// \warning If node \c v in unreachable from the root the return value
1.668 + /// of this funcion is undefined.
1.669 + Value cardinality(Node node) const { return (*_cardinality)[node]; }
1.670 +
1.671 + /// \brief Returns a reference to the NodeMap of cardinalities.
1.672 + ///
1.673 + /// Returns a reference to the NodeMap of cardinalities. \pre \ref run()
1.674 + /// must be called before using this function.
1.675 + const CardinalityMap &cardinalityMap() const { return *_cardinality;}
1.676 +
1.677 + /// \brief Checks if a node is reachable from the root.
1.678 + ///
1.679 + /// Returns \c true if \c v is reachable from the root.
1.680 + /// \warning The source nodes are inditated as unreached.
1.681 + /// \pre \ref run() must be called before using this function.
1.682 + bool reached(Node v) { return (*_heap_cross_ref)[v] != Heap::PRE_HEAP; }
1.683 +
1.684 + /// \brief Checks if a node is processed.
1.685 + ///
1.686 + /// Returns \c true if \c v is processed, i.e. the shortest
1.687 + /// path to \c v has already found.
1.688 + /// \pre \ref run() must be called before using this function.
1.689 + bool processed(Node v) { return (*_heap_cross_ref)[v] == Heap::POST_HEAP; }
1.690 +
1.691 + ///@}
1.692 + };
1.693 +
1.694 + /// \brief Default traits class of MinCut class.
1.695 + ///
1.696 + /// Default traits class of MinCut class.
1.697 + /// \param Graph Graph type.
1.698 + /// \param CapacityMap Type of length map.
1.699 + template <typename _Graph, typename _CapacityMap>
1.700 + struct MinCutDefaultTraits {
1.701 + /// \brief The type of the capacity of the edges.
1.702 + typedef typename _CapacityMap::Value Value;
1.703 +
1.704 + /// The graph type the algorithm runs on.
1.705 + typedef _Graph Graph;
1.706 +
1.707 + /// The AuxGraph type which is an EraseableGraph
1.708 + typedef ListUGraph AuxGraph;
1.709 +
1.710 + /// \brief Instantiates a AuxGraph.
1.711 + ///
1.712 + /// This function instantiates a \ref AuxGraph.
1.713 + static AuxGraph *createAuxGraph() {
1.714 + return new AuxGraph();
1.715 + }
1.716 +
1.717 + /// \brief The type of the map that stores the edge capacities.
1.718 + ///
1.719 + /// The type of the map that stores the edge capacities.
1.720 + /// It must meet the \ref concept::ReadMap "ReadMap" concept.
1.721 + typedef _CapacityMap CapacityMap;
1.722 +
1.723 + /// \brief Instantiates a CapacityMap.
1.724 + ///
1.725 + /// This function instantiates a \ref CapacityMap.
1.726 +#ifdef DOXYGEN
1.727 + static CapacityMap *createCapacityMap(const Graph& graph)
1.728 +#else
1.729 + static CapacityMap *createCapacityMap(const Graph&)
1.730 +#endif
1.731 + {
1.732 + throw UninitializedParameter();
1.733 + }
1.734 +
1.735 + /// \brief The AuxCapacityMap type
1.736 + ///
1.737 + /// The type of the map that stores the auxing edge capacities.
1.738 + typedef AuxGraph::UEdgeMap<Value> AuxCapacityMap;
1.739 +
1.740 + /// \brief Instantiates a AuxCapacityMap.
1.741 + ///
1.742 + /// This function instantiates a \ref AuxCapacityMap.
1.743 + static AuxCapacityMap *createAuxCapacityMap(const AuxGraph& graph) {
1.744 + return new AuxCapacityMap(graph);
1.745 + }
1.746 +
1.747 + /// \brief The cross reference type used by heap.
1.748 + ///
1.749 + /// The cross reference type used by heap.
1.750 + /// Usually it is \c Graph::NodeMap<int>.
1.751 + typedef AuxGraph::NodeMap<int> HeapCrossRef;
1.752 +
1.753 + /// \brief Instantiates a HeapCrossRef.
1.754 + ///
1.755 + /// This function instantiates a \ref HeapCrossRef.
1.756 + /// \param graph is the graph, to which we would like to define the
1.757 + /// HeapCrossRef.
1.758 + static HeapCrossRef *createHeapCrossRef(const AuxGraph &graph) {
1.759 + return new HeapCrossRef(graph);
1.760 + }
1.761 +
1.762 + /// \brief The heap type used by MinCut algorithm.
1.763 + ///
1.764 + /// The heap type used by MinCut algorithm. It should
1.765 + /// maximalize the priorities and the heap's key type is
1.766 + /// the aux graph's node.
1.767 + ///
1.768 + /// \sa BinHeap
1.769 + /// \sa MinCut
1.770 + typedef typename _min_cut_bits
1.771 + ::HeapSelector<CapacityMap>
1.772 + ::template Selector<typename AuxGraph::Node, Value, HeapCrossRef>
1.773 + ::Heap Heap;
1.774 +
1.775 + /// \brief Instantiates a Heap.
1.776 + ///
1.777 + /// This function instantiates a \ref Heap.
1.778 + /// \param crossref The cross reference of the heap.
1.779 + static Heap *createHeap(HeapCrossRef& crossref) {
1.780 + return new Heap(crossref);
1.781 + }
1.782 +
1.783 + /// \brief Map from the AuxGraph's node type to the Graph's node type.
1.784 + ///
1.785 + /// Map from the AuxGraph's node type to the Graph's node type.
1.786 + typedef typename AuxGraph
1.787 + ::template NodeMap<typename Graph::Node> NodeRefMap;
1.788 +
1.789 + /// \brief Instantiates a NodeRefMap.
1.790 + ///
1.791 + /// This function instantiates a \ref NodeRefMap.
1.792 + static NodeRefMap *createNodeRefMap(const AuxGraph& graph) {
1.793 + return new NodeRefMap(graph);
1.794 + }
1.795 +
1.796 + /// \brief Map from the Graph's node type to the Graph's node type.
1.797 + ///
1.798 + /// Map from the Graph's node type to the Graph's node type.
1.799 + typedef typename Graph
1.800 + ::template NodeMap<typename Graph::Node> ListRefMap;
1.801 +
1.802 + /// \brief Instantiates a ListRefMap.
1.803 + ///
1.804 + /// This function instantiates a \ref ListRefMap.
1.805 + static ListRefMap *createListRefMap(const Graph& graph) {
1.806 + return new ListRefMap(graph);
1.807 + }
1.808 +
1.809 +
1.810 + };
1.811 +
1.812 + namespace _min_cut_bits {
1.813 + template <typename _Key>
1.814 + class LastTwoMap {
1.815 + public:
1.816 + typedef _Key Key;
1.817 + typedef bool Value;
1.818 +
1.819 + LastTwoMap(int _num) : num(_num) {}
1.820 + void set(const Key& key, bool val) {
1.821 + if (!val) return;
1.822 + --num;
1.823 + if (num > 1) return;
1.824 + keys[num] = key;
1.825 + }
1.826 +
1.827 + Key operator[](int index) const { return keys[index]; }
1.828 + private:
1.829 + Key keys[2];
1.830 + int num;
1.831 + };
1.832 + }
1.833 +
1.834 + /// \ingroup topology
1.835 + ///
1.836 + /// \brief Calculates the min cut in an undirected graph.
1.837 + ///
1.838 + /// Calculates the min cut in an undirected graph.
1.839 + /// The algorithm separates the graph's nodes to two partitions with the
1.840 + /// min sum of edge capacities between the two partitions. The
1.841 + /// algorithm can be used to test the netaux reliability specifically
1.842 + /// to test how many links have to be destroyed in the netaux to split it
1.843 + /// at least two distinict subnetaux.
1.844 + ///
1.845 + /// The complexity of the algorithm is O(n*e*log(n)) but with Fibonacci
1.846 + /// heap it can be decreased to O(n*e+n^2*log(n)). When the neutral capacity
1.847 + /// map is used then it uses LinearHeap which results O(n*e) time complexity.
1.848 +#ifdef DOXYGEN
1.849 + template <typename _Graph, typename _CapacityMap, typename _Traits>
1.850 +#else
1.851 + template <typename _Graph = ListUGraph,
1.852 + typename _CapacityMap = typename _Graph::template UEdgeMap<int>,
1.853 + typename _Traits = MinCutDefaultTraits<_Graph, _CapacityMap> >
1.854 +#endif
1.855 + class MinCut {
1.856 + public:
1.857 + /// \brief \ref Exception for uninitialized parameters.
1.858 + ///
1.859 + /// This error represents problems in the initialization
1.860 + /// of the parameters of the algorithms.
1.861 + class UninitializedParameter : public lemon::UninitializedParameter {
1.862 + public:
1.863 + virtual const char* exceptionName() const {
1.864 + return "lemon::MinCut::UninitializedParameter";
1.865 + }
1.866 + };
1.867 +
1.868 +
1.869 + private:
1.870 +
1.871 + typedef _Traits Traits;
1.872 + /// The type of the underlying graph.
1.873 + typedef typename Traits::Graph Graph;
1.874 +
1.875 + /// The type of the capacity of the edges.
1.876 + typedef typename Traits::CapacityMap::Value Value;
1.877 + /// The type of the map that stores the edge capacities.
1.878 + typedef typename Traits::CapacityMap CapacityMap;
1.879 + /// The type of the aux graph
1.880 + typedef typename Traits::AuxGraph AuxGraph;
1.881 + /// The type of the aux capacity map
1.882 + typedef typename Traits::AuxCapacityMap AuxCapacityMap;
1.883 + /// The cross reference type used for the current heap.
1.884 + typedef typename Traits::HeapCrossRef HeapCrossRef;
1.885 + /// The heap type used by the max cardinality algorithm.
1.886 + typedef typename Traits::Heap Heap;
1.887 + /// The node refrefernces between the original and aux graph type.
1.888 + typedef typename Traits::NodeRefMap NodeRefMap;
1.889 + /// The list node refrefernces in the original graph type.
1.890 + typedef typename Traits::ListRefMap ListRefMap;
1.891 +
1.892 + public:
1.893 +
1.894 + ///\name Named template parameters
1.895 +
1.896 + ///@{
1.897 +
1.898 + struct DefNeutralCapacityTraits : public Traits {
1.899 + typedef ConstMap<typename Graph::UEdge, Const<int, 1> > CapacityMap;
1.900 + static CapacityMap *createCapacityMap(const Graph&) {
1.901 + return new CapacityMap();
1.902 + }
1.903 + };
1.904 + /// \brief \ref named-templ-param "Named parameter" for setting
1.905 + /// the capacity type to constMap<UEdge, int, 1>()
1.906 + ///
1.907 + /// \ref named-templ-param "Named parameter" for setting
1.908 + /// the capacity type to constMap<UEdge, int, 1>()
1.909 + struct DefNeutralCapacity
1.910 + : public MinCut<Graph, CapacityMap, DefNeutralCapacityTraits> {
1.911 + typedef MinCut<Graph, CapacityMap, DefNeutralCapacityTraits> Create;
1.912 + };
1.913 +
1.914 +
1.915 + template <class H, class CR>
1.916 + struct DefHeapTraits : public Traits {
1.917 + typedef CR HeapCrossRef;
1.918 + typedef H Heap;
1.919 + static HeapCrossRef *createHeapCrossRef(const AuxGraph &) {
1.920 + throw UninitializedParameter();
1.921 + }
1.922 + static Heap *createHeap(HeapCrossRef &) {
1.923 + throw UninitializedParameter();
1.924 + }
1.925 + };
1.926 + /// \brief \ref named-templ-param "Named parameter" for setting heap
1.927 + /// and cross reference type
1.928 + ///
1.929 + /// \ref named-templ-param "Named parameter" for setting heap and cross
1.930 + /// reference type
1.931 + template <class H, class CR = typename Graph::template NodeMap<int> >
1.932 + struct DefHeap
1.933 + : public MinCut<Graph, CapacityMap, DefHeapTraits<H, CR> > {
1.934 + typedef MinCut< Graph, CapacityMap, DefHeapTraits<H, CR> > Create;
1.935 + };
1.936 +
1.937 + template <class H, class CR>
1.938 + struct DefStandardHeapTraits : public Traits {
1.939 + typedef CR HeapCrossRef;
1.940 + typedef H Heap;
1.941 + static HeapCrossRef *createHeapCrossRef(const AuxGraph &graph) {
1.942 + return new HeapCrossRef(graph);
1.943 + }
1.944 + static Heap *createHeap(HeapCrossRef &crossref) {
1.945 + return new Heap(crossref);
1.946 + }
1.947 + };
1.948 +
1.949 + /// \brief \ref named-templ-param "Named parameter" for setting heap and
1.950 + /// cross reference type with automatic allocation
1.951 + ///
1.952 + /// \ref named-templ-param "Named parameter" for setting heap and cross
1.953 + /// reference type. It can allocate the heap and the cross reference
1.954 + /// object if the cross reference's constructor waits for the graph as
1.955 + /// parameter and the heap's constructor waits for the cross reference.
1.956 + template <class H, class CR = typename Graph::template NodeMap<int> >
1.957 + struct DefStandardHeap
1.958 + : public MinCut<Graph, CapacityMap, DefStandardHeapTraits<H, CR> > {
1.959 + typedef MinCut<Graph, CapacityMap, DefStandardHeapTraits<H, CR> >
1.960 + Create;
1.961 + };
1.962 +
1.963 + ///@}
1.964 +
1.965 +
1.966 + private:
1.967 + /// Pointer to the underlying graph.
1.968 + const Graph *_graph;
1.969 + /// Pointer to the capacity map
1.970 + const CapacityMap *_capacity;
1.971 + /// \brief Indicates if \ref _capacity is locally allocated
1.972 + /// (\c true) or not.
1.973 + bool local_capacity;
1.974 +
1.975 + /// Pointer to the aux graph.
1.976 + AuxGraph *_aux_graph;
1.977 + /// \brief Indicates if \ref _aux_graph is locally allocated
1.978 + /// (\c true) or not.
1.979 + bool local_aux_graph;
1.980 + /// Pointer to the aux capacity map
1.981 + AuxCapacityMap *_aux_capacity;
1.982 + /// \brief Indicates if \ref _aux_capacity is locally allocated
1.983 + /// (\c true) or not.
1.984 + bool local_aux_capacity;
1.985 + /// Pointer to the heap cross references.
1.986 + HeapCrossRef *_heap_cross_ref;
1.987 + /// \brief Indicates if \ref _heap_cross_ref is locally allocated
1.988 + /// (\c true) or not.
1.989 + bool local_heap_cross_ref;
1.990 + /// Pointer to the heap.
1.991 + Heap *_heap;
1.992 + /// Indicates if \ref _heap is locally allocated (\c true) or not.
1.993 + bool local_heap;
1.994 +
1.995 + /// The min cut value.
1.996 + Value _min_cut;
1.997 + /// The number of the nodes of the aux graph.
1.998 + int _node_num;
1.999 + /// The first and last node of the min cut in the next list;
1.1000 + typename Graph::Node _first_node, _last_node;
1.1001 +
1.1002 + /// \brief The first and last element in the list associated
1.1003 + /// to the aux graph node.
1.1004 + NodeRefMap *_first, *_last;
1.1005 + /// \brief The next node in the node lists.
1.1006 + ListRefMap *_next;
1.1007 +
1.1008 + void create_structures() {
1.1009 + if (!_capacity) {
1.1010 + local_capacity = true;
1.1011 + _capacity = Traits::createCapacityMap(*_graph);
1.1012 + }
1.1013 + if(!_aux_graph) {
1.1014 + local_aux_graph = true;
1.1015 + _aux_graph = Traits::createAuxGraph();
1.1016 + }
1.1017 + if(!_aux_capacity) {
1.1018 + local_aux_capacity = true;
1.1019 + _aux_capacity = Traits::createAuxCapacityMap(*_aux_graph);
1.1020 + }
1.1021 +
1.1022 + _first = Traits::createNodeRefMap(*_aux_graph);
1.1023 + _last = Traits::createNodeRefMap(*_aux_graph);
1.1024 +
1.1025 + _next = Traits::createListRefMap(*_graph);
1.1026 +
1.1027 + typename Graph::template NodeMap<typename AuxGraph::Node> ref(*_graph);
1.1028 +
1.1029 + for (typename Graph::NodeIt it(*_graph); it != INVALID; ++it) {
1.1030 + _next->set(it, INVALID);
1.1031 + typename AuxGraph::Node node = _aux_graph->addNode();
1.1032 + _first->set(node, it);
1.1033 + _last->set(node, it);
1.1034 + ref.set(it, node);
1.1035 + }
1.1036 +
1.1037 + for (typename Graph::UEdgeIt it(*_graph); it != INVALID; ++it) {
1.1038 + if (_graph->source(it) == _graph->target(it)) continue;
1.1039 + typename AuxGraph::UEdge uedge =
1.1040 + _aux_graph->addEdge(ref[_graph->source(it)],
1.1041 + ref[_graph->target(it)]);
1.1042 + _aux_capacity->set(uedge, (*_capacity)[it]);
1.1043 +
1.1044 + }
1.1045 +
1.1046 + if (!_heap_cross_ref) {
1.1047 + local_heap_cross_ref = true;
1.1048 + _heap_cross_ref = Traits::createHeapCrossRef(*_aux_graph);
1.1049 + }
1.1050 + if (!_heap) {
1.1051 + local_heap = true;
1.1052 + _heap = Traits::createHeap(*_heap_cross_ref);
1.1053 + }
1.1054 + }
1.1055 +
1.1056 + public :
1.1057 +
1.1058 + typedef MinCut Create;
1.1059 +
1.1060 +
1.1061 + /// \brief Constructor.
1.1062 + ///
1.1063 + ///\param graph the graph the algorithm will run on.
1.1064 + ///\param capacity the capacity map used by the algorithm.
1.1065 + MinCut(const Graph& graph, const CapacityMap& capacity)
1.1066 + : _graph(&graph),
1.1067 + _capacity(&capacity), local_capacity(false),
1.1068 + _aux_graph(0), local_aux_graph(false),
1.1069 + _aux_capacity(0), local_aux_capacity(false),
1.1070 + _heap_cross_ref(0), local_heap_cross_ref(false),
1.1071 + _heap(0), local_heap(false),
1.1072 + _first(0), _last(0), _next(0) {}
1.1073 +
1.1074 + /// \brief Constructor.
1.1075 + ///
1.1076 + /// This constructor can be used only when the Traits class
1.1077 + /// defines how can we instantiate a local capacity map.
1.1078 + /// If the DefNeutralCapacity used the algorithm automatically
1.1079 + /// construct the capacity map.
1.1080 + ///
1.1081 + ///\param graph the graph the algorithm will run on.
1.1082 + MinCut(const Graph& graph)
1.1083 + : _graph(&graph),
1.1084 + _capacity(0), local_capacity(false),
1.1085 + _aux_graph(0), local_aux_graph(false),
1.1086 + _aux_capacity(0), local_aux_capacity(false),
1.1087 + _heap_cross_ref(0), local_heap_cross_ref(false),
1.1088 + _heap(0), local_heap(false),
1.1089 + _first(0), _last(0), _next(0) {}
1.1090 +
1.1091 + /// \brief Destructor.
1.1092 + ///
1.1093 + /// Destructor.
1.1094 + ~MinCut() {
1.1095 + if (local_heap) delete _heap;
1.1096 + if (local_heap_cross_ref) delete _heap_cross_ref;
1.1097 + if (_first) delete _first;
1.1098 + if (_last) delete _last;
1.1099 + if (_next) delete _next;
1.1100 + if (local_aux_capacity) delete _aux_capacity;
1.1101 + if (local_aux_graph) delete _aux_graph;
1.1102 + if (local_capacity) delete _capacity;
1.1103 + }
1.1104 +
1.1105 + /// \brief Sets the heap and the cross reference used by algorithm.
1.1106 + ///
1.1107 + /// Sets the heap and the cross reference used by algorithm.
1.1108 + /// If you don't use this function before calling \ref run(),
1.1109 + /// it will allocate one. The destuctor deallocates this
1.1110 + /// automatically allocated heap and cross reference, of course.
1.1111 + /// \return <tt> (*this) </tt>
1.1112 + MinCut &heap(Heap& heap, HeapCrossRef &crossRef)
1.1113 + {
1.1114 + if (local_heap_cross_ref) {
1.1115 + delete _heap_cross_ref;
1.1116 + local_heap_cross_ref=false;
1.1117 + }
1.1118 + _heap_cross_ref = &crossRef;
1.1119 + if (local_heap) {
1.1120 + delete _heap;
1.1121 + local_heap=false;
1.1122 + }
1.1123 + _heap = &heap;
1.1124 + return *this;
1.1125 + }
1.1126 +
1.1127 + /// \brief Sets the aux graph.
1.1128 + ///
1.1129 + /// Sets the aux graph used by algorithm.
1.1130 + /// If you don't use this function before calling \ref run(),
1.1131 + /// it will allocate one. The destuctor deallocates this
1.1132 + /// automatically allocated graph, of course.
1.1133 + /// \return <tt> (*this) </tt>
1.1134 + MinCut &auxGraph(AuxGraph& aux_graph)
1.1135 + {
1.1136 + if(local_aux_graph) {
1.1137 + delete _aux_graph;
1.1138 + local_aux_graph=false;
1.1139 + }
1.1140 + _aux_graph = &aux_graph;
1.1141 + return *this;
1.1142 + }
1.1143 +
1.1144 + /// \brief Sets the aux capacity map.
1.1145 + ///
1.1146 + /// Sets the aux capacity map used by algorithm.
1.1147 + /// If you don't use this function before calling \ref run(),
1.1148 + /// it will allocate one. The destuctor deallocates this
1.1149 + /// automatically allocated graph, of course.
1.1150 + /// \return <tt> (*this) </tt>
1.1151 + MinCut &auxCapacityMap(AuxCapacityMap& aux_capacity_map)
1.1152 + {
1.1153 + if(local_aux_capacity) {
1.1154 + delete _aux_capacity;
1.1155 + local_aux_capacity=false;
1.1156 + }
1.1157 + _aux_capacity = &aux_capacity_map;
1.1158 + return *this;
1.1159 + }
1.1160 +
1.1161 + /// \name Execution control
1.1162 + /// The simplest way to execute the algorithm is to use
1.1163 + /// one of the member functions called \c run().
1.1164 + /// \n
1.1165 + /// If you need more control on the execution,
1.1166 + /// first you must call \ref init() and then call the start()
1.1167 + /// or proper times the processNextPhase() member functions.
1.1168 +
1.1169 + ///@{
1.1170 +
1.1171 + /// \brief Initializes the internal data structures.
1.1172 + ///
1.1173 + /// Initializes the internal data structures.
1.1174 + void init() {
1.1175 + create_structures();
1.1176 + _first_node = _last_node = INVALID;
1.1177 + _node_num = countNodes(*_graph);
1.1178 + }
1.1179 +
1.1180 + /// \brief Processes the next phase
1.1181 + ///
1.1182 + /// Processes the next phase in the algorithm. The function
1.1183 + /// should be called countNodes(graph) - 1 times to get
1.1184 + /// surely the min cut in the graph. The
1.1185 + ///
1.1186 + ///\return %True when the algorithm finished.
1.1187 + bool processNextPhase() {
1.1188 + if (_node_num <= 1) return true;
1.1189 + using namespace _min_cut_bits;
1.1190 +
1.1191 + typedef typename AuxGraph::Node Node;
1.1192 + typedef typename AuxGraph::NodeIt NodeIt;
1.1193 + typedef typename AuxGraph::UEdge UEdge;
1.1194 + typedef typename AuxGraph::IncEdgeIt IncEdgeIt;
1.1195 +
1.1196 + typedef typename MaxCardinalitySearch<AuxGraph, AuxCapacityMap>::
1.1197 + template DefHeap<Heap, HeapCrossRef>::
1.1198 + template DefCardinalityMap<NullMap<Node, Value> >::
1.1199 + template DefProcessedMap<LastTwoMap<Node> >::
1.1200 + Create MaxCardinalitySearch;
1.1201 +
1.1202 + MaxCardinalitySearch mcs(*_aux_graph, *_aux_capacity);
1.1203 + for (NodeIt it(*_aux_graph); it != INVALID; ++it) {
1.1204 + _heap_cross_ref->set(it, Heap::PRE_HEAP);
1.1205 + }
1.1206 + mcs.heap(*_heap, *_heap_cross_ref);
1.1207 +
1.1208 + LastTwoMap<Node> last_two_nodes(_node_num);
1.1209 + mcs.processedMap(last_two_nodes);
1.1210 +
1.1211 + NullMap<Node, Value> cardinality;
1.1212 + mcs.cardinalityMap(cardinality);
1.1213 +
1.1214 + mcs.run();
1.1215 +
1.1216 + Node new_node = _aux_graph->addNode();
1.1217 +
1.1218 + typename AuxGraph::template NodeMap<UEdge> edges(*_aux_graph, INVALID);
1.1219 +
1.1220 + Node first_node = last_two_nodes[0];
1.1221 + Node second_node = last_two_nodes[1];
1.1222 +
1.1223 + _next->set((*_last)[first_node], (*_first)[second_node]);
1.1224 + _first->set(new_node, (*_first)[first_node]);
1.1225 + _last->set(new_node, (*_last)[second_node]);
1.1226 +
1.1227 + Value current_cut = 0;
1.1228 + for (IncEdgeIt it(*_aux_graph, first_node); it != INVALID; ++it) {
1.1229 + Node node = _aux_graph->runningNode(it);
1.1230 + current_cut += (*_aux_capacity)[it];
1.1231 + if (node == second_node) continue;
1.1232 + if (edges[node] == INVALID) {
1.1233 + edges[node] = _aux_graph->addEdge(new_node, node);
1.1234 + (*_aux_capacity)[edges[node]] = (*_aux_capacity)[it];
1.1235 + } else {
1.1236 + (*_aux_capacity)[edges[node]] += (*_aux_capacity)[it];
1.1237 + }
1.1238 + }
1.1239 +
1.1240 + if (_first_node == INVALID || current_cut < _min_cut) {
1.1241 + _first_node = (*_first)[first_node];
1.1242 + _last_node = (*_last)[first_node];
1.1243 + _min_cut = current_cut;
1.1244 + }
1.1245 +
1.1246 + _aux_graph->erase(first_node);
1.1247 +
1.1248 + for (IncEdgeIt it(*_aux_graph, second_node); it != INVALID; ++it) {
1.1249 + Node node = _aux_graph->runningNode(it);
1.1250 + if (edges[node] == INVALID) {
1.1251 + edges[node] = _aux_graph->addEdge(new_node, node);
1.1252 + (*_aux_capacity)[edges[node]] = (*_aux_capacity)[it];
1.1253 + } else {
1.1254 + (*_aux_capacity)[edges[node]] += (*_aux_capacity)[it];
1.1255 + }
1.1256 + }
1.1257 + _aux_graph->erase(second_node);
1.1258 +
1.1259 + --_node_num;
1.1260 + return _node_num == 1;
1.1261 + }
1.1262 +
1.1263 + /// \brief Executes the algorithm.
1.1264 + ///
1.1265 + /// Executes the algorithm.
1.1266 + ///
1.1267 + /// \pre init() must be called
1.1268 + void start() {
1.1269 + while (!processNextPhase());
1.1270 + }
1.1271 +
1.1272 +
1.1273 + /// \brief Runs %MinCut algorithm.
1.1274 + ///
1.1275 + /// This method runs the %Min cut algorithm
1.1276 + ///
1.1277 + /// \note mc.run(s) is just a shortcut of the following code.
1.1278 + ///\code
1.1279 + /// mc.init();
1.1280 + /// mc.start();
1.1281 + ///\endcode
1.1282 + void run() {
1.1283 + init();
1.1284 + start();
1.1285 + }
1.1286 +
1.1287 + ///@}
1.1288 +
1.1289 + /// \name Query Functions
1.1290 + /// The result of the %MinCut algorithm can be obtained using these
1.1291 + /// functions.\n
1.1292 + /// Before the use of these functions,
1.1293 + /// either run() or start() must be called.
1.1294 +
1.1295 + ///@{
1.1296 +
1.1297 + /// \brief Returns the min cut value.
1.1298 + ///
1.1299 + /// Returns the min cut value if the algorithm finished.
1.1300 + /// After the first processNextPhase() it is a value of a
1.1301 + /// valid cut in the graph.
1.1302 + Value minCut() const {
1.1303 + return _min_cut;
1.1304 + }
1.1305 +
1.1306 + /// \brief Returns a min cut in a NodeMap.
1.1307 + ///
1.1308 + /// It sets the nodes of one of the two partitions to true in
1.1309 + /// the given BoolNodeMap. The map contains a valid cut if the
1.1310 + /// map have been set false previously.
1.1311 + template <typename NodeMap>
1.1312 + Value quickMinCut(NodeMap& nodeMap) const {
1.1313 + for (typename Graph::Node it = _first_node;
1.1314 + it != _last_node; it = (*_next)[it]) {
1.1315 + nodeMap.set(it, true);
1.1316 + }
1.1317 + nodeMap.set(_last_node, true);
1.1318 + return minCut();
1.1319 + }
1.1320 +
1.1321 + /// \brief Returns a min cut in a NodeMap.
1.1322 + ///
1.1323 + /// It sets the nodes of one of the two partitions to true and
1.1324 + /// the other partition to false. The function first set all of the
1.1325 + /// nodes to false and after it call the quickMinCut() member.
1.1326 + template <typename NodeMap>
1.1327 + Value minCut(NodeMap& nodeMap) const {
1.1328 + for (typename Graph::NodeIt it(*_graph); it != INVALID; ++it) {
1.1329 + nodeMap.set(it, false);
1.1330 + }
1.1331 + quickMinCut(nodeMap);
1.1332 + return minCut();
1.1333 + }
1.1334 +
1.1335 + /// \brief Returns a min cut in an EdgeMap.
1.1336 + ///
1.1337 + /// If an undirected edge is in a min cut then it will be
1.1338 + /// set to true and the others will be set to false in the given map.
1.1339 + template <typename EdgeMap>
1.1340 + Value cutEdges(EdgeMap& edgeMap) const {
1.1341 + typename Graph::template NodeMap<bool> cut(*_graph, false);
1.1342 + quickMinCut(cut);
1.1343 + for (typename Graph::EdgeIt it(*_graph); it != INVALID; ++it) {
1.1344 + edgeMap.set(it, cut[_graph->source(it)] ^ cut[_graph->target(it)]);
1.1345 + }
1.1346 + return minCut();
1.1347 + }
1.1348 +
1.1349 + ///@}
1.1350 +
1.1351 + };
1.1352 +}
1.1353 +
1.1354 +#endif