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