# HG changeset patch # User deba # Date 1162305054 0 # Node ID 05ff57dc401d5df81b26a2e902300de2b1b88cbe # Parent a877258468e4e5f3873d92341e47028904321f90 Renaming MinCut diff -r a877258468e4 -r 05ff57dc401d lemon/Makefile.am --- a/lemon/Makefile.am Tue Oct 31 14:28:27 2006 +0000 +++ b/lemon/Makefile.am Tue Oct 31 14:30:54 2006 +0000 @@ -76,9 +76,9 @@ lemon/matrix_maps.h \ lemon/max_matching.h \ lemon/min_cost_arborescence.h \ - lemon/min_cut.h \ lemon/mip_glpk.h \ lemon/mip_cplex.h \ + lemon/nagamochi_ibaraki.h \ lemon/path.h \ lemon/polynomial.h \ lemon/preflow.h \ diff -r a877258468e4 -r 05ff57dc401d lemon/min_cut.h --- a/lemon/min_cut.h Tue Oct 31 14:28:27 2006 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,1353 +0,0 @@ -/* -*- C++ -*- - * lemon/min_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_MIN_CUT_H -#define LEMON_MIN_CUT_H - - -/// \ingroup topology -/// \file -/// \brief Maximum cardinality search and min cut in undirected graphs. - -#include -#include -#include - -#include -#include -#include - -#include - -namespace lemon { - - namespace _min_cut_bits { - - template - struct HeapSelector { - template - struct Selector { - typedef BinHeap > Heap; - }; - }; - - template - struct HeapSelector > > { - template - struct Selector { - typedef BucketHeap 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 concepts::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 BucketHeap. - /// - /// \sa MaxCardinalitySearch - typedef typename _min_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 concepts::WriteMap "WriteMap" concept. - /// By default it is a NullMap. - typedef NullMap ProcessedMap; - - /// \brief Instantiates a ProcessedMap. - /// - /// This function instantiates a \ref ProcessedMap. - /// \param graph 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 concepts::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 it chooses the node which is 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 node 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 concepts::ReadMap "ReadMap", so it is easy to change it to any - /// kind of capacity. - /// - /// The type of the capacity is determined by the \ref - /// concepts::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 - /// concepts::Graph::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* what() const throw() { - 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 MinCut class. - /// - /// Default traits class of MinCut class. - /// \param Graph Graph type. - /// \param CapacityMap Type of length map. - template - struct MinCutDefaultTraits { - /// \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 AuxGraph type which is an Graph - typedef ListUGraph AuxGraph; - - /// \brief Instantiates a AuxGraph. - /// - /// This function instantiates a \ref AuxGraph. - static AuxGraph *createAuxGraph() { - return new AuxGraph(); - } - - /// \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 concepts::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 AuxCapacityMap type - /// - /// The type of the map that stores the auxing edge capacities. - typedef AuxGraph::UEdgeMap AuxCapacityMap; - - /// \brief Instantiates a AuxCapacityMap. - /// - /// This function instantiates a \ref AuxCapacityMap. - static AuxCapacityMap *createAuxCapacityMap(const AuxGraph& graph) { - return new AuxCapacityMap(graph); - } - - /// \brief The cross reference type used by heap. - /// - /// The cross reference type used by heap. - /// Usually it is \c Graph::NodeMap. - typedef AuxGraph::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 AuxGraph &graph) { - return new HeapCrossRef(graph); - } - - /// \brief The heap type used by MinCut algorithm. - /// - /// The heap type used by MinCut algorithm. It should - /// maximalize the priorities and the heap's key type is - /// the aux graph's node. - /// - /// \sa BinHeap - /// \sa MinCut - typedef typename _min_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 AuxGraph's node type to the Graph's node type. - /// - /// Map from the AuxGraph's node type to the Graph's node type. - typedef typename AuxGraph - ::template NodeMap NodeRefMap; - - /// \brief Instantiates a NodeRefMap. - /// - /// This function instantiates a \ref NodeRefMap. - static NodeRefMap *createNodeRefMap(const AuxGraph& 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 _min_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 minimum cut in an undirected graph. - /// - /// Calculates the minimum cut in an undirected graph with the - /// Nagamochi-Ibaraki algorithm. The algorithm separates the graph's - /// nodes into two partitions with the minimum 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 \f$ O(ne\log(n)) \f$ but with - /// Fibonacci heap it can be decreased to \f$ O(ne+n^2\log(n)) - /// \f$. When capacity map is neutral then it uses BucketHeap which - /// results \f$ O(ne) \f$ time complexity. -#ifdef DOXYGEN - template -#else - template , - typename _Traits = MinCutDefaultTraits<_Graph, _CapacityMap> > -#endif - class MinCut { - 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* what() const throw() { - return "lemon::MinCut::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 aux graph - typedef typename Traits::AuxGraph AuxGraph; - /// The type of the aux capacity map - typedef typename Traits::AuxCapacityMap AuxCapacityMap; - /// 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 aux 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 MinCut { - typedef MinCut Create; - }; - - - template - struct DefHeapTraits : public Traits { - typedef CR HeapCrossRef; - typedef H Heap; - static HeapCrossRef *createHeapCrossRef(const AuxGraph &) { - 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 MinCut > { - typedef MinCut< Graph, CapacityMap, DefHeapTraits > Create; - }; - - template - struct DefStandardHeapTraits : public Traits { - typedef CR HeapCrossRef; - typedef H Heap; - static HeapCrossRef *createHeapCrossRef(const AuxGraph &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 MinCut > { - typedef MinCut > - 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 aux graph. - AuxGraph *_aux_graph; - /// \brief Indicates if \ref _aux_graph is locally allocated - /// (\c true) or not. - bool local_aux_graph; - /// Pointer to the aux capacity map - AuxCapacityMap *_aux_capacity; - /// \brief Indicates if \ref _aux_capacity is locally allocated - /// (\c true) or not. - bool local_aux_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 min cut value. - Value _min_cut; - /// The number of the nodes of the aux 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 aux 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(!_aux_graph) { - local_aux_graph = true; - _aux_graph = Traits::createAuxGraph(); - } - if(!_aux_capacity) { - local_aux_capacity = true; - _aux_capacity = Traits::createAuxCapacityMap(*_aux_graph); - } - - _first = Traits::createNodeRefMap(*_aux_graph); - _last = Traits::createNodeRefMap(*_aux_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 AuxGraph::Node node = _aux_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 AuxGraph::UEdge uedge = - _aux_graph->addEdge(ref[_graph->source(it)], - ref[_graph->target(it)]); - _aux_capacity->set(uedge, (*_capacity)[it]); - - } - - if (!_heap_cross_ref) { - local_heap_cross_ref = true; - _heap_cross_ref = Traits::createHeapCrossRef(*_aux_graph); - } - if (!_heap) { - local_heap = true; - _heap = Traits::createHeap(*_heap_cross_ref); - } - } - - public : - - typedef MinCut Create; - - - /// \brief Constructor. - /// - ///\param graph the graph the algorithm will run on. - ///\param capacity the capacity map used by the algorithm. - MinCut(const Graph& graph, const CapacityMap& capacity) - : _graph(&graph), - _capacity(&capacity), local_capacity(false), - _aux_graph(0), local_aux_graph(false), - _aux_capacity(0), local_aux_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. - MinCut(const Graph& graph) - : _graph(&graph), - _capacity(0), local_capacity(false), - _aux_graph(0), local_aux_graph(false), - _aux_capacity(0), local_aux_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. - ~MinCut() { - 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_aux_capacity) delete _aux_capacity; - if (local_aux_graph) delete _aux_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) - MinCut &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 aux graph. - /// - /// Sets the aux 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) - MinCut &auxGraph(AuxGraph& aux_graph) - { - if(local_aux_graph) { - delete _aux_graph; - local_aux_graph=false; - } - _aux_graph = &aux_graph; - return *this; - } - - /// \brief Sets the aux capacity map. - /// - /// Sets the aux 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) - MinCut &auxCapacityMap(AuxCapacityMap& aux_capacity_map) - { - if(local_aux_capacity) { - delete _aux_capacity; - local_aux_capacity=false; - } - _aux_capacity = &aux_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 min cut in the graph. The - /// - ///\return %True when the algorithm finished. - bool processNextPhase() { - if (_node_num <= 1) return true; - using namespace _min_cut_bits; - - typedef typename AuxGraph::Node Node; - typedef typename AuxGraph::NodeIt NodeIt; - typedef typename AuxGraph::UEdge UEdge; - typedef typename AuxGraph::IncEdgeIt IncEdgeIt; - - typedef typename MaxCardinalitySearch:: - template DefHeap:: - template DefCardinalityMap >:: - template DefProcessedMap >:: - Create MaxCardinalitySearch; - - MaxCardinalitySearch mcs(*_aux_graph, *_aux_capacity); - for (NodeIt it(*_aux_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 = _aux_graph->addNode(); - - typename AuxGraph::template NodeMap edges(*_aux_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(*_aux_graph, first_node); it != INVALID; ++it) { - Node node = _aux_graph->runningNode(it); - current_cut += (*_aux_capacity)[it]; - if (node == second_node) continue; - if (edges[node] == INVALID) { - edges[node] = _aux_graph->addEdge(new_node, node); - (*_aux_capacity)[edges[node]] = (*_aux_capacity)[it]; - } else { - (*_aux_capacity)[edges[node]] += (*_aux_capacity)[it]; - } - } - - if (_first_node == INVALID || current_cut < _min_cut) { - _first_node = (*_first)[first_node]; - _last_node = (*_last)[first_node]; - _min_cut = current_cut; - } - - _aux_graph->erase(first_node); - - for (IncEdgeIt it(*_aux_graph, second_node); it != INVALID; ++it) { - Node node = _aux_graph->runningNode(it); - if (edges[node] == INVALID) { - edges[node] = _aux_graph->addEdge(new_node, node); - (*_aux_capacity)[edges[node]] = (*_aux_capacity)[it]; - } else { - (*_aux_capacity)[edges[node]] += (*_aux_capacity)[it]; - } - } - _aux_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 %MinCut algorithm. - /// - /// This method runs the %Min 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 %MinCut algorithm can be obtained using these - /// functions.\n - /// Before the use of these functions, - /// either run() or start() must be called. - - ///@{ - - /// \brief Returns the min cut value. - /// - /// Returns the min 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 _min_cut; - } - - /// \brief Returns a min 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 set 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 min 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 min cut in an EdgeMap. - /// - /// If an undirected edge is in a min cut then it will be - /// set to true and the others will be set 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 diff -r a877258468e4 -r 05ff57dc401d lemon/nagamochi_ibaraki.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/lemon/nagamochi_ibaraki.h Tue Oct 31 14:30:54 2006 +0000 @@ -0,0 +1,1361 @@ +/* -*- C++ -*- + * lemon/min_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_MIN_CUT_H +#define LEMON_MIN_CUT_H + + +/// \ingroup topology +/// \file +/// \brief Maximum cardinality search and min cut in undirected graphs. + +#include +#include +#include + +#include +#include +#include + +#include + +namespace lemon { + + namespace _min_cut_bits { + + template + struct HeapSelector { + template + struct Selector { + typedef BinHeap > Heap; + }; + }; + + template + struct HeapSelector > > { + template + struct Selector { + typedef BucketHeap 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 concepts::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 BucketHeap. + /// + /// \sa MaxCardinalitySearch + typedef typename _min_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 concepts::WriteMap "WriteMap" concept. + /// By default it is a NullMap. + typedef NullMap ProcessedMap; + + /// \brief Instantiates a ProcessedMap. + /// + /// This function instantiates a \ref ProcessedMap. + /// \param graph 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 concepts::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 it chooses the node which is 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 node 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 concepts::ReadMap "ReadMap", so it is easy to change it to any + /// kind of capacity. + /// + /// The type of the capacity is determined by the \ref + /// concepts::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 + /// concepts::Graph::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* what() const throw() { + 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 NagamochiIbaraki class. + /// + /// Default traits class of NagamochiIbaraki class. + /// \param Graph Graph type. + /// \param CapacityMap Type of length map. + template + struct NagamochiIbarakiDefaultTraits { + /// \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 AuxGraph type which is an Graph + typedef ListUGraph AuxGraph; + + /// \brief Instantiates a AuxGraph. + /// + /// This function instantiates a \ref AuxGraph. + static AuxGraph *createAuxGraph() { + return new AuxGraph(); + } + + /// \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 concepts::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 AuxCapacityMap type + /// + /// The type of the map that stores the auxing edge capacities. + typedef AuxGraph::UEdgeMap AuxCapacityMap; + + /// \brief Instantiates a AuxCapacityMap. + /// + /// This function instantiates a \ref AuxCapacityMap. + static AuxCapacityMap *createAuxCapacityMap(const AuxGraph& graph) { + return new AuxCapacityMap(graph); + } + + /// \brief The cross reference type used by heap. + /// + /// The cross reference type used by heap. + /// Usually it is \c Graph::NodeMap. + typedef AuxGraph::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 AuxGraph &graph) { + return new HeapCrossRef(graph); + } + + /// \brief The heap type used by NagamochiIbaraki algorithm. + /// + /// The heap type used by NagamochiIbaraki algorithm. It should + /// maximalize the priorities and the heap's key type is + /// the aux graph's node. + /// + /// \sa BinHeap + /// \sa NagamochiIbaraki + typedef typename _min_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 AuxGraph's node type to the Graph's node type. + /// + /// Map from the AuxGraph's node type to the Graph's node type. + typedef typename AuxGraph + ::template NodeMap NodeRefMap; + + /// \brief Instantiates a NodeRefMap. + /// + /// This function instantiates a \ref NodeRefMap. + static NodeRefMap *createNodeRefMap(const AuxGraph& 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 _min_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 minimum cut in an undirected graph. + /// + /// Calculates the minimum cut in an undirected graph with the + /// Nagamochi-Ibaraki algorithm. The algorithm separates the graph's + /// nodes into two partitions with the minimum 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 \f$ O(ne\log(n)) \f$ but with + /// Fibonacci heap it can be decreased to \f$ O(ne+n^2\log(n)) + /// \f$. When capacity map is neutral then it uses BucketHeap which + /// results \f$ O(ne) \f$ time complexity. +#ifdef DOXYGEN + template +#else + template , + typename _Traits + = NagamochiIbarakiDefaultTraits<_Graph, _CapacityMap> > +#endif + class NagamochiIbaraki { + 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* what() const throw() { + return "lemon::NagamochiIbaraki::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 aux graph + typedef typename Traits::AuxGraph AuxGraph; + /// The type of the aux capacity map + typedef typename Traits::AuxCapacityMap AuxCapacityMap; + /// 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 aux 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 NagamochiIbaraki { + typedef NagamochiIbaraki Create; + }; + + + template + struct DefHeapTraits : public Traits { + typedef CR HeapCrossRef; + typedef H Heap; + static HeapCrossRef *createHeapCrossRef(const AuxGraph &) { + 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 NagamochiIbaraki > { + typedef NagamochiIbaraki< Graph, CapacityMap, + DefHeapTraits > Create; + }; + + template + struct DefStandardHeapTraits : public Traits { + typedef CR HeapCrossRef; + typedef H Heap; + static HeapCrossRef *createHeapCrossRef(const AuxGraph &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 NagamochiIbaraki > { + typedef NagamochiIbaraki > + 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 aux graph. + AuxGraph *_aux_graph; + /// \brief Indicates if \ref _aux_graph is locally allocated + /// (\c true) or not. + bool local_aux_graph; + /// Pointer to the aux capacity map + AuxCapacityMap *_aux_capacity; + /// \brief Indicates if \ref _aux_capacity is locally allocated + /// (\c true) or not. + bool local_aux_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 min cut value. + Value _min_cut; + /// The number of the nodes of the aux 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 aux 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(!_aux_graph) { + local_aux_graph = true; + _aux_graph = Traits::createAuxGraph(); + } + if(!_aux_capacity) { + local_aux_capacity = true; + _aux_capacity = Traits::createAuxCapacityMap(*_aux_graph); + } + + _first = Traits::createNodeRefMap(*_aux_graph); + _last = Traits::createNodeRefMap(*_aux_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 AuxGraph::Node node = _aux_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 AuxGraph::UEdge uedge = + _aux_graph->addEdge(ref[_graph->source(it)], + ref[_graph->target(it)]); + _aux_capacity->set(uedge, (*_capacity)[it]); + + } + + if (!_heap_cross_ref) { + local_heap_cross_ref = true; + _heap_cross_ref = Traits::createHeapCrossRef(*_aux_graph); + } + if (!_heap) { + local_heap = true; + _heap = Traits::createHeap(*_heap_cross_ref); + } + } + + public : + + typedef NagamochiIbaraki Create; + + + /// \brief Constructor. + /// + ///\param graph the graph the algorithm will run on. + ///\param capacity the capacity map used by the algorithm. + NagamochiIbaraki(const Graph& graph, const CapacityMap& capacity) + : _graph(&graph), + _capacity(&capacity), local_capacity(false), + _aux_graph(0), local_aux_graph(false), + _aux_capacity(0), local_aux_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. + NagamochiIbaraki(const Graph& graph) + : _graph(&graph), + _capacity(0), local_capacity(false), + _aux_graph(0), local_aux_graph(false), + _aux_capacity(0), local_aux_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. + ~NagamochiIbaraki() { + 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_aux_capacity) delete _aux_capacity; + if (local_aux_graph) delete _aux_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) + NagamochiIbaraki &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 aux graph. + /// + /// Sets the aux 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) + NagamochiIbaraki &auxGraph(AuxGraph& aux_graph) + { + if(local_aux_graph) { + delete _aux_graph; + local_aux_graph=false; + } + _aux_graph = &aux_graph; + return *this; + } + + /// \brief Sets the aux capacity map. + /// + /// Sets the aux 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) + NagamochiIbaraki &auxCapacityMap(AuxCapacityMap& aux_capacity_map) + { + if(local_aux_capacity) { + delete _aux_capacity; + local_aux_capacity=false; + } + _aux_capacity = &aux_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 min cut in the graph. The + /// + ///\return %True when the algorithm finished. + bool processNextPhase() { + if (_node_num <= 1) return true; + using namespace _min_cut_bits; + + typedef typename AuxGraph::Node Node; + typedef typename AuxGraph::NodeIt NodeIt; + typedef typename AuxGraph::UEdge UEdge; + typedef typename AuxGraph::IncEdgeIt IncEdgeIt; + + typedef typename MaxCardinalitySearch:: + template DefHeap:: + template DefCardinalityMap >:: + template DefProcessedMap >:: + Create MaxCardinalitySearch; + + MaxCardinalitySearch mcs(*_aux_graph, *_aux_capacity); + for (NodeIt it(*_aux_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 = _aux_graph->addNode(); + + typename AuxGraph::template NodeMap edges(*_aux_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(*_aux_graph, first_node); it != INVALID; ++it) { + Node node = _aux_graph->runningNode(it); + current_cut += (*_aux_capacity)[it]; + if (node == second_node) continue; + if (edges[node] == INVALID) { + edges[node] = _aux_graph->addEdge(new_node, node); + (*_aux_capacity)[edges[node]] = (*_aux_capacity)[it]; + } else { + (*_aux_capacity)[edges[node]] += (*_aux_capacity)[it]; + } + } + + if (_first_node == INVALID || current_cut < _min_cut) { + _first_node = (*_first)[first_node]; + _last_node = (*_last)[first_node]; + _min_cut = current_cut; + } + + _aux_graph->erase(first_node); + + for (IncEdgeIt it(*_aux_graph, second_node); it != INVALID; ++it) { + Node node = _aux_graph->runningNode(it); + if (edges[node] == INVALID) { + edges[node] = _aux_graph->addEdge(new_node, node); + (*_aux_capacity)[edges[node]] = (*_aux_capacity)[it]; + } else { + (*_aux_capacity)[edges[node]] += (*_aux_capacity)[it]; + } + } + _aux_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 %NagamochiIbaraki algorithm. + /// + /// This method runs the %Min 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 %NagamochiIbaraki + /// algorithm can be obtained using these functions.\n + /// Before the use of these functions, either run() or start() + /// must be called. + + ///@{ + + /// \brief Returns the min cut value. + /// + /// Returns the min 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 _min_cut; + } + + /// \brief Returns a min 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 set 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 min 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 min cut in an EdgeMap. + /// + /// If an undirected edge is in a min cut then it will be + /// set to true and the others will be set 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