1.1 --- a/lemon/Makefile.am Tue Feb 07 09:32:55 2006 +0000
1.2 +++ b/lemon/Makefile.am Mon Feb 13 09:42:53 2006 +0000
1.3 @@ -58,6 +58,7 @@
1.4 map_iterator.h \
1.5 max_matching.h \
1.6 min_cost_flow.h \
1.7 + minimal_cut.h \
1.8 suurballe.h \
1.9 preflow.h \
1.10 path.h \
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/lemon/minimal_cut.h Mon Feb 13 09:42:53 2006 +0000
2.3 @@ -0,0 +1,1351 @@
2.4 +/* -*- C++ -*-
2.5 + * lemon/minimal_cut.h - Part of LEMON, a generic C++ optimization library
2.6 + *
2.7 + * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
2.8 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
2.9 + *
2.10 + * Permission to use, modify and distribute this software is granted
2.11 + * provided that this copyright notice appears in all copies. For
2.12 + * precise terms see the accompanying LICENSE file.
2.13 + *
2.14 + * This software is provided "AS IS" with no warranty of any kind,
2.15 + * express or implied, and with no claim as to its suitability for any
2.16 + * purpose.
2.17 + *
2.18 + */
2.19 +
2.20 +#ifndef LEMON_MINIMAL_CUT_H
2.21 +#define LEMON_MINIMAL_CUT_H
2.22 +
2.23 +
2.24 +/// \ingroup topology
2.25 +/// \file
2.26 +/// \brief Maximum cardinality search and minimal cut in undirected graphs.
2.27 +
2.28 +#include <lemon/list_graph.h>
2.29 +#include <lemon/bin_heap.h>
2.30 +#include <lemon/linear_heap.h>
2.31 +
2.32 +#include <lemon/invalid.h>
2.33 +#include <lemon/error.h>
2.34 +#include <lemon/maps.h>
2.35 +
2.36 +#include <functional>
2.37 +
2.38 +namespace lemon {
2.39 +
2.40 + namespace _minimal_cut_bits {
2.41 +
2.42 + template <typename CapacityMap>
2.43 + struct HeapSelector {
2.44 + template <typename Key, typename Value, typename Ref>
2.45 + struct Selector {
2.46 + typedef BinHeap<Key, Value, Ref, std::greater<Value> > Heap;
2.47 + };
2.48 + };
2.49 +
2.50 + template <typename CapacityKey>
2.51 + struct HeapSelector<ConstMap<CapacityKey, Const<int, 1> > > {
2.52 + template <typename Key, typename Value, typename Ref>
2.53 + struct Selector {
2.54 + typedef LinearHeap<Key, Ref, false > Heap;
2.55 + };
2.56 + };
2.57 +
2.58 + }
2.59 +
2.60 + /// \brief Default traits class of MaxCardinalitySearch class.
2.61 + ///
2.62 + /// Default traits class of MaxCardinalitySearch class.
2.63 + /// \param Graph Graph type.
2.64 + /// \param CapacityMap Type of length map.
2.65 + template <typename _Graph, typename _CapacityMap>
2.66 + struct MaxCardinalitySearchDefaultTraits {
2.67 + /// The graph type the algorithm runs on.
2.68 + typedef _Graph Graph;
2.69 +
2.70 + /// \brief The type of the map that stores the edge capacities.
2.71 + ///
2.72 + /// The type of the map that stores the edge capacities.
2.73 + /// It must meet the \ref concept::ReadMap "ReadMap" concept.
2.74 + typedef _CapacityMap CapacityMap;
2.75 +
2.76 + /// \brief The type of the capacity of the edges.
2.77 + typedef typename CapacityMap::Value Value;
2.78 +
2.79 + /// \brief The cross reference type used by heap.
2.80 + ///
2.81 + /// The cross reference type used by heap.
2.82 + /// Usually it is \c Graph::NodeMap<int>.
2.83 + typedef typename Graph::template NodeMap<int> HeapCrossRef;
2.84 +
2.85 + /// \brief Instantiates a HeapCrossRef.
2.86 + ///
2.87 + /// This function instantiates a \ref HeapCrossRef.
2.88 + /// \param graph is the graph, to which we would like to define the
2.89 + /// HeapCrossRef.
2.90 + static HeapCrossRef *createHeapCrossRef(const Graph &graph) {
2.91 + return new HeapCrossRef(graph);
2.92 + }
2.93 +
2.94 + /// \brief The heap type used by MaxCardinalitySearch algorithm.
2.95 + ///
2.96 + /// The heap type used by MaxCardinalitySearch algorithm. It should
2.97 + /// maximalize the priorities. The default heap type is
2.98 + /// the \ref BinHeap, but it is specialized when the
2.99 + /// CapacityMap is ConstMap<Graph::Node, Const<int, 1> >
2.100 + /// to LinearHeap.
2.101 + ///
2.102 + /// \sa MaxCardinalitySearch
2.103 + typedef typename _minimal_cut_bits
2.104 + ::HeapSelector<CapacityMap>
2.105 + ::template Selector<typename Graph::Node, Value, HeapCrossRef>
2.106 + ::Heap Heap;
2.107 +
2.108 + /// \brief Instantiates a Heap.
2.109 + ///
2.110 + /// This function instantiates a \ref Heap.
2.111 + /// \param crossref The cross reference of the heap.
2.112 + static Heap *createHeap(HeapCrossRef& crossref) {
2.113 + return new Heap(crossref);
2.114 + }
2.115 +
2.116 + /// \brief The type of the map that stores whether a nodes is processed.
2.117 + ///
2.118 + /// The type of the map that stores whether a nodes is processed.
2.119 + /// It must meet the \ref concept::WriteMap "WriteMap" concept.
2.120 + /// By default it is a NullMap.
2.121 + typedef NullMap<typename Graph::Node, bool> ProcessedMap;
2.122 +
2.123 + /// \brief Instantiates a ProcessedMap.
2.124 + ///
2.125 + /// This function instantiates a \ref ProcessedMap.
2.126 + /// \param g is the graph, to which
2.127 + /// we would like to define the \ref ProcessedMap
2.128 +#ifdef DOXYGEN
2.129 + static ProcessedMap *createProcessedMap(const Graph &graph)
2.130 +#else
2.131 + static ProcessedMap *createProcessedMap(const Graph &)
2.132 +#endif
2.133 + {
2.134 + return new ProcessedMap();
2.135 + }
2.136 +
2.137 + /// \brief The type of the map that stores the cardinalties of the nodes.
2.138 + ///
2.139 + /// The type of the map that stores the cardinalities of the nodes.
2.140 + /// It must meet the \ref concept::WriteMap "WriteMap" concept.
2.141 + typedef typename Graph::template NodeMap<Value> CardinalityMap;
2.142 +
2.143 + /// \brief Instantiates a CardinalityMap.
2.144 + ///
2.145 + /// This function instantiates a \ref CardinalityMap.
2.146 + /// \param graph is the graph, to which we would like to define the \ref
2.147 + /// CardinalityMap
2.148 + static CardinalityMap *createCardinalityMap(const Graph &graph) {
2.149 + return new CardinalityMap(graph);
2.150 + }
2.151 +
2.152 + };
2.153 +
2.154 + /// \ingroup topology
2.155 + ///
2.156 + /// \brief Maximum Cardinality Search algorithm class.
2.157 + ///
2.158 + /// This class provides an efficient implementation of Maximum Cardinality
2.159 + /// Search algorithm. The maximum cardinality search chooses first time any
2.160 + /// node of the graph. Then every time chooses that node which connected
2.161 + /// to the processed nodes at most in the sum of capacities on the out
2.162 + /// edges. If there is a cut in the graph the algorithm should choose
2.163 + /// again any unprocessed node of the graph. Each nodes cardinality is
2.164 + /// the sum of capacities on the out edges to the nodes which are processed
2.165 + /// before the given node.
2.166 + ///
2.167 + /// The edge capacities are passed to the algorithm using a
2.168 + /// \ref concept::ReadMap "ReadMap", so it is easy to change it to any
2.169 + /// kind of capacity.
2.170 + ///
2.171 + /// The type of the capacity is determined by the \ref
2.172 + /// concept::ReadMap::Value "Value" of the capacity map.
2.173 + ///
2.174 + /// It is also possible to change the underlying priority heap.
2.175 + ///
2.176 + ///
2.177 + /// \param _Graph The graph type the algorithm runs on. The default value
2.178 + /// is \ref ListGraph. The value of Graph is not used directly by
2.179 + /// the search algorithm, it is only passed to
2.180 + /// \ref MaxCardinalitySearchDefaultTraits.
2.181 + /// \param _CapacityMap This read-only EdgeMap determines the capacities of
2.182 + /// the edges. It is read once for each edge, so the map may involve in
2.183 + /// relatively time consuming process to compute the edge capacity if
2.184 + /// it is necessary. The default map type is \ref
2.185 + /// concept::StaticGraph::EdgeMap "Graph::EdgeMap<int>". The value
2.186 + /// of CapacityMap is not used directly by search algorithm, it is only
2.187 + /// passed to \ref MaxCardinalitySearchDefaultTraits.
2.188 + /// \param _Traits Traits class to set various data types used by the
2.189 + /// algorithm. The default traits class is
2.190 + /// \ref MaxCardinalitySearchDefaultTraits
2.191 + /// "MaxCardinalitySearchDefaultTraits<_Graph, _CapacityMap>".
2.192 + /// See \ref MaxCardinalitySearchDefaultTraits
2.193 + /// for the documentation of a MaxCardinalitySearch traits class.
2.194 + ///
2.195 + /// \author Balazs Dezso
2.196 +
2.197 +#ifdef DOXYGEN
2.198 + template <typename _Graph, typename _CapacityMap, typename _Traits>
2.199 +#else
2.200 + template <typename _Graph = ListUGraph,
2.201 + typename _CapacityMap = typename _Graph::template EdgeMap<int>,
2.202 + typename _Traits =
2.203 + MaxCardinalitySearchDefaultTraits<_Graph, _CapacityMap> >
2.204 +#endif
2.205 + class MaxCardinalitySearch {
2.206 + public:
2.207 + /// \brief \ref Exception for uninitialized parameters.
2.208 + ///
2.209 + /// This error represents problems in the initialization
2.210 + /// of the parameters of the algorithms.
2.211 + class UninitializedParameter : public lemon::UninitializedParameter {
2.212 + public:
2.213 + virtual const char* exceptionName() const {
2.214 + return "lemon::MaxCardinalitySearch::UninitializedParameter";
2.215 + }
2.216 + };
2.217 +
2.218 + typedef _Traits Traits;
2.219 + ///The type of the underlying graph.
2.220 + typedef typename Traits::Graph Graph;
2.221 +
2.222 + ///The type of the capacity of the edges.
2.223 + typedef typename Traits::CapacityMap::Value Value;
2.224 + ///The type of the map that stores the edge capacities.
2.225 + typedef typename Traits::CapacityMap CapacityMap;
2.226 + ///The type of the map indicating if a node is processed.
2.227 + typedef typename Traits::ProcessedMap ProcessedMap;
2.228 + ///The type of the map that stores the cardinalities of the nodes.
2.229 + typedef typename Traits::CardinalityMap CardinalityMap;
2.230 + ///The cross reference type used for the current heap.
2.231 + typedef typename Traits::HeapCrossRef HeapCrossRef;
2.232 + ///The heap type used by the algorithm. It maximize the priorities.
2.233 + typedef typename Traits::Heap Heap;
2.234 + private:
2.235 + /// Pointer to the underlying graph.
2.236 + const Graph *_graph;
2.237 + /// Pointer to the capacity map
2.238 + const CapacityMap *_capacity;
2.239 + ///Pointer to the map of cardinality.
2.240 + CardinalityMap *_cardinality;
2.241 + ///Indicates if \ref _cardinality is locally allocated (\c true) or not.
2.242 + bool local_cardinality;
2.243 + ///Pointer to the map of processed status of the nodes.
2.244 + ProcessedMap *_processed;
2.245 + ///Indicates if \ref _processed is locally allocated (\c true) or not.
2.246 + bool local_processed;
2.247 + ///Pointer to the heap cross references.
2.248 + HeapCrossRef *_heap_cross_ref;
2.249 + ///Indicates if \ref _heap_cross_ref is locally allocated (\c true) or not.
2.250 + bool local_heap_cross_ref;
2.251 + ///Pointer to the heap.
2.252 + Heap *_heap;
2.253 + ///Indicates if \ref _heap is locally allocated (\c true) or not.
2.254 + bool local_heap;
2.255 +
2.256 + public :
2.257 +
2.258 + typedef MaxCardinalitySearch Create;
2.259 +
2.260 + ///\name Named template parameters
2.261 +
2.262 + ///@{
2.263 +
2.264 + template <class T>
2.265 + struct DefCardinalityMapTraits : public Traits {
2.266 + typedef T CardinalityMap;
2.267 + static CardinalityMap *createCardinalityMap(const Graph &)
2.268 + {
2.269 + throw UninitializedParameter();
2.270 + }
2.271 + };
2.272 + /// \brief \ref named-templ-param "Named parameter" for setting
2.273 + /// CardinalityMap type
2.274 + ///
2.275 + /// \ref named-templ-param "Named parameter" for setting CardinalityMap
2.276 + /// type
2.277 + template <class T>
2.278 + struct DefCardinalityMap
2.279 + : public MaxCardinalitySearch<Graph, CapacityMap,
2.280 + DefCardinalityMapTraits<T> > {
2.281 + typedef MaxCardinalitySearch<Graph, CapacityMap,
2.282 + DefCardinalityMapTraits<T> > Create;
2.283 + };
2.284 +
2.285 + template <class T>
2.286 + struct DefProcessedMapTraits : public Traits {
2.287 + typedef T ProcessedMap;
2.288 + static ProcessedMap *createProcessedMap(const Graph &) {
2.289 + throw UninitializedParameter();
2.290 + }
2.291 + };
2.292 + /// \brief \ref named-templ-param "Named parameter" for setting
2.293 + /// ProcessedMap type
2.294 + ///
2.295 + /// \ref named-templ-param "Named parameter" for setting ProcessedMap type
2.296 + ///
2.297 + template <class T>
2.298 + struct DefProcessedMap
2.299 + : public MaxCardinalitySearch<Graph, CapacityMap,
2.300 + DefProcessedMapTraits<T> > {
2.301 + typedef MaxCardinalitySearch<Graph, CapacityMap,
2.302 + DefProcessedMapTraits<T> > Create;
2.303 + };
2.304 +
2.305 + template <class H, class CR>
2.306 + struct DefHeapTraits : public Traits {
2.307 + typedef CR HeapCrossRef;
2.308 + typedef H Heap;
2.309 + static HeapCrossRef *createHeapCrossRef(const Graph &) {
2.310 + throw UninitializedParameter();
2.311 + }
2.312 + static Heap *createHeap(HeapCrossRef &) {
2.313 + throw UninitializedParameter();
2.314 + }
2.315 + };
2.316 + /// \brief \ref named-templ-param "Named parameter" for setting heap
2.317 + /// and cross reference type
2.318 + ///
2.319 + /// \ref named-templ-param "Named parameter" for setting heap and cross
2.320 + /// reference type
2.321 + template <class H, class CR = typename Graph::template NodeMap<int> >
2.322 + struct DefHeap
2.323 + : public MaxCardinalitySearch<Graph, CapacityMap,
2.324 + DefHeapTraits<H, CR> > {
2.325 + typedef MaxCardinalitySearch< Graph, CapacityMap,
2.326 + DefHeapTraits<H, CR> > Create;
2.327 + };
2.328 +
2.329 + template <class H, class CR>
2.330 + struct DefStandardHeapTraits : public Traits {
2.331 + typedef CR HeapCrossRef;
2.332 + typedef H Heap;
2.333 + static HeapCrossRef *createHeapCrossRef(const Graph &graph) {
2.334 + return new HeapCrossRef(graph);
2.335 + }
2.336 + static Heap *createHeap(HeapCrossRef &crossref) {
2.337 + return new Heap(crossref);
2.338 + }
2.339 + };
2.340 +
2.341 + /// \brief \ref named-templ-param "Named parameter" for setting heap and
2.342 + /// cross reference type with automatic allocation
2.343 + ///
2.344 + /// \ref named-templ-param "Named parameter" for setting heap and cross
2.345 + /// reference type. It can allocate the heap and the cross reference
2.346 + /// object if the cross reference's constructor waits for the graph as
2.347 + /// parameter and the heap's constructor waits for the cross reference.
2.348 + template <class H, class CR = typename Graph::template NodeMap<int> >
2.349 + struct DefStandardHeap
2.350 + : public MaxCardinalitySearch<Graph, CapacityMap,
2.351 + DefStandardHeapTraits<H, CR> > {
2.352 + typedef MaxCardinalitySearch<Graph, CapacityMap,
2.353 + DefStandardHeapTraits<H, CR> >
2.354 + Create;
2.355 + };
2.356 +
2.357 + ///@}
2.358 +
2.359 +
2.360 + protected:
2.361 +
2.362 + MaxCardinalitySearch() {}
2.363 +
2.364 + public:
2.365 +
2.366 + /// \brief Constructor.
2.367 + ///
2.368 + ///\param _graph the graph the algorithm will run on.
2.369 + ///\param _capacity the capacity map used by the algorithm.
2.370 + MaxCardinalitySearch(const Graph& graph, const CapacityMap& capacity) :
2.371 + _graph(&graph), _capacity(&capacity),
2.372 + _cardinality(0), local_cardinality(false),
2.373 + _processed(0), local_processed(false),
2.374 + _heap_cross_ref(0), local_heap_cross_ref(false),
2.375 + _heap(0), local_heap(false)
2.376 + { }
2.377 +
2.378 + /// \brief Destructor.
2.379 + ~MaxCardinalitySearch() {
2.380 + if(local_cardinality) delete _cardinality;
2.381 + if(local_processed) delete _processed;
2.382 + if(local_heap_cross_ref) delete _heap_cross_ref;
2.383 + if(local_heap) delete _heap;
2.384 + }
2.385 +
2.386 + /// \brief Sets the capacity map.
2.387 + ///
2.388 + /// Sets the capacity map.
2.389 + /// \return <tt> (*this) </tt>
2.390 + MaxCardinalitySearch &capacityMap(const CapacityMap &m) {
2.391 + _capacity = &m;
2.392 + return *this;
2.393 + }
2.394 +
2.395 + /// \brief Sets the map storing the cardinalities calculated by the
2.396 + /// algorithm.
2.397 + ///
2.398 + /// Sets the map storing the cardinalities calculated by the algorithm.
2.399 + /// If you don't use this function before calling \ref run(),
2.400 + /// it will allocate one. The destuctor deallocates this
2.401 + /// automatically allocated map, of course.
2.402 + /// \return <tt> (*this) </tt>
2.403 + MaxCardinalitySearch &cardinalityMap(CardinalityMap &m) {
2.404 + if(local_cardinality) {
2.405 + delete _cardinality;
2.406 + local_cardinality=false;
2.407 + }
2.408 + _cardinality = &m;
2.409 + return *this;
2.410 + }
2.411 +
2.412 + /// \brief Sets the map storing the processed nodes.
2.413 + ///
2.414 + /// Sets the map storing the processed nodes.
2.415 + /// If you don't use this function before calling \ref run(),
2.416 + /// it will allocate one. The destuctor deallocates this
2.417 + /// automatically allocated map, of course.
2.418 + /// \return <tt> (*this) </tt>
2.419 + MaxCardinalitySearch &processedMap(ProcessedMap &m)
2.420 + {
2.421 + if(local_processed) {
2.422 + delete _processed;
2.423 + local_processed=false;
2.424 + }
2.425 + _processed = &m;
2.426 + return *this;
2.427 + }
2.428 +
2.429 + /// \brief Sets the heap and the cross reference used by algorithm.
2.430 + ///
2.431 + /// Sets the heap and the cross reference used by algorithm.
2.432 + /// If you don't use this function before calling \ref run(),
2.433 + /// it will allocate one. The destuctor deallocates this
2.434 + /// automatically allocated map, of course.
2.435 + /// \return <tt> (*this) </tt>
2.436 + MaxCardinalitySearch &heap(Heap& heap, HeapCrossRef &crossRef) {
2.437 + if(local_heap_cross_ref) {
2.438 + delete _heap_cross_ref;
2.439 + local_heap_cross_ref = false;
2.440 + }
2.441 + _heap_cross_ref = &crossRef;
2.442 + if(local_heap) {
2.443 + delete _heap;
2.444 + local_heap = false;
2.445 + }
2.446 + _heap = &heap;
2.447 + return *this;
2.448 + }
2.449 +
2.450 + private:
2.451 +
2.452 + typedef typename Graph::Node Node;
2.453 + typedef typename Graph::NodeIt NodeIt;
2.454 + typedef typename Graph::Edge Edge;
2.455 + typedef typename Graph::InEdgeIt InEdgeIt;
2.456 +
2.457 + void create_maps() {
2.458 + if(!_cardinality) {
2.459 + local_cardinality = true;
2.460 + _cardinality = Traits::createCardinalityMap(*_graph);
2.461 + }
2.462 + if(!_processed) {
2.463 + local_processed = true;
2.464 + _processed = Traits::createProcessedMap(*_graph);
2.465 + }
2.466 + if (!_heap_cross_ref) {
2.467 + local_heap_cross_ref = true;
2.468 + _heap_cross_ref = Traits::createHeapCrossRef(*_graph);
2.469 + }
2.470 + if (!_heap) {
2.471 + local_heap = true;
2.472 + _heap = Traits::createHeap(*_heap_cross_ref);
2.473 + }
2.474 + }
2.475 +
2.476 + void finalizeNodeData(Node node, Value capacity) {
2.477 + _processed->set(node, true);
2.478 + _cardinality->set(node, capacity);
2.479 + }
2.480 +
2.481 + public:
2.482 + /// \name Execution control
2.483 + /// The simplest way to execute the algorithm is to use
2.484 + /// one of the member functions called \c run(...).
2.485 + /// \n
2.486 + /// If you need more control on the execution,
2.487 + /// first you must call \ref init(), then you can add several source nodes
2.488 + /// with \ref addSource().
2.489 + /// Finally \ref start() will perform the actual path
2.490 + /// computation.
2.491 +
2.492 + ///@{
2.493 +
2.494 + /// \brief Initializes the internal data structures.
2.495 + ///
2.496 + /// Initializes the internal data structures.
2.497 + void init() {
2.498 + create_maps();
2.499 + _heap->clear();
2.500 + for (NodeIt it(*_graph) ; it != INVALID ; ++it) {
2.501 + _processed->set(it, false);
2.502 + _heap_cross_ref->set(it, Heap::PRE_HEAP);
2.503 + }
2.504 + }
2.505 +
2.506 + /// \brief Adds a new source node.
2.507 + ///
2.508 + /// Adds a new source node to the priority heap.
2.509 + ///
2.510 + /// It checks if the node has not yet been added to the heap.
2.511 + void addSource(Node source, Value capacity = 0) {
2.512 + if(_heap->state(source) == Heap::PRE_HEAP) {
2.513 + _heap->push(source, capacity);
2.514 + }
2.515 + }
2.516 +
2.517 + /// \brief Processes the next node in the priority heap
2.518 + ///
2.519 + /// Processes the next node in the priority heap.
2.520 + ///
2.521 + /// \return The processed node.
2.522 + ///
2.523 + /// \warning The priority heap must not be empty!
2.524 + Node processNextNode() {
2.525 + Node node = _heap->top();
2.526 + finalizeNodeData(node, _heap->prio());
2.527 + _heap->pop();
2.528 +
2.529 + for (InEdgeIt it(*_graph, node); it != INVALID; ++it) {
2.530 + Node source = _graph->source(it);
2.531 + switch (_heap->state(source)) {
2.532 + case Heap::PRE_HEAP:
2.533 + _heap->push(source, (*_capacity)[it]);
2.534 + break;
2.535 + case Heap::IN_HEAP:
2.536 + _heap->decrease(source, (*_heap)[source] + (*_capacity)[it]);
2.537 + break;
2.538 + case Heap::POST_HEAP:
2.539 + break;
2.540 + }
2.541 + }
2.542 + return node;
2.543 + }
2.544 +
2.545 + /// \brief Next node to be processed.
2.546 + ///
2.547 + /// Next node to be processed.
2.548 + ///
2.549 + /// \return The next node to be processed or INVALID if the
2.550 + /// priority heap is empty.
2.551 + Node nextNode() {
2.552 + return _heap->empty() ? _heap->top() : INVALID;
2.553 + }
2.554 +
2.555 + /// \brief Returns \c false if there are nodes
2.556 + /// to be processed in the priority heap
2.557 + ///
2.558 + /// Returns \c false if there are nodes
2.559 + /// to be processed in the priority heap
2.560 + bool emptyQueue() { return _heap->empty(); }
2.561 + /// \brief Returns the number of the nodes to be processed
2.562 + /// in the priority heap
2.563 + ///
2.564 + /// Returns the number of the nodes to be processed in the priority heap
2.565 + int queueSize() { return _heap->size(); }
2.566 +
2.567 + /// \brief Executes the algorithm.
2.568 + ///
2.569 + /// Executes the algorithm.
2.570 + ///
2.571 + ///\pre init() must be called and at least one node should be added
2.572 + /// with addSource() before using this function.
2.573 + ///
2.574 + /// This method runs the Maximum Cardinality Search algorithm from the
2.575 + /// source node(s).
2.576 + void start() {
2.577 + while ( !_heap->empty() ) processNextNode();
2.578 + }
2.579 +
2.580 + /// \brief Executes the algorithm until \c dest is reached.
2.581 + ///
2.582 + /// Executes the algorithm until \c dest is reached.
2.583 + ///
2.584 + /// \pre init() must be called and at least one node should be added
2.585 + /// with addSource() before using this function.
2.586 + ///
2.587 + /// This method runs the %MaxCardinalitySearch algorithm from the source
2.588 + /// nodes.
2.589 + void start(Node dest) {
2.590 + while ( !_heap->empty() && _heap->top()!=dest ) processNextNode();
2.591 + if ( !_heap->empty() ) finalizeNodeData(_heap->top(), _heap->prio());
2.592 + }
2.593 +
2.594 + /// \brief Executes the algorithm until a condition is met.
2.595 + ///
2.596 + /// Executes the algorithm until a condition is met.
2.597 + ///
2.598 + /// \pre init() must be called and at least one node should be added
2.599 + /// with addSource() before using this function.
2.600 + ///
2.601 + /// \param nm must be a bool (or convertible) node map. The algorithm
2.602 + /// will stop when it reaches a node \c v with <tt>nm[v]==true</tt>.
2.603 + template <typename NodeBoolMap>
2.604 + void start(const NodeBoolMap &nm) {
2.605 + while ( !_heap->empty() && !nm[_heap->top()] ) processNextNode();
2.606 + if ( !_heap->empty() ) finalizeNodeData(_heap->top(),_heap->prio());
2.607 + }
2.608 +
2.609 + /// \brief Runs the maximal cardinality search algorithm from node \c s.
2.610 + ///
2.611 + /// This method runs the %MaxCardinalitySearch algorithm from a root
2.612 + /// node \c s.
2.613 + ///
2.614 + ///\note d.run(s) is just a shortcut of the following code.
2.615 + ///\code
2.616 + /// d.init();
2.617 + /// d.addSource(s);
2.618 + /// d.start();
2.619 + ///\endcode
2.620 + void run(Node s) {
2.621 + init();
2.622 + addSource(s);
2.623 + start();
2.624 + }
2.625 +
2.626 + /// \brief Runs the maximal cardinality search algorithm for the
2.627 + /// whole graph.
2.628 + ///
2.629 + /// This method runs the %MaxCardinalitySearch algorithm from all
2.630 + /// unprocessed node of the graph.
2.631 + ///
2.632 + ///\note d.run(s) is just a shortcut of the following code.
2.633 + ///\code
2.634 + /// d.init();
2.635 + /// for (NodeIt it(graph); it != INVALID; ++it) {
2.636 + /// if (!d.reached(it)) {
2.637 + /// d.addSource(s);
2.638 + /// d.start();
2.639 + /// }
2.640 + /// }
2.641 + ///\endcode
2.642 + void run() {
2.643 + init();
2.644 + for (NodeIt it(*_graph); it != INVALID; ++it) {
2.645 + if (!reached(it)) {
2.646 + addSource(it);
2.647 + start();
2.648 + }
2.649 + }
2.650 + }
2.651 +
2.652 + ///@}
2.653 +
2.654 + /// \name Query Functions
2.655 + /// The result of the maximum cardinality search algorithm can be
2.656 + /// obtained using these functions.
2.657 + /// \n
2.658 + /// Before the use of these functions, either run() or start() must be
2.659 + /// called.
2.660 +
2.661 + ///@{
2.662 +
2.663 + /// \brief The cardinality of a node.
2.664 + ///
2.665 + /// Returns the cardinality of a node.
2.666 + /// \pre \ref run() must be called before using this function.
2.667 + /// \warning If node \c v in unreachable from the root the return value
2.668 + /// of this funcion is undefined.
2.669 + Value cardinality(Node node) const { return (*_cardinality)[node]; }
2.670 +
2.671 + /// \brief Returns a reference to the NodeMap of cardinalities.
2.672 + ///
2.673 + /// Returns a reference to the NodeMap of cardinalities. \pre \ref run()
2.674 + /// must be called before using this function.
2.675 + const CardinalityMap &cardinalityMap() const { return *_cardinality;}
2.676 +
2.677 + /// \brief Checks if a node is reachable from the root.
2.678 + ///
2.679 + /// Returns \c true if \c v is reachable from the root.
2.680 + /// \warning The source nodes are inditated as unreached.
2.681 + /// \pre \ref run() must be called before using this function.
2.682 + bool reached(Node v) { return (*_heap_cross_ref)[v] != Heap::PRE_HEAP; }
2.683 +
2.684 + /// \brief Checks if a node is processed.
2.685 + ///
2.686 + /// Returns \c true if \c v is processed, i.e. the shortest
2.687 + /// path to \c v has already found.
2.688 + /// \pre \ref run() must be called before using this function.
2.689 + bool processed(Node v) { return (*_heap_cross_ref)[v] == Heap::POST_HEAP; }
2.690 +
2.691 + ///@}
2.692 + };
2.693 +
2.694 + /// \brief Default traits class of MinimalCut class.
2.695 + ///
2.696 + /// Default traits class of MinimalCut class.
2.697 + /// \param Graph Graph type.
2.698 + /// \param CapacityMap Type of length map.
2.699 + template <typename _Graph, typename _CapacityMap>
2.700 + struct MinimalCutDefaultTraits {
2.701 + /// \brief The type of the capacity of the edges.
2.702 + typedef typename _CapacityMap::Value Value;
2.703 +
2.704 + /// The graph type the algorithm runs on.
2.705 + typedef _Graph Graph;
2.706 +
2.707 + /// The WorkGraph type which is an EraseableGraph
2.708 + typedef ListUGraph WorkGraph;
2.709 +
2.710 + /// \brief Instantiates a WorkGraph.
2.711 + ///
2.712 + /// This function instantiates a \ref WorkGraph.
2.713 + static WorkGraph *createWorkGraph() {
2.714 + return new WorkGraph();
2.715 + }
2.716 +
2.717 + /// \brief The type of the map that stores the edge capacities.
2.718 + ///
2.719 + /// The type of the map that stores the edge capacities.
2.720 + /// It must meet the \ref concept::ReadMap "ReadMap" concept.
2.721 + typedef _CapacityMap CapacityMap;
2.722 +
2.723 + /// \brief Instantiates a CapacityMap.
2.724 + ///
2.725 + /// This function instantiates a \ref CapacityMap.
2.726 +#ifdef DOXYGEN
2.727 + static CapacityMap *createCapacityMap(const Graph& graph)
2.728 +#else
2.729 + static CapacityMap *createCapacityMap(const Graph&)
2.730 +#endif
2.731 + {
2.732 + throw UninitializedParameter();
2.733 + }
2.734 +
2.735 + /// \brief The WorkCapacityMap type
2.736 + ///
2.737 + /// The type of the map that stores the working edge capacities.
2.738 + typedef WorkGraph::UEdgeMap<Value> WorkCapacityMap;
2.739 +
2.740 + /// \brief Instantiates a WorkCapacityMap.
2.741 + ///
2.742 + /// This function instantiates a \ref WorkCapacityMap.
2.743 + static WorkCapacityMap *createWorkCapacityMap(const WorkGraph& graph) {
2.744 + return new WorkCapacityMap(graph);
2.745 + }
2.746 +
2.747 + /// \brief The cross reference type used by heap.
2.748 + ///
2.749 + /// The cross reference type used by heap.
2.750 + /// Usually it is \c Graph::NodeMap<int>.
2.751 + typedef WorkGraph::NodeMap<int> HeapCrossRef;
2.752 +
2.753 + /// \brief Instantiates a HeapCrossRef.
2.754 + ///
2.755 + /// This function instantiates a \ref HeapCrossRef.
2.756 + /// \param graph is the graph, to which we would like to define the
2.757 + /// HeapCrossRef.
2.758 + static HeapCrossRef *createHeapCrossRef(const WorkGraph &graph) {
2.759 + return new HeapCrossRef(graph);
2.760 + }
2.761 +
2.762 + /// \brief The heap type used by MinimalCut algorithm.
2.763 + ///
2.764 + /// The heap type used by MinimalCut algorithm. It should
2.765 + /// maximalize the priorities and the heap's key type is
2.766 + /// the work graph's node.
2.767 + ///
2.768 + /// \sa BinHeap
2.769 + /// \sa MinimalCut
2.770 + typedef typename _minimal_cut_bits
2.771 + ::HeapSelector<CapacityMap>
2.772 + ::template Selector<typename WorkGraph::Node, Value, HeapCrossRef>
2.773 + ::Heap Heap;
2.774 +
2.775 + /// \brief Instantiates a Heap.
2.776 + ///
2.777 + /// This function instantiates a \ref Heap.
2.778 + /// \param crossref The cross reference of the heap.
2.779 + static Heap *createHeap(HeapCrossRef& crossref) {
2.780 + return new Heap(crossref);
2.781 + }
2.782 +
2.783 + /// \brief Map from the WorkGraph's node type to the Graph's node type.
2.784 + ///
2.785 + /// Map from the WorkGraph's node type to the Graph's node type.
2.786 + typedef typename WorkGraph
2.787 + ::template NodeMap<typename Graph::Node> NodeRefMap;
2.788 +
2.789 + /// \brief Instantiates a NodeRefMap.
2.790 + ///
2.791 + /// This function instantiates a \ref NodeRefMap.
2.792 + static NodeRefMap *createNodeRefMap(const WorkGraph& graph) {
2.793 + return new NodeRefMap(graph);
2.794 + }
2.795 +
2.796 + /// \brief Map from the Graph's node type to the Graph's node type.
2.797 + ///
2.798 + /// Map from the Graph's node type to the Graph's node type.
2.799 + typedef typename Graph
2.800 + ::template NodeMap<typename Graph::Node> ListRefMap;
2.801 +
2.802 + /// \brief Instantiates a ListRefMap.
2.803 + ///
2.804 + /// This function instantiates a \ref ListRefMap.
2.805 + static ListRefMap *createListRefMap(const Graph& graph) {
2.806 + return new ListRefMap(graph);
2.807 + }
2.808 +
2.809 +
2.810 + };
2.811 +
2.812 + namespace _minimal_cut_bits {
2.813 + template <typename _Key>
2.814 + class LastTwoMap {
2.815 + public:
2.816 + typedef _Key Key;
2.817 + typedef bool Value;
2.818 +
2.819 + LastTwoMap(int _num) : num(_num) {}
2.820 + void set(const Key& key, bool val) {
2.821 + if (!val) return;
2.822 + --num;
2.823 + if (num > 1) return;
2.824 + keys[num] = key;
2.825 + }
2.826 +
2.827 + Key operator[](int index) const { return keys[index]; }
2.828 + private:
2.829 + Key keys[2];
2.830 + int num;
2.831 + };
2.832 + }
2.833 +
2.834 + /// \ingroup topology
2.835 + ///
2.836 + /// \brief Calculates the minimal cut in an undirected graph.
2.837 + ///
2.838 + /// Calculates the minimal cut in an undirected graph.
2.839 + /// The algorithm separates the graph's nodes to two partitions with the
2.840 + /// minimal sum of edge capacities between the two partitions. The
2.841 + /// algorithm can be used to test the network reliability specifically
2.842 + /// to test how many links have to be destroyed in the network to split it
2.843 + /// at least two distinict subnetwork.
2.844 + ///
2.845 + /// The complexity of the algorithm is O(n*e*log(n)) but with Fibonacci
2.846 + /// heap it can be decreased to O(n*e+n^2*log(n)). When the neutral capacity
2.847 + /// map is used then it uses LinearHeap which results O(n*e) time complexity.
2.848 +#ifdef DOXYGEN
2.849 + template <typename _Graph, typename _CapacityMap, typename _Traits>
2.850 +#else
2.851 + template <typename _Graph = ListUGraph,
2.852 + typename _CapacityMap = typename _Graph::template UEdgeMap<int>,
2.853 + typename _Traits = MinimalCutDefaultTraits<_Graph, _CapacityMap> >
2.854 +#endif
2.855 + class MinimalCut {
2.856 + public:
2.857 + /// \brief \ref Exception for uninitialized parameters.
2.858 + ///
2.859 + /// This error represents problems in the initialization
2.860 + /// of the parameters of the algorithms.
2.861 + class UninitializedParameter : public lemon::UninitializedParameter {
2.862 + public:
2.863 + virtual const char* exceptionName() const {
2.864 + return "lemon::MinimalCut::UninitializedParameter";
2.865 + }
2.866 + };
2.867 +
2.868 +
2.869 + private:
2.870 +
2.871 + typedef _Traits Traits;
2.872 + /// The type of the underlying graph.
2.873 + typedef typename Traits::Graph Graph;
2.874 +
2.875 + /// The type of the capacity of the edges.
2.876 + typedef typename Traits::CapacityMap::Value Value;
2.877 + /// The type of the map that stores the edge capacities.
2.878 + typedef typename Traits::CapacityMap CapacityMap;
2.879 + /// The type of the work graph
2.880 + typedef typename Traits::WorkGraph WorkGraph;
2.881 + /// The type of the work capacity map
2.882 + typedef typename Traits::WorkCapacityMap WorkCapacityMap;
2.883 + /// The cross reference type used for the current heap.
2.884 + typedef typename Traits::HeapCrossRef HeapCrossRef;
2.885 + /// The heap type used by the max cardinality algorithm.
2.886 + typedef typename Traits::Heap Heap;
2.887 + /// The node refrefernces between the original and work graph type.
2.888 + typedef typename Traits::NodeRefMap NodeRefMap;
2.889 + /// The list node refrefernces in the original graph type.
2.890 + typedef typename Traits::ListRefMap ListRefMap;
2.891 +
2.892 + public:
2.893 +
2.894 + ///\name Named template parameters
2.895 +
2.896 + ///@{
2.897 +
2.898 + struct DefNeutralCapacityTraits : public Traits {
2.899 + typedef ConstMap<typename Graph::UEdge, Const<int, 1> > CapacityMap;
2.900 + static CapacityMap *createCapacityMap(const Graph&) {
2.901 + return new CapacityMap();
2.902 + }
2.903 + };
2.904 + /// \brief \ref named-templ-param "Named parameter" for setting
2.905 + /// the capacity type to constMap<UEdge, int, 1>()
2.906 + ///
2.907 + /// \ref named-templ-param "Named parameter" for setting
2.908 + /// the capacity type to constMap<UEdge, int, 1>()
2.909 + struct DefNeutralCapacity
2.910 + : public MinimalCut<Graph, CapacityMap, DefNeutralCapacityTraits> {
2.911 + typedef MinimalCut<Graph, CapacityMap, DefNeutralCapacityTraits> Create;
2.912 + };
2.913 +
2.914 +
2.915 + template <class H, class CR>
2.916 + struct DefHeapTraits : public Traits {
2.917 + typedef CR HeapCrossRef;
2.918 + typedef H Heap;
2.919 + static HeapCrossRef *createHeapCrossRef(const WorkGraph &) {
2.920 + throw UninitializedParameter();
2.921 + }
2.922 + static Heap *createHeap(HeapCrossRef &) {
2.923 + throw UninitializedParameter();
2.924 + }
2.925 + };
2.926 + /// \brief \ref named-templ-param "Named parameter" for setting heap
2.927 + /// and cross reference type
2.928 + ///
2.929 + /// \ref named-templ-param "Named parameter" for setting heap and cross
2.930 + /// reference type
2.931 + template <class H, class CR = typename Graph::template NodeMap<int> >
2.932 + struct DefHeap
2.933 + : public MinimalCut<Graph, CapacityMap, DefHeapTraits<H, CR> > {
2.934 + typedef MinimalCut< Graph, CapacityMap, DefHeapTraits<H, CR> > Create;
2.935 + };
2.936 +
2.937 + template <class H, class CR>
2.938 + struct DefStandardHeapTraits : public Traits {
2.939 + typedef CR HeapCrossRef;
2.940 + typedef H Heap;
2.941 + static HeapCrossRef *createHeapCrossRef(const WorkGraph &graph) {
2.942 + return new HeapCrossRef(graph);
2.943 + }
2.944 + static Heap *createHeap(HeapCrossRef &crossref) {
2.945 + return new Heap(crossref);
2.946 + }
2.947 + };
2.948 +
2.949 + /// \brief \ref named-templ-param "Named parameter" for setting heap and
2.950 + /// cross reference type with automatic allocation
2.951 + ///
2.952 + /// \ref named-templ-param "Named parameter" for setting heap and cross
2.953 + /// reference type. It can allocate the heap and the cross reference
2.954 + /// object if the cross reference's constructor waits for the graph as
2.955 + /// parameter and the heap's constructor waits for the cross reference.
2.956 + template <class H, class CR = typename Graph::template NodeMap<int> >
2.957 + struct DefStandardHeap
2.958 + : public MinimalCut<Graph, CapacityMap, DefStandardHeapTraits<H, CR> > {
2.959 + typedef MinimalCut<Graph, CapacityMap, DefStandardHeapTraits<H, CR> >
2.960 + Create;
2.961 + };
2.962 +
2.963 + ///@}
2.964 +
2.965 +
2.966 + private:
2.967 + /// Pointer to the underlying graph.
2.968 + const Graph *_graph;
2.969 + /// Pointer to the capacity map
2.970 + const CapacityMap *_capacity;
2.971 + /// \brief Indicates if \ref _capacity is locally allocated
2.972 + /// (\c true) or not.
2.973 + bool local_capacity;
2.974 +
2.975 + /// Pointer to the work graph.
2.976 + WorkGraph *_work_graph;
2.977 + /// \brief Indicates if \ref _work_graph is locally allocated
2.978 + /// (\c true) or not.
2.979 + bool local_work_graph;
2.980 + /// Pointer to the work capacity map
2.981 + WorkCapacityMap *_work_capacity;
2.982 + /// \brief Indicates if \ref _work_capacity is locally allocated
2.983 + /// (\c true) or not.
2.984 + bool local_work_capacity;
2.985 + /// Pointer to the heap cross references.
2.986 + HeapCrossRef *_heap_cross_ref;
2.987 + /// \brief Indicates if \ref _heap_cross_ref is locally allocated
2.988 + /// (\c true) or not.
2.989 + bool local_heap_cross_ref;
2.990 + /// Pointer to the heap.
2.991 + Heap *_heap;
2.992 + /// Indicates if \ref _heap is locally allocated (\c true) or not.
2.993 + bool local_heap;
2.994 +
2.995 + /// The minimal cut value.
2.996 + Value _minimal_cut;
2.997 + /// The number of the nodes of the work graph.
2.998 + int _node_num;
2.999 + /// The first and last node of the min cut in the next list;
2.1000 + typename Graph::Node _first_node, _last_node;
2.1001 +
2.1002 + /// \brief The first and last element in the list associated
2.1003 + /// to the work graph node.
2.1004 + NodeRefMap *_first, *_last;
2.1005 + /// \brief The next node in the node lists.
2.1006 + ListRefMap *_next;
2.1007 +
2.1008 + void create_structures() {
2.1009 + if (!_capacity) {
2.1010 + local_capacity = true;
2.1011 + _capacity = Traits::createCapacityMap(*_graph);
2.1012 + }
2.1013 + if(!_work_graph) {
2.1014 + local_work_graph = true;
2.1015 + _work_graph = Traits::createWorkGraph();
2.1016 + }
2.1017 + if(!_work_capacity) {
2.1018 + local_work_capacity = true;
2.1019 + _work_capacity = Traits::createWorkCapacityMap(*_work_graph);
2.1020 + }
2.1021 +
2.1022 + _first = Traits::createNodeRefMap(*_work_graph);
2.1023 + _last = Traits::createNodeRefMap(*_work_graph);
2.1024 +
2.1025 + _next = Traits::createListRefMap(*_graph);
2.1026 +
2.1027 + typename Graph::template NodeMap<typename WorkGraph::Node> ref(*_graph);
2.1028 +
2.1029 + for (typename Graph::NodeIt it(*_graph); it != INVALID; ++it) {
2.1030 + _next->set(it, INVALID);
2.1031 + typename WorkGraph::Node node = _work_graph->addNode();
2.1032 + _first->set(node, it);
2.1033 + _last->set(node, it);
2.1034 + ref.set(it, node);
2.1035 + }
2.1036 +
2.1037 + for (typename Graph::UEdgeIt it(*_graph); it != INVALID; ++it) {
2.1038 + if (_graph->source(it) == _graph->target(it)) continue;
2.1039 + typename WorkGraph::UEdge uedge =
2.1040 + _work_graph->addEdge(ref[_graph->source(it)],
2.1041 + ref[_graph->target(it)]);
2.1042 + _work_capacity->set(uedge, (*_capacity)[it]);
2.1043 +
2.1044 + }
2.1045 +
2.1046 + if (!_heap_cross_ref) {
2.1047 + local_heap_cross_ref = true;
2.1048 + _heap_cross_ref = Traits::createHeapCrossRef(*_work_graph);
2.1049 + }
2.1050 + if (!_heap) {
2.1051 + local_heap = true;
2.1052 + _heap = Traits::createHeap(*_heap_cross_ref);
2.1053 + }
2.1054 + }
2.1055 +
2.1056 + public :
2.1057 +
2.1058 + typedef MinimalCut Create;
2.1059 +
2.1060 +
2.1061 + /// \brief Constructor.
2.1062 + ///
2.1063 + ///\param graph the graph the algorithm will run on.
2.1064 + ///\param capacity the capacity map used by the algorithm.
2.1065 + MinimalCut(const Graph& graph, const CapacityMap& capacity)
2.1066 + : _graph(&graph),
2.1067 + _capacity(&capacity), local_capacity(false),
2.1068 + _work_graph(0), local_work_graph(false),
2.1069 + _work_capacity(0), local_work_capacity(false),
2.1070 + _heap_cross_ref(0), local_heap_cross_ref(false),
2.1071 + _heap(0), local_heap(false),
2.1072 + _first(0), _last(0), _next(0) {}
2.1073 +
2.1074 + /// \brief Constructor.
2.1075 + ///
2.1076 + /// This constructor can be used only when the Traits class
2.1077 + /// defines how can we instantiate a local capacity map.
2.1078 + /// If the DefNeutralCapacity used the algorithm automatically
2.1079 + /// construct the capacity map.
2.1080 + ///
2.1081 + ///\param graph the graph the algorithm will run on.
2.1082 + MinimalCut(const Graph& graph)
2.1083 + : _graph(&graph),
2.1084 + _capacity(0), local_capacity(false),
2.1085 + _work_graph(0), local_work_graph(false),
2.1086 + _work_capacity(0), local_work_capacity(false),
2.1087 + _heap_cross_ref(0), local_heap_cross_ref(false),
2.1088 + _heap(0), local_heap(false),
2.1089 + _first(0), _last(0), _next(0) {}
2.1090 +
2.1091 + /// \brief Destructor.
2.1092 + ///
2.1093 + /// Destructor.
2.1094 + ~MinimalCut() {
2.1095 + if (local_heap) delete _heap;
2.1096 + if (local_heap_cross_ref) delete _heap_cross_ref;
2.1097 + if (_first) delete _first;
2.1098 + if (_last) delete _last;
2.1099 + if (_next) delete _next;
2.1100 + if (local_work_capacity) delete _work_capacity;
2.1101 + if (local_work_graph) delete _work_graph;
2.1102 + if (local_capacity) delete _capacity;
2.1103 + }
2.1104 +
2.1105 + /// \brief Sets the heap and the cross reference used by algorithm.
2.1106 + ///
2.1107 + /// Sets the heap and the cross reference used by algorithm.
2.1108 + /// If you don't use this function before calling \ref run(),
2.1109 + /// it will allocate one. The destuctor deallocates this
2.1110 + /// automatically allocated heap and cross reference, of course.
2.1111 + /// \return <tt> (*this) </tt>
2.1112 + MinimalCut &heap(Heap& heap, HeapCrossRef &crossRef)
2.1113 + {
2.1114 + if (local_heap_cross_ref) {
2.1115 + delete _heap_cross_ref;
2.1116 + local_heap_cross_ref=false;
2.1117 + }
2.1118 + _heap_cross_ref = &crossRef;
2.1119 + if (local_heap) {
2.1120 + delete _heap;
2.1121 + local_heap=false;
2.1122 + }
2.1123 + _heap = &heap;
2.1124 + return *this;
2.1125 + }
2.1126 +
2.1127 + /// \brief Sets the work graph.
2.1128 + ///
2.1129 + /// Sets the work graph used by algorithm.
2.1130 + /// If you don't use this function before calling \ref run(),
2.1131 + /// it will allocate one. The destuctor deallocates this
2.1132 + /// automatically allocated graph, of course.
2.1133 + /// \return <tt> (*this) </tt>
2.1134 + MinimalCut &workGraph(WorkGraph& work_graph)
2.1135 + {
2.1136 + if(local_work_graph) {
2.1137 + delete _work_graph;
2.1138 + local_work_graph=false;
2.1139 + }
2.1140 + _work_graph = &work_graph;
2.1141 + return *this;
2.1142 + }
2.1143 +
2.1144 + /// \brief Sets the work capacity map.
2.1145 + ///
2.1146 + /// Sets the work capacity map used by algorithm.
2.1147 + /// If you don't use this function before calling \ref run(),
2.1148 + /// it will allocate one. The destuctor deallocates this
2.1149 + /// automatically allocated graph, of course.
2.1150 + /// \return <tt> (*this) </tt>
2.1151 + MinimalCut &workCapacityMap(WorkCapacityMap& work_capacity_map)
2.1152 + {
2.1153 + if(local_work_capacity) {
2.1154 + delete _work_capacity;
2.1155 + local_work_capacity=false;
2.1156 + }
2.1157 + _work_capacity = &work_capacity_map;
2.1158 + return *this;
2.1159 + }
2.1160 +
2.1161 + /// \name Execution control
2.1162 + /// The simplest way to execute the algorithm is to use
2.1163 + /// one of the member functions called \c run().
2.1164 + /// \n
2.1165 + /// If you need more control on the execution,
2.1166 + /// first you must call \ref init() and then call the start()
2.1167 + /// or proper times the processNextPhase() member functions.
2.1168 +
2.1169 + ///@{
2.1170 +
2.1171 + /// \brief Initializes the internal data structures.
2.1172 + ///
2.1173 + /// Initializes the internal data structures.
2.1174 + void init() {
2.1175 + create_structures();
2.1176 + _first_node = _last_node = INVALID;
2.1177 + _node_num = countNodes(*_graph);
2.1178 + }
2.1179 +
2.1180 + /// \brief Processes the next phase
2.1181 + ///
2.1182 + /// Processes the next phase in the algorithm. The function
2.1183 + /// should be called countNodes(graph) - 1 times to get
2.1184 + /// surely the minimal cut in the graph. The
2.1185 + ///
2.1186 + ///\return %True when the algorithm finished.
2.1187 + bool processNextPhase() {
2.1188 + if (_node_num <= 1) return true;
2.1189 + using namespace _minimal_cut_bits;
2.1190 +
2.1191 + typedef typename WorkGraph::Node Node;
2.1192 + typedef typename WorkGraph::NodeIt NodeIt;
2.1193 + typedef typename WorkGraph::UEdge UEdge;
2.1194 + typedef typename WorkGraph::IncEdgeIt IncEdgeIt;
2.1195 +
2.1196 + typedef typename MaxCardinalitySearch<WorkGraph, WorkCapacityMap>::
2.1197 + template DefHeap<Heap, HeapCrossRef>::
2.1198 + template DefCardinalityMap<NullMap<Node, Value> >::
2.1199 + template DefProcessedMap<LastTwoMap<Node> >::
2.1200 + Create MaxCardinalitySearch;
2.1201 +
2.1202 + MaxCardinalitySearch mcs(*_work_graph, *_work_capacity);
2.1203 + for (NodeIt it(*_work_graph); it != INVALID; ++it) {
2.1204 + _heap_cross_ref->set(it, Heap::PRE_HEAP);
2.1205 + }
2.1206 + mcs.heap(*_heap, *_heap_cross_ref);
2.1207 +
2.1208 + LastTwoMap<Node> last_two_nodes(_node_num);
2.1209 + mcs.processedMap(last_two_nodes);
2.1210 +
2.1211 + NullMap<Node, Value> cardinality;
2.1212 + mcs.cardinalityMap(cardinality);
2.1213 +
2.1214 + mcs.run();
2.1215 +
2.1216 + Node new_node = _work_graph->addNode();
2.1217 +
2.1218 + typename WorkGraph::template NodeMap<UEdge> edges(*_work_graph, INVALID);
2.1219 +
2.1220 + Node first_node = last_two_nodes[0];
2.1221 + Node second_node = last_two_nodes[1];
2.1222 +
2.1223 + _next->set((*_last)[first_node], (*_first)[second_node]);
2.1224 + _first->set(new_node, (*_first)[first_node]);
2.1225 + _last->set(new_node, (*_last)[second_node]);
2.1226 +
2.1227 + Value current_cut = 0;
2.1228 + for (IncEdgeIt it(*_work_graph, first_node); it != INVALID; ++it) {
2.1229 + Node node = _work_graph->runningNode(it);
2.1230 + current_cut += (*_work_capacity)[it];
2.1231 + if (node == second_node) continue;
2.1232 + if (edges[node] == INVALID) {
2.1233 + edges[node] = _work_graph->addEdge(new_node, node);
2.1234 + (*_work_capacity)[edges[node]] = (*_work_capacity)[it];
2.1235 + } else {
2.1236 + (*_work_capacity)[edges[node]] += (*_work_capacity)[it];
2.1237 + }
2.1238 + }
2.1239 +
2.1240 + if (_first_node == INVALID || current_cut < _minimal_cut) {
2.1241 + _first_node = (*_first)[first_node];
2.1242 + _last_node = (*_last)[first_node];
2.1243 + _minimal_cut = current_cut;
2.1244 + }
2.1245 +
2.1246 + _work_graph->erase(first_node);
2.1247 +
2.1248 + for (IncEdgeIt it(*_work_graph, second_node); it != INVALID; ++it) {
2.1249 + Node node = _work_graph->runningNode(it);
2.1250 + if (edges[node] == INVALID) {
2.1251 + edges[node] = _work_graph->addEdge(new_node, node);
2.1252 + (*_work_capacity)[edges[node]] = (*_work_capacity)[it];
2.1253 + } else {
2.1254 + (*_work_capacity)[edges[node]] += (*_work_capacity)[it];
2.1255 + }
2.1256 + }
2.1257 + _work_graph->erase(second_node);
2.1258 +
2.1259 + --_node_num;
2.1260 + return _node_num == 1;
2.1261 + }
2.1262 +
2.1263 + /// \brief Executes the algorithm.
2.1264 + ///
2.1265 + /// Executes the algorithm.
2.1266 + ///
2.1267 + /// \pre init() must be called
2.1268 + void start() {
2.1269 + while (!processNextPhase());
2.1270 + }
2.1271 +
2.1272 +
2.1273 + /// \brief Runs %MinimalCut algorithm.
2.1274 + ///
2.1275 + /// This method runs the %Minimal cut algorithm
2.1276 + ///
2.1277 + /// \note mc.run(s) is just a shortcut of the following code.
2.1278 + ///\code
2.1279 + /// mc.init();
2.1280 + /// mc.start();
2.1281 + ///\endcode
2.1282 + void run() {
2.1283 + init();
2.1284 + start();
2.1285 + }
2.1286 +
2.1287 + ///@}
2.1288 +
2.1289 + /// \name Query Functions
2.1290 + /// The result of the %MinimalCut algorithm can be obtained using these
2.1291 + /// functions.\n
2.1292 + /// Before the use of these functions,
2.1293 + /// either run() or start() must be called.
2.1294 +
2.1295 + ///@{
2.1296 +
2.1297 + /// \brief Returns the minimal cut value.
2.1298 + ///
2.1299 + /// Returns the minimal cut value if the algorithm finished.
2.1300 + /// After the first processNextPhase() it is a value of a
2.1301 + /// valid cut in the graph.
2.1302 + Value minCut() const {
2.1303 + return _minimal_cut;
2.1304 + }
2.1305 +
2.1306 + /// \brief Returns a minimal cut in a NodeMap.
2.1307 + ///
2.1308 + /// It sets the nodes of one of the two partitions to true in
2.1309 + /// the given BoolNodeMap. The map contains a valid cut if the
2.1310 + /// map have been setted false previously.
2.1311 + template <typename NodeMap>
2.1312 + Value quickMinCut(NodeMap& nodeMap) const {
2.1313 + for (typename Graph::Node it = _first_node;
2.1314 + it != _last_node; it = (*_next)[it]) {
2.1315 + nodeMap.set(it, true);
2.1316 + }
2.1317 + nodeMap.set(_last_node, true);
2.1318 + return minCut();
2.1319 + }
2.1320 +
2.1321 + /// \brief Returns a minimal cut in a NodeMap.
2.1322 + ///
2.1323 + /// It sets the nodes of one of the two partitions to true and
2.1324 + /// the other partition to false. The function first set all of the
2.1325 + /// nodes to false and after it call the quickMinCut() member.
2.1326 + template <typename NodeMap>
2.1327 + Value minCut(NodeMap& nodeMap) const {
2.1328 + for (typename Graph::NodeIt it(*_graph); it != INVALID; ++it) {
2.1329 + nodeMap.set(it, false);
2.1330 + }
2.1331 + quickMinCut(nodeMap);
2.1332 + return minCut();
2.1333 + }
2.1334 +
2.1335 + /// \brief Returns a minimal cut in an EdgeMap.
2.1336 + ///
2.1337 + /// If an undirected edge is cut edge then it will be
2.1338 + /// setted to true and the others will be setted to false in the given map.
2.1339 + template <typename EdgeMap>
2.1340 + Value cutEdges(EdgeMap& edgeMap) const {
2.1341 + typename Graph::template NodeMap<bool> cut(*_graph, false);
2.1342 + quickMinCut(cut);
2.1343 + for (typename Graph::EdgeIt it(*_graph); it != INVALID; ++it) {
2.1344 + edgeMap.set(it, cut[_graph->source(it)] ^ cut[_graph->target(it)]);
2.1345 + }
2.1346 + return minCut();
2.1347 + }
2.1348 +
2.1349 + ///@}
2.1350 +
2.1351 + };
2.1352 +}
2.1353 +
2.1354 +#endif