diff -r 5d81ba873b90 -r 78e6e2d1fd96 lemon/minimal_cut.h --- a/lemon/minimal_cut.h Mon Feb 13 09:42:53 2006 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,1351 +0,0 @@ -/* -*- C++ -*- - * lemon/minimal_cut.h - Part of LEMON, a generic C++ optimization library - * - * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport - * (Egervary Research Group on Combinatorial Optimization, EGRES). - * - * Permission to use, modify and distribute this software is granted - * provided that this copyright notice appears in all copies. For - * precise terms see the accompanying LICENSE file. - * - * This software is provided "AS IS" with no warranty of any kind, - * express or implied, and with no claim as to its suitability for any - * purpose. - * - */ - -#ifndef LEMON_MINIMAL_CUT_H -#define LEMON_MINIMAL_CUT_H - - -/// \ingroup topology -/// \file -/// \brief Maximum cardinality search and minimal cut in undirected graphs. - -#include -#include -#include - -#include -#include -#include - -#include - -namespace lemon { - - namespace _minimal_cut_bits { - - template - struct HeapSelector { - template - struct Selector { - typedef BinHeap > Heap; - }; - }; - - template - struct HeapSelector > > { - template - struct Selector { - typedef LinearHeap Heap; - }; - }; - - } - - /// \brief Default traits class of MaxCardinalitySearch class. - /// - /// Default traits class of MaxCardinalitySearch class. - /// \param Graph Graph type. - /// \param CapacityMap Type of length map. - template - struct MaxCardinalitySearchDefaultTraits { - /// The graph type the algorithm runs on. - typedef _Graph Graph; - - /// \brief The type of the map that stores the edge capacities. - /// - /// The type of the map that stores the edge capacities. - /// It must meet the \ref concept::ReadMap "ReadMap" concept. - typedef _CapacityMap CapacityMap; - - /// \brief The type of the capacity of the edges. - typedef typename CapacityMap::Value Value; - - /// \brief The cross reference type used by heap. - /// - /// The cross reference type used by heap. - /// Usually it is \c Graph::NodeMap. - typedef typename Graph::template NodeMap HeapCrossRef; - - /// \brief Instantiates a HeapCrossRef. - /// - /// This function instantiates a \ref HeapCrossRef. - /// \param graph is the graph, to which we would like to define the - /// HeapCrossRef. - static HeapCrossRef *createHeapCrossRef(const Graph &graph) { - return new HeapCrossRef(graph); - } - - /// \brief The heap type used by MaxCardinalitySearch algorithm. - /// - /// The heap type used by MaxCardinalitySearch algorithm. It should - /// maximalize the priorities. The default heap type is - /// the \ref BinHeap, but it is specialized when the - /// CapacityMap is ConstMap > - /// to LinearHeap. - /// - /// \sa MaxCardinalitySearch - typedef typename _minimal_cut_bits - ::HeapSelector - ::template Selector - ::Heap Heap; - - /// \brief Instantiates a Heap. - /// - /// This function instantiates a \ref Heap. - /// \param crossref The cross reference of the heap. - static Heap *createHeap(HeapCrossRef& crossref) { - return new Heap(crossref); - } - - /// \brief The type of the map that stores whether a nodes is processed. - /// - /// The type of the map that stores whether a nodes is processed. - /// It must meet the \ref concept::WriteMap "WriteMap" concept. - /// By default it is a NullMap. - typedef NullMap ProcessedMap; - - /// \brief Instantiates a ProcessedMap. - /// - /// This function instantiates a \ref ProcessedMap. - /// \param g is the graph, to which - /// we would like to define the \ref ProcessedMap -#ifdef DOXYGEN - static ProcessedMap *createProcessedMap(const Graph &graph) -#else - static ProcessedMap *createProcessedMap(const Graph &) -#endif - { - return new ProcessedMap(); - } - - /// \brief The type of the map that stores the cardinalties of the nodes. - /// - /// The type of the map that stores the cardinalities of the nodes. - /// It must meet the \ref concept::WriteMap "WriteMap" concept. - typedef typename Graph::template NodeMap CardinalityMap; - - /// \brief Instantiates a CardinalityMap. - /// - /// This function instantiates a \ref CardinalityMap. - /// \param graph is the graph, to which we would like to define the \ref - /// CardinalityMap - static CardinalityMap *createCardinalityMap(const Graph &graph) { - return new CardinalityMap(graph); - } - - }; - - /// \ingroup topology - /// - /// \brief Maximum Cardinality Search algorithm class. - /// - /// This class provides an efficient implementation of Maximum Cardinality - /// Search algorithm. The maximum cardinality search chooses first time any - /// node of the graph. Then every time chooses that node which connected - /// to the processed nodes at most in the sum of capacities on the out - /// edges. If there is a cut in the graph the algorithm should choose - /// again any unprocessed node of the graph. Each nodes cardinality is - /// the sum of capacities on the out edges to the nodes which are processed - /// before the given node. - /// - /// The edge capacities are passed to the algorithm using a - /// \ref concept::ReadMap "ReadMap", so it is easy to change it to any - /// kind of capacity. - /// - /// The type of the capacity is determined by the \ref - /// concept::ReadMap::Value "Value" of the capacity map. - /// - /// It is also possible to change the underlying priority heap. - /// - /// - /// \param _Graph The graph type the algorithm runs on. The default value - /// is \ref ListGraph. The value of Graph is not used directly by - /// the search algorithm, it is only passed to - /// \ref MaxCardinalitySearchDefaultTraits. - /// \param _CapacityMap This read-only EdgeMap determines the capacities of - /// the edges. It is read once for each edge, so the map may involve in - /// relatively time consuming process to compute the edge capacity if - /// it is necessary. The default map type is \ref - /// concept::StaticGraph::EdgeMap "Graph::EdgeMap". The value - /// of CapacityMap is not used directly by search algorithm, it is only - /// passed to \ref MaxCardinalitySearchDefaultTraits. - /// \param _Traits Traits class to set various data types used by the - /// algorithm. The default traits class is - /// \ref MaxCardinalitySearchDefaultTraits - /// "MaxCardinalitySearchDefaultTraits<_Graph, _CapacityMap>". - /// See \ref MaxCardinalitySearchDefaultTraits - /// for the documentation of a MaxCardinalitySearch traits class. - /// - /// \author Balazs Dezso - -#ifdef DOXYGEN - template -#else - template , - typename _Traits = - MaxCardinalitySearchDefaultTraits<_Graph, _CapacityMap> > -#endif - class MaxCardinalitySearch { - public: - /// \brief \ref Exception for uninitialized parameters. - /// - /// This error represents problems in the initialization - /// of the parameters of the algorithms. - class UninitializedParameter : public lemon::UninitializedParameter { - public: - virtual const char* exceptionName() const { - return "lemon::MaxCardinalitySearch::UninitializedParameter"; - } - }; - - typedef _Traits Traits; - ///The type of the underlying graph. - typedef typename Traits::Graph Graph; - - ///The type of the capacity of the edges. - typedef typename Traits::CapacityMap::Value Value; - ///The type of the map that stores the edge capacities. - typedef typename Traits::CapacityMap CapacityMap; - ///The type of the map indicating if a node is processed. - typedef typename Traits::ProcessedMap ProcessedMap; - ///The type of the map that stores the cardinalities of the nodes. - typedef typename Traits::CardinalityMap CardinalityMap; - ///The cross reference type used for the current heap. - typedef typename Traits::HeapCrossRef HeapCrossRef; - ///The heap type used by the algorithm. It maximize the priorities. - typedef typename Traits::Heap Heap; - private: - /// Pointer to the underlying graph. - const Graph *_graph; - /// Pointer to the capacity map - const CapacityMap *_capacity; - ///Pointer to the map of cardinality. - CardinalityMap *_cardinality; - ///Indicates if \ref _cardinality is locally allocated (\c true) or not. - bool local_cardinality; - ///Pointer to the map of processed status of the nodes. - ProcessedMap *_processed; - ///Indicates if \ref _processed is locally allocated (\c true) or not. - bool local_processed; - ///Pointer to the heap cross references. - HeapCrossRef *_heap_cross_ref; - ///Indicates if \ref _heap_cross_ref is locally allocated (\c true) or not. - bool local_heap_cross_ref; - ///Pointer to the heap. - Heap *_heap; - ///Indicates if \ref _heap is locally allocated (\c true) or not. - bool local_heap; - - public : - - typedef MaxCardinalitySearch Create; - - ///\name Named template parameters - - ///@{ - - template - struct DefCardinalityMapTraits : public Traits { - typedef T CardinalityMap; - static CardinalityMap *createCardinalityMap(const Graph &) - { - throw UninitializedParameter(); - } - }; - /// \brief \ref named-templ-param "Named parameter" for setting - /// CardinalityMap type - /// - /// \ref named-templ-param "Named parameter" for setting CardinalityMap - /// type - template - struct DefCardinalityMap - : public MaxCardinalitySearch > { - typedef MaxCardinalitySearch > Create; - }; - - template - struct DefProcessedMapTraits : public Traits { - typedef T ProcessedMap; - static ProcessedMap *createProcessedMap(const Graph &) { - throw UninitializedParameter(); - } - }; - /// \brief \ref named-templ-param "Named parameter" for setting - /// ProcessedMap type - /// - /// \ref named-templ-param "Named parameter" for setting ProcessedMap type - /// - template - struct DefProcessedMap - : public MaxCardinalitySearch > { - typedef MaxCardinalitySearch > Create; - }; - - template - struct DefHeapTraits : public Traits { - typedef CR HeapCrossRef; - typedef H Heap; - static HeapCrossRef *createHeapCrossRef(const Graph &) { - throw UninitializedParameter(); - } - static Heap *createHeap(HeapCrossRef &) { - throw UninitializedParameter(); - } - }; - /// \brief \ref named-templ-param "Named parameter" for setting heap - /// and cross reference type - /// - /// \ref named-templ-param "Named parameter" for setting heap and cross - /// reference type - template > - struct DefHeap - : public MaxCardinalitySearch > { - typedef MaxCardinalitySearch< Graph, CapacityMap, - DefHeapTraits > Create; - }; - - template - struct DefStandardHeapTraits : public Traits { - typedef CR HeapCrossRef; - typedef H Heap; - static HeapCrossRef *createHeapCrossRef(const Graph &graph) { - return new HeapCrossRef(graph); - } - static Heap *createHeap(HeapCrossRef &crossref) { - return new Heap(crossref); - } - }; - - /// \brief \ref named-templ-param "Named parameter" for setting heap and - /// cross reference type with automatic allocation - /// - /// \ref named-templ-param "Named parameter" for setting heap and cross - /// reference type. It can allocate the heap and the cross reference - /// object if the cross reference's constructor waits for the graph as - /// parameter and the heap's constructor waits for the cross reference. - template > - struct DefStandardHeap - : public MaxCardinalitySearch > { - typedef MaxCardinalitySearch > - Create; - }; - - ///@} - - - protected: - - MaxCardinalitySearch() {} - - public: - - /// \brief Constructor. - /// - ///\param _graph the graph the algorithm will run on. - ///\param _capacity the capacity map used by the algorithm. - MaxCardinalitySearch(const Graph& graph, const CapacityMap& capacity) : - _graph(&graph), _capacity(&capacity), - _cardinality(0), local_cardinality(false), - _processed(0), local_processed(false), - _heap_cross_ref(0), local_heap_cross_ref(false), - _heap(0), local_heap(false) - { } - - /// \brief Destructor. - ~MaxCardinalitySearch() { - if(local_cardinality) delete _cardinality; - if(local_processed) delete _processed; - if(local_heap_cross_ref) delete _heap_cross_ref; - if(local_heap) delete _heap; - } - - /// \brief Sets the capacity map. - /// - /// Sets the capacity map. - /// \return (*this) - MaxCardinalitySearch &capacityMap(const CapacityMap &m) { - _capacity = &m; - return *this; - } - - /// \brief Sets the map storing the cardinalities calculated by the - /// algorithm. - /// - /// Sets the map storing the cardinalities calculated by the algorithm. - /// If you don't use this function before calling \ref run(), - /// it will allocate one. The destuctor deallocates this - /// automatically allocated map, of course. - /// \return (*this) - MaxCardinalitySearch &cardinalityMap(CardinalityMap &m) { - if(local_cardinality) { - delete _cardinality; - local_cardinality=false; - } - _cardinality = &m; - return *this; - } - - /// \brief Sets the map storing the processed nodes. - /// - /// Sets the map storing the processed nodes. - /// If you don't use this function before calling \ref run(), - /// it will allocate one. The destuctor deallocates this - /// automatically allocated map, of course. - /// \return (*this) - MaxCardinalitySearch &processedMap(ProcessedMap &m) - { - if(local_processed) { - delete _processed; - local_processed=false; - } - _processed = &m; - return *this; - } - - /// \brief Sets the heap and the cross reference used by algorithm. - /// - /// Sets the heap and the cross reference used by algorithm. - /// If you don't use this function before calling \ref run(), - /// it will allocate one. The destuctor deallocates this - /// automatically allocated map, of course. - /// \return (*this) - MaxCardinalitySearch &heap(Heap& heap, HeapCrossRef &crossRef) { - if(local_heap_cross_ref) { - delete _heap_cross_ref; - local_heap_cross_ref = false; - } - _heap_cross_ref = &crossRef; - if(local_heap) { - delete _heap; - local_heap = false; - } - _heap = &heap; - return *this; - } - - private: - - typedef typename Graph::Node Node; - typedef typename Graph::NodeIt NodeIt; - typedef typename Graph::Edge Edge; - typedef typename Graph::InEdgeIt InEdgeIt; - - void create_maps() { - if(!_cardinality) { - local_cardinality = true; - _cardinality = Traits::createCardinalityMap(*_graph); - } - if(!_processed) { - local_processed = true; - _processed = Traits::createProcessedMap(*_graph); - } - if (!_heap_cross_ref) { - local_heap_cross_ref = true; - _heap_cross_ref = Traits::createHeapCrossRef(*_graph); - } - if (!_heap) { - local_heap = true; - _heap = Traits::createHeap(*_heap_cross_ref); - } - } - - void finalizeNodeData(Node node, Value capacity) { - _processed->set(node, true); - _cardinality->set(node, capacity); - } - - public: - /// \name Execution control - /// The simplest way to execute the algorithm is to use - /// one of the member functions called \c run(...). - /// \n - /// If you need more control on the execution, - /// first you must call \ref init(), then you can add several source nodes - /// with \ref addSource(). - /// Finally \ref start() will perform the actual path - /// computation. - - ///@{ - - /// \brief Initializes the internal data structures. - /// - /// Initializes the internal data structures. - void init() { - create_maps(); - _heap->clear(); - for (NodeIt it(*_graph) ; it != INVALID ; ++it) { - _processed->set(it, false); - _heap_cross_ref->set(it, Heap::PRE_HEAP); - } - } - - /// \brief Adds a new source node. - /// - /// Adds a new source node to the priority heap. - /// - /// It checks if the node has not yet been added to the heap. - void addSource(Node source, Value capacity = 0) { - if(_heap->state(source) == Heap::PRE_HEAP) { - _heap->push(source, capacity); - } - } - - /// \brief Processes the next node in the priority heap - /// - /// Processes the next node in the priority heap. - /// - /// \return The processed node. - /// - /// \warning The priority heap must not be empty! - Node processNextNode() { - Node node = _heap->top(); - finalizeNodeData(node, _heap->prio()); - _heap->pop(); - - for (InEdgeIt it(*_graph, node); it != INVALID; ++it) { - Node source = _graph->source(it); - switch (_heap->state(source)) { - case Heap::PRE_HEAP: - _heap->push(source, (*_capacity)[it]); - break; - case Heap::IN_HEAP: - _heap->decrease(source, (*_heap)[source] + (*_capacity)[it]); - break; - case Heap::POST_HEAP: - break; - } - } - return node; - } - - /// \brief Next node to be processed. - /// - /// Next node to be processed. - /// - /// \return The next node to be processed or INVALID if the - /// priority heap is empty. - Node nextNode() { - return _heap->empty() ? _heap->top() : INVALID; - } - - /// \brief Returns \c false if there are nodes - /// to be processed in the priority heap - /// - /// Returns \c false if there are nodes - /// to be processed in the priority heap - bool emptyQueue() { return _heap->empty(); } - /// \brief Returns the number of the nodes to be processed - /// in the priority heap - /// - /// Returns the number of the nodes to be processed in the priority heap - int queueSize() { return _heap->size(); } - - /// \brief Executes the algorithm. - /// - /// Executes the algorithm. - /// - ///\pre init() must be called and at least one node should be added - /// with addSource() before using this function. - /// - /// This method runs the Maximum Cardinality Search algorithm from the - /// source node(s). - void start() { - while ( !_heap->empty() ) processNextNode(); - } - - /// \brief Executes the algorithm until \c dest is reached. - /// - /// Executes the algorithm until \c dest is reached. - /// - /// \pre init() must be called and at least one node should be added - /// with addSource() before using this function. - /// - /// This method runs the %MaxCardinalitySearch algorithm from the source - /// nodes. - void start(Node dest) { - while ( !_heap->empty() && _heap->top()!=dest ) processNextNode(); - if ( !_heap->empty() ) finalizeNodeData(_heap->top(), _heap->prio()); - } - - /// \brief Executes the algorithm until a condition is met. - /// - /// Executes the algorithm until a condition is met. - /// - /// \pre init() must be called and at least one node should be added - /// with addSource() before using this function. - /// - /// \param nm must be a bool (or convertible) node map. The algorithm - /// will stop when it reaches a node \c v with nm[v]==true. - template - void start(const NodeBoolMap &nm) { - while ( !_heap->empty() && !nm[_heap->top()] ) processNextNode(); - if ( !_heap->empty() ) finalizeNodeData(_heap->top(),_heap->prio()); - } - - /// \brief Runs the maximal cardinality search algorithm from node \c s. - /// - /// This method runs the %MaxCardinalitySearch algorithm from a root - /// node \c s. - /// - ///\note d.run(s) is just a shortcut of the following code. - ///\code - /// d.init(); - /// d.addSource(s); - /// d.start(); - ///\endcode - void run(Node s) { - init(); - addSource(s); - start(); - } - - /// \brief Runs the maximal cardinality search algorithm for the - /// whole graph. - /// - /// This method runs the %MaxCardinalitySearch algorithm from all - /// unprocessed node of the graph. - /// - ///\note d.run(s) is just a shortcut of the following code. - ///\code - /// d.init(); - /// for (NodeIt it(graph); it != INVALID; ++it) { - /// if (!d.reached(it)) { - /// d.addSource(s); - /// d.start(); - /// } - /// } - ///\endcode - void run() { - init(); - for (NodeIt it(*_graph); it != INVALID; ++it) { - if (!reached(it)) { - addSource(it); - start(); - } - } - } - - ///@} - - /// \name Query Functions - /// The result of the maximum cardinality search algorithm can be - /// obtained using these functions. - /// \n - /// Before the use of these functions, either run() or start() must be - /// called. - - ///@{ - - /// \brief The cardinality of a node. - /// - /// Returns the cardinality of a node. - /// \pre \ref run() must be called before using this function. - /// \warning If node \c v in unreachable from the root the return value - /// of this funcion is undefined. - Value cardinality(Node node) const { return (*_cardinality)[node]; } - - /// \brief Returns a reference to the NodeMap of cardinalities. - /// - /// Returns a reference to the NodeMap of cardinalities. \pre \ref run() - /// must be called before using this function. - const CardinalityMap &cardinalityMap() const { return *_cardinality;} - - /// \brief Checks if a node is reachable from the root. - /// - /// Returns \c true if \c v is reachable from the root. - /// \warning The source nodes are inditated as unreached. - /// \pre \ref run() must be called before using this function. - bool reached(Node v) { return (*_heap_cross_ref)[v] != Heap::PRE_HEAP; } - - /// \brief Checks if a node is processed. - /// - /// Returns \c true if \c v is processed, i.e. the shortest - /// path to \c v has already found. - /// \pre \ref run() must be called before using this function. - bool processed(Node v) { return (*_heap_cross_ref)[v] == Heap::POST_HEAP; } - - ///@} - }; - - /// \brief Default traits class of MinimalCut class. - /// - /// Default traits class of MinimalCut class. - /// \param Graph Graph type. - /// \param CapacityMap Type of length map. - template - struct MinimalCutDefaultTraits { - /// \brief The type of the capacity of the edges. - typedef typename _CapacityMap::Value Value; - - /// The graph type the algorithm runs on. - typedef _Graph Graph; - - /// The WorkGraph type which is an EraseableGraph - typedef ListUGraph WorkGraph; - - /// \brief Instantiates a WorkGraph. - /// - /// This function instantiates a \ref WorkGraph. - static WorkGraph *createWorkGraph() { - return new WorkGraph(); - } - - /// \brief The type of the map that stores the edge capacities. - /// - /// The type of the map that stores the edge capacities. - /// It must meet the \ref concept::ReadMap "ReadMap" concept. - typedef _CapacityMap CapacityMap; - - /// \brief Instantiates a CapacityMap. - /// - /// This function instantiates a \ref CapacityMap. -#ifdef DOXYGEN - static CapacityMap *createCapacityMap(const Graph& graph) -#else - static CapacityMap *createCapacityMap(const Graph&) -#endif - { - throw UninitializedParameter(); - } - - /// \brief The WorkCapacityMap type - /// - /// The type of the map that stores the working edge capacities. - typedef WorkGraph::UEdgeMap WorkCapacityMap; - - /// \brief Instantiates a WorkCapacityMap. - /// - /// This function instantiates a \ref WorkCapacityMap. - static WorkCapacityMap *createWorkCapacityMap(const WorkGraph& graph) { - return new WorkCapacityMap(graph); - } - - /// \brief The cross reference type used by heap. - /// - /// The cross reference type used by heap. - /// Usually it is \c Graph::NodeMap. - typedef WorkGraph::NodeMap HeapCrossRef; - - /// \brief Instantiates a HeapCrossRef. - /// - /// This function instantiates a \ref HeapCrossRef. - /// \param graph is the graph, to which we would like to define the - /// HeapCrossRef. - static HeapCrossRef *createHeapCrossRef(const WorkGraph &graph) { - return new HeapCrossRef(graph); - } - - /// \brief The heap type used by MinimalCut algorithm. - /// - /// The heap type used by MinimalCut algorithm. It should - /// maximalize the priorities and the heap's key type is - /// the work graph's node. - /// - /// \sa BinHeap - /// \sa MinimalCut - typedef typename _minimal_cut_bits - ::HeapSelector - ::template Selector - ::Heap Heap; - - /// \brief Instantiates a Heap. - /// - /// This function instantiates a \ref Heap. - /// \param crossref The cross reference of the heap. - static Heap *createHeap(HeapCrossRef& crossref) { - return new Heap(crossref); - } - - /// \brief Map from the WorkGraph's node type to the Graph's node type. - /// - /// Map from the WorkGraph's node type to the Graph's node type. - typedef typename WorkGraph - ::template NodeMap NodeRefMap; - - /// \brief Instantiates a NodeRefMap. - /// - /// This function instantiates a \ref NodeRefMap. - static NodeRefMap *createNodeRefMap(const WorkGraph& graph) { - return new NodeRefMap(graph); - } - - /// \brief Map from the Graph's node type to the Graph's node type. - /// - /// Map from the Graph's node type to the Graph's node type. - typedef typename Graph - ::template NodeMap ListRefMap; - - /// \brief Instantiates a ListRefMap. - /// - /// This function instantiates a \ref ListRefMap. - static ListRefMap *createListRefMap(const Graph& graph) { - return new ListRefMap(graph); - } - - - }; - - namespace _minimal_cut_bits { - template - class LastTwoMap { - public: - typedef _Key Key; - typedef bool Value; - - LastTwoMap(int _num) : num(_num) {} - void set(const Key& key, bool val) { - if (!val) return; - --num; - if (num > 1) return; - keys[num] = key; - } - - Key operator[](int index) const { return keys[index]; } - private: - Key keys[2]; - int num; - }; - } - - /// \ingroup topology - /// - /// \brief Calculates the minimal cut in an undirected graph. - /// - /// Calculates the minimal cut in an undirected graph. - /// The algorithm separates the graph's nodes to two partitions with the - /// minimal sum of edge capacities between the two partitions. The - /// algorithm can be used to test the network reliability specifically - /// to test how many links have to be destroyed in the network to split it - /// at least two distinict subnetwork. - /// - /// The complexity of the algorithm is O(n*e*log(n)) but with Fibonacci - /// heap it can be decreased to O(n*e+n^2*log(n)). When the neutral capacity - /// map is used then it uses LinearHeap which results O(n*e) time complexity. -#ifdef DOXYGEN - template -#else - template , - typename _Traits = MinimalCutDefaultTraits<_Graph, _CapacityMap> > -#endif - class MinimalCut { - public: - /// \brief \ref Exception for uninitialized parameters. - /// - /// This error represents problems in the initialization - /// of the parameters of the algorithms. - class UninitializedParameter : public lemon::UninitializedParameter { - public: - virtual const char* exceptionName() const { - return "lemon::MinimalCut::UninitializedParameter"; - } - }; - - - private: - - typedef _Traits Traits; - /// The type of the underlying graph. - typedef typename Traits::Graph Graph; - - /// The type of the capacity of the edges. - typedef typename Traits::CapacityMap::Value Value; - /// The type of the map that stores the edge capacities. - typedef typename Traits::CapacityMap CapacityMap; - /// The type of the work graph - typedef typename Traits::WorkGraph WorkGraph; - /// The type of the work capacity map - typedef typename Traits::WorkCapacityMap WorkCapacityMap; - /// The cross reference type used for the current heap. - typedef typename Traits::HeapCrossRef HeapCrossRef; - /// The heap type used by the max cardinality algorithm. - typedef typename Traits::Heap Heap; - /// The node refrefernces between the original and work graph type. - typedef typename Traits::NodeRefMap NodeRefMap; - /// The list node refrefernces in the original graph type. - typedef typename Traits::ListRefMap ListRefMap; - - public: - - ///\name Named template parameters - - ///@{ - - struct DefNeutralCapacityTraits : public Traits { - typedef ConstMap > CapacityMap; - static CapacityMap *createCapacityMap(const Graph&) { - return new CapacityMap(); - } - }; - /// \brief \ref named-templ-param "Named parameter" for setting - /// the capacity type to constMap() - /// - /// \ref named-templ-param "Named parameter" for setting - /// the capacity type to constMap() - struct DefNeutralCapacity - : public MinimalCut { - typedef MinimalCut Create; - }; - - - template - struct DefHeapTraits : public Traits { - typedef CR HeapCrossRef; - typedef H Heap; - static HeapCrossRef *createHeapCrossRef(const WorkGraph &) { - throw UninitializedParameter(); - } - static Heap *createHeap(HeapCrossRef &) { - throw UninitializedParameter(); - } - }; - /// \brief \ref named-templ-param "Named parameter" for setting heap - /// and cross reference type - /// - /// \ref named-templ-param "Named parameter" for setting heap and cross - /// reference type - template > - struct DefHeap - : public MinimalCut > { - typedef MinimalCut< Graph, CapacityMap, DefHeapTraits > Create; - }; - - template - struct DefStandardHeapTraits : public Traits { - typedef CR HeapCrossRef; - typedef H Heap; - static HeapCrossRef *createHeapCrossRef(const WorkGraph &graph) { - return new HeapCrossRef(graph); - } - static Heap *createHeap(HeapCrossRef &crossref) { - return new Heap(crossref); - } - }; - - /// \brief \ref named-templ-param "Named parameter" for setting heap and - /// cross reference type with automatic allocation - /// - /// \ref named-templ-param "Named parameter" for setting heap and cross - /// reference type. It can allocate the heap and the cross reference - /// object if the cross reference's constructor waits for the graph as - /// parameter and the heap's constructor waits for the cross reference. - template > - struct DefStandardHeap - : public MinimalCut > { - typedef MinimalCut > - Create; - }; - - ///@} - - - private: - /// Pointer to the underlying graph. - const Graph *_graph; - /// Pointer to the capacity map - const CapacityMap *_capacity; - /// \brief Indicates if \ref _capacity is locally allocated - /// (\c true) or not. - bool local_capacity; - - /// Pointer to the work graph. - WorkGraph *_work_graph; - /// \brief Indicates if \ref _work_graph is locally allocated - /// (\c true) or not. - bool local_work_graph; - /// Pointer to the work capacity map - WorkCapacityMap *_work_capacity; - /// \brief Indicates if \ref _work_capacity is locally allocated - /// (\c true) or not. - bool local_work_capacity; - /// Pointer to the heap cross references. - HeapCrossRef *_heap_cross_ref; - /// \brief Indicates if \ref _heap_cross_ref is locally allocated - /// (\c true) or not. - bool local_heap_cross_ref; - /// Pointer to the heap. - Heap *_heap; - /// Indicates if \ref _heap is locally allocated (\c true) or not. - bool local_heap; - - /// The minimal cut value. - Value _minimal_cut; - /// The number of the nodes of the work graph. - int _node_num; - /// The first and last node of the min cut in the next list; - typename Graph::Node _first_node, _last_node; - - /// \brief The first and last element in the list associated - /// to the work graph node. - NodeRefMap *_first, *_last; - /// \brief The next node in the node lists. - ListRefMap *_next; - - void create_structures() { - if (!_capacity) { - local_capacity = true; - _capacity = Traits::createCapacityMap(*_graph); - } - if(!_work_graph) { - local_work_graph = true; - _work_graph = Traits::createWorkGraph(); - } - if(!_work_capacity) { - local_work_capacity = true; - _work_capacity = Traits::createWorkCapacityMap(*_work_graph); - } - - _first = Traits::createNodeRefMap(*_work_graph); - _last = Traits::createNodeRefMap(*_work_graph); - - _next = Traits::createListRefMap(*_graph); - - typename Graph::template NodeMap ref(*_graph); - - for (typename Graph::NodeIt it(*_graph); it != INVALID; ++it) { - _next->set(it, INVALID); - typename WorkGraph::Node node = _work_graph->addNode(); - _first->set(node, it); - _last->set(node, it); - ref.set(it, node); - } - - for (typename Graph::UEdgeIt it(*_graph); it != INVALID; ++it) { - if (_graph->source(it) == _graph->target(it)) continue; - typename WorkGraph::UEdge uedge = - _work_graph->addEdge(ref[_graph->source(it)], - ref[_graph->target(it)]); - _work_capacity->set(uedge, (*_capacity)[it]); - - } - - if (!_heap_cross_ref) { - local_heap_cross_ref = true; - _heap_cross_ref = Traits::createHeapCrossRef(*_work_graph); - } - if (!_heap) { - local_heap = true; - _heap = Traits::createHeap(*_heap_cross_ref); - } - } - - public : - - typedef MinimalCut Create; - - - /// \brief Constructor. - /// - ///\param graph the graph the algorithm will run on. - ///\param capacity the capacity map used by the algorithm. - MinimalCut(const Graph& graph, const CapacityMap& capacity) - : _graph(&graph), - _capacity(&capacity), local_capacity(false), - _work_graph(0), local_work_graph(false), - _work_capacity(0), local_work_capacity(false), - _heap_cross_ref(0), local_heap_cross_ref(false), - _heap(0), local_heap(false), - _first(0), _last(0), _next(0) {} - - /// \brief Constructor. - /// - /// This constructor can be used only when the Traits class - /// defines how can we instantiate a local capacity map. - /// If the DefNeutralCapacity used the algorithm automatically - /// construct the capacity map. - /// - ///\param graph the graph the algorithm will run on. - MinimalCut(const Graph& graph) - : _graph(&graph), - _capacity(0), local_capacity(false), - _work_graph(0), local_work_graph(false), - _work_capacity(0), local_work_capacity(false), - _heap_cross_ref(0), local_heap_cross_ref(false), - _heap(0), local_heap(false), - _first(0), _last(0), _next(0) {} - - /// \brief Destructor. - /// - /// Destructor. - ~MinimalCut() { - if (local_heap) delete _heap; - if (local_heap_cross_ref) delete _heap_cross_ref; - if (_first) delete _first; - if (_last) delete _last; - if (_next) delete _next; - if (local_work_capacity) delete _work_capacity; - if (local_work_graph) delete _work_graph; - if (local_capacity) delete _capacity; - } - - /// \brief Sets the heap and the cross reference used by algorithm. - /// - /// Sets the heap and the cross reference used by algorithm. - /// If you don't use this function before calling \ref run(), - /// it will allocate one. The destuctor deallocates this - /// automatically allocated heap and cross reference, of course. - /// \return (*this) - MinimalCut &heap(Heap& heap, HeapCrossRef &crossRef) - { - if (local_heap_cross_ref) { - delete _heap_cross_ref; - local_heap_cross_ref=false; - } - _heap_cross_ref = &crossRef; - if (local_heap) { - delete _heap; - local_heap=false; - } - _heap = &heap; - return *this; - } - - /// \brief Sets the work graph. - /// - /// Sets the work graph used by algorithm. - /// If you don't use this function before calling \ref run(), - /// it will allocate one. The destuctor deallocates this - /// automatically allocated graph, of course. - /// \return (*this) - MinimalCut &workGraph(WorkGraph& work_graph) - { - if(local_work_graph) { - delete _work_graph; - local_work_graph=false; - } - _work_graph = &work_graph; - return *this; - } - - /// \brief Sets the work capacity map. - /// - /// Sets the work capacity map used by algorithm. - /// If you don't use this function before calling \ref run(), - /// it will allocate one. The destuctor deallocates this - /// automatically allocated graph, of course. - /// \return (*this) - MinimalCut &workCapacityMap(WorkCapacityMap& work_capacity_map) - { - if(local_work_capacity) { - delete _work_capacity; - local_work_capacity=false; - } - _work_capacity = &work_capacity_map; - return *this; - } - - /// \name Execution control - /// The simplest way to execute the algorithm is to use - /// one of the member functions called \c run(). - /// \n - /// If you need more control on the execution, - /// first you must call \ref init() and then call the start() - /// or proper times the processNextPhase() member functions. - - ///@{ - - /// \brief Initializes the internal data structures. - /// - /// Initializes the internal data structures. - void init() { - create_structures(); - _first_node = _last_node = INVALID; - _node_num = countNodes(*_graph); - } - - /// \brief Processes the next phase - /// - /// Processes the next phase in the algorithm. The function - /// should be called countNodes(graph) - 1 times to get - /// surely the minimal cut in the graph. The - /// - ///\return %True when the algorithm finished. - bool processNextPhase() { - if (_node_num <= 1) return true; - using namespace _minimal_cut_bits; - - typedef typename WorkGraph::Node Node; - typedef typename WorkGraph::NodeIt NodeIt; - typedef typename WorkGraph::UEdge UEdge; - typedef typename WorkGraph::IncEdgeIt IncEdgeIt; - - typedef typename MaxCardinalitySearch:: - template DefHeap:: - template DefCardinalityMap >:: - template DefProcessedMap >:: - Create MaxCardinalitySearch; - - MaxCardinalitySearch mcs(*_work_graph, *_work_capacity); - for (NodeIt it(*_work_graph); it != INVALID; ++it) { - _heap_cross_ref->set(it, Heap::PRE_HEAP); - } - mcs.heap(*_heap, *_heap_cross_ref); - - LastTwoMap last_two_nodes(_node_num); - mcs.processedMap(last_two_nodes); - - NullMap cardinality; - mcs.cardinalityMap(cardinality); - - mcs.run(); - - Node new_node = _work_graph->addNode(); - - typename WorkGraph::template NodeMap edges(*_work_graph, INVALID); - - Node first_node = last_two_nodes[0]; - Node second_node = last_two_nodes[1]; - - _next->set((*_last)[first_node], (*_first)[second_node]); - _first->set(new_node, (*_first)[first_node]); - _last->set(new_node, (*_last)[second_node]); - - Value current_cut = 0; - for (IncEdgeIt it(*_work_graph, first_node); it != INVALID; ++it) { - Node node = _work_graph->runningNode(it); - current_cut += (*_work_capacity)[it]; - if (node == second_node) continue; - if (edges[node] == INVALID) { - edges[node] = _work_graph->addEdge(new_node, node); - (*_work_capacity)[edges[node]] = (*_work_capacity)[it]; - } else { - (*_work_capacity)[edges[node]] += (*_work_capacity)[it]; - } - } - - if (_first_node == INVALID || current_cut < _minimal_cut) { - _first_node = (*_first)[first_node]; - _last_node = (*_last)[first_node]; - _minimal_cut = current_cut; - } - - _work_graph->erase(first_node); - - for (IncEdgeIt it(*_work_graph, second_node); it != INVALID; ++it) { - Node node = _work_graph->runningNode(it); - if (edges[node] == INVALID) { - edges[node] = _work_graph->addEdge(new_node, node); - (*_work_capacity)[edges[node]] = (*_work_capacity)[it]; - } else { - (*_work_capacity)[edges[node]] += (*_work_capacity)[it]; - } - } - _work_graph->erase(second_node); - - --_node_num; - return _node_num == 1; - } - - /// \brief Executes the algorithm. - /// - /// Executes the algorithm. - /// - /// \pre init() must be called - void start() { - while (!processNextPhase()); - } - - - /// \brief Runs %MinimalCut algorithm. - /// - /// This method runs the %Minimal cut algorithm - /// - /// \note mc.run(s) is just a shortcut of the following code. - ///\code - /// mc.init(); - /// mc.start(); - ///\endcode - void run() { - init(); - start(); - } - - ///@} - - /// \name Query Functions - /// The result of the %MinimalCut algorithm can be obtained using these - /// functions.\n - /// Before the use of these functions, - /// either run() or start() must be called. - - ///@{ - - /// \brief Returns the minimal cut value. - /// - /// Returns the minimal cut value if the algorithm finished. - /// After the first processNextPhase() it is a value of a - /// valid cut in the graph. - Value minCut() const { - return _minimal_cut; - } - - /// \brief Returns a minimal cut in a NodeMap. - /// - /// It sets the nodes of one of the two partitions to true in - /// the given BoolNodeMap. The map contains a valid cut if the - /// map have been setted false previously. - template - Value quickMinCut(NodeMap& nodeMap) const { - for (typename Graph::Node it = _first_node; - it != _last_node; it = (*_next)[it]) { - nodeMap.set(it, true); - } - nodeMap.set(_last_node, true); - return minCut(); - } - - /// \brief Returns a minimal cut in a NodeMap. - /// - /// It sets the nodes of one of the two partitions to true and - /// the other partition to false. The function first set all of the - /// nodes to false and after it call the quickMinCut() member. - template - Value minCut(NodeMap& nodeMap) const { - for (typename Graph::NodeIt it(*_graph); it != INVALID; ++it) { - nodeMap.set(it, false); - } - quickMinCut(nodeMap); - return minCut(); - } - - /// \brief Returns a minimal cut in an EdgeMap. - /// - /// If an undirected edge is cut edge then it will be - /// setted to true and the others will be setted to false in the given map. - template - Value cutEdges(EdgeMap& edgeMap) const { - typename Graph::template NodeMap cut(*_graph, false); - quickMinCut(cut); - for (typename Graph::EdgeIt it(*_graph); it != INVALID; ++it) { - edgeMap.set(it, cut[_graph->source(it)] ^ cut[_graph->target(it)]); - } - return minCut(); - } - - ///@} - - }; -} - -#endif