1.1 --- a/lemon/minimal_cut.h Mon Feb 13 09:42:53 2006 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,1351 +0,0 @@
1.4 -/* -*- C++ -*-
1.5 - * lemon/minimal_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_MINIMAL_CUT_H
1.21 -#define LEMON_MINIMAL_CUT_H
1.22 -
1.23 -
1.24 -/// \ingroup topology
1.25 -/// \file
1.26 -/// \brief Maximum cardinality search and minimal 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 _minimal_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 _minimal_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 chooses that node which 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 nodes 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 MinimalCut class.
1.695 - ///
1.696 - /// Default traits class of MinimalCut 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 MinimalCutDefaultTraits {
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 WorkGraph type which is an EraseableGraph
1.708 - typedef ListUGraph WorkGraph;
1.709 -
1.710 - /// \brief Instantiates a WorkGraph.
1.711 - ///
1.712 - /// This function instantiates a \ref WorkGraph.
1.713 - static WorkGraph *createWorkGraph() {
1.714 - return new WorkGraph();
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 WorkCapacityMap type
1.736 - ///
1.737 - /// The type of the map that stores the working edge capacities.
1.738 - typedef WorkGraph::UEdgeMap<Value> WorkCapacityMap;
1.739 -
1.740 - /// \brief Instantiates a WorkCapacityMap.
1.741 - ///
1.742 - /// This function instantiates a \ref WorkCapacityMap.
1.743 - static WorkCapacityMap *createWorkCapacityMap(const WorkGraph& graph) {
1.744 - return new WorkCapacityMap(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 WorkGraph::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 WorkGraph &graph) {
1.759 - return new HeapCrossRef(graph);
1.760 - }
1.761 -
1.762 - /// \brief The heap type used by MinimalCut algorithm.
1.763 - ///
1.764 - /// The heap type used by MinimalCut algorithm. It should
1.765 - /// maximalize the priorities and the heap's key type is
1.766 - /// the work graph's node.
1.767 - ///
1.768 - /// \sa BinHeap
1.769 - /// \sa MinimalCut
1.770 - typedef typename _minimal_cut_bits
1.771 - ::HeapSelector<CapacityMap>
1.772 - ::template Selector<typename WorkGraph::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 WorkGraph's node type to the Graph's node type.
1.784 - ///
1.785 - /// Map from the WorkGraph's node type to the Graph's node type.
1.786 - typedef typename WorkGraph
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 WorkGraph& 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 _minimal_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 minimal cut in an undirected graph.
1.837 - ///
1.838 - /// Calculates the minimal cut in an undirected graph.
1.839 - /// The algorithm separates the graph's nodes to two partitions with the
1.840 - /// minimal sum of edge capacities between the two partitions. The
1.841 - /// algorithm can be used to test the network reliability specifically
1.842 - /// to test how many links have to be destroyed in the network to split it
1.843 - /// at least two distinict subnetwork.
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 = MinimalCutDefaultTraits<_Graph, _CapacityMap> >
1.854 -#endif
1.855 - class MinimalCut {
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::MinimalCut::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 work graph
1.880 - typedef typename Traits::WorkGraph WorkGraph;
1.881 - /// The type of the work capacity map
1.882 - typedef typename Traits::WorkCapacityMap WorkCapacityMap;
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 work 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 MinimalCut<Graph, CapacityMap, DefNeutralCapacityTraits> {
1.911 - typedef MinimalCut<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 WorkGraph &) {
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 MinimalCut<Graph, CapacityMap, DefHeapTraits<H, CR> > {
1.934 - typedef MinimalCut< 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 WorkGraph &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 MinimalCut<Graph, CapacityMap, DefStandardHeapTraits<H, CR> > {
1.959 - typedef MinimalCut<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 work graph.
1.976 - WorkGraph *_work_graph;
1.977 - /// \brief Indicates if \ref _work_graph is locally allocated
1.978 - /// (\c true) or not.
1.979 - bool local_work_graph;
1.980 - /// Pointer to the work capacity map
1.981 - WorkCapacityMap *_work_capacity;
1.982 - /// \brief Indicates if \ref _work_capacity is locally allocated
1.983 - /// (\c true) or not.
1.984 - bool local_work_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 minimal cut value.
1.996 - Value _minimal_cut;
1.997 - /// The number of the nodes of the work 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 work 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(!_work_graph) {
1.1014 - local_work_graph = true;
1.1015 - _work_graph = Traits::createWorkGraph();
1.1016 - }
1.1017 - if(!_work_capacity) {
1.1018 - local_work_capacity = true;
1.1019 - _work_capacity = Traits::createWorkCapacityMap(*_work_graph);
1.1020 - }
1.1021 -
1.1022 - _first = Traits::createNodeRefMap(*_work_graph);
1.1023 - _last = Traits::createNodeRefMap(*_work_graph);
1.1024 -
1.1025 - _next = Traits::createListRefMap(*_graph);
1.1026 -
1.1027 - typename Graph::template NodeMap<typename WorkGraph::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 WorkGraph::Node node = _work_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 WorkGraph::UEdge uedge =
1.1040 - _work_graph->addEdge(ref[_graph->source(it)],
1.1041 - ref[_graph->target(it)]);
1.1042 - _work_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(*_work_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 MinimalCut 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 - MinimalCut(const Graph& graph, const CapacityMap& capacity)
1.1066 - : _graph(&graph),
1.1067 - _capacity(&capacity), local_capacity(false),
1.1068 - _work_graph(0), local_work_graph(false),
1.1069 - _work_capacity(0), local_work_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 - MinimalCut(const Graph& graph)
1.1083 - : _graph(&graph),
1.1084 - _capacity(0), local_capacity(false),
1.1085 - _work_graph(0), local_work_graph(false),
1.1086 - _work_capacity(0), local_work_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 - ~MinimalCut() {
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_work_capacity) delete _work_capacity;
1.1101 - if (local_work_graph) delete _work_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 - MinimalCut &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 work graph.
1.1128 - ///
1.1129 - /// Sets the work 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 - MinimalCut &workGraph(WorkGraph& work_graph)
1.1135 - {
1.1136 - if(local_work_graph) {
1.1137 - delete _work_graph;
1.1138 - local_work_graph=false;
1.1139 - }
1.1140 - _work_graph = &work_graph;
1.1141 - return *this;
1.1142 - }
1.1143 -
1.1144 - /// \brief Sets the work capacity map.
1.1145 - ///
1.1146 - /// Sets the work 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 - MinimalCut &workCapacityMap(WorkCapacityMap& work_capacity_map)
1.1152 - {
1.1153 - if(local_work_capacity) {
1.1154 - delete _work_capacity;
1.1155 - local_work_capacity=false;
1.1156 - }
1.1157 - _work_capacity = &work_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 minimal 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 _minimal_cut_bits;
1.1190 -
1.1191 - typedef typename WorkGraph::Node Node;
1.1192 - typedef typename WorkGraph::NodeIt NodeIt;
1.1193 - typedef typename WorkGraph::UEdge UEdge;
1.1194 - typedef typename WorkGraph::IncEdgeIt IncEdgeIt;
1.1195 -
1.1196 - typedef typename MaxCardinalitySearch<WorkGraph, WorkCapacityMap>::
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(*_work_graph, *_work_capacity);
1.1203 - for (NodeIt it(*_work_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 = _work_graph->addNode();
1.1217 -
1.1218 - typename WorkGraph::template NodeMap<UEdge> edges(*_work_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(*_work_graph, first_node); it != INVALID; ++it) {
1.1229 - Node node = _work_graph->runningNode(it);
1.1230 - current_cut += (*_work_capacity)[it];
1.1231 - if (node == second_node) continue;
1.1232 - if (edges[node] == INVALID) {
1.1233 - edges[node] = _work_graph->addEdge(new_node, node);
1.1234 - (*_work_capacity)[edges[node]] = (*_work_capacity)[it];
1.1235 - } else {
1.1236 - (*_work_capacity)[edges[node]] += (*_work_capacity)[it];
1.1237 - }
1.1238 - }
1.1239 -
1.1240 - if (_first_node == INVALID || current_cut < _minimal_cut) {
1.1241 - _first_node = (*_first)[first_node];
1.1242 - _last_node = (*_last)[first_node];
1.1243 - _minimal_cut = current_cut;
1.1244 - }
1.1245 -
1.1246 - _work_graph->erase(first_node);
1.1247 -
1.1248 - for (IncEdgeIt it(*_work_graph, second_node); it != INVALID; ++it) {
1.1249 - Node node = _work_graph->runningNode(it);
1.1250 - if (edges[node] == INVALID) {
1.1251 - edges[node] = _work_graph->addEdge(new_node, node);
1.1252 - (*_work_capacity)[edges[node]] = (*_work_capacity)[it];
1.1253 - } else {
1.1254 - (*_work_capacity)[edges[node]] += (*_work_capacity)[it];
1.1255 - }
1.1256 - }
1.1257 - _work_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 %MinimalCut algorithm.
1.1274 - ///
1.1275 - /// This method runs the %Minimal 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 %MinimalCut 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 minimal cut value.
1.1298 - ///
1.1299 - /// Returns the minimal 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 _minimal_cut;
1.1304 - }
1.1305 -
1.1306 - /// \brief Returns a minimal 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 setted 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 minimal 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 minimal cut in an EdgeMap.
1.1336 - ///
1.1337 - /// If an undirected edge is cut edge then it will be
1.1338 - /// setted to true and the others will be setted 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