1.1 --- a/lemon/Makefile.am Tue Oct 31 14:28:27 2006 +0000
1.2 +++ b/lemon/Makefile.am Tue Oct 31 14:30:54 2006 +0000
1.3 @@ -76,9 +76,9 @@
1.4 lemon/matrix_maps.h \
1.5 lemon/max_matching.h \
1.6 lemon/min_cost_arborescence.h \
1.7 - lemon/min_cut.h \
1.8 lemon/mip_glpk.h \
1.9 lemon/mip_cplex.h \
1.10 + lemon/nagamochi_ibaraki.h \
1.11 lemon/path.h \
1.12 lemon/polynomial.h \
1.13 lemon/preflow.h \
2.1 --- a/lemon/min_cut.h Tue Oct 31 14:28:27 2006 +0000
2.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
2.3 @@ -1,1353 +0,0 @@
2.4 -/* -*- C++ -*-
2.5 - * lemon/min_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_MIN_CUT_H
2.21 -#define LEMON_MIN_CUT_H
2.22 -
2.23 -
2.24 -/// \ingroup topology
2.25 -/// \file
2.26 -/// \brief Maximum cardinality search and min cut in undirected graphs.
2.27 -
2.28 -#include <lemon/list_graph.h>
2.29 -#include <lemon/bin_heap.h>
2.30 -#include <lemon/bucket_heap.h>
2.31 -
2.32 -#include <lemon/bits/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 _min_cut_bits {
2.41 -
2.42 - template <typename CapacityMap>
2.43 - struct HeapSelector {
2.44 - template <typename Value, typename Ref>
2.45 - struct Selector {
2.46 - typedef BinHeap<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 Value, typename Ref>
2.53 - struct Selector {
2.54 - typedef BucketHeap<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 concepts::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 BucketHeap.
2.101 - ///
2.102 - /// \sa MaxCardinalitySearch
2.103 - typedef typename _min_cut_bits
2.104 - ::HeapSelector<CapacityMap>
2.105 - ::template Selector<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 concepts::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 graph 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 concepts::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 it chooses the node which is 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 node 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 concepts::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 - /// concepts::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 - /// concepts::Graph::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* what() const throw() {
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 MinCut class.
2.695 - ///
2.696 - /// Default traits class of MinCut 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 MinCutDefaultTraits {
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 AuxGraph type which is an Graph
2.708 - typedef ListUGraph AuxGraph;
2.709 -
2.710 - /// \brief Instantiates a AuxGraph.
2.711 - ///
2.712 - /// This function instantiates a \ref AuxGraph.
2.713 - static AuxGraph *createAuxGraph() {
2.714 - return new AuxGraph();
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 concepts::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 AuxCapacityMap type
2.736 - ///
2.737 - /// The type of the map that stores the auxing edge capacities.
2.738 - typedef AuxGraph::UEdgeMap<Value> AuxCapacityMap;
2.739 -
2.740 - /// \brief Instantiates a AuxCapacityMap.
2.741 - ///
2.742 - /// This function instantiates a \ref AuxCapacityMap.
2.743 - static AuxCapacityMap *createAuxCapacityMap(const AuxGraph& graph) {
2.744 - return new AuxCapacityMap(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 AuxGraph::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 AuxGraph &graph) {
2.759 - return new HeapCrossRef(graph);
2.760 - }
2.761 -
2.762 - /// \brief The heap type used by MinCut algorithm.
2.763 - ///
2.764 - /// The heap type used by MinCut algorithm. It should
2.765 - /// maximalize the priorities and the heap's key type is
2.766 - /// the aux graph's node.
2.767 - ///
2.768 - /// \sa BinHeap
2.769 - /// \sa MinCut
2.770 - typedef typename _min_cut_bits
2.771 - ::HeapSelector<CapacityMap>
2.772 - ::template Selector<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 AuxGraph's node type to the Graph's node type.
2.784 - ///
2.785 - /// Map from the AuxGraph's node type to the Graph's node type.
2.786 - typedef typename AuxGraph
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 AuxGraph& 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 _min_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 minimum cut in an undirected graph.
2.837 - ///
2.838 - /// Calculates the minimum cut in an undirected graph with the
2.839 - /// Nagamochi-Ibaraki algorithm. The algorithm separates the graph's
2.840 - /// nodes into two partitions with the minimum sum of edge capacities
2.841 - /// between the two partitions. The algorithm can be used to test
2.842 - /// the network reliability specifically to test how many links have
2.843 - /// to be destroyed in the network to split it at least two
2.844 - /// distinict subnetwork.
2.845 - ///
2.846 - /// The complexity of the algorithm is \f$ O(ne\log(n)) \f$ but with
2.847 - /// Fibonacci heap it can be decreased to \f$ O(ne+n^2\log(n))
2.848 - /// \f$. When capacity map is neutral then it uses BucketHeap which
2.849 - /// results \f$ O(ne) \f$ time complexity.
2.850 -#ifdef DOXYGEN
2.851 - template <typename _Graph, typename _CapacityMap, typename _Traits>
2.852 -#else
2.853 - template <typename _Graph = ListUGraph,
2.854 - typename _CapacityMap = typename _Graph::template UEdgeMap<int>,
2.855 - typename _Traits = MinCutDefaultTraits<_Graph, _CapacityMap> >
2.856 -#endif
2.857 - class MinCut {
2.858 - public:
2.859 - /// \brief \ref Exception for uninitialized parameters.
2.860 - ///
2.861 - /// This error represents problems in the initialization
2.862 - /// of the parameters of the algorithms.
2.863 - class UninitializedParameter : public lemon::UninitializedParameter {
2.864 - public:
2.865 - virtual const char* what() const throw() {
2.866 - return "lemon::MinCut::UninitializedParameter";
2.867 - }
2.868 - };
2.869 -
2.870 -
2.871 - private:
2.872 -
2.873 - typedef _Traits Traits;
2.874 - /// The type of the underlying graph.
2.875 - typedef typename Traits::Graph Graph;
2.876 -
2.877 - /// The type of the capacity of the edges.
2.878 - typedef typename Traits::CapacityMap::Value Value;
2.879 - /// The type of the map that stores the edge capacities.
2.880 - typedef typename Traits::CapacityMap CapacityMap;
2.881 - /// The type of the aux graph
2.882 - typedef typename Traits::AuxGraph AuxGraph;
2.883 - /// The type of the aux capacity map
2.884 - typedef typename Traits::AuxCapacityMap AuxCapacityMap;
2.885 - /// The cross reference type used for the current heap.
2.886 - typedef typename Traits::HeapCrossRef HeapCrossRef;
2.887 - /// The heap type used by the max cardinality algorithm.
2.888 - typedef typename Traits::Heap Heap;
2.889 - /// The node refrefernces between the original and aux graph type.
2.890 - typedef typename Traits::NodeRefMap NodeRefMap;
2.891 - /// The list node refrefernces in the original graph type.
2.892 - typedef typename Traits::ListRefMap ListRefMap;
2.893 -
2.894 - public:
2.895 -
2.896 - ///\name Named template parameters
2.897 -
2.898 - ///@{
2.899 -
2.900 - struct DefNeutralCapacityTraits : public Traits {
2.901 - typedef ConstMap<typename Graph::UEdge, Const<int, 1> > CapacityMap;
2.902 - static CapacityMap *createCapacityMap(const Graph&) {
2.903 - return new CapacityMap();
2.904 - }
2.905 - };
2.906 - /// \brief \ref named-templ-param "Named parameter" for setting
2.907 - /// the capacity type to constMap<UEdge, int, 1>()
2.908 - ///
2.909 - /// \ref named-templ-param "Named parameter" for setting
2.910 - /// the capacity type to constMap<UEdge, int, 1>()
2.911 - struct DefNeutralCapacity
2.912 - : public MinCut<Graph, CapacityMap, DefNeutralCapacityTraits> {
2.913 - typedef MinCut<Graph, CapacityMap, DefNeutralCapacityTraits> Create;
2.914 - };
2.915 -
2.916 -
2.917 - template <class H, class CR>
2.918 - struct DefHeapTraits : public Traits {
2.919 - typedef CR HeapCrossRef;
2.920 - typedef H Heap;
2.921 - static HeapCrossRef *createHeapCrossRef(const AuxGraph &) {
2.922 - throw UninitializedParameter();
2.923 - }
2.924 - static Heap *createHeap(HeapCrossRef &) {
2.925 - throw UninitializedParameter();
2.926 - }
2.927 - };
2.928 - /// \brief \ref named-templ-param "Named parameter" for setting heap
2.929 - /// and cross reference type
2.930 - ///
2.931 - /// \ref named-templ-param "Named parameter" for setting heap and cross
2.932 - /// reference type
2.933 - template <class H, class CR = typename Graph::template NodeMap<int> >
2.934 - struct DefHeap
2.935 - : public MinCut<Graph, CapacityMap, DefHeapTraits<H, CR> > {
2.936 - typedef MinCut< Graph, CapacityMap, DefHeapTraits<H, CR> > Create;
2.937 - };
2.938 -
2.939 - template <class H, class CR>
2.940 - struct DefStandardHeapTraits : public Traits {
2.941 - typedef CR HeapCrossRef;
2.942 - typedef H Heap;
2.943 - static HeapCrossRef *createHeapCrossRef(const AuxGraph &graph) {
2.944 - return new HeapCrossRef(graph);
2.945 - }
2.946 - static Heap *createHeap(HeapCrossRef &crossref) {
2.947 - return new Heap(crossref);
2.948 - }
2.949 - };
2.950 -
2.951 - /// \brief \ref named-templ-param "Named parameter" for setting heap and
2.952 - /// cross reference type with automatic allocation
2.953 - ///
2.954 - /// \ref named-templ-param "Named parameter" for setting heap and cross
2.955 - /// reference type. It can allocate the heap and the cross reference
2.956 - /// object if the cross reference's constructor waits for the graph as
2.957 - /// parameter and the heap's constructor waits for the cross reference.
2.958 - template <class H, class CR = typename Graph::template NodeMap<int> >
2.959 - struct DefStandardHeap
2.960 - : public MinCut<Graph, CapacityMap, DefStandardHeapTraits<H, CR> > {
2.961 - typedef MinCut<Graph, CapacityMap, DefStandardHeapTraits<H, CR> >
2.962 - Create;
2.963 - };
2.964 -
2.965 - ///@}
2.966 -
2.967 -
2.968 - private:
2.969 - /// Pointer to the underlying graph.
2.970 - const Graph *_graph;
2.971 - /// Pointer to the capacity map
2.972 - const CapacityMap *_capacity;
2.973 - /// \brief Indicates if \ref _capacity is locally allocated
2.974 - /// (\c true) or not.
2.975 - bool local_capacity;
2.976 -
2.977 - /// Pointer to the aux graph.
2.978 - AuxGraph *_aux_graph;
2.979 - /// \brief Indicates if \ref _aux_graph is locally allocated
2.980 - /// (\c true) or not.
2.981 - bool local_aux_graph;
2.982 - /// Pointer to the aux capacity map
2.983 - AuxCapacityMap *_aux_capacity;
2.984 - /// \brief Indicates if \ref _aux_capacity is locally allocated
2.985 - /// (\c true) or not.
2.986 - bool local_aux_capacity;
2.987 - /// Pointer to the heap cross references.
2.988 - HeapCrossRef *_heap_cross_ref;
2.989 - /// \brief Indicates if \ref _heap_cross_ref is locally allocated
2.990 - /// (\c true) or not.
2.991 - bool local_heap_cross_ref;
2.992 - /// Pointer to the heap.
2.993 - Heap *_heap;
2.994 - /// Indicates if \ref _heap is locally allocated (\c true) or not.
2.995 - bool local_heap;
2.996 -
2.997 - /// The min cut value.
2.998 - Value _min_cut;
2.999 - /// The number of the nodes of the aux graph.
2.1000 - int _node_num;
2.1001 - /// The first and last node of the min cut in the next list;
2.1002 - typename Graph::Node _first_node, _last_node;
2.1003 -
2.1004 - /// \brief The first and last element in the list associated
2.1005 - /// to the aux graph node.
2.1006 - NodeRefMap *_first, *_last;
2.1007 - /// \brief The next node in the node lists.
2.1008 - ListRefMap *_next;
2.1009 -
2.1010 - void create_structures() {
2.1011 - if (!_capacity) {
2.1012 - local_capacity = true;
2.1013 - _capacity = Traits::createCapacityMap(*_graph);
2.1014 - }
2.1015 - if(!_aux_graph) {
2.1016 - local_aux_graph = true;
2.1017 - _aux_graph = Traits::createAuxGraph();
2.1018 - }
2.1019 - if(!_aux_capacity) {
2.1020 - local_aux_capacity = true;
2.1021 - _aux_capacity = Traits::createAuxCapacityMap(*_aux_graph);
2.1022 - }
2.1023 -
2.1024 - _first = Traits::createNodeRefMap(*_aux_graph);
2.1025 - _last = Traits::createNodeRefMap(*_aux_graph);
2.1026 -
2.1027 - _next = Traits::createListRefMap(*_graph);
2.1028 -
2.1029 - typename Graph::template NodeMap<typename AuxGraph::Node> ref(*_graph);
2.1030 -
2.1031 - for (typename Graph::NodeIt it(*_graph); it != INVALID; ++it) {
2.1032 - _next->set(it, INVALID);
2.1033 - typename AuxGraph::Node node = _aux_graph->addNode();
2.1034 - _first->set(node, it);
2.1035 - _last->set(node, it);
2.1036 - ref.set(it, node);
2.1037 - }
2.1038 -
2.1039 - for (typename Graph::UEdgeIt it(*_graph); it != INVALID; ++it) {
2.1040 - if (_graph->source(it) == _graph->target(it)) continue;
2.1041 - typename AuxGraph::UEdge uedge =
2.1042 - _aux_graph->addEdge(ref[_graph->source(it)],
2.1043 - ref[_graph->target(it)]);
2.1044 - _aux_capacity->set(uedge, (*_capacity)[it]);
2.1045 -
2.1046 - }
2.1047 -
2.1048 - if (!_heap_cross_ref) {
2.1049 - local_heap_cross_ref = true;
2.1050 - _heap_cross_ref = Traits::createHeapCrossRef(*_aux_graph);
2.1051 - }
2.1052 - if (!_heap) {
2.1053 - local_heap = true;
2.1054 - _heap = Traits::createHeap(*_heap_cross_ref);
2.1055 - }
2.1056 - }
2.1057 -
2.1058 - public :
2.1059 -
2.1060 - typedef MinCut Create;
2.1061 -
2.1062 -
2.1063 - /// \brief Constructor.
2.1064 - ///
2.1065 - ///\param graph the graph the algorithm will run on.
2.1066 - ///\param capacity the capacity map used by the algorithm.
2.1067 - MinCut(const Graph& graph, const CapacityMap& capacity)
2.1068 - : _graph(&graph),
2.1069 - _capacity(&capacity), local_capacity(false),
2.1070 - _aux_graph(0), local_aux_graph(false),
2.1071 - _aux_capacity(0), local_aux_capacity(false),
2.1072 - _heap_cross_ref(0), local_heap_cross_ref(false),
2.1073 - _heap(0), local_heap(false),
2.1074 - _first(0), _last(0), _next(0) {}
2.1075 -
2.1076 - /// \brief Constructor.
2.1077 - ///
2.1078 - /// This constructor can be used only when the Traits class
2.1079 - /// defines how can we instantiate a local capacity map.
2.1080 - /// If the DefNeutralCapacity used the algorithm automatically
2.1081 - /// construct the capacity map.
2.1082 - ///
2.1083 - ///\param graph the graph the algorithm will run on.
2.1084 - MinCut(const Graph& graph)
2.1085 - : _graph(&graph),
2.1086 - _capacity(0), local_capacity(false),
2.1087 - _aux_graph(0), local_aux_graph(false),
2.1088 - _aux_capacity(0), local_aux_capacity(false),
2.1089 - _heap_cross_ref(0), local_heap_cross_ref(false),
2.1090 - _heap(0), local_heap(false),
2.1091 - _first(0), _last(0), _next(0) {}
2.1092 -
2.1093 - /// \brief Destructor.
2.1094 - ///
2.1095 - /// Destructor.
2.1096 - ~MinCut() {
2.1097 - if (local_heap) delete _heap;
2.1098 - if (local_heap_cross_ref) delete _heap_cross_ref;
2.1099 - if (_first) delete _first;
2.1100 - if (_last) delete _last;
2.1101 - if (_next) delete _next;
2.1102 - if (local_aux_capacity) delete _aux_capacity;
2.1103 - if (local_aux_graph) delete _aux_graph;
2.1104 - if (local_capacity) delete _capacity;
2.1105 - }
2.1106 -
2.1107 - /// \brief Sets the heap and the cross reference used by algorithm.
2.1108 - ///
2.1109 - /// Sets the heap and the cross reference used by algorithm.
2.1110 - /// If you don't use this function before calling \ref run(),
2.1111 - /// it will allocate one. The destuctor deallocates this
2.1112 - /// automatically allocated heap and cross reference, of course.
2.1113 - /// \return <tt> (*this) </tt>
2.1114 - MinCut &heap(Heap& heap, HeapCrossRef &crossRef)
2.1115 - {
2.1116 - if (local_heap_cross_ref) {
2.1117 - delete _heap_cross_ref;
2.1118 - local_heap_cross_ref=false;
2.1119 - }
2.1120 - _heap_cross_ref = &crossRef;
2.1121 - if (local_heap) {
2.1122 - delete _heap;
2.1123 - local_heap=false;
2.1124 - }
2.1125 - _heap = &heap;
2.1126 - return *this;
2.1127 - }
2.1128 -
2.1129 - /// \brief Sets the aux graph.
2.1130 - ///
2.1131 - /// Sets the aux graph used by algorithm.
2.1132 - /// If you don't use this function before calling \ref run(),
2.1133 - /// it will allocate one. The destuctor deallocates this
2.1134 - /// automatically allocated graph, of course.
2.1135 - /// \return <tt> (*this) </tt>
2.1136 - MinCut &auxGraph(AuxGraph& aux_graph)
2.1137 - {
2.1138 - if(local_aux_graph) {
2.1139 - delete _aux_graph;
2.1140 - local_aux_graph=false;
2.1141 - }
2.1142 - _aux_graph = &aux_graph;
2.1143 - return *this;
2.1144 - }
2.1145 -
2.1146 - /// \brief Sets the aux capacity map.
2.1147 - ///
2.1148 - /// Sets the aux capacity map used by algorithm.
2.1149 - /// If you don't use this function before calling \ref run(),
2.1150 - /// it will allocate one. The destuctor deallocates this
2.1151 - /// automatically allocated graph, of course.
2.1152 - /// \return <tt> (*this) </tt>
2.1153 - MinCut &auxCapacityMap(AuxCapacityMap& aux_capacity_map)
2.1154 - {
2.1155 - if(local_aux_capacity) {
2.1156 - delete _aux_capacity;
2.1157 - local_aux_capacity=false;
2.1158 - }
2.1159 - _aux_capacity = &aux_capacity_map;
2.1160 - return *this;
2.1161 - }
2.1162 -
2.1163 - /// \name Execution control
2.1164 - /// The simplest way to execute the algorithm is to use
2.1165 - /// one of the member functions called \c run().
2.1166 - /// \n
2.1167 - /// If you need more control on the execution,
2.1168 - /// first you must call \ref init() and then call the start()
2.1169 - /// or proper times the processNextPhase() member functions.
2.1170 -
2.1171 - ///@{
2.1172 -
2.1173 - /// \brief Initializes the internal data structures.
2.1174 - ///
2.1175 - /// Initializes the internal data structures.
2.1176 - void init() {
2.1177 - create_structures();
2.1178 - _first_node = _last_node = INVALID;
2.1179 - _node_num = countNodes(*_graph);
2.1180 - }
2.1181 -
2.1182 - /// \brief Processes the next phase
2.1183 - ///
2.1184 - /// Processes the next phase in the algorithm. The function
2.1185 - /// should be called countNodes(graph) - 1 times to get
2.1186 - /// surely the min cut in the graph. The
2.1187 - ///
2.1188 - ///\return %True when the algorithm finished.
2.1189 - bool processNextPhase() {
2.1190 - if (_node_num <= 1) return true;
2.1191 - using namespace _min_cut_bits;
2.1192 -
2.1193 - typedef typename AuxGraph::Node Node;
2.1194 - typedef typename AuxGraph::NodeIt NodeIt;
2.1195 - typedef typename AuxGraph::UEdge UEdge;
2.1196 - typedef typename AuxGraph::IncEdgeIt IncEdgeIt;
2.1197 -
2.1198 - typedef typename MaxCardinalitySearch<AuxGraph, AuxCapacityMap>::
2.1199 - template DefHeap<Heap, HeapCrossRef>::
2.1200 - template DefCardinalityMap<NullMap<Node, Value> >::
2.1201 - template DefProcessedMap<LastTwoMap<Node> >::
2.1202 - Create MaxCardinalitySearch;
2.1203 -
2.1204 - MaxCardinalitySearch mcs(*_aux_graph, *_aux_capacity);
2.1205 - for (NodeIt it(*_aux_graph); it != INVALID; ++it) {
2.1206 - _heap_cross_ref->set(it, Heap::PRE_HEAP);
2.1207 - }
2.1208 - mcs.heap(*_heap, *_heap_cross_ref);
2.1209 -
2.1210 - LastTwoMap<Node> last_two_nodes(_node_num);
2.1211 - mcs.processedMap(last_two_nodes);
2.1212 -
2.1213 - NullMap<Node, Value> cardinality;
2.1214 - mcs.cardinalityMap(cardinality);
2.1215 -
2.1216 - mcs.run();
2.1217 -
2.1218 - Node new_node = _aux_graph->addNode();
2.1219 -
2.1220 - typename AuxGraph::template NodeMap<UEdge> edges(*_aux_graph, INVALID);
2.1221 -
2.1222 - Node first_node = last_two_nodes[0];
2.1223 - Node second_node = last_two_nodes[1];
2.1224 -
2.1225 - _next->set((*_last)[first_node], (*_first)[second_node]);
2.1226 - _first->set(new_node, (*_first)[first_node]);
2.1227 - _last->set(new_node, (*_last)[second_node]);
2.1228 -
2.1229 - Value current_cut = 0;
2.1230 - for (IncEdgeIt it(*_aux_graph, first_node); it != INVALID; ++it) {
2.1231 - Node node = _aux_graph->runningNode(it);
2.1232 - current_cut += (*_aux_capacity)[it];
2.1233 - if (node == second_node) continue;
2.1234 - if (edges[node] == INVALID) {
2.1235 - edges[node] = _aux_graph->addEdge(new_node, node);
2.1236 - (*_aux_capacity)[edges[node]] = (*_aux_capacity)[it];
2.1237 - } else {
2.1238 - (*_aux_capacity)[edges[node]] += (*_aux_capacity)[it];
2.1239 - }
2.1240 - }
2.1241 -
2.1242 - if (_first_node == INVALID || current_cut < _min_cut) {
2.1243 - _first_node = (*_first)[first_node];
2.1244 - _last_node = (*_last)[first_node];
2.1245 - _min_cut = current_cut;
2.1246 - }
2.1247 -
2.1248 - _aux_graph->erase(first_node);
2.1249 -
2.1250 - for (IncEdgeIt it(*_aux_graph, second_node); it != INVALID; ++it) {
2.1251 - Node node = _aux_graph->runningNode(it);
2.1252 - if (edges[node] == INVALID) {
2.1253 - edges[node] = _aux_graph->addEdge(new_node, node);
2.1254 - (*_aux_capacity)[edges[node]] = (*_aux_capacity)[it];
2.1255 - } else {
2.1256 - (*_aux_capacity)[edges[node]] += (*_aux_capacity)[it];
2.1257 - }
2.1258 - }
2.1259 - _aux_graph->erase(second_node);
2.1260 -
2.1261 - --_node_num;
2.1262 - return _node_num == 1;
2.1263 - }
2.1264 -
2.1265 - /// \brief Executes the algorithm.
2.1266 - ///
2.1267 - /// Executes the algorithm.
2.1268 - ///
2.1269 - /// \pre init() must be called
2.1270 - void start() {
2.1271 - while (!processNextPhase());
2.1272 - }
2.1273 -
2.1274 -
2.1275 - /// \brief Runs %MinCut algorithm.
2.1276 - ///
2.1277 - /// This method runs the %Min cut algorithm
2.1278 - ///
2.1279 - /// \note mc.run(s) is just a shortcut of the following code.
2.1280 - ///\code
2.1281 - /// mc.init();
2.1282 - /// mc.start();
2.1283 - ///\endcode
2.1284 - void run() {
2.1285 - init();
2.1286 - start();
2.1287 - }
2.1288 -
2.1289 - ///@}
2.1290 -
2.1291 - /// \name Query Functions
2.1292 - /// The result of the %MinCut algorithm can be obtained using these
2.1293 - /// functions.\n
2.1294 - /// Before the use of these functions,
2.1295 - /// either run() or start() must be called.
2.1296 -
2.1297 - ///@{
2.1298 -
2.1299 - /// \brief Returns the min cut value.
2.1300 - ///
2.1301 - /// Returns the min cut value if the algorithm finished.
2.1302 - /// After the first processNextPhase() it is a value of a
2.1303 - /// valid cut in the graph.
2.1304 - Value minCut() const {
2.1305 - return _min_cut;
2.1306 - }
2.1307 -
2.1308 - /// \brief Returns a min cut in a NodeMap.
2.1309 - ///
2.1310 - /// It sets the nodes of one of the two partitions to true in
2.1311 - /// the given BoolNodeMap. The map contains a valid cut if the
2.1312 - /// map have been set false previously.
2.1313 - template <typename NodeMap>
2.1314 - Value quickMinCut(NodeMap& nodeMap) const {
2.1315 - for (typename Graph::Node it = _first_node;
2.1316 - it != _last_node; it = (*_next)[it]) {
2.1317 - nodeMap.set(it, true);
2.1318 - }
2.1319 - nodeMap.set(_last_node, true);
2.1320 - return minCut();
2.1321 - }
2.1322 -
2.1323 - /// \brief Returns a min cut in a NodeMap.
2.1324 - ///
2.1325 - /// It sets the nodes of one of the two partitions to true and
2.1326 - /// the other partition to false. The function first set all of the
2.1327 - /// nodes to false and after it call the quickMinCut() member.
2.1328 - template <typename NodeMap>
2.1329 - Value minCut(NodeMap& nodeMap) const {
2.1330 - for (typename Graph::NodeIt it(*_graph); it != INVALID; ++it) {
2.1331 - nodeMap.set(it, false);
2.1332 - }
2.1333 - quickMinCut(nodeMap);
2.1334 - return minCut();
2.1335 - }
2.1336 -
2.1337 - /// \brief Returns a min cut in an EdgeMap.
2.1338 - ///
2.1339 - /// If an undirected edge is in a min cut then it will be
2.1340 - /// set to true and the others will be set to false in the given map.
2.1341 - template <typename EdgeMap>
2.1342 - Value cutEdges(EdgeMap& edgeMap) const {
2.1343 - typename Graph::template NodeMap<bool> cut(*_graph, false);
2.1344 - quickMinCut(cut);
2.1345 - for (typename Graph::EdgeIt it(*_graph); it != INVALID; ++it) {
2.1346 - edgeMap.set(it, cut[_graph->source(it)] ^ cut[_graph->target(it)]);
2.1347 - }
2.1348 - return minCut();
2.1349 - }
2.1350 -
2.1351 - ///@}
2.1352 -
2.1353 - };
2.1354 -}
2.1355 -
2.1356 -#endif
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/lemon/nagamochi_ibaraki.h Tue Oct 31 14:30:54 2006 +0000
3.3 @@ -0,0 +1,1361 @@
3.4 +/* -*- C++ -*-
3.5 + * lemon/min_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_MIN_CUT_H
3.21 +#define LEMON_MIN_CUT_H
3.22 +
3.23 +
3.24 +/// \ingroup topology
3.25 +/// \file
3.26 +/// \brief Maximum cardinality search and min cut in undirected graphs.
3.27 +
3.28 +#include <lemon/list_graph.h>
3.29 +#include <lemon/bin_heap.h>
3.30 +#include <lemon/bucket_heap.h>
3.31 +
3.32 +#include <lemon/bits/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 _min_cut_bits {
3.41 +
3.42 + template <typename CapacityMap>
3.43 + struct HeapSelector {
3.44 + template <typename Value, typename Ref>
3.45 + struct Selector {
3.46 + typedef BinHeap<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 Value, typename Ref>
3.53 + struct Selector {
3.54 + typedef BucketHeap<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 concepts::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 BucketHeap.
3.101 + ///
3.102 + /// \sa MaxCardinalitySearch
3.103 + typedef typename _min_cut_bits
3.104 + ::HeapSelector<CapacityMap>
3.105 + ::template Selector<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 concepts::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 graph 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 concepts::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 it chooses the node which is 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 node 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 concepts::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 + /// concepts::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 + /// concepts::Graph::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* what() const throw() {
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 NagamochiIbaraki class.
3.695 + ///
3.696 + /// Default traits class of NagamochiIbaraki 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 NagamochiIbarakiDefaultTraits {
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 AuxGraph type which is an Graph
3.708 + typedef ListUGraph AuxGraph;
3.709 +
3.710 + /// \brief Instantiates a AuxGraph.
3.711 + ///
3.712 + /// This function instantiates a \ref AuxGraph.
3.713 + static AuxGraph *createAuxGraph() {
3.714 + return new AuxGraph();
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 concepts::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 AuxCapacityMap type
3.736 + ///
3.737 + /// The type of the map that stores the auxing edge capacities.
3.738 + typedef AuxGraph::UEdgeMap<Value> AuxCapacityMap;
3.739 +
3.740 + /// \brief Instantiates a AuxCapacityMap.
3.741 + ///
3.742 + /// This function instantiates a \ref AuxCapacityMap.
3.743 + static AuxCapacityMap *createAuxCapacityMap(const AuxGraph& graph) {
3.744 + return new AuxCapacityMap(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 AuxGraph::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 AuxGraph &graph) {
3.759 + return new HeapCrossRef(graph);
3.760 + }
3.761 +
3.762 + /// \brief The heap type used by NagamochiIbaraki algorithm.
3.763 + ///
3.764 + /// The heap type used by NagamochiIbaraki algorithm. It should
3.765 + /// maximalize the priorities and the heap's key type is
3.766 + /// the aux graph's node.
3.767 + ///
3.768 + /// \sa BinHeap
3.769 + /// \sa NagamochiIbaraki
3.770 + typedef typename _min_cut_bits
3.771 + ::HeapSelector<CapacityMap>
3.772 + ::template Selector<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 AuxGraph's node type to the Graph's node type.
3.784 + ///
3.785 + /// Map from the AuxGraph's node type to the Graph's node type.
3.786 + typedef typename AuxGraph
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 AuxGraph& 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 _min_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 with the
3.839 + /// Nagamochi-Ibaraki algorithm. The algorithm separates the graph's
3.840 + /// nodes into two partitions with the minimum sum of edge capacities
3.841 + /// between the two partitions. The algorithm can be used to test
3.842 + /// the network reliability specifically to test how many links have
3.843 + /// to be destroyed in the network to split it at least two
3.844 + /// distinict subnetwork.
3.845 + ///
3.846 + /// The complexity of the algorithm is \f$ O(ne\log(n)) \f$ but with
3.847 + /// Fibonacci heap it can be decreased to \f$ O(ne+n^2\log(n))
3.848 + /// \f$. When capacity map is neutral then it uses BucketHeap which
3.849 + /// results \f$ O(ne) \f$ time complexity.
3.850 +#ifdef DOXYGEN
3.851 + template <typename _Graph, typename _CapacityMap, typename _Traits>
3.852 +#else
3.853 + template <typename _Graph = ListUGraph,
3.854 + typename _CapacityMap = typename _Graph::template UEdgeMap<int>,
3.855 + typename _Traits
3.856 + = NagamochiIbarakiDefaultTraits<_Graph, _CapacityMap> >
3.857 +#endif
3.858 + class NagamochiIbaraki {
3.859 + public:
3.860 + /// \brief \ref Exception for uninitialized parameters.
3.861 + ///
3.862 + /// This error represents problems in the initialization
3.863 + /// of the parameters of the algorithms.
3.864 + class UninitializedParameter : public lemon::UninitializedParameter {
3.865 + public:
3.866 + virtual const char* what() const throw() {
3.867 + return "lemon::NagamochiIbaraki::UninitializedParameter";
3.868 + }
3.869 + };
3.870 +
3.871 +
3.872 + private:
3.873 +
3.874 + typedef _Traits Traits;
3.875 + /// The type of the underlying graph.
3.876 + typedef typename Traits::Graph Graph;
3.877 +
3.878 + /// The type of the capacity of the edges.
3.879 + typedef typename Traits::CapacityMap::Value Value;
3.880 + /// The type of the map that stores the edge capacities.
3.881 + typedef typename Traits::CapacityMap CapacityMap;
3.882 + /// The type of the aux graph
3.883 + typedef typename Traits::AuxGraph AuxGraph;
3.884 + /// The type of the aux capacity map
3.885 + typedef typename Traits::AuxCapacityMap AuxCapacityMap;
3.886 + /// The cross reference type used for the current heap.
3.887 + typedef typename Traits::HeapCrossRef HeapCrossRef;
3.888 + /// The heap type used by the max cardinality algorithm.
3.889 + typedef typename Traits::Heap Heap;
3.890 + /// The node refrefernces between the original and aux graph type.
3.891 + typedef typename Traits::NodeRefMap NodeRefMap;
3.892 + /// The list node refrefernces in the original graph type.
3.893 + typedef typename Traits::ListRefMap ListRefMap;
3.894 +
3.895 + public:
3.896 +
3.897 + ///\name Named template parameters
3.898 +
3.899 + ///@{
3.900 +
3.901 + struct DefNeutralCapacityTraits : public Traits {
3.902 + typedef ConstMap<typename Graph::UEdge, Const<int, 1> > CapacityMap;
3.903 + static CapacityMap *createCapacityMap(const Graph&) {
3.904 + return new CapacityMap();
3.905 + }
3.906 + };
3.907 + /// \brief \ref named-templ-param "Named parameter" for setting
3.908 + /// the capacity type to constMap<UEdge, int, 1>()
3.909 + ///
3.910 + /// \ref named-templ-param "Named parameter" for setting
3.911 + /// the capacity type to constMap<UEdge, int, 1>()
3.912 + struct DefNeutralCapacity
3.913 + : public NagamochiIbaraki<Graph, CapacityMap,
3.914 + DefNeutralCapacityTraits> {
3.915 + typedef NagamochiIbaraki<Graph, CapacityMap,
3.916 + DefNeutralCapacityTraits> Create;
3.917 + };
3.918 +
3.919 +
3.920 + template <class H, class CR>
3.921 + struct DefHeapTraits : public Traits {
3.922 + typedef CR HeapCrossRef;
3.923 + typedef H Heap;
3.924 + static HeapCrossRef *createHeapCrossRef(const AuxGraph &) {
3.925 + throw UninitializedParameter();
3.926 + }
3.927 + static Heap *createHeap(HeapCrossRef &) {
3.928 + throw UninitializedParameter();
3.929 + }
3.930 + };
3.931 + /// \brief \ref named-templ-param "Named parameter" for setting heap
3.932 + /// and cross reference type
3.933 + ///
3.934 + /// \ref named-templ-param "Named parameter" for setting heap and cross
3.935 + /// reference type
3.936 + template <class H, class CR = typename Graph::template NodeMap<int> >
3.937 + struct DefHeap
3.938 + : public NagamochiIbaraki<Graph, CapacityMap,
3.939 + DefHeapTraits<H, CR> > {
3.940 + typedef NagamochiIbaraki< Graph, CapacityMap,
3.941 + DefHeapTraits<H, CR> > Create;
3.942 + };
3.943 +
3.944 + template <class H, class CR>
3.945 + struct DefStandardHeapTraits : public Traits {
3.946 + typedef CR HeapCrossRef;
3.947 + typedef H Heap;
3.948 + static HeapCrossRef *createHeapCrossRef(const AuxGraph &graph) {
3.949 + return new HeapCrossRef(graph);
3.950 + }
3.951 + static Heap *createHeap(HeapCrossRef &crossref) {
3.952 + return new Heap(crossref);
3.953 + }
3.954 + };
3.955 +
3.956 + /// \brief \ref named-templ-param "Named parameter" for setting heap and
3.957 + /// cross reference type with automatic allocation
3.958 + ///
3.959 + /// \ref named-templ-param "Named parameter" for setting heap and cross
3.960 + /// reference type. It can allocate the heap and the cross reference
3.961 + /// object if the cross reference's constructor waits for the graph as
3.962 + /// parameter and the heap's constructor waits for the cross reference.
3.963 + template <class H, class CR = typename Graph::template NodeMap<int> >
3.964 + struct DefStandardHeap
3.965 + : public NagamochiIbaraki<Graph, CapacityMap,
3.966 + DefStandardHeapTraits<H, CR> > {
3.967 + typedef NagamochiIbaraki<Graph, CapacityMap,
3.968 + DefStandardHeapTraits<H, CR> >
3.969 + Create;
3.970 + };
3.971 +
3.972 + ///@}
3.973 +
3.974 +
3.975 + private:
3.976 + /// Pointer to the underlying graph.
3.977 + const Graph *_graph;
3.978 + /// Pointer to the capacity map
3.979 + const CapacityMap *_capacity;
3.980 + /// \brief Indicates if \ref _capacity is locally allocated
3.981 + /// (\c true) or not.
3.982 + bool local_capacity;
3.983 +
3.984 + /// Pointer to the aux graph.
3.985 + AuxGraph *_aux_graph;
3.986 + /// \brief Indicates if \ref _aux_graph is locally allocated
3.987 + /// (\c true) or not.
3.988 + bool local_aux_graph;
3.989 + /// Pointer to the aux capacity map
3.990 + AuxCapacityMap *_aux_capacity;
3.991 + /// \brief Indicates if \ref _aux_capacity is locally allocated
3.992 + /// (\c true) or not.
3.993 + bool local_aux_capacity;
3.994 + /// Pointer to the heap cross references.
3.995 + HeapCrossRef *_heap_cross_ref;
3.996 + /// \brief Indicates if \ref _heap_cross_ref is locally allocated
3.997 + /// (\c true) or not.
3.998 + bool local_heap_cross_ref;
3.999 + /// Pointer to the heap.
3.1000 + Heap *_heap;
3.1001 + /// Indicates if \ref _heap is locally allocated (\c true) or not.
3.1002 + bool local_heap;
3.1003 +
3.1004 + /// The min cut value.
3.1005 + Value _min_cut;
3.1006 + /// The number of the nodes of the aux graph.
3.1007 + int _node_num;
3.1008 + /// The first and last node of the min cut in the next list;
3.1009 + typename Graph::Node _first_node, _last_node;
3.1010 +
3.1011 + /// \brief The first and last element in the list associated
3.1012 + /// to the aux graph node.
3.1013 + NodeRefMap *_first, *_last;
3.1014 + /// \brief The next node in the node lists.
3.1015 + ListRefMap *_next;
3.1016 +
3.1017 + void create_structures() {
3.1018 + if (!_capacity) {
3.1019 + local_capacity = true;
3.1020 + _capacity = Traits::createCapacityMap(*_graph);
3.1021 + }
3.1022 + if(!_aux_graph) {
3.1023 + local_aux_graph = true;
3.1024 + _aux_graph = Traits::createAuxGraph();
3.1025 + }
3.1026 + if(!_aux_capacity) {
3.1027 + local_aux_capacity = true;
3.1028 + _aux_capacity = Traits::createAuxCapacityMap(*_aux_graph);
3.1029 + }
3.1030 +
3.1031 + _first = Traits::createNodeRefMap(*_aux_graph);
3.1032 + _last = Traits::createNodeRefMap(*_aux_graph);
3.1033 +
3.1034 + _next = Traits::createListRefMap(*_graph);
3.1035 +
3.1036 + typename Graph::template NodeMap<typename AuxGraph::Node> ref(*_graph);
3.1037 +
3.1038 + for (typename Graph::NodeIt it(*_graph); it != INVALID; ++it) {
3.1039 + _next->set(it, INVALID);
3.1040 + typename AuxGraph::Node node = _aux_graph->addNode();
3.1041 + _first->set(node, it);
3.1042 + _last->set(node, it);
3.1043 + ref.set(it, node);
3.1044 + }
3.1045 +
3.1046 + for (typename Graph::UEdgeIt it(*_graph); it != INVALID; ++it) {
3.1047 + if (_graph->source(it) == _graph->target(it)) continue;
3.1048 + typename AuxGraph::UEdge uedge =
3.1049 + _aux_graph->addEdge(ref[_graph->source(it)],
3.1050 + ref[_graph->target(it)]);
3.1051 + _aux_capacity->set(uedge, (*_capacity)[it]);
3.1052 +
3.1053 + }
3.1054 +
3.1055 + if (!_heap_cross_ref) {
3.1056 + local_heap_cross_ref = true;
3.1057 + _heap_cross_ref = Traits::createHeapCrossRef(*_aux_graph);
3.1058 + }
3.1059 + if (!_heap) {
3.1060 + local_heap = true;
3.1061 + _heap = Traits::createHeap(*_heap_cross_ref);
3.1062 + }
3.1063 + }
3.1064 +
3.1065 + public :
3.1066 +
3.1067 + typedef NagamochiIbaraki Create;
3.1068 +
3.1069 +
3.1070 + /// \brief Constructor.
3.1071 + ///
3.1072 + ///\param graph the graph the algorithm will run on.
3.1073 + ///\param capacity the capacity map used by the algorithm.
3.1074 + NagamochiIbaraki(const Graph& graph, const CapacityMap& capacity)
3.1075 + : _graph(&graph),
3.1076 + _capacity(&capacity), local_capacity(false),
3.1077 + _aux_graph(0), local_aux_graph(false),
3.1078 + _aux_capacity(0), local_aux_capacity(false),
3.1079 + _heap_cross_ref(0), local_heap_cross_ref(false),
3.1080 + _heap(0), local_heap(false),
3.1081 + _first(0), _last(0), _next(0) {}
3.1082 +
3.1083 + /// \brief Constructor.
3.1084 + ///
3.1085 + /// This constructor can be used only when the Traits class
3.1086 + /// defines how can we instantiate a local capacity map.
3.1087 + /// If the DefNeutralCapacity used the algorithm automatically
3.1088 + /// construct the capacity map.
3.1089 + ///
3.1090 + ///\param graph the graph the algorithm will run on.
3.1091 + NagamochiIbaraki(const Graph& graph)
3.1092 + : _graph(&graph),
3.1093 + _capacity(0), local_capacity(false),
3.1094 + _aux_graph(0), local_aux_graph(false),
3.1095 + _aux_capacity(0), local_aux_capacity(false),
3.1096 + _heap_cross_ref(0), local_heap_cross_ref(false),
3.1097 + _heap(0), local_heap(false),
3.1098 + _first(0), _last(0), _next(0) {}
3.1099 +
3.1100 + /// \brief Destructor.
3.1101 + ///
3.1102 + /// Destructor.
3.1103 + ~NagamochiIbaraki() {
3.1104 + if (local_heap) delete _heap;
3.1105 + if (local_heap_cross_ref) delete _heap_cross_ref;
3.1106 + if (_first) delete _first;
3.1107 + if (_last) delete _last;
3.1108 + if (_next) delete _next;
3.1109 + if (local_aux_capacity) delete _aux_capacity;
3.1110 + if (local_aux_graph) delete _aux_graph;
3.1111 + if (local_capacity) delete _capacity;
3.1112 + }
3.1113 +
3.1114 + /// \brief Sets the heap and the cross reference used by algorithm.
3.1115 + ///
3.1116 + /// Sets the heap and the cross reference used by algorithm.
3.1117 + /// If you don't use this function before calling \ref run(),
3.1118 + /// it will allocate one. The destuctor deallocates this
3.1119 + /// automatically allocated heap and cross reference, of course.
3.1120 + /// \return <tt> (*this) </tt>
3.1121 + NagamochiIbaraki &heap(Heap& heap, HeapCrossRef &crossRef)
3.1122 + {
3.1123 + if (local_heap_cross_ref) {
3.1124 + delete _heap_cross_ref;
3.1125 + local_heap_cross_ref=false;
3.1126 + }
3.1127 + _heap_cross_ref = &crossRef;
3.1128 + if (local_heap) {
3.1129 + delete _heap;
3.1130 + local_heap=false;
3.1131 + }
3.1132 + _heap = &heap;
3.1133 + return *this;
3.1134 + }
3.1135 +
3.1136 + /// \brief Sets the aux graph.
3.1137 + ///
3.1138 + /// Sets the aux graph used by algorithm.
3.1139 + /// If you don't use this function before calling \ref run(),
3.1140 + /// it will allocate one. The destuctor deallocates this
3.1141 + /// automatically allocated graph, of course.
3.1142 + /// \return <tt> (*this) </tt>
3.1143 + NagamochiIbaraki &auxGraph(AuxGraph& aux_graph)
3.1144 + {
3.1145 + if(local_aux_graph) {
3.1146 + delete _aux_graph;
3.1147 + local_aux_graph=false;
3.1148 + }
3.1149 + _aux_graph = &aux_graph;
3.1150 + return *this;
3.1151 + }
3.1152 +
3.1153 + /// \brief Sets the aux capacity map.
3.1154 + ///
3.1155 + /// Sets the aux capacity map used by algorithm.
3.1156 + /// If you don't use this function before calling \ref run(),
3.1157 + /// it will allocate one. The destuctor deallocates this
3.1158 + /// automatically allocated graph, of course.
3.1159 + /// \return <tt> (*this) </tt>
3.1160 + NagamochiIbaraki &auxCapacityMap(AuxCapacityMap& aux_capacity_map)
3.1161 + {
3.1162 + if(local_aux_capacity) {
3.1163 + delete _aux_capacity;
3.1164 + local_aux_capacity=false;
3.1165 + }
3.1166 + _aux_capacity = &aux_capacity_map;
3.1167 + return *this;
3.1168 + }
3.1169 +
3.1170 + /// \name Execution control
3.1171 + /// The simplest way to execute the algorithm is to use
3.1172 + /// one of the member functions called \c run().
3.1173 + /// \n
3.1174 + /// If you need more control on the execution,
3.1175 + /// first you must call \ref init() and then call the start()
3.1176 + /// or proper times the processNextPhase() member functions.
3.1177 +
3.1178 + ///@{
3.1179 +
3.1180 + /// \brief Initializes the internal data structures.
3.1181 + ///
3.1182 + /// Initializes the internal data structures.
3.1183 + void init() {
3.1184 + create_structures();
3.1185 + _first_node = _last_node = INVALID;
3.1186 + _node_num = countNodes(*_graph);
3.1187 + }
3.1188 +
3.1189 + /// \brief Processes the next phase
3.1190 + ///
3.1191 + /// Processes the next phase in the algorithm. The function
3.1192 + /// should be called countNodes(graph) - 1 times to get
3.1193 + /// surely the min cut in the graph. The
3.1194 + ///
3.1195 + ///\return %True when the algorithm finished.
3.1196 + bool processNextPhase() {
3.1197 + if (_node_num <= 1) return true;
3.1198 + using namespace _min_cut_bits;
3.1199 +
3.1200 + typedef typename AuxGraph::Node Node;
3.1201 + typedef typename AuxGraph::NodeIt NodeIt;
3.1202 + typedef typename AuxGraph::UEdge UEdge;
3.1203 + typedef typename AuxGraph::IncEdgeIt IncEdgeIt;
3.1204 +
3.1205 + typedef typename MaxCardinalitySearch<AuxGraph, AuxCapacityMap>::
3.1206 + template DefHeap<Heap, HeapCrossRef>::
3.1207 + template DefCardinalityMap<NullMap<Node, Value> >::
3.1208 + template DefProcessedMap<LastTwoMap<Node> >::
3.1209 + Create MaxCardinalitySearch;
3.1210 +
3.1211 + MaxCardinalitySearch mcs(*_aux_graph, *_aux_capacity);
3.1212 + for (NodeIt it(*_aux_graph); it != INVALID; ++it) {
3.1213 + _heap_cross_ref->set(it, Heap::PRE_HEAP);
3.1214 + }
3.1215 + mcs.heap(*_heap, *_heap_cross_ref);
3.1216 +
3.1217 + LastTwoMap<Node> last_two_nodes(_node_num);
3.1218 + mcs.processedMap(last_two_nodes);
3.1219 +
3.1220 + NullMap<Node, Value> cardinality;
3.1221 + mcs.cardinalityMap(cardinality);
3.1222 +
3.1223 + mcs.run();
3.1224 +
3.1225 + Node new_node = _aux_graph->addNode();
3.1226 +
3.1227 + typename AuxGraph::template NodeMap<UEdge> edges(*_aux_graph, INVALID);
3.1228 +
3.1229 + Node first_node = last_two_nodes[0];
3.1230 + Node second_node = last_two_nodes[1];
3.1231 +
3.1232 + _next->set((*_last)[first_node], (*_first)[second_node]);
3.1233 + _first->set(new_node, (*_first)[first_node]);
3.1234 + _last->set(new_node, (*_last)[second_node]);
3.1235 +
3.1236 + Value current_cut = 0;
3.1237 + for (IncEdgeIt it(*_aux_graph, first_node); it != INVALID; ++it) {
3.1238 + Node node = _aux_graph->runningNode(it);
3.1239 + current_cut += (*_aux_capacity)[it];
3.1240 + if (node == second_node) continue;
3.1241 + if (edges[node] == INVALID) {
3.1242 + edges[node] = _aux_graph->addEdge(new_node, node);
3.1243 + (*_aux_capacity)[edges[node]] = (*_aux_capacity)[it];
3.1244 + } else {
3.1245 + (*_aux_capacity)[edges[node]] += (*_aux_capacity)[it];
3.1246 + }
3.1247 + }
3.1248 +
3.1249 + if (_first_node == INVALID || current_cut < _min_cut) {
3.1250 + _first_node = (*_first)[first_node];
3.1251 + _last_node = (*_last)[first_node];
3.1252 + _min_cut = current_cut;
3.1253 + }
3.1254 +
3.1255 + _aux_graph->erase(first_node);
3.1256 +
3.1257 + for (IncEdgeIt it(*_aux_graph, second_node); it != INVALID; ++it) {
3.1258 + Node node = _aux_graph->runningNode(it);
3.1259 + if (edges[node] == INVALID) {
3.1260 + edges[node] = _aux_graph->addEdge(new_node, node);
3.1261 + (*_aux_capacity)[edges[node]] = (*_aux_capacity)[it];
3.1262 + } else {
3.1263 + (*_aux_capacity)[edges[node]] += (*_aux_capacity)[it];
3.1264 + }
3.1265 + }
3.1266 + _aux_graph->erase(second_node);
3.1267 +
3.1268 + --_node_num;
3.1269 + return _node_num == 1;
3.1270 + }
3.1271 +
3.1272 + /// \brief Executes the algorithm.
3.1273 + ///
3.1274 + /// Executes the algorithm.
3.1275 + ///
3.1276 + /// \pre init() must be called
3.1277 + void start() {
3.1278 + while (!processNextPhase());
3.1279 + }
3.1280 +
3.1281 +
3.1282 + /// \brief Runs %NagamochiIbaraki algorithm.
3.1283 + ///
3.1284 + /// This method runs the %Min cut algorithm
3.1285 + ///
3.1286 + /// \note mc.run(s) is just a shortcut of the following code.
3.1287 + ///\code
3.1288 + /// mc.init();
3.1289 + /// mc.start();
3.1290 + ///\endcode
3.1291 + void run() {
3.1292 + init();
3.1293 + start();
3.1294 + }
3.1295 +
3.1296 + ///@}
3.1297 +
3.1298 + /// \name Query Functions
3.1299 + ///
3.1300 + /// The result of the %NagamochiIbaraki
3.1301 + /// algorithm can be obtained using these functions.\n
3.1302 + /// Before the use of these functions, either run() or start()
3.1303 + /// must be called.
3.1304 +
3.1305 + ///@{
3.1306 +
3.1307 + /// \brief Returns the min cut value.
3.1308 + ///
3.1309 + /// Returns the min cut value if the algorithm finished.
3.1310 + /// After the first processNextPhase() it is a value of a
3.1311 + /// valid cut in the graph.
3.1312 + Value minCut() const {
3.1313 + return _min_cut;
3.1314 + }
3.1315 +
3.1316 + /// \brief Returns a min cut in a NodeMap.
3.1317 + ///
3.1318 + /// It sets the nodes of one of the two partitions to true in
3.1319 + /// the given BoolNodeMap. The map contains a valid cut if the
3.1320 + /// map have been set false previously.
3.1321 + template <typename NodeMap>
3.1322 + Value quickMinCut(NodeMap& nodeMap) const {
3.1323 + for (typename Graph::Node it = _first_node;
3.1324 + it != _last_node; it = (*_next)[it]) {
3.1325 + nodeMap.set(it, true);
3.1326 + }
3.1327 + nodeMap.set(_last_node, true);
3.1328 + return minCut();
3.1329 + }
3.1330 +
3.1331 + /// \brief Returns a min cut in a NodeMap.
3.1332 + ///
3.1333 + /// It sets the nodes of one of the two partitions to true and
3.1334 + /// the other partition to false. The function first set all of the
3.1335 + /// nodes to false and after it call the quickMinCut() member.
3.1336 + template <typename NodeMap>
3.1337 + Value minCut(NodeMap& nodeMap) const {
3.1338 + for (typename Graph::NodeIt it(*_graph); it != INVALID; ++it) {
3.1339 + nodeMap.set(it, false);
3.1340 + }
3.1341 + quickMinCut(nodeMap);
3.1342 + return minCut();
3.1343 + }
3.1344 +
3.1345 + /// \brief Returns a min cut in an EdgeMap.
3.1346 + ///
3.1347 + /// If an undirected edge is in a min cut then it will be
3.1348 + /// set to true and the others will be set to false in the given map.
3.1349 + template <typename EdgeMap>
3.1350 + Value cutEdges(EdgeMap& edgeMap) const {
3.1351 + typename Graph::template NodeMap<bool> cut(*_graph, false);
3.1352 + quickMinCut(cut);
3.1353 + for (typename Graph::EdgeIt it(*_graph); it != INVALID; ++it) {
3.1354 + edgeMap.set(it, cut[_graph->source(it)] ^ cut[_graph->target(it)]);
3.1355 + }
3.1356 + return minCut();
3.1357 + }
3.1358 +
3.1359 + ///@}
3.1360 +
3.1361 + };
3.1362 +}
3.1363 +
3.1364 +#endif