1.1 --- a/lemon/Makefile.am Mon Feb 13 09:42:53 2006 +0000
1.2 +++ b/lemon/Makefile.am Tue Feb 14 10:41:16 2006 +0000
1.3 @@ -58,7 +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 + minimum_cut.h \
1.9 suurballe.h \
1.10 preflow.h \
1.11 path.h \
2.1 --- a/lemon/minimal_cut.h Mon Feb 13 09:42:53 2006 +0000
2.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
2.3 @@ -1,1351 +0,0 @@
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
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/lemon/minimum_cut.h Tue Feb 14 10:41:16 2006 +0000
3.3 @@ -0,0 +1,1351 @@
3.4 +/* -*- C++ -*-
3.5 + * lemon/minimum_cut.h - Part of LEMON, a generic C++ optimization library
3.6 + *
3.7 + * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
3.8 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
3.9 + *
3.10 + * Permission to use, modify and distribute this software is granted
3.11 + * provided that this copyright notice appears in all copies. For
3.12 + * precise terms see the accompanying LICENSE file.
3.13 + *
3.14 + * This software is provided "AS IS" with no warranty of any kind,
3.15 + * express or implied, and with no claim as to its suitability for any
3.16 + * purpose.
3.17 + *
3.18 + */
3.19 +
3.20 +#ifndef LEMON_MINIMUM_CUT_H
3.21 +#define LEMON_MINIMUM_CUT_H
3.22 +
3.23 +
3.24 +/// \ingroup topology
3.25 +/// \file
3.26 +/// \brief Maximum cardinality search and minimum cut in undirected graphs.
3.27 +
3.28 +#include <lemon/list_graph.h>
3.29 +#include <lemon/bin_heap.h>
3.30 +#include <lemon/linear_heap.h>
3.31 +
3.32 +#include <lemon/invalid.h>
3.33 +#include <lemon/error.h>
3.34 +#include <lemon/maps.h>
3.35 +
3.36 +#include <functional>
3.37 +
3.38 +namespace lemon {
3.39 +
3.40 + namespace _minimum_cut_bits {
3.41 +
3.42 + template <typename CapacityMap>
3.43 + struct HeapSelector {
3.44 + template <typename Key, typename Value, typename Ref>
3.45 + struct Selector {
3.46 + typedef BinHeap<Key, Value, Ref, std::greater<Value> > Heap;
3.47 + };
3.48 + };
3.49 +
3.50 + template <typename CapacityKey>
3.51 + struct HeapSelector<ConstMap<CapacityKey, Const<int, 1> > > {
3.52 + template <typename Key, typename Value, typename Ref>
3.53 + struct Selector {
3.54 + typedef LinearHeap<Key, Ref, false > Heap;
3.55 + };
3.56 + };
3.57 +
3.58 + }
3.59 +
3.60 + /// \brief Default traits class of MaxCardinalitySearch class.
3.61 + ///
3.62 + /// Default traits class of MaxCardinalitySearch class.
3.63 + /// \param Graph Graph type.
3.64 + /// \param CapacityMap Type of length map.
3.65 + template <typename _Graph, typename _CapacityMap>
3.66 + struct MaxCardinalitySearchDefaultTraits {
3.67 + /// The graph type the algorithm runs on.
3.68 + typedef _Graph Graph;
3.69 +
3.70 + /// \brief The type of the map that stores the edge capacities.
3.71 + ///
3.72 + /// The type of the map that stores the edge capacities.
3.73 + /// It must meet the \ref concept::ReadMap "ReadMap" concept.
3.74 + typedef _CapacityMap CapacityMap;
3.75 +
3.76 + /// \brief The type of the capacity of the edges.
3.77 + typedef typename CapacityMap::Value Value;
3.78 +
3.79 + /// \brief The cross reference type used by heap.
3.80 + ///
3.81 + /// The cross reference type used by heap.
3.82 + /// Usually it is \c Graph::NodeMap<int>.
3.83 + typedef typename Graph::template NodeMap<int> HeapCrossRef;
3.84 +
3.85 + /// \brief Instantiates a HeapCrossRef.
3.86 + ///
3.87 + /// This function instantiates a \ref HeapCrossRef.
3.88 + /// \param graph is the graph, to which we would like to define the
3.89 + /// HeapCrossRef.
3.90 + static HeapCrossRef *createHeapCrossRef(const Graph &graph) {
3.91 + return new HeapCrossRef(graph);
3.92 + }
3.93 +
3.94 + /// \brief The heap type used by MaxCardinalitySearch algorithm.
3.95 + ///
3.96 + /// The heap type used by MaxCardinalitySearch algorithm. It should
3.97 + /// maximalize the priorities. The default heap type is
3.98 + /// the \ref BinHeap, but it is specialized when the
3.99 + /// CapacityMap is ConstMap<Graph::Node, Const<int, 1> >
3.100 + /// to LinearHeap.
3.101 + ///
3.102 + /// \sa MaxCardinalitySearch
3.103 + typedef typename _minimum_cut_bits
3.104 + ::HeapSelector<CapacityMap>
3.105 + ::template Selector<typename Graph::Node, Value, HeapCrossRef>
3.106 + ::Heap Heap;
3.107 +
3.108 + /// \brief Instantiates a Heap.
3.109 + ///
3.110 + /// This function instantiates a \ref Heap.
3.111 + /// \param crossref The cross reference of the heap.
3.112 + static Heap *createHeap(HeapCrossRef& crossref) {
3.113 + return new Heap(crossref);
3.114 + }
3.115 +
3.116 + /// \brief The type of the map that stores whether a nodes is processed.
3.117 + ///
3.118 + /// The type of the map that stores whether a nodes is processed.
3.119 + /// It must meet the \ref concept::WriteMap "WriteMap" concept.
3.120 + /// By default it is a NullMap.
3.121 + typedef NullMap<typename Graph::Node, bool> ProcessedMap;
3.122 +
3.123 + /// \brief Instantiates a ProcessedMap.
3.124 + ///
3.125 + /// This function instantiates a \ref ProcessedMap.
3.126 + /// \param g is the graph, to which
3.127 + /// we would like to define the \ref ProcessedMap
3.128 +#ifdef DOXYGEN
3.129 + static ProcessedMap *createProcessedMap(const Graph &graph)
3.130 +#else
3.131 + static ProcessedMap *createProcessedMap(const Graph &)
3.132 +#endif
3.133 + {
3.134 + return new ProcessedMap();
3.135 + }
3.136 +
3.137 + /// \brief The type of the map that stores the cardinalties of the nodes.
3.138 + ///
3.139 + /// The type of the map that stores the cardinalities of the nodes.
3.140 + /// It must meet the \ref concept::WriteMap "WriteMap" concept.
3.141 + typedef typename Graph::template NodeMap<Value> CardinalityMap;
3.142 +
3.143 + /// \brief Instantiates a CardinalityMap.
3.144 + ///
3.145 + /// This function instantiates a \ref CardinalityMap.
3.146 + /// \param graph is the graph, to which we would like to define the \ref
3.147 + /// CardinalityMap
3.148 + static CardinalityMap *createCardinalityMap(const Graph &graph) {
3.149 + return new CardinalityMap(graph);
3.150 + }
3.151 +
3.152 + };
3.153 +
3.154 + /// \ingroup topology
3.155 + ///
3.156 + /// \brief Maximum Cardinality Search algorithm class.
3.157 + ///
3.158 + /// This class provides an efficient implementation of Maximum Cardinality
3.159 + /// Search algorithm. The maximum cardinality search chooses first time any
3.160 + /// node of the graph. Then every time chooses that node which connected
3.161 + /// to the processed nodes at most in the sum of capacities on the out
3.162 + /// edges. If there is a cut in the graph the algorithm should choose
3.163 + /// again any unprocessed node of the graph. Each nodes cardinality is
3.164 + /// the sum of capacities on the out edges to the nodes which are processed
3.165 + /// before the given node.
3.166 + ///
3.167 + /// The edge capacities are passed to the algorithm using a
3.168 + /// \ref concept::ReadMap "ReadMap", so it is easy to change it to any
3.169 + /// kind of capacity.
3.170 + ///
3.171 + /// The type of the capacity is determined by the \ref
3.172 + /// concept::ReadMap::Value "Value" of the capacity map.
3.173 + ///
3.174 + /// It is also possible to change the underlying priority heap.
3.175 + ///
3.176 + ///
3.177 + /// \param _Graph The graph type the algorithm runs on. The default value
3.178 + /// is \ref ListGraph. The value of Graph is not used directly by
3.179 + /// the search algorithm, it is only passed to
3.180 + /// \ref MaxCardinalitySearchDefaultTraits.
3.181 + /// \param _CapacityMap This read-only EdgeMap determines the capacities of
3.182 + /// the edges. It is read once for each edge, so the map may involve in
3.183 + /// relatively time consuming process to compute the edge capacity if
3.184 + /// it is necessary. The default map type is \ref
3.185 + /// concept::StaticGraph::EdgeMap "Graph::EdgeMap<int>". The value
3.186 + /// of CapacityMap is not used directly by search algorithm, it is only
3.187 + /// passed to \ref MaxCardinalitySearchDefaultTraits.
3.188 + /// \param _Traits Traits class to set various data types used by the
3.189 + /// algorithm. The default traits class is
3.190 + /// \ref MaxCardinalitySearchDefaultTraits
3.191 + /// "MaxCardinalitySearchDefaultTraits<_Graph, _CapacityMap>".
3.192 + /// See \ref MaxCardinalitySearchDefaultTraits
3.193 + /// for the documentation of a MaxCardinalitySearch traits class.
3.194 + ///
3.195 + /// \author Balazs Dezso
3.196 +
3.197 +#ifdef DOXYGEN
3.198 + template <typename _Graph, typename _CapacityMap, typename _Traits>
3.199 +#else
3.200 + template <typename _Graph = ListUGraph,
3.201 + typename _CapacityMap = typename _Graph::template EdgeMap<int>,
3.202 + typename _Traits =
3.203 + MaxCardinalitySearchDefaultTraits<_Graph, _CapacityMap> >
3.204 +#endif
3.205 + class MaxCardinalitySearch {
3.206 + public:
3.207 + /// \brief \ref Exception for uninitialized parameters.
3.208 + ///
3.209 + /// This error represents problems in the initialization
3.210 + /// of the parameters of the algorithms.
3.211 + class UninitializedParameter : public lemon::UninitializedParameter {
3.212 + public:
3.213 + virtual const char* exceptionName() const {
3.214 + return "lemon::MaxCardinalitySearch::UninitializedParameter";
3.215 + }
3.216 + };
3.217 +
3.218 + typedef _Traits Traits;
3.219 + ///The type of the underlying graph.
3.220 + typedef typename Traits::Graph Graph;
3.221 +
3.222 + ///The type of the capacity of the edges.
3.223 + typedef typename Traits::CapacityMap::Value Value;
3.224 + ///The type of the map that stores the edge capacities.
3.225 + typedef typename Traits::CapacityMap CapacityMap;
3.226 + ///The type of the map indicating if a node is processed.
3.227 + typedef typename Traits::ProcessedMap ProcessedMap;
3.228 + ///The type of the map that stores the cardinalities of the nodes.
3.229 + typedef typename Traits::CardinalityMap CardinalityMap;
3.230 + ///The cross reference type used for the current heap.
3.231 + typedef typename Traits::HeapCrossRef HeapCrossRef;
3.232 + ///The heap type used by the algorithm. It maximize the priorities.
3.233 + typedef typename Traits::Heap Heap;
3.234 + private:
3.235 + /// Pointer to the underlying graph.
3.236 + const Graph *_graph;
3.237 + /// Pointer to the capacity map
3.238 + const CapacityMap *_capacity;
3.239 + ///Pointer to the map of cardinality.
3.240 + CardinalityMap *_cardinality;
3.241 + ///Indicates if \ref _cardinality is locally allocated (\c true) or not.
3.242 + bool local_cardinality;
3.243 + ///Pointer to the map of processed status of the nodes.
3.244 + ProcessedMap *_processed;
3.245 + ///Indicates if \ref _processed is locally allocated (\c true) or not.
3.246 + bool local_processed;
3.247 + ///Pointer to the heap cross references.
3.248 + HeapCrossRef *_heap_cross_ref;
3.249 + ///Indicates if \ref _heap_cross_ref is locally allocated (\c true) or not.
3.250 + bool local_heap_cross_ref;
3.251 + ///Pointer to the heap.
3.252 + Heap *_heap;
3.253 + ///Indicates if \ref _heap is locally allocated (\c true) or not.
3.254 + bool local_heap;
3.255 +
3.256 + public :
3.257 +
3.258 + typedef MaxCardinalitySearch Create;
3.259 +
3.260 + ///\name Named template parameters
3.261 +
3.262 + ///@{
3.263 +
3.264 + template <class T>
3.265 + struct DefCardinalityMapTraits : public Traits {
3.266 + typedef T CardinalityMap;
3.267 + static CardinalityMap *createCardinalityMap(const Graph &)
3.268 + {
3.269 + throw UninitializedParameter();
3.270 + }
3.271 + };
3.272 + /// \brief \ref named-templ-param "Named parameter" for setting
3.273 + /// CardinalityMap type
3.274 + ///
3.275 + /// \ref named-templ-param "Named parameter" for setting CardinalityMap
3.276 + /// type
3.277 + template <class T>
3.278 + struct DefCardinalityMap
3.279 + : public MaxCardinalitySearch<Graph, CapacityMap,
3.280 + DefCardinalityMapTraits<T> > {
3.281 + typedef MaxCardinalitySearch<Graph, CapacityMap,
3.282 + DefCardinalityMapTraits<T> > Create;
3.283 + };
3.284 +
3.285 + template <class T>
3.286 + struct DefProcessedMapTraits : public Traits {
3.287 + typedef T ProcessedMap;
3.288 + static ProcessedMap *createProcessedMap(const Graph &) {
3.289 + throw UninitializedParameter();
3.290 + }
3.291 + };
3.292 + /// \brief \ref named-templ-param "Named parameter" for setting
3.293 + /// ProcessedMap type
3.294 + ///
3.295 + /// \ref named-templ-param "Named parameter" for setting ProcessedMap type
3.296 + ///
3.297 + template <class T>
3.298 + struct DefProcessedMap
3.299 + : public MaxCardinalitySearch<Graph, CapacityMap,
3.300 + DefProcessedMapTraits<T> > {
3.301 + typedef MaxCardinalitySearch<Graph, CapacityMap,
3.302 + DefProcessedMapTraits<T> > Create;
3.303 + };
3.304 +
3.305 + template <class H, class CR>
3.306 + struct DefHeapTraits : public Traits {
3.307 + typedef CR HeapCrossRef;
3.308 + typedef H Heap;
3.309 + static HeapCrossRef *createHeapCrossRef(const Graph &) {
3.310 + throw UninitializedParameter();
3.311 + }
3.312 + static Heap *createHeap(HeapCrossRef &) {
3.313 + throw UninitializedParameter();
3.314 + }
3.315 + };
3.316 + /// \brief \ref named-templ-param "Named parameter" for setting heap
3.317 + /// and cross reference type
3.318 + ///
3.319 + /// \ref named-templ-param "Named parameter" for setting heap and cross
3.320 + /// reference type
3.321 + template <class H, class CR = typename Graph::template NodeMap<int> >
3.322 + struct DefHeap
3.323 + : public MaxCardinalitySearch<Graph, CapacityMap,
3.324 + DefHeapTraits<H, CR> > {
3.325 + typedef MaxCardinalitySearch< Graph, CapacityMap,
3.326 + DefHeapTraits<H, CR> > Create;
3.327 + };
3.328 +
3.329 + template <class H, class CR>
3.330 + struct DefStandardHeapTraits : public Traits {
3.331 + typedef CR HeapCrossRef;
3.332 + typedef H Heap;
3.333 + static HeapCrossRef *createHeapCrossRef(const Graph &graph) {
3.334 + return new HeapCrossRef(graph);
3.335 + }
3.336 + static Heap *createHeap(HeapCrossRef &crossref) {
3.337 + return new Heap(crossref);
3.338 + }
3.339 + };
3.340 +
3.341 + /// \brief \ref named-templ-param "Named parameter" for setting heap and
3.342 + /// cross reference type with automatic allocation
3.343 + ///
3.344 + /// \ref named-templ-param "Named parameter" for setting heap and cross
3.345 + /// reference type. It can allocate the heap and the cross reference
3.346 + /// object if the cross reference's constructor waits for the graph as
3.347 + /// parameter and the heap's constructor waits for the cross reference.
3.348 + template <class H, class CR = typename Graph::template NodeMap<int> >
3.349 + struct DefStandardHeap
3.350 + : public MaxCardinalitySearch<Graph, CapacityMap,
3.351 + DefStandardHeapTraits<H, CR> > {
3.352 + typedef MaxCardinalitySearch<Graph, CapacityMap,
3.353 + DefStandardHeapTraits<H, CR> >
3.354 + Create;
3.355 + };
3.356 +
3.357 + ///@}
3.358 +
3.359 +
3.360 + protected:
3.361 +
3.362 + MaxCardinalitySearch() {}
3.363 +
3.364 + public:
3.365 +
3.366 + /// \brief Constructor.
3.367 + ///
3.368 + ///\param _graph the graph the algorithm will run on.
3.369 + ///\param _capacity the capacity map used by the algorithm.
3.370 + MaxCardinalitySearch(const Graph& graph, const CapacityMap& capacity) :
3.371 + _graph(&graph), _capacity(&capacity),
3.372 + _cardinality(0), local_cardinality(false),
3.373 + _processed(0), local_processed(false),
3.374 + _heap_cross_ref(0), local_heap_cross_ref(false),
3.375 + _heap(0), local_heap(false)
3.376 + { }
3.377 +
3.378 + /// \brief Destructor.
3.379 + ~MaxCardinalitySearch() {
3.380 + if(local_cardinality) delete _cardinality;
3.381 + if(local_processed) delete _processed;
3.382 + if(local_heap_cross_ref) delete _heap_cross_ref;
3.383 + if(local_heap) delete _heap;
3.384 + }
3.385 +
3.386 + /// \brief Sets the capacity map.
3.387 + ///
3.388 + /// Sets the capacity map.
3.389 + /// \return <tt> (*this) </tt>
3.390 + MaxCardinalitySearch &capacityMap(const CapacityMap &m) {
3.391 + _capacity = &m;
3.392 + return *this;
3.393 + }
3.394 +
3.395 + /// \brief Sets the map storing the cardinalities calculated by the
3.396 + /// algorithm.
3.397 + ///
3.398 + /// Sets the map storing the cardinalities calculated by the algorithm.
3.399 + /// If you don't use this function before calling \ref run(),
3.400 + /// it will allocate one. The destuctor deallocates this
3.401 + /// automatically allocated map, of course.
3.402 + /// \return <tt> (*this) </tt>
3.403 + MaxCardinalitySearch &cardinalityMap(CardinalityMap &m) {
3.404 + if(local_cardinality) {
3.405 + delete _cardinality;
3.406 + local_cardinality=false;
3.407 + }
3.408 + _cardinality = &m;
3.409 + return *this;
3.410 + }
3.411 +
3.412 + /// \brief Sets the map storing the processed nodes.
3.413 + ///
3.414 + /// Sets the map storing the processed nodes.
3.415 + /// If you don't use this function before calling \ref run(),
3.416 + /// it will allocate one. The destuctor deallocates this
3.417 + /// automatically allocated map, of course.
3.418 + /// \return <tt> (*this) </tt>
3.419 + MaxCardinalitySearch &processedMap(ProcessedMap &m)
3.420 + {
3.421 + if(local_processed) {
3.422 + delete _processed;
3.423 + local_processed=false;
3.424 + }
3.425 + _processed = &m;
3.426 + return *this;
3.427 + }
3.428 +
3.429 + /// \brief Sets the heap and the cross reference used by algorithm.
3.430 + ///
3.431 + /// Sets the heap and the cross reference used by algorithm.
3.432 + /// If you don't use this function before calling \ref run(),
3.433 + /// it will allocate one. The destuctor deallocates this
3.434 + /// automatically allocated map, of course.
3.435 + /// \return <tt> (*this) </tt>
3.436 + MaxCardinalitySearch &heap(Heap& heap, HeapCrossRef &crossRef) {
3.437 + if(local_heap_cross_ref) {
3.438 + delete _heap_cross_ref;
3.439 + local_heap_cross_ref = false;
3.440 + }
3.441 + _heap_cross_ref = &crossRef;
3.442 + if(local_heap) {
3.443 + delete _heap;
3.444 + local_heap = false;
3.445 + }
3.446 + _heap = &heap;
3.447 + return *this;
3.448 + }
3.449 +
3.450 + private:
3.451 +
3.452 + typedef typename Graph::Node Node;
3.453 + typedef typename Graph::NodeIt NodeIt;
3.454 + typedef typename Graph::Edge Edge;
3.455 + typedef typename Graph::InEdgeIt InEdgeIt;
3.456 +
3.457 + void create_maps() {
3.458 + if(!_cardinality) {
3.459 + local_cardinality = true;
3.460 + _cardinality = Traits::createCardinalityMap(*_graph);
3.461 + }
3.462 + if(!_processed) {
3.463 + local_processed = true;
3.464 + _processed = Traits::createProcessedMap(*_graph);
3.465 + }
3.466 + if (!_heap_cross_ref) {
3.467 + local_heap_cross_ref = true;
3.468 + _heap_cross_ref = Traits::createHeapCrossRef(*_graph);
3.469 + }
3.470 + if (!_heap) {
3.471 + local_heap = true;
3.472 + _heap = Traits::createHeap(*_heap_cross_ref);
3.473 + }
3.474 + }
3.475 +
3.476 + void finalizeNodeData(Node node, Value capacity) {
3.477 + _processed->set(node, true);
3.478 + _cardinality->set(node, capacity);
3.479 + }
3.480 +
3.481 + public:
3.482 + /// \name Execution control
3.483 + /// The simplest way to execute the algorithm is to use
3.484 + /// one of the member functions called \c run(...).
3.485 + /// \n
3.486 + /// If you need more control on the execution,
3.487 + /// first you must call \ref init(), then you can add several source nodes
3.488 + /// with \ref addSource().
3.489 + /// Finally \ref start() will perform the actual path
3.490 + /// computation.
3.491 +
3.492 + ///@{
3.493 +
3.494 + /// \brief Initializes the internal data structures.
3.495 + ///
3.496 + /// Initializes the internal data structures.
3.497 + void init() {
3.498 + create_maps();
3.499 + _heap->clear();
3.500 + for (NodeIt it(*_graph) ; it != INVALID ; ++it) {
3.501 + _processed->set(it, false);
3.502 + _heap_cross_ref->set(it, Heap::PRE_HEAP);
3.503 + }
3.504 + }
3.505 +
3.506 + /// \brief Adds a new source node.
3.507 + ///
3.508 + /// Adds a new source node to the priority heap.
3.509 + ///
3.510 + /// It checks if the node has not yet been added to the heap.
3.511 + void addSource(Node source, Value capacity = 0) {
3.512 + if(_heap->state(source) == Heap::PRE_HEAP) {
3.513 + _heap->push(source, capacity);
3.514 + }
3.515 + }
3.516 +
3.517 + /// \brief Processes the next node in the priority heap
3.518 + ///
3.519 + /// Processes the next node in the priority heap.
3.520 + ///
3.521 + /// \return The processed node.
3.522 + ///
3.523 + /// \warning The priority heap must not be empty!
3.524 + Node processNextNode() {
3.525 + Node node = _heap->top();
3.526 + finalizeNodeData(node, _heap->prio());
3.527 + _heap->pop();
3.528 +
3.529 + for (InEdgeIt it(*_graph, node); it != INVALID; ++it) {
3.530 + Node source = _graph->source(it);
3.531 + switch (_heap->state(source)) {
3.532 + case Heap::PRE_HEAP:
3.533 + _heap->push(source, (*_capacity)[it]);
3.534 + break;
3.535 + case Heap::IN_HEAP:
3.536 + _heap->decrease(source, (*_heap)[source] + (*_capacity)[it]);
3.537 + break;
3.538 + case Heap::POST_HEAP:
3.539 + break;
3.540 + }
3.541 + }
3.542 + return node;
3.543 + }
3.544 +
3.545 + /// \brief Next node to be processed.
3.546 + ///
3.547 + /// Next node to be processed.
3.548 + ///
3.549 + /// \return The next node to be processed or INVALID if the
3.550 + /// priority heap is empty.
3.551 + Node nextNode() {
3.552 + return _heap->empty() ? _heap->top() : INVALID;
3.553 + }
3.554 +
3.555 + /// \brief Returns \c false if there are nodes
3.556 + /// to be processed in the priority heap
3.557 + ///
3.558 + /// Returns \c false if there are nodes
3.559 + /// to be processed in the priority heap
3.560 + bool emptyQueue() { return _heap->empty(); }
3.561 + /// \brief Returns the number of the nodes to be processed
3.562 + /// in the priority heap
3.563 + ///
3.564 + /// Returns the number of the nodes to be processed in the priority heap
3.565 + int queueSize() { return _heap->size(); }
3.566 +
3.567 + /// \brief Executes the algorithm.
3.568 + ///
3.569 + /// Executes the algorithm.
3.570 + ///
3.571 + ///\pre init() must be called and at least one node should be added
3.572 + /// with addSource() before using this function.
3.573 + ///
3.574 + /// This method runs the Maximum Cardinality Search algorithm from the
3.575 + /// source node(s).
3.576 + void start() {
3.577 + while ( !_heap->empty() ) processNextNode();
3.578 + }
3.579 +
3.580 + /// \brief Executes the algorithm until \c dest is reached.
3.581 + ///
3.582 + /// Executes the algorithm until \c dest is reached.
3.583 + ///
3.584 + /// \pre init() must be called and at least one node should be added
3.585 + /// with addSource() before using this function.
3.586 + ///
3.587 + /// This method runs the %MaxCardinalitySearch algorithm from the source
3.588 + /// nodes.
3.589 + void start(Node dest) {
3.590 + while ( !_heap->empty() && _heap->top()!=dest ) processNextNode();
3.591 + if ( !_heap->empty() ) finalizeNodeData(_heap->top(), _heap->prio());
3.592 + }
3.593 +
3.594 + /// \brief Executes the algorithm until a condition is met.
3.595 + ///
3.596 + /// Executes the algorithm until a condition is met.
3.597 + ///
3.598 + /// \pre init() must be called and at least one node should be added
3.599 + /// with addSource() before using this function.
3.600 + ///
3.601 + /// \param nm must be a bool (or convertible) node map. The algorithm
3.602 + /// will stop when it reaches a node \c v with <tt>nm[v]==true</tt>.
3.603 + template <typename NodeBoolMap>
3.604 + void start(const NodeBoolMap &nm) {
3.605 + while ( !_heap->empty() && !nm[_heap->top()] ) processNextNode();
3.606 + if ( !_heap->empty() ) finalizeNodeData(_heap->top(),_heap->prio());
3.607 + }
3.608 +
3.609 + /// \brief Runs the maximal cardinality search algorithm from node \c s.
3.610 + ///
3.611 + /// This method runs the %MaxCardinalitySearch algorithm from a root
3.612 + /// node \c s.
3.613 + ///
3.614 + ///\note d.run(s) is just a shortcut of the following code.
3.615 + ///\code
3.616 + /// d.init();
3.617 + /// d.addSource(s);
3.618 + /// d.start();
3.619 + ///\endcode
3.620 + void run(Node s) {
3.621 + init();
3.622 + addSource(s);
3.623 + start();
3.624 + }
3.625 +
3.626 + /// \brief Runs the maximal cardinality search algorithm for the
3.627 + /// whole graph.
3.628 + ///
3.629 + /// This method runs the %MaxCardinalitySearch algorithm from all
3.630 + /// unprocessed node of the graph.
3.631 + ///
3.632 + ///\note d.run(s) is just a shortcut of the following code.
3.633 + ///\code
3.634 + /// d.init();
3.635 + /// for (NodeIt it(graph); it != INVALID; ++it) {
3.636 + /// if (!d.reached(it)) {
3.637 + /// d.addSource(s);
3.638 + /// d.start();
3.639 + /// }
3.640 + /// }
3.641 + ///\endcode
3.642 + void run() {
3.643 + init();
3.644 + for (NodeIt it(*_graph); it != INVALID; ++it) {
3.645 + if (!reached(it)) {
3.646 + addSource(it);
3.647 + start();
3.648 + }
3.649 + }
3.650 + }
3.651 +
3.652 + ///@}
3.653 +
3.654 + /// \name Query Functions
3.655 + /// The result of the maximum cardinality search algorithm can be
3.656 + /// obtained using these functions.
3.657 + /// \n
3.658 + /// Before the use of these functions, either run() or start() must be
3.659 + /// called.
3.660 +
3.661 + ///@{
3.662 +
3.663 + /// \brief The cardinality of a node.
3.664 + ///
3.665 + /// Returns the cardinality of a node.
3.666 + /// \pre \ref run() must be called before using this function.
3.667 + /// \warning If node \c v in unreachable from the root the return value
3.668 + /// of this funcion is undefined.
3.669 + Value cardinality(Node node) const { return (*_cardinality)[node]; }
3.670 +
3.671 + /// \brief Returns a reference to the NodeMap of cardinalities.
3.672 + ///
3.673 + /// Returns a reference to the NodeMap of cardinalities. \pre \ref run()
3.674 + /// must be called before using this function.
3.675 + const CardinalityMap &cardinalityMap() const { return *_cardinality;}
3.676 +
3.677 + /// \brief Checks if a node is reachable from the root.
3.678 + ///
3.679 + /// Returns \c true if \c v is reachable from the root.
3.680 + /// \warning The source nodes are inditated as unreached.
3.681 + /// \pre \ref run() must be called before using this function.
3.682 + bool reached(Node v) { return (*_heap_cross_ref)[v] != Heap::PRE_HEAP; }
3.683 +
3.684 + /// \brief Checks if a node is processed.
3.685 + ///
3.686 + /// Returns \c true if \c v is processed, i.e. the shortest
3.687 + /// path to \c v has already found.
3.688 + /// \pre \ref run() must be called before using this function.
3.689 + bool processed(Node v) { return (*_heap_cross_ref)[v] == Heap::POST_HEAP; }
3.690 +
3.691 + ///@}
3.692 + };
3.693 +
3.694 + /// \brief Default traits class of MinimumCut class.
3.695 + ///
3.696 + /// Default traits class of MinimumCut class.
3.697 + /// \param Graph Graph type.
3.698 + /// \param CapacityMap Type of length map.
3.699 + template <typename _Graph, typename _CapacityMap>
3.700 + struct MinimumCutDefaultTraits {
3.701 + /// \brief The type of the capacity of the edges.
3.702 + typedef typename _CapacityMap::Value Value;
3.703 +
3.704 + /// The graph type the algorithm runs on.
3.705 + typedef _Graph Graph;
3.706 +
3.707 + /// The WorkGraph type which is an EraseableGraph
3.708 + typedef ListUGraph WorkGraph;
3.709 +
3.710 + /// \brief Instantiates a WorkGraph.
3.711 + ///
3.712 + /// This function instantiates a \ref WorkGraph.
3.713 + static WorkGraph *createWorkGraph() {
3.714 + return new WorkGraph();
3.715 + }
3.716 +
3.717 + /// \brief The type of the map that stores the edge capacities.
3.718 + ///
3.719 + /// The type of the map that stores the edge capacities.
3.720 + /// It must meet the \ref concept::ReadMap "ReadMap" concept.
3.721 + typedef _CapacityMap CapacityMap;
3.722 +
3.723 + /// \brief Instantiates a CapacityMap.
3.724 + ///
3.725 + /// This function instantiates a \ref CapacityMap.
3.726 +#ifdef DOXYGEN
3.727 + static CapacityMap *createCapacityMap(const Graph& graph)
3.728 +#else
3.729 + static CapacityMap *createCapacityMap(const Graph&)
3.730 +#endif
3.731 + {
3.732 + throw UninitializedParameter();
3.733 + }
3.734 +
3.735 + /// \brief The WorkCapacityMap type
3.736 + ///
3.737 + /// The type of the map that stores the working edge capacities.
3.738 + typedef WorkGraph::UEdgeMap<Value> WorkCapacityMap;
3.739 +
3.740 + /// \brief Instantiates a WorkCapacityMap.
3.741 + ///
3.742 + /// This function instantiates a \ref WorkCapacityMap.
3.743 + static WorkCapacityMap *createWorkCapacityMap(const WorkGraph& graph) {
3.744 + return new WorkCapacityMap(graph);
3.745 + }
3.746 +
3.747 + /// \brief The cross reference type used by heap.
3.748 + ///
3.749 + /// The cross reference type used by heap.
3.750 + /// Usually it is \c Graph::NodeMap<int>.
3.751 + typedef WorkGraph::NodeMap<int> HeapCrossRef;
3.752 +
3.753 + /// \brief Instantiates a HeapCrossRef.
3.754 + ///
3.755 + /// This function instantiates a \ref HeapCrossRef.
3.756 + /// \param graph is the graph, to which we would like to define the
3.757 + /// HeapCrossRef.
3.758 + static HeapCrossRef *createHeapCrossRef(const WorkGraph &graph) {
3.759 + return new HeapCrossRef(graph);
3.760 + }
3.761 +
3.762 + /// \brief The heap type used by MinimumCut algorithm.
3.763 + ///
3.764 + /// The heap type used by MinimumCut algorithm. It should
3.765 + /// maximalize the priorities and the heap's key type is
3.766 + /// the work graph's node.
3.767 + ///
3.768 + /// \sa BinHeap
3.769 + /// \sa MinimumCut
3.770 + typedef typename _minimum_cut_bits
3.771 + ::HeapSelector<CapacityMap>
3.772 + ::template Selector<typename WorkGraph::Node, Value, HeapCrossRef>
3.773 + ::Heap Heap;
3.774 +
3.775 + /// \brief Instantiates a Heap.
3.776 + ///
3.777 + /// This function instantiates a \ref Heap.
3.778 + /// \param crossref The cross reference of the heap.
3.779 + static Heap *createHeap(HeapCrossRef& crossref) {
3.780 + return new Heap(crossref);
3.781 + }
3.782 +
3.783 + /// \brief Map from the WorkGraph's node type to the Graph's node type.
3.784 + ///
3.785 + /// Map from the WorkGraph's node type to the Graph's node type.
3.786 + typedef typename WorkGraph
3.787 + ::template NodeMap<typename Graph::Node> NodeRefMap;
3.788 +
3.789 + /// \brief Instantiates a NodeRefMap.
3.790 + ///
3.791 + /// This function instantiates a \ref NodeRefMap.
3.792 + static NodeRefMap *createNodeRefMap(const WorkGraph& graph) {
3.793 + return new NodeRefMap(graph);
3.794 + }
3.795 +
3.796 + /// \brief Map from the Graph's node type to the Graph's node type.
3.797 + ///
3.798 + /// Map from the Graph's node type to the Graph's node type.
3.799 + typedef typename Graph
3.800 + ::template NodeMap<typename Graph::Node> ListRefMap;
3.801 +
3.802 + /// \brief Instantiates a ListRefMap.
3.803 + ///
3.804 + /// This function instantiates a \ref ListRefMap.
3.805 + static ListRefMap *createListRefMap(const Graph& graph) {
3.806 + return new ListRefMap(graph);
3.807 + }
3.808 +
3.809 +
3.810 + };
3.811 +
3.812 + namespace _minimum_cut_bits {
3.813 + template <typename _Key>
3.814 + class LastTwoMap {
3.815 + public:
3.816 + typedef _Key Key;
3.817 + typedef bool Value;
3.818 +
3.819 + LastTwoMap(int _num) : num(_num) {}
3.820 + void set(const Key& key, bool val) {
3.821 + if (!val) return;
3.822 + --num;
3.823 + if (num > 1) return;
3.824 + keys[num] = key;
3.825 + }
3.826 +
3.827 + Key operator[](int index) const { return keys[index]; }
3.828 + private:
3.829 + Key keys[2];
3.830 + int num;
3.831 + };
3.832 + }
3.833 +
3.834 + /// \ingroup topology
3.835 + ///
3.836 + /// \brief Calculates the minimum cut in an undirected graph.
3.837 + ///
3.838 + /// Calculates the minimum cut in an undirected graph.
3.839 + /// The algorithm separates the graph's nodes to two partitions with the
3.840 + /// minimum sum of edge capacities between the two partitions. The
3.841 + /// algorithm can be used to test the network reliability specifically
3.842 + /// to test how many links have to be destroyed in the network to split it
3.843 + /// at least two distinict subnetwork.
3.844 + ///
3.845 + /// The complexity of the algorithm is O(n*e*log(n)) but with Fibonacci
3.846 + /// heap it can be decreased to O(n*e+n^2*log(n)). When the neutral capacity
3.847 + /// map is used then it uses LinearHeap which results O(n*e) time complexity.
3.848 +#ifdef DOXYGEN
3.849 + template <typename _Graph, typename _CapacityMap, typename _Traits>
3.850 +#else
3.851 + template <typename _Graph = ListUGraph,
3.852 + typename _CapacityMap = typename _Graph::template UEdgeMap<int>,
3.853 + typename _Traits = MinimumCutDefaultTraits<_Graph, _CapacityMap> >
3.854 +#endif
3.855 + class MinimumCut {
3.856 + public:
3.857 + /// \brief \ref Exception for uninitialized parameters.
3.858 + ///
3.859 + /// This error represents problems in the initialization
3.860 + /// of the parameters of the algorithms.
3.861 + class UninitializedParameter : public lemon::UninitializedParameter {
3.862 + public:
3.863 + virtual const char* exceptionName() const {
3.864 + return "lemon::MinimumCut::UninitializedParameter";
3.865 + }
3.866 + };
3.867 +
3.868 +
3.869 + private:
3.870 +
3.871 + typedef _Traits Traits;
3.872 + /// The type of the underlying graph.
3.873 + typedef typename Traits::Graph Graph;
3.874 +
3.875 + /// The type of the capacity of the edges.
3.876 + typedef typename Traits::CapacityMap::Value Value;
3.877 + /// The type of the map that stores the edge capacities.
3.878 + typedef typename Traits::CapacityMap CapacityMap;
3.879 + /// The type of the work graph
3.880 + typedef typename Traits::WorkGraph WorkGraph;
3.881 + /// The type of the work capacity map
3.882 + typedef typename Traits::WorkCapacityMap WorkCapacityMap;
3.883 + /// The cross reference type used for the current heap.
3.884 + typedef typename Traits::HeapCrossRef HeapCrossRef;
3.885 + /// The heap type used by the max cardinality algorithm.
3.886 + typedef typename Traits::Heap Heap;
3.887 + /// The node refrefernces between the original and work graph type.
3.888 + typedef typename Traits::NodeRefMap NodeRefMap;
3.889 + /// The list node refrefernces in the original graph type.
3.890 + typedef typename Traits::ListRefMap ListRefMap;
3.891 +
3.892 + public:
3.893 +
3.894 + ///\name Named template parameters
3.895 +
3.896 + ///@{
3.897 +
3.898 + struct DefNeutralCapacityTraits : public Traits {
3.899 + typedef ConstMap<typename Graph::UEdge, Const<int, 1> > CapacityMap;
3.900 + static CapacityMap *createCapacityMap(const Graph&) {
3.901 + return new CapacityMap();
3.902 + }
3.903 + };
3.904 + /// \brief \ref named-templ-param "Named parameter" for setting
3.905 + /// the capacity type to constMap<UEdge, int, 1>()
3.906 + ///
3.907 + /// \ref named-templ-param "Named parameter" for setting
3.908 + /// the capacity type to constMap<UEdge, int, 1>()
3.909 + struct DefNeutralCapacity
3.910 + : public MinimumCut<Graph, CapacityMap, DefNeutralCapacityTraits> {
3.911 + typedef MinimumCut<Graph, CapacityMap, DefNeutralCapacityTraits> Create;
3.912 + };
3.913 +
3.914 +
3.915 + template <class H, class CR>
3.916 + struct DefHeapTraits : public Traits {
3.917 + typedef CR HeapCrossRef;
3.918 + typedef H Heap;
3.919 + static HeapCrossRef *createHeapCrossRef(const WorkGraph &) {
3.920 + throw UninitializedParameter();
3.921 + }
3.922 + static Heap *createHeap(HeapCrossRef &) {
3.923 + throw UninitializedParameter();
3.924 + }
3.925 + };
3.926 + /// \brief \ref named-templ-param "Named parameter" for setting heap
3.927 + /// and cross reference type
3.928 + ///
3.929 + /// \ref named-templ-param "Named parameter" for setting heap and cross
3.930 + /// reference type
3.931 + template <class H, class CR = typename Graph::template NodeMap<int> >
3.932 + struct DefHeap
3.933 + : public MinimumCut<Graph, CapacityMap, DefHeapTraits<H, CR> > {
3.934 + typedef MinimumCut< Graph, CapacityMap, DefHeapTraits<H, CR> > Create;
3.935 + };
3.936 +
3.937 + template <class H, class CR>
3.938 + struct DefStandardHeapTraits : public Traits {
3.939 + typedef CR HeapCrossRef;
3.940 + typedef H Heap;
3.941 + static HeapCrossRef *createHeapCrossRef(const WorkGraph &graph) {
3.942 + return new HeapCrossRef(graph);
3.943 + }
3.944 + static Heap *createHeap(HeapCrossRef &crossref) {
3.945 + return new Heap(crossref);
3.946 + }
3.947 + };
3.948 +
3.949 + /// \brief \ref named-templ-param "Named parameter" for setting heap and
3.950 + /// cross reference type with automatic allocation
3.951 + ///
3.952 + /// \ref named-templ-param "Named parameter" for setting heap and cross
3.953 + /// reference type. It can allocate the heap and the cross reference
3.954 + /// object if the cross reference's constructor waits for the graph as
3.955 + /// parameter and the heap's constructor waits for the cross reference.
3.956 + template <class H, class CR = typename Graph::template NodeMap<int> >
3.957 + struct DefStandardHeap
3.958 + : public MinimumCut<Graph, CapacityMap, DefStandardHeapTraits<H, CR> > {
3.959 + typedef MinimumCut<Graph, CapacityMap, DefStandardHeapTraits<H, CR> >
3.960 + Create;
3.961 + };
3.962 +
3.963 + ///@}
3.964 +
3.965 +
3.966 + private:
3.967 + /// Pointer to the underlying graph.
3.968 + const Graph *_graph;
3.969 + /// Pointer to the capacity map
3.970 + const CapacityMap *_capacity;
3.971 + /// \brief Indicates if \ref _capacity is locally allocated
3.972 + /// (\c true) or not.
3.973 + bool local_capacity;
3.974 +
3.975 + /// Pointer to the work graph.
3.976 + WorkGraph *_work_graph;
3.977 + /// \brief Indicates if \ref _work_graph is locally allocated
3.978 + /// (\c true) or not.
3.979 + bool local_work_graph;
3.980 + /// Pointer to the work capacity map
3.981 + WorkCapacityMap *_work_capacity;
3.982 + /// \brief Indicates if \ref _work_capacity is locally allocated
3.983 + /// (\c true) or not.
3.984 + bool local_work_capacity;
3.985 + /// Pointer to the heap cross references.
3.986 + HeapCrossRef *_heap_cross_ref;
3.987 + /// \brief Indicates if \ref _heap_cross_ref is locally allocated
3.988 + /// (\c true) or not.
3.989 + bool local_heap_cross_ref;
3.990 + /// Pointer to the heap.
3.991 + Heap *_heap;
3.992 + /// Indicates if \ref _heap is locally allocated (\c true) or not.
3.993 + bool local_heap;
3.994 +
3.995 + /// The minimum cut value.
3.996 + Value _minimum_cut;
3.997 + /// The number of the nodes of the work graph.
3.998 + int _node_num;
3.999 + /// The first and last node of the min cut in the next list;
3.1000 + typename Graph::Node _first_node, _last_node;
3.1001 +
3.1002 + /// \brief The first and last element in the list associated
3.1003 + /// to the work graph node.
3.1004 + NodeRefMap *_first, *_last;
3.1005 + /// \brief The next node in the node lists.
3.1006 + ListRefMap *_next;
3.1007 +
3.1008 + void create_structures() {
3.1009 + if (!_capacity) {
3.1010 + local_capacity = true;
3.1011 + _capacity = Traits::createCapacityMap(*_graph);
3.1012 + }
3.1013 + if(!_work_graph) {
3.1014 + local_work_graph = true;
3.1015 + _work_graph = Traits::createWorkGraph();
3.1016 + }
3.1017 + if(!_work_capacity) {
3.1018 + local_work_capacity = true;
3.1019 + _work_capacity = Traits::createWorkCapacityMap(*_work_graph);
3.1020 + }
3.1021 +
3.1022 + _first = Traits::createNodeRefMap(*_work_graph);
3.1023 + _last = Traits::createNodeRefMap(*_work_graph);
3.1024 +
3.1025 + _next = Traits::createListRefMap(*_graph);
3.1026 +
3.1027 + typename Graph::template NodeMap<typename WorkGraph::Node> ref(*_graph);
3.1028 +
3.1029 + for (typename Graph::NodeIt it(*_graph); it != INVALID; ++it) {
3.1030 + _next->set(it, INVALID);
3.1031 + typename WorkGraph::Node node = _work_graph->addNode();
3.1032 + _first->set(node, it);
3.1033 + _last->set(node, it);
3.1034 + ref.set(it, node);
3.1035 + }
3.1036 +
3.1037 + for (typename Graph::UEdgeIt it(*_graph); it != INVALID; ++it) {
3.1038 + if (_graph->source(it) == _graph->target(it)) continue;
3.1039 + typename WorkGraph::UEdge uedge =
3.1040 + _work_graph->addEdge(ref[_graph->source(it)],
3.1041 + ref[_graph->target(it)]);
3.1042 + _work_capacity->set(uedge, (*_capacity)[it]);
3.1043 +
3.1044 + }
3.1045 +
3.1046 + if (!_heap_cross_ref) {
3.1047 + local_heap_cross_ref = true;
3.1048 + _heap_cross_ref = Traits::createHeapCrossRef(*_work_graph);
3.1049 + }
3.1050 + if (!_heap) {
3.1051 + local_heap = true;
3.1052 + _heap = Traits::createHeap(*_heap_cross_ref);
3.1053 + }
3.1054 + }
3.1055 +
3.1056 + public :
3.1057 +
3.1058 + typedef MinimumCut Create;
3.1059 +
3.1060 +
3.1061 + /// \brief Constructor.
3.1062 + ///
3.1063 + ///\param graph the graph the algorithm will run on.
3.1064 + ///\param capacity the capacity map used by the algorithm.
3.1065 + MinimumCut(const Graph& graph, const CapacityMap& capacity)
3.1066 + : _graph(&graph),
3.1067 + _capacity(&capacity), local_capacity(false),
3.1068 + _work_graph(0), local_work_graph(false),
3.1069 + _work_capacity(0), local_work_capacity(false),
3.1070 + _heap_cross_ref(0), local_heap_cross_ref(false),
3.1071 + _heap(0), local_heap(false),
3.1072 + _first(0), _last(0), _next(0) {}
3.1073 +
3.1074 + /// \brief Constructor.
3.1075 + ///
3.1076 + /// This constructor can be used only when the Traits class
3.1077 + /// defines how can we instantiate a local capacity map.
3.1078 + /// If the DefNeutralCapacity used the algorithm automatically
3.1079 + /// construct the capacity map.
3.1080 + ///
3.1081 + ///\param graph the graph the algorithm will run on.
3.1082 + MinimumCut(const Graph& graph)
3.1083 + : _graph(&graph),
3.1084 + _capacity(0), local_capacity(false),
3.1085 + _work_graph(0), local_work_graph(false),
3.1086 + _work_capacity(0), local_work_capacity(false),
3.1087 + _heap_cross_ref(0), local_heap_cross_ref(false),
3.1088 + _heap(0), local_heap(false),
3.1089 + _first(0), _last(0), _next(0) {}
3.1090 +
3.1091 + /// \brief Destructor.
3.1092 + ///
3.1093 + /// Destructor.
3.1094 + ~MinimumCut() {
3.1095 + if (local_heap) delete _heap;
3.1096 + if (local_heap_cross_ref) delete _heap_cross_ref;
3.1097 + if (_first) delete _first;
3.1098 + if (_last) delete _last;
3.1099 + if (_next) delete _next;
3.1100 + if (local_work_capacity) delete _work_capacity;
3.1101 + if (local_work_graph) delete _work_graph;
3.1102 + if (local_capacity) delete _capacity;
3.1103 + }
3.1104 +
3.1105 + /// \brief Sets the heap and the cross reference used by algorithm.
3.1106 + ///
3.1107 + /// Sets the heap and the cross reference used by algorithm.
3.1108 + /// If you don't use this function before calling \ref run(),
3.1109 + /// it will allocate one. The destuctor deallocates this
3.1110 + /// automatically allocated heap and cross reference, of course.
3.1111 + /// \return <tt> (*this) </tt>
3.1112 + MinimumCut &heap(Heap& heap, HeapCrossRef &crossRef)
3.1113 + {
3.1114 + if (local_heap_cross_ref) {
3.1115 + delete _heap_cross_ref;
3.1116 + local_heap_cross_ref=false;
3.1117 + }
3.1118 + _heap_cross_ref = &crossRef;
3.1119 + if (local_heap) {
3.1120 + delete _heap;
3.1121 + local_heap=false;
3.1122 + }
3.1123 + _heap = &heap;
3.1124 + return *this;
3.1125 + }
3.1126 +
3.1127 + /// \brief Sets the work graph.
3.1128 + ///
3.1129 + /// Sets the work graph used by algorithm.
3.1130 + /// If you don't use this function before calling \ref run(),
3.1131 + /// it will allocate one. The destuctor deallocates this
3.1132 + /// automatically allocated graph, of course.
3.1133 + /// \return <tt> (*this) </tt>
3.1134 + MinimumCut &workGraph(WorkGraph& work_graph)
3.1135 + {
3.1136 + if(local_work_graph) {
3.1137 + delete _work_graph;
3.1138 + local_work_graph=false;
3.1139 + }
3.1140 + _work_graph = &work_graph;
3.1141 + return *this;
3.1142 + }
3.1143 +
3.1144 + /// \brief Sets the work capacity map.
3.1145 + ///
3.1146 + /// Sets the work capacity map used by algorithm.
3.1147 + /// If you don't use this function before calling \ref run(),
3.1148 + /// it will allocate one. The destuctor deallocates this
3.1149 + /// automatically allocated graph, of course.
3.1150 + /// \return <tt> (*this) </tt>
3.1151 + MinimumCut &workCapacityMap(WorkCapacityMap& work_capacity_map)
3.1152 + {
3.1153 + if(local_work_capacity) {
3.1154 + delete _work_capacity;
3.1155 + local_work_capacity=false;
3.1156 + }
3.1157 + _work_capacity = &work_capacity_map;
3.1158 + return *this;
3.1159 + }
3.1160 +
3.1161 + /// \name Execution control
3.1162 + /// The simplest way to execute the algorithm is to use
3.1163 + /// one of the member functions called \c run().
3.1164 + /// \n
3.1165 + /// If you need more control on the execution,
3.1166 + /// first you must call \ref init() and then call the start()
3.1167 + /// or proper times the processNextPhase() member functions.
3.1168 +
3.1169 + ///@{
3.1170 +
3.1171 + /// \brief Initializes the internal data structures.
3.1172 + ///
3.1173 + /// Initializes the internal data structures.
3.1174 + void init() {
3.1175 + create_structures();
3.1176 + _first_node = _last_node = INVALID;
3.1177 + _node_num = countNodes(*_graph);
3.1178 + }
3.1179 +
3.1180 + /// \brief Processes the next phase
3.1181 + ///
3.1182 + /// Processes the next phase in the algorithm. The function
3.1183 + /// should be called countNodes(graph) - 1 times to get
3.1184 + /// surely the minimum cut in the graph. The
3.1185 + ///
3.1186 + ///\return %True when the algorithm finished.
3.1187 + bool processNextPhase() {
3.1188 + if (_node_num <= 1) return true;
3.1189 + using namespace _minimum_cut_bits;
3.1190 +
3.1191 + typedef typename WorkGraph::Node Node;
3.1192 + typedef typename WorkGraph::NodeIt NodeIt;
3.1193 + typedef typename WorkGraph::UEdge UEdge;
3.1194 + typedef typename WorkGraph::IncEdgeIt IncEdgeIt;
3.1195 +
3.1196 + typedef typename MaxCardinalitySearch<WorkGraph, WorkCapacityMap>::
3.1197 + template DefHeap<Heap, HeapCrossRef>::
3.1198 + template DefCardinalityMap<NullMap<Node, Value> >::
3.1199 + template DefProcessedMap<LastTwoMap<Node> >::
3.1200 + Create MaxCardinalitySearch;
3.1201 +
3.1202 + MaxCardinalitySearch mcs(*_work_graph, *_work_capacity);
3.1203 + for (NodeIt it(*_work_graph); it != INVALID; ++it) {
3.1204 + _heap_cross_ref->set(it, Heap::PRE_HEAP);
3.1205 + }
3.1206 + mcs.heap(*_heap, *_heap_cross_ref);
3.1207 +
3.1208 + LastTwoMap<Node> last_two_nodes(_node_num);
3.1209 + mcs.processedMap(last_two_nodes);
3.1210 +
3.1211 + NullMap<Node, Value> cardinality;
3.1212 + mcs.cardinalityMap(cardinality);
3.1213 +
3.1214 + mcs.run();
3.1215 +
3.1216 + Node new_node = _work_graph->addNode();
3.1217 +
3.1218 + typename WorkGraph::template NodeMap<UEdge> edges(*_work_graph, INVALID);
3.1219 +
3.1220 + Node first_node = last_two_nodes[0];
3.1221 + Node second_node = last_two_nodes[1];
3.1222 +
3.1223 + _next->set((*_last)[first_node], (*_first)[second_node]);
3.1224 + _first->set(new_node, (*_first)[first_node]);
3.1225 + _last->set(new_node, (*_last)[second_node]);
3.1226 +
3.1227 + Value current_cut = 0;
3.1228 + for (IncEdgeIt it(*_work_graph, first_node); it != INVALID; ++it) {
3.1229 + Node node = _work_graph->runningNode(it);
3.1230 + current_cut += (*_work_capacity)[it];
3.1231 + if (node == second_node) continue;
3.1232 + if (edges[node] == INVALID) {
3.1233 + edges[node] = _work_graph->addEdge(new_node, node);
3.1234 + (*_work_capacity)[edges[node]] = (*_work_capacity)[it];
3.1235 + } else {
3.1236 + (*_work_capacity)[edges[node]] += (*_work_capacity)[it];
3.1237 + }
3.1238 + }
3.1239 +
3.1240 + if (_first_node == INVALID || current_cut < _minimum_cut) {
3.1241 + _first_node = (*_first)[first_node];
3.1242 + _last_node = (*_last)[first_node];
3.1243 + _minimum_cut = current_cut;
3.1244 + }
3.1245 +
3.1246 + _work_graph->erase(first_node);
3.1247 +
3.1248 + for (IncEdgeIt it(*_work_graph, second_node); it != INVALID; ++it) {
3.1249 + Node node = _work_graph->runningNode(it);
3.1250 + if (edges[node] == INVALID) {
3.1251 + edges[node] = _work_graph->addEdge(new_node, node);
3.1252 + (*_work_capacity)[edges[node]] = (*_work_capacity)[it];
3.1253 + } else {
3.1254 + (*_work_capacity)[edges[node]] += (*_work_capacity)[it];
3.1255 + }
3.1256 + }
3.1257 + _work_graph->erase(second_node);
3.1258 +
3.1259 + --_node_num;
3.1260 + return _node_num == 1;
3.1261 + }
3.1262 +
3.1263 + /// \brief Executes the algorithm.
3.1264 + ///
3.1265 + /// Executes the algorithm.
3.1266 + ///
3.1267 + /// \pre init() must be called
3.1268 + void start() {
3.1269 + while (!processNextPhase());
3.1270 + }
3.1271 +
3.1272 +
3.1273 + /// \brief Runs %MinimumCut algorithm.
3.1274 + ///
3.1275 + /// This method runs the %Minimum cut algorithm
3.1276 + ///
3.1277 + /// \note mc.run(s) is just a shortcut of the following code.
3.1278 + ///\code
3.1279 + /// mc.init();
3.1280 + /// mc.start();
3.1281 + ///\endcode
3.1282 + void run() {
3.1283 + init();
3.1284 + start();
3.1285 + }
3.1286 +
3.1287 + ///@}
3.1288 +
3.1289 + /// \name Query Functions
3.1290 + /// The result of the %MinimumCut algorithm can be obtained using these
3.1291 + /// functions.\n
3.1292 + /// Before the use of these functions,
3.1293 + /// either run() or start() must be called.
3.1294 +
3.1295 + ///@{
3.1296 +
3.1297 + /// \brief Returns the minimum cut value.
3.1298 + ///
3.1299 + /// Returns the minimum cut value if the algorithm finished.
3.1300 + /// After the first processNextPhase() it is a value of a
3.1301 + /// valid cut in the graph.
3.1302 + Value minCut() const {
3.1303 + return _minimum_cut;
3.1304 + }
3.1305 +
3.1306 + /// \brief Returns a minimum cut in a NodeMap.
3.1307 + ///
3.1308 + /// It sets the nodes of one of the two partitions to true in
3.1309 + /// the given BoolNodeMap. The map contains a valid cut if the
3.1310 + /// map have been setted false previously.
3.1311 + template <typename NodeMap>
3.1312 + Value quickMinCut(NodeMap& nodeMap) const {
3.1313 + for (typename Graph::Node it = _first_node;
3.1314 + it != _last_node; it = (*_next)[it]) {
3.1315 + nodeMap.set(it, true);
3.1316 + }
3.1317 + nodeMap.set(_last_node, true);
3.1318 + return minCut();
3.1319 + }
3.1320 +
3.1321 + /// \brief Returns a minimum cut in a NodeMap.
3.1322 + ///
3.1323 + /// It sets the nodes of one of the two partitions to true and
3.1324 + /// the other partition to false. The function first set all of the
3.1325 + /// nodes to false and after it call the quickMinCut() member.
3.1326 + template <typename NodeMap>
3.1327 + Value minCut(NodeMap& nodeMap) const {
3.1328 + for (typename Graph::NodeIt it(*_graph); it != INVALID; ++it) {
3.1329 + nodeMap.set(it, false);
3.1330 + }
3.1331 + quickMinCut(nodeMap);
3.1332 + return minCut();
3.1333 + }
3.1334 +
3.1335 + /// \brief Returns a minimum cut in an EdgeMap.
3.1336 + ///
3.1337 + /// If an undirected edge is cut edge then it will be
3.1338 + /// setted to true and the others will be setted to false in the given map.
3.1339 + template <typename EdgeMap>
3.1340 + Value cutEdges(EdgeMap& edgeMap) const {
3.1341 + typename Graph::template NodeMap<bool> cut(*_graph, false);
3.1342 + quickMinCut(cut);
3.1343 + for (typename Graph::EdgeIt it(*_graph); it != INVALID; ++it) {
3.1344 + edgeMap.set(it, cut[_graph->source(it)] ^ cut[_graph->target(it)]);
3.1345 + }
3.1346 + return minCut();
3.1347 + }
3.1348 +
3.1349 + ///@}
3.1350 +
3.1351 + };
3.1352 +}
3.1353 +
3.1354 +#endif