COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/min_cut.h @ 2242:16523135943d

Last change on this file since 2242:16523135943d was 2225:bb3d5e6f9fcb, checked in by Balazs Dezso, 13 years ago

Doc fix

File size: 43.9 KB
Line 
1/* -*- C++ -*-
2 * lemon/min_cut.h - Part of LEMON, a generic C++ optimization library
3 *
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Research Group on Combinatorial Optimization, EGRES).
6 *
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
10 *
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
13 * purpose.
14 *
15 */
16
17#ifndef LEMON_MIN_CUT_H
18#define LEMON_MIN_CUT_H
19
20
21/// \ingroup topology
22/// \file
23/// \brief Maximum cardinality search and min cut in undirected graphs.
24
25#include <lemon/list_graph.h>
26#include <lemon/bin_heap.h>
27#include <lemon/bucket_heap.h>
28
29#include <lemon/bits/invalid.h>
30#include <lemon/error.h>
31#include <lemon/maps.h>
32
33#include <functional>
34
35namespace lemon {
36
37  namespace _min_cut_bits {
38
39    template <typename CapacityMap>
40    struct HeapSelector {
41      template <typename Key, typename Value, typename Ref>
42      struct Selector {
43        typedef BinHeap<Key, Value, Ref, std::greater<Value> > Heap;
44      };
45    };
46
47    template <typename CapacityKey>
48    struct HeapSelector<ConstMap<CapacityKey, Const<int, 1> > > {
49      template <typename Key, typename Value, typename Ref>
50      struct Selector {
51        typedef BucketHeap<Key, Ref, false > Heap;
52      };
53    };
54
55  }
56
57  /// \brief Default traits class of MaxCardinalitySearch class.
58  ///
59  /// Default traits class of MaxCardinalitySearch class.
60  /// \param Graph Graph type.
61  /// \param CapacityMap Type of length map.
62  template <typename _Graph, typename _CapacityMap>
63  struct MaxCardinalitySearchDefaultTraits {
64    /// The graph type the algorithm runs on.
65    typedef _Graph Graph;
66
67    /// \brief The type of the map that stores the edge capacities.
68    ///
69    /// The type of the map that stores the edge capacities.
70    /// It must meet the \ref concept::ReadMap "ReadMap" concept.
71    typedef _CapacityMap CapacityMap;
72
73    /// \brief The type of the capacity of the edges.
74    typedef typename CapacityMap::Value Value;
75
76    /// \brief The cross reference type used by heap.
77    ///
78    /// The cross reference type used by heap.
79    /// Usually it is \c Graph::NodeMap<int>.
80    typedef typename Graph::template NodeMap<int> HeapCrossRef;
81
82    /// \brief Instantiates a HeapCrossRef.
83    ///
84    /// This function instantiates a \ref HeapCrossRef.
85    /// \param graph is the graph, to which we would like to define the
86    /// HeapCrossRef.
87    static HeapCrossRef *createHeapCrossRef(const Graph &graph) {
88      return new HeapCrossRef(graph);
89    }
90   
91    /// \brief The heap type used by MaxCardinalitySearch algorithm.
92    ///
93    /// The heap type used by MaxCardinalitySearch algorithm. It should
94    /// maximalize the priorities. The default heap type is
95    /// the \ref BinHeap, but it is specialized when the
96    /// CapacityMap is ConstMap<Graph::Node, Const<int, 1> >
97    /// to BucketHeap.
98    ///
99    /// \sa MaxCardinalitySearch
100    typedef typename _min_cut_bits
101    ::HeapSelector<CapacityMap>
102    ::template Selector<typename Graph::Node, Value, HeapCrossRef>
103    ::Heap Heap;
104
105    /// \brief Instantiates a Heap.
106    ///
107    /// This function instantiates a \ref Heap.
108    /// \param crossref The cross reference of the heap.
109    static Heap *createHeap(HeapCrossRef& crossref) {
110      return new Heap(crossref);
111    }
112
113    /// \brief The type of the map that stores whether a nodes is processed.
114    ///
115    /// The type of the map that stores whether a nodes is processed.
116    /// It must meet the \ref concept::WriteMap "WriteMap" concept.
117    /// By default it is a NullMap.
118    typedef NullMap<typename Graph::Node, bool> ProcessedMap;
119
120    /// \brief Instantiates a ProcessedMap.
121    ///
122    /// This function instantiates a \ref ProcessedMap.
123    /// \param graph is the graph, to which
124    /// we would like to define the \ref ProcessedMap
125#ifdef DOXYGEN
126    static ProcessedMap *createProcessedMap(const Graph &graph)
127#else
128    static ProcessedMap *createProcessedMap(const Graph &)
129#endif
130    {
131      return new ProcessedMap();
132    }
133
134    /// \brief The type of the map that stores the cardinalties of the nodes.
135    ///
136    /// The type of the map that stores the cardinalities of the nodes.
137    /// It must meet the \ref concept::WriteMap "WriteMap" concept.
138    typedef typename Graph::template NodeMap<Value> CardinalityMap;
139
140    /// \brief Instantiates a CardinalityMap.
141    ///
142    /// This function instantiates a \ref CardinalityMap.
143    /// \param graph is the graph, to which we would like to define the \ref
144    /// CardinalityMap
145    static CardinalityMap *createCardinalityMap(const Graph &graph) {
146      return new CardinalityMap(graph);
147    }
148
149  };
150 
151  /// \ingroup topology
152  ///
153  /// \brief Maximum Cardinality Search algorithm class.
154  ///
155  /// This class provides an efficient implementation of Maximum Cardinality
156  /// Search algorithm. The maximum cardinality search chooses first time any
157  /// node of the graph. Then every time it chooses the node which is connected
158  /// to the processed nodes at most in the sum of capacities on the out
159  /// edges. If there is a cut in the graph the algorithm should choose
160  /// again any unprocessed node of the graph. Each node cardinality is
161  /// the sum of capacities on the out edges to the nodes which are processed
162  /// before the given node.
163  ///
164  /// The edge capacities are passed to the algorithm using a
165  /// \ref concept::ReadMap "ReadMap", so it is easy to change it to any
166  /// kind of capacity.
167  ///
168  /// The type of the capacity is determined by the \ref
169  /// concept::ReadMap::Value "Value" of the capacity map.
170  ///
171  /// It is also possible to change the underlying priority heap.
172  ///
173  ///
174  /// \param _Graph The graph type the algorithm runs on. The default value
175  /// is \ref ListGraph. The value of Graph is not used directly by
176  /// the search algorithm, it is only passed to
177  /// \ref MaxCardinalitySearchDefaultTraits.
178  /// \param _CapacityMap This read-only EdgeMap determines the capacities of
179  /// the edges. It is read once for each edge, so the map may involve in
180  /// relatively time consuming process to compute the edge capacity if
181  /// it is necessary. The default map type is \ref
182  /// concept::Graph::EdgeMap "Graph::EdgeMap<int>".  The value
183  /// of CapacityMap is not used directly by search algorithm, it is only
184  /// passed to \ref MaxCardinalitySearchDefaultTraits. 
185  /// \param _Traits Traits class to set various data types used by the
186  /// algorithm.  The default traits class is
187  /// \ref MaxCardinalitySearchDefaultTraits
188  /// "MaxCardinalitySearchDefaultTraits<_Graph, _CapacityMap>". 
189  /// See \ref MaxCardinalitySearchDefaultTraits
190  /// for the documentation of a MaxCardinalitySearch traits class.
191  ///
192  /// \author Balazs Dezso
193
194#ifdef DOXYGEN
195  template <typename _Graph, typename _CapacityMap, typename _Traits>
196#else
197  template <typename _Graph = ListUGraph,
198            typename _CapacityMap = typename _Graph::template EdgeMap<int>,
199            typename _Traits =
200            MaxCardinalitySearchDefaultTraits<_Graph, _CapacityMap> >
201#endif
202  class MaxCardinalitySearch {
203  public:
204    /// \brief \ref Exception for uninitialized parameters.
205    ///
206    /// This error represents problems in the initialization
207    /// of the parameters of the algorithms.
208    class UninitializedParameter : public lemon::UninitializedParameter {
209    public:
210      virtual const char* what() const throw() {
211        return "lemon::MaxCardinalitySearch::UninitializedParameter";
212      }
213    };
214
215    typedef _Traits Traits;
216    ///The type of the underlying graph.
217    typedef typename Traits::Graph Graph;
218   
219    ///The type of the capacity of the edges.
220    typedef typename Traits::CapacityMap::Value Value;
221    ///The type of the map that stores the edge capacities.
222    typedef typename Traits::CapacityMap CapacityMap;
223    ///The type of the map indicating if a node is processed.
224    typedef typename Traits::ProcessedMap ProcessedMap;
225    ///The type of the map that stores the cardinalities of the nodes.
226    typedef typename Traits::CardinalityMap CardinalityMap;
227    ///The cross reference type used for the current heap.
228    typedef typename Traits::HeapCrossRef HeapCrossRef;
229    ///The heap type used by the algorithm. It maximize the priorities.
230    typedef typename Traits::Heap Heap;
231  private:
232    /// Pointer to the underlying graph.
233    const Graph *_graph;
234    /// Pointer to the capacity map
235    const CapacityMap *_capacity;
236    ///Pointer to the map of cardinality.
237    CardinalityMap *_cardinality;
238    ///Indicates if \ref _cardinality is locally allocated (\c true) or not.
239    bool local_cardinality;
240    ///Pointer to the map of processed status of the nodes.
241    ProcessedMap *_processed;
242    ///Indicates if \ref _processed is locally allocated (\c true) or not.
243    bool local_processed;
244    ///Pointer to the heap cross references.
245    HeapCrossRef *_heap_cross_ref;
246    ///Indicates if \ref _heap_cross_ref is locally allocated (\c true) or not.
247    bool local_heap_cross_ref;
248    ///Pointer to the heap.
249    Heap *_heap;
250    ///Indicates if \ref _heap is locally allocated (\c true) or not.
251    bool local_heap;
252
253  public :
254
255    typedef MaxCardinalitySearch Create;
256 
257    ///\name Named template parameters
258
259    ///@{
260
261    template <class T>
262    struct DefCardinalityMapTraits : public Traits {
263      typedef T CardinalityMap;
264      static CardinalityMap *createCardinalityMap(const Graph &)
265      {
266        throw UninitializedParameter();
267      }
268    };
269    /// \brief \ref named-templ-param "Named parameter" for setting
270    /// CardinalityMap type
271    ///
272    /// \ref named-templ-param "Named parameter" for setting CardinalityMap
273    /// type
274    template <class T>
275    struct DefCardinalityMap
276      : public MaxCardinalitySearch<Graph, CapacityMap,
277                                    DefCardinalityMapTraits<T> > {
278      typedef MaxCardinalitySearch<Graph, CapacityMap,
279                                   DefCardinalityMapTraits<T> > Create;
280    };
281   
282    template <class T>
283    struct DefProcessedMapTraits : public Traits {
284      typedef T ProcessedMap;
285      static ProcessedMap *createProcessedMap(const Graph &) {
286        throw UninitializedParameter();
287      }
288    };
289    /// \brief \ref named-templ-param "Named parameter" for setting
290    /// ProcessedMap type
291    ///
292    /// \ref named-templ-param "Named parameter" for setting ProcessedMap type
293    ///
294    template <class T>
295    struct DefProcessedMap
296      : public MaxCardinalitySearch<Graph, CapacityMap,
297                                    DefProcessedMapTraits<T> > {
298      typedef MaxCardinalitySearch<Graph, CapacityMap,
299                                   DefProcessedMapTraits<T> > Create;
300    };
301   
302    template <class H, class CR>
303    struct DefHeapTraits : public Traits {
304      typedef CR HeapCrossRef;
305      typedef H Heap;
306      static HeapCrossRef *createHeapCrossRef(const Graph &) {
307        throw UninitializedParameter();
308      }
309      static Heap *createHeap(HeapCrossRef &) {
310        throw UninitializedParameter();
311      }
312    };
313    /// \brief \ref named-templ-param "Named parameter" for setting heap
314    /// and cross reference type
315    ///
316    /// \ref named-templ-param "Named parameter" for setting heap and cross
317    /// reference type
318    template <class H, class CR = typename Graph::template NodeMap<int> >
319    struct DefHeap
320      : public MaxCardinalitySearch<Graph, CapacityMap,
321                                    DefHeapTraits<H, CR> > {
322      typedef MaxCardinalitySearch< Graph, CapacityMap,
323                                    DefHeapTraits<H, CR> > Create;
324    };
325
326    template <class H, class CR>
327    struct DefStandardHeapTraits : public Traits {
328      typedef CR HeapCrossRef;
329      typedef H Heap;
330      static HeapCrossRef *createHeapCrossRef(const Graph &graph) {
331        return new HeapCrossRef(graph);
332      }
333      static Heap *createHeap(HeapCrossRef &crossref) {
334        return new Heap(crossref);
335      }
336    };
337
338    /// \brief \ref named-templ-param "Named parameter" for setting heap and
339    /// cross reference type with automatic allocation
340    ///
341    /// \ref named-templ-param "Named parameter" for setting heap and cross
342    /// reference type. It can allocate the heap and the cross reference
343    /// object if the cross reference's constructor waits for the graph as
344    /// parameter and the heap's constructor waits for the cross reference.
345    template <class H, class CR = typename Graph::template NodeMap<int> >
346    struct DefStandardHeap
347      : public MaxCardinalitySearch<Graph, CapacityMap,
348                                    DefStandardHeapTraits<H, CR> > {
349      typedef MaxCardinalitySearch<Graph, CapacityMap,
350                                   DefStandardHeapTraits<H, CR> >
351      Create;
352    };
353   
354    ///@}
355
356
357  protected:
358
359    MaxCardinalitySearch() {}
360
361  public:     
362   
363    /// \brief Constructor.
364    ///
365    ///\param graph the graph the algorithm will run on.
366    ///\param capacity the capacity map used by the algorithm.
367    MaxCardinalitySearch(const Graph& graph, const CapacityMap& capacity) :
368      _graph(&graph), _capacity(&capacity),
369      _cardinality(0), local_cardinality(false),
370      _processed(0), local_processed(false),
371      _heap_cross_ref(0), local_heap_cross_ref(false),
372      _heap(0), local_heap(false)
373    { }
374   
375    /// \brief Destructor.
376    ~MaxCardinalitySearch() {
377      if(local_cardinality) delete _cardinality;
378      if(local_processed) delete _processed;
379      if(local_heap_cross_ref) delete _heap_cross_ref;
380      if(local_heap) delete _heap;
381    }
382
383    /// \brief Sets the capacity map.
384    ///
385    /// Sets the capacity map.
386    /// \return <tt> (*this) </tt>
387    MaxCardinalitySearch &capacityMap(const CapacityMap &m) {
388      _capacity = &m;
389      return *this;
390    }
391
392    /// \brief Sets the map storing the cardinalities calculated by the
393    /// algorithm.
394    ///
395    /// Sets the map storing the cardinalities calculated by the algorithm.
396    /// If you don't use this function before calling \ref run(),
397    /// it will allocate one. The destuctor deallocates this
398    /// automatically allocated map, of course.
399    /// \return <tt> (*this) </tt>
400    MaxCardinalitySearch &cardinalityMap(CardinalityMap &m) {
401      if(local_cardinality) {
402        delete _cardinality;
403        local_cardinality=false;
404      }
405      _cardinality = &m;
406      return *this;
407    }
408
409    /// \brief Sets the map storing the processed nodes.
410    ///
411    /// Sets the map storing the processed nodes.
412    /// If you don't use this function before calling \ref run(),
413    /// it will allocate one. The destuctor deallocates this
414    /// automatically allocated map, of course.
415    /// \return <tt> (*this) </tt>
416    MaxCardinalitySearch &processedMap(ProcessedMap &m)
417    {
418      if(local_processed) {
419        delete _processed;
420        local_processed=false;
421      }
422      _processed = &m;
423      return *this;
424    }
425
426    /// \brief Sets the heap and the cross reference used by algorithm.
427    ///
428    /// Sets the heap and the cross reference used by algorithm.
429    /// If you don't use this function before calling \ref run(),
430    /// it will allocate one. The destuctor deallocates this
431    /// automatically allocated map, of course.
432    /// \return <tt> (*this) </tt>
433    MaxCardinalitySearch &heap(Heap& heap, HeapCrossRef &crossRef) {
434      if(local_heap_cross_ref) {
435        delete _heap_cross_ref;
436        local_heap_cross_ref = false;
437      }
438      _heap_cross_ref = &crossRef;
439      if(local_heap) {
440        delete _heap;
441        local_heap = false;
442      }
443      _heap = &heap;
444      return *this;
445    }
446
447  private:
448
449    typedef typename Graph::Node Node;
450    typedef typename Graph::NodeIt NodeIt;
451    typedef typename Graph::Edge Edge;
452    typedef typename Graph::InEdgeIt InEdgeIt;
453
454    void create_maps() {
455      if(!_cardinality) {
456        local_cardinality = true;
457        _cardinality = Traits::createCardinalityMap(*_graph);
458      }
459      if(!_processed) {
460        local_processed = true;
461        _processed = Traits::createProcessedMap(*_graph);
462      }
463      if (!_heap_cross_ref) {
464        local_heap_cross_ref = true;
465        _heap_cross_ref = Traits::createHeapCrossRef(*_graph);
466      }
467      if (!_heap) {
468        local_heap = true;
469        _heap = Traits::createHeap(*_heap_cross_ref);
470      }
471    }
472   
473    void finalizeNodeData(Node node, Value capacity) {
474      _processed->set(node, true);
475      _cardinality->set(node, capacity);
476    }
477
478  public:
479    /// \name Execution control
480    /// The simplest way to execute the algorithm is to use
481    /// one of the member functions called \c run(...).
482    /// \n
483    /// If you need more control on the execution,
484    /// first you must call \ref init(), then you can add several source nodes
485    /// with \ref addSource().
486    /// Finally \ref start() will perform the actual path
487    /// computation.
488
489    ///@{
490
491    /// \brief Initializes the internal data structures.
492    ///
493    /// Initializes the internal data structures.
494    void init() {
495      create_maps();
496      _heap->clear();
497      for (NodeIt it(*_graph) ; it != INVALID ; ++it) {
498        _processed->set(it, false);
499        _heap_cross_ref->set(it, Heap::PRE_HEAP);
500      }
501    }
502   
503    /// \brief Adds a new source node.
504    ///
505    /// Adds a new source node to the priority heap.
506    ///
507    /// It checks if the node has not yet been added to the heap.
508    void addSource(Node source, Value capacity = 0) {
509      if(_heap->state(source) == Heap::PRE_HEAP) {
510        _heap->push(source, capacity);
511      }
512    }
513   
514    /// \brief Processes the next node in the priority heap
515    ///
516    /// Processes the next node in the priority heap.
517    ///
518    /// \return The processed node.
519    ///
520    /// \warning The priority heap must not be empty!
521    Node processNextNode() {
522      Node node = _heap->top();
523      finalizeNodeData(node, _heap->prio());
524      _heap->pop();
525     
526      for (InEdgeIt it(*_graph, node); it != INVALID; ++it) {
527        Node source = _graph->source(it);
528        switch (_heap->state(source)) {
529        case Heap::PRE_HEAP:
530          _heap->push(source, (*_capacity)[it]);
531          break;
532        case Heap::IN_HEAP:
533          _heap->decrease(source, (*_heap)[source] + (*_capacity)[it]);
534          break;
535        case Heap::POST_HEAP:
536          break;
537        }
538      }
539      return node;
540    }
541
542    /// \brief Next node to be processed.
543    ///
544    /// Next node to be processed.
545    ///
546    /// \return The next node to be processed or INVALID if the
547    /// priority heap is empty.
548    Node nextNode() {
549      return _heap->empty() ? _heap->top() : INVALID;
550    }
551 
552    /// \brief Returns \c false if there are nodes
553    /// to be processed in the priority heap
554    ///
555    /// Returns \c false if there are nodes
556    /// to be processed in the priority heap
557    bool emptyQueue() { return _heap->empty(); }
558    /// \brief Returns the number of the nodes to be processed
559    /// in the priority heap
560    ///
561    /// Returns the number of the nodes to be processed in the priority heap
562    int queueSize() { return _heap->size(); }
563   
564    /// \brief Executes the algorithm.
565    ///
566    /// Executes the algorithm.
567    ///
568    ///\pre init() must be called and at least one node should be added
569    /// with addSource() before using this function.
570    ///
571    /// This method runs the Maximum Cardinality Search algorithm from the
572    /// source node(s).
573    void start() {
574      while ( !_heap->empty() ) processNextNode();
575    }
576   
577    /// \brief Executes the algorithm until \c dest is reached.
578    ///
579    /// Executes the algorithm until \c dest is reached.
580    ///
581    /// \pre init() must be called and at least one node should be added
582    /// with addSource() before using this function.
583    ///
584    /// This method runs the %MaxCardinalitySearch algorithm from the source
585    /// nodes.
586    void start(Node dest) {
587      while ( !_heap->empty() && _heap->top()!=dest ) processNextNode();
588      if ( !_heap->empty() ) finalizeNodeData(_heap->top(), _heap->prio());
589    }
590   
591    /// \brief Executes the algorithm until a condition is met.
592    ///
593    /// Executes the algorithm until a condition is met.
594    ///
595    /// \pre init() must be called and at least one node should be added
596    /// with addSource() before using this function.
597    ///
598    /// \param nm must be a bool (or convertible) node map. The algorithm
599    /// will stop when it reaches a node \c v with <tt>nm[v]==true</tt>.
600    template <typename NodeBoolMap>
601    void start(const NodeBoolMap &nm) {
602      while ( !_heap->empty() && !nm[_heap->top()] ) processNextNode();
603      if ( !_heap->empty() ) finalizeNodeData(_heap->top(),_heap->prio());
604    }
605   
606    /// \brief Runs the maximal cardinality search algorithm from node \c s.
607    ///
608    /// This method runs the %MaxCardinalitySearch algorithm from a root
609    /// node \c s.
610    ///
611    ///\note d.run(s) is just a shortcut of the following code.
612    ///\code
613    ///  d.init();
614    ///  d.addSource(s);
615    ///  d.start();
616    ///\endcode
617    void run(Node s) {
618      init();
619      addSource(s);
620      start();
621    }
622
623    /// \brief Runs the maximal cardinality search algorithm for the
624    /// whole graph.
625    ///
626    /// This method runs the %MaxCardinalitySearch algorithm from all
627    /// unprocessed node of the graph.
628    ///
629    ///\note d.run(s) is just a shortcut of the following code.
630    ///\code
631    ///  d.init();
632    ///  for (NodeIt it(graph); it != INVALID; ++it) {
633    ///    if (!d.reached(it)) {
634    ///      d.addSource(s);
635    ///      d.start();
636    ///    }
637    ///  }
638    ///\endcode
639    void run() {
640      init();
641      for (NodeIt it(*_graph); it != INVALID; ++it) {
642        if (!reached(it)) {
643          addSource(it);
644          start();
645        }
646      }
647    }
648   
649    ///@}
650
651    /// \name Query Functions
652    /// The result of the maximum cardinality search algorithm can be
653    /// obtained using these functions.
654    /// \n
655    /// Before the use of these functions, either run() or start() must be
656    /// called.
657   
658    ///@{
659
660    /// \brief The cardinality of a node.
661    ///
662    /// Returns the cardinality of a node.
663    /// \pre \ref run() must be called before using this function.
664    /// \warning If node \c v in unreachable from the root the return value
665    /// of this funcion is undefined.
666    Value cardinality(Node node) const { return (*_cardinality)[node]; }
667
668    /// \brief Returns a reference to the NodeMap of cardinalities.
669    ///
670    /// Returns a reference to the NodeMap of cardinalities. \pre \ref run()
671    /// must be called before using this function.
672    const CardinalityMap &cardinalityMap() const { return *_cardinality;}
673 
674    /// \brief Checks if a node is reachable from the root.
675    ///
676    /// Returns \c true if \c v is reachable from the root.
677    /// \warning The source nodes are inditated as unreached.
678    /// \pre \ref run() must be called before using this function.
679    bool reached(Node v) { return (*_heap_cross_ref)[v] != Heap::PRE_HEAP; }
680
681    /// \brief Checks if a node is processed.
682    ///
683    /// Returns \c true if \c v is processed, i.e. the shortest
684    /// path to \c v has already found.
685    /// \pre \ref run() must be called before using this function.
686    bool processed(Node v) { return (*_heap_cross_ref)[v] == Heap::POST_HEAP; }
687   
688    ///@}
689  };
690
691  /// \brief Default traits class of MinCut class.
692  ///
693  /// Default traits class of MinCut class.
694  /// \param Graph Graph type.
695  /// \param CapacityMap Type of length map.
696  template <typename _Graph, typename _CapacityMap>
697  struct MinCutDefaultTraits {
698    /// \brief The type of the capacity of the edges.
699    typedef typename _CapacityMap::Value Value;
700
701    /// The graph type the algorithm runs on.
702    typedef _Graph Graph;
703
704    /// The AuxGraph type which is an Graph
705    typedef ListUGraph AuxGraph;
706
707    /// \brief Instantiates a AuxGraph.
708    ///
709    /// This function instantiates a \ref AuxGraph.
710    static AuxGraph *createAuxGraph() {
711      return new AuxGraph();
712    }
713
714    /// \brief The type of the map that stores the edge capacities.
715    ///
716    /// The type of the map that stores the edge capacities.
717    /// It must meet the \ref concept::ReadMap "ReadMap" concept.
718    typedef _CapacityMap CapacityMap;
719
720    /// \brief Instantiates a CapacityMap.
721    ///
722    /// This function instantiates a \ref CapacityMap.
723#ifdef DOXYGEN
724    static CapacityMap *createCapacityMap(const Graph& graph)
725#else
726    static CapacityMap *createCapacityMap(const Graph&)
727#endif
728    {
729      throw UninitializedParameter();
730    }
731
732    /// \brief The AuxCapacityMap type
733    ///
734    /// The type of the map that stores the auxing edge capacities.
735    typedef AuxGraph::UEdgeMap<Value> AuxCapacityMap;
736
737    /// \brief Instantiates a AuxCapacityMap.
738    ///
739    /// This function instantiates a \ref AuxCapacityMap.
740    static AuxCapacityMap *createAuxCapacityMap(const AuxGraph& graph) {
741      return new AuxCapacityMap(graph);
742    }
743
744    /// \brief The cross reference type used by heap.
745    ///
746    /// The cross reference type used by heap.
747    /// Usually it is \c Graph::NodeMap<int>.
748    typedef AuxGraph::NodeMap<int> HeapCrossRef;
749
750    /// \brief Instantiates a HeapCrossRef.
751    ///
752    /// This function instantiates a \ref HeapCrossRef.
753    /// \param graph is the graph, to which we would like to define the
754    /// HeapCrossRef.
755    static HeapCrossRef *createHeapCrossRef(const AuxGraph &graph) {
756      return new HeapCrossRef(graph);
757    }
758   
759    /// \brief The heap type used by MinCut algorithm.
760    ///
761    /// The heap type used by MinCut algorithm. It should
762    /// maximalize the priorities and the heap's key type is
763    /// the aux graph's node.
764    ///
765    /// \sa BinHeap
766    /// \sa MinCut
767    typedef typename _min_cut_bits
768    ::HeapSelector<CapacityMap>
769    ::template Selector<typename AuxGraph::Node, Value, HeapCrossRef>
770    ::Heap Heap;
771   
772    /// \brief Instantiates a Heap.
773    ///
774    /// This function instantiates a \ref Heap.
775    /// \param crossref The cross reference of the heap.
776    static Heap *createHeap(HeapCrossRef& crossref) {
777      return new Heap(crossref);
778    }
779
780    /// \brief Map from the AuxGraph's node type to the Graph's node type.
781    ///
782    /// Map from the AuxGraph's node type to the Graph's node type.
783    typedef typename AuxGraph
784    ::template NodeMap<typename Graph::Node> NodeRefMap;
785
786    /// \brief Instantiates a NodeRefMap.
787    ///
788    /// This function instantiates a \ref NodeRefMap.
789    static NodeRefMap *createNodeRefMap(const AuxGraph& graph) {
790      return new NodeRefMap(graph);
791    }
792
793    /// \brief Map from the Graph's node type to the Graph's node type.
794    ///
795    /// Map from the Graph's node type to the Graph's node type.
796    typedef typename Graph
797    ::template NodeMap<typename Graph::Node> ListRefMap;
798
799    /// \brief Instantiates a ListRefMap.
800    ///
801    /// This function instantiates a \ref ListRefMap.
802    static ListRefMap *createListRefMap(const Graph& graph) {
803      return new ListRefMap(graph);
804    }
805   
806
807  };
808
809  namespace _min_cut_bits {
810    template <typename _Key>
811    class LastTwoMap {
812    public:
813      typedef _Key Key;
814      typedef bool Value;
815
816      LastTwoMap(int _num) : num(_num) {}
817      void set(const Key& key, bool val) {
818        if (!val) return;
819        --num;
820        if (num > 1) return;
821        keys[num] = key;
822      }
823     
824      Key operator[](int index) const { return keys[index]; }
825    private:
826      Key keys[2];
827      int num;
828    };
829  }
830
831  /// \ingroup topology
832  ///
833  /// \brief Calculates the minimum cut in an undirected graph.
834  ///
835  /// Calculates the minimum cut in an undirected graph with the
836  /// Nagamochi-Ibaraki algorithm. The algorithm separates the graph's
837  /// nodes into two partitions with the minimum sum of edge capacities
838  /// between the two partitions. The algorithm can be used to test
839  /// the network reliability specifically to test how many links have
840  /// to be destroyed in the network to split it at least two
841  /// distinict subnetwork.
842  ///
843  /// The complexity of the algorithm is \f$ O(ne\log(n)) \f$ but with
844  /// Fibonacci heap it can be decreased to \f$ O(ne+n^2\log(n))
845  /// \f$. When capacity map is neutral then it uses BucketHeap which
846  /// results \f$ O(ne) \f$ time complexity.
847#ifdef DOXYGEN
848  template <typename _Graph, typename _CapacityMap, typename _Traits>
849#else
850  template <typename _Graph = ListUGraph,
851            typename _CapacityMap = typename _Graph::template UEdgeMap<int>,
852            typename _Traits = MinCutDefaultTraits<_Graph, _CapacityMap> >
853#endif
854  class MinCut {
855  public:
856    /// \brief \ref Exception for uninitialized parameters.
857    ///
858    /// This error represents problems in the initialization
859    /// of the parameters of the algorithms.
860    class UninitializedParameter : public lemon::UninitializedParameter {
861    public:
862      virtual const char* what() const throw() {
863        return "lemon::MinCut::UninitializedParameter";
864      }
865    };
866
867
868  private:
869
870    typedef _Traits Traits;
871    /// The type of the underlying graph.
872    typedef typename Traits::Graph Graph;
873   
874    /// The type of the capacity of the edges.
875    typedef typename Traits::CapacityMap::Value Value;
876    /// The type of the map that stores the edge capacities.
877    typedef typename Traits::CapacityMap CapacityMap;
878    /// The type of the aux graph
879    typedef typename Traits::AuxGraph AuxGraph;
880    /// The type of the aux capacity map
881    typedef typename Traits::AuxCapacityMap AuxCapacityMap;
882    /// The cross reference type used for the current heap.
883    typedef typename Traits::HeapCrossRef HeapCrossRef;
884    /// The heap type used by the max cardinality algorithm.
885    typedef typename Traits::Heap Heap;
886    /// The node refrefernces between the original and aux graph type.
887    typedef typename Traits::NodeRefMap NodeRefMap;
888    /// The list node refrefernces in the original graph type.
889    typedef typename Traits::ListRefMap ListRefMap;
890
891  public:
892
893    ///\name Named template parameters
894
895    ///@{
896
897    struct DefNeutralCapacityTraits : public Traits {
898      typedef ConstMap<typename Graph::UEdge, Const<int, 1> > CapacityMap;
899      static CapacityMap *createCapacityMap(const Graph&) {
900        return new CapacityMap();
901      }
902    };
903    /// \brief \ref named-templ-param "Named parameter" for setting 
904    /// the capacity type to constMap<UEdge, int, 1>()
905    ///
906    /// \ref named-templ-param "Named parameter" for setting
907    /// the capacity type to constMap<UEdge, int, 1>()
908    struct DefNeutralCapacity
909      : public MinCut<Graph, CapacityMap, DefNeutralCapacityTraits> {
910      typedef MinCut<Graph, CapacityMap, DefNeutralCapacityTraits> Create;
911    };
912
913
914    template <class H, class CR>
915    struct DefHeapTraits : public Traits {
916      typedef CR HeapCrossRef;
917      typedef H Heap;
918      static HeapCrossRef *createHeapCrossRef(const AuxGraph &) {
919        throw UninitializedParameter();
920      }
921      static Heap *createHeap(HeapCrossRef &) {
922        throw UninitializedParameter();
923      }
924    };
925    /// \brief \ref named-templ-param "Named parameter" for setting heap
926    /// and cross reference type
927    ///
928    /// \ref named-templ-param "Named parameter" for setting heap and cross
929    /// reference type
930    template <class H, class CR = typename Graph::template NodeMap<int> >
931    struct DefHeap
932      : public MinCut<Graph, CapacityMap, DefHeapTraits<H, CR> > {
933      typedef MinCut< Graph, CapacityMap, DefHeapTraits<H, CR> > Create;
934    };
935
936    template <class H, class CR>
937    struct DefStandardHeapTraits : public Traits {
938      typedef CR HeapCrossRef;
939      typedef H Heap;
940      static HeapCrossRef *createHeapCrossRef(const AuxGraph &graph) {
941        return new HeapCrossRef(graph);
942      }
943      static Heap *createHeap(HeapCrossRef &crossref) {
944        return new Heap(crossref);
945      }
946    };
947
948    /// \brief \ref named-templ-param "Named parameter" for setting heap and
949    /// cross reference type with automatic allocation
950    ///
951    /// \ref named-templ-param "Named parameter" for setting heap and cross
952    /// reference type. It can allocate the heap and the cross reference
953    /// object if the cross reference's constructor waits for the graph as
954    /// parameter and the heap's constructor waits for the cross reference.
955    template <class H, class CR = typename Graph::template NodeMap<int> >
956    struct DefStandardHeap
957      : public MinCut<Graph, CapacityMap, DefStandardHeapTraits<H, CR> > {
958      typedef MinCut<Graph, CapacityMap, DefStandardHeapTraits<H, CR> >
959      Create;
960    };
961
962    ///@}
963
964
965  private:
966    /// Pointer to the underlying graph.
967    const Graph *_graph;
968    /// Pointer to the capacity map
969    const CapacityMap *_capacity;
970    /// \brief Indicates if \ref _capacity is locally allocated
971    /// (\c true) or not.
972    bool local_capacity;
973
974    /// Pointer to the aux graph.
975    AuxGraph *_aux_graph;
976    /// \brief Indicates if \ref _aux_graph is locally allocated
977    /// (\c true) or not.
978    bool local_aux_graph;
979    /// Pointer to the aux capacity map
980    AuxCapacityMap *_aux_capacity;
981    /// \brief Indicates if \ref _aux_capacity is locally allocated
982    /// (\c true) or not.
983    bool local_aux_capacity;
984    /// Pointer to the heap cross references.
985    HeapCrossRef *_heap_cross_ref;
986    /// \brief Indicates if \ref _heap_cross_ref is locally allocated
987    /// (\c true) or not.
988    bool local_heap_cross_ref;
989    /// Pointer to the heap.
990    Heap *_heap;
991    /// Indicates if \ref _heap is locally allocated (\c true) or not.
992    bool local_heap;
993
994    /// The min cut value.
995    Value _min_cut;
996    /// The number of the nodes of the aux graph.
997    int _node_num;
998    /// The first and last node of the min cut in the next list;
999    typename Graph::Node _first_node, _last_node;
1000
1001    /// \brief The first and last element in the list associated
1002    /// to the aux graph node.
1003    NodeRefMap *_first, *_last;
1004    /// \brief The next node in the node lists.
1005    ListRefMap *_next;
1006   
1007    void create_structures() {
1008      if (!_capacity) {
1009        local_capacity = true;
1010        _capacity = Traits::createCapacityMap(*_graph);
1011      }
1012      if(!_aux_graph) {
1013        local_aux_graph = true;
1014        _aux_graph = Traits::createAuxGraph();
1015      }
1016      if(!_aux_capacity) {
1017        local_aux_capacity = true;
1018        _aux_capacity = Traits::createAuxCapacityMap(*_aux_graph);
1019      }
1020
1021      _first = Traits::createNodeRefMap(*_aux_graph);
1022      _last = Traits::createNodeRefMap(*_aux_graph);
1023
1024      _next = Traits::createListRefMap(*_graph);
1025
1026      typename Graph::template NodeMap<typename AuxGraph::Node> ref(*_graph);
1027
1028      for (typename Graph::NodeIt it(*_graph); it != INVALID; ++it) {
1029        _next->set(it, INVALID);
1030        typename AuxGraph::Node node = _aux_graph->addNode();
1031        _first->set(node, it);
1032        _last->set(node, it);
1033        ref.set(it, node);
1034      }
1035
1036      for (typename Graph::UEdgeIt it(*_graph); it != INVALID; ++it) {
1037        if (_graph->source(it) == _graph->target(it)) continue;
1038        typename AuxGraph::UEdge uedge =
1039          _aux_graph->addEdge(ref[_graph->source(it)],
1040                               ref[_graph->target(it)]);
1041        _aux_capacity->set(uedge, (*_capacity)[it]);
1042       
1043      }
1044
1045      if (!_heap_cross_ref) {
1046        local_heap_cross_ref = true;
1047        _heap_cross_ref = Traits::createHeapCrossRef(*_aux_graph);
1048      }
1049      if (!_heap) {
1050        local_heap = true;
1051        _heap = Traits::createHeap(*_heap_cross_ref);
1052      }
1053    }
1054
1055  public :
1056
1057    typedef MinCut Create;
1058
1059
1060    /// \brief Constructor.
1061    ///
1062    ///\param graph the graph the algorithm will run on.
1063    ///\param capacity the capacity map used by the algorithm.
1064    MinCut(const Graph& graph, const CapacityMap& capacity)
1065      : _graph(&graph),
1066        _capacity(&capacity), local_capacity(false),
1067        _aux_graph(0), local_aux_graph(false),
1068        _aux_capacity(0), local_aux_capacity(false),
1069        _heap_cross_ref(0), local_heap_cross_ref(false),
1070        _heap(0), local_heap(false),
1071        _first(0), _last(0), _next(0) {}
1072
1073    /// \brief Constructor.
1074    ///
1075    /// This constructor can be used only when the Traits class
1076    /// defines how can we instantiate a local capacity map.
1077    /// If the DefNeutralCapacity used the algorithm automatically
1078    /// construct the capacity map.
1079    ///
1080    ///\param graph the graph the algorithm will run on.
1081    MinCut(const Graph& graph)
1082      : _graph(&graph),
1083        _capacity(0), local_capacity(false),
1084        _aux_graph(0), local_aux_graph(false),
1085        _aux_capacity(0), local_aux_capacity(false),
1086        _heap_cross_ref(0), local_heap_cross_ref(false),
1087        _heap(0), local_heap(false),
1088        _first(0), _last(0), _next(0) {}
1089
1090    /// \brief Destructor.
1091    ///
1092    /// Destructor.
1093    ~MinCut() {
1094      if (local_heap) delete _heap;
1095      if (local_heap_cross_ref) delete _heap_cross_ref;
1096      if (_first) delete _first;
1097      if (_last) delete _last;
1098      if (_next) delete _next;
1099      if (local_aux_capacity) delete _aux_capacity;
1100      if (local_aux_graph) delete _aux_graph;
1101      if (local_capacity) delete _capacity;
1102    }
1103
1104    /// \brief Sets the heap and the cross reference used by algorithm.
1105    ///
1106    /// Sets the heap and the cross reference used by algorithm.
1107    /// If you don't use this function before calling \ref run(),
1108    /// it will allocate one. The destuctor deallocates this
1109    /// automatically allocated heap and cross reference, of course.
1110    /// \return <tt> (*this) </tt>
1111    MinCut &heap(Heap& heap, HeapCrossRef &crossRef)
1112    {
1113      if (local_heap_cross_ref) {
1114        delete _heap_cross_ref;
1115        local_heap_cross_ref=false;
1116      }
1117      _heap_cross_ref = &crossRef;
1118      if (local_heap) {
1119        delete _heap;
1120        local_heap=false;
1121      }
1122      _heap = &heap;
1123      return *this;
1124    }
1125
1126    /// \brief Sets the aux graph.
1127    ///
1128    /// Sets the aux graph used by algorithm.
1129    /// If you don't use this function before calling \ref run(),
1130    /// it will allocate one. The destuctor deallocates this
1131    /// automatically allocated graph, of course.
1132    /// \return <tt> (*this) </tt>
1133    MinCut &auxGraph(AuxGraph& aux_graph)
1134    {
1135      if(local_aux_graph) {
1136        delete _aux_graph;
1137        local_aux_graph=false;
1138      }
1139      _aux_graph = &aux_graph;
1140      return *this;
1141    }
1142
1143    /// \brief Sets the aux capacity map.
1144    ///
1145    /// Sets the aux capacity map used by algorithm.
1146    /// If you don't use this function before calling \ref run(),
1147    /// it will allocate one. The destuctor deallocates this
1148    /// automatically allocated graph, of course.
1149    /// \return <tt> (*this) </tt>
1150    MinCut &auxCapacityMap(AuxCapacityMap& aux_capacity_map)
1151    {
1152      if(local_aux_capacity) {
1153        delete _aux_capacity;
1154        local_aux_capacity=false;
1155      }
1156      _aux_capacity = &aux_capacity_map;
1157      return *this;
1158    }
1159
1160    /// \name Execution control
1161    /// The simplest way to execute the algorithm is to use
1162    /// one of the member functions called \c run().
1163    /// \n
1164    /// If you need more control on the execution,
1165    /// first you must call \ref init() and then call the start()
1166    /// or proper times the processNextPhase() member functions.
1167
1168    ///@{
1169
1170    /// \brief Initializes the internal data structures.
1171    ///
1172    /// Initializes the internal data structures.
1173    void init() {
1174      create_structures();
1175      _first_node = _last_node = INVALID;
1176      _node_num = countNodes(*_graph);
1177    }
1178
1179    /// \brief Processes the next phase
1180    ///
1181    /// Processes the next phase in the algorithm. The function
1182    /// should be called countNodes(graph) - 1 times to get
1183    /// surely the min cut in the graph. The 
1184    ///
1185    ///\return %True when the algorithm finished.
1186    bool processNextPhase() {
1187      if (_node_num <= 1) return true;
1188      using namespace _min_cut_bits;
1189
1190      typedef typename AuxGraph::Node Node;
1191      typedef typename AuxGraph::NodeIt NodeIt;
1192      typedef typename AuxGraph::UEdge UEdge;
1193      typedef typename AuxGraph::IncEdgeIt IncEdgeIt;
1194     
1195      typedef typename MaxCardinalitySearch<AuxGraph, AuxCapacityMap>::
1196      template DefHeap<Heap, HeapCrossRef>::
1197      template DefCardinalityMap<NullMap<Node, Value> >::
1198      template DefProcessedMap<LastTwoMap<Node> >::
1199      Create MaxCardinalitySearch;
1200     
1201      MaxCardinalitySearch mcs(*_aux_graph, *_aux_capacity);
1202      for (NodeIt it(*_aux_graph); it != INVALID; ++it) {
1203        _heap_cross_ref->set(it, Heap::PRE_HEAP);
1204      }
1205      mcs.heap(*_heap, *_heap_cross_ref);
1206
1207      LastTwoMap<Node> last_two_nodes(_node_num);
1208      mcs.processedMap(last_two_nodes);
1209
1210      NullMap<Node, Value> cardinality;
1211      mcs.cardinalityMap(cardinality);
1212
1213      mcs.run();
1214
1215      Node new_node = _aux_graph->addNode();
1216
1217      typename AuxGraph::template NodeMap<UEdge> edges(*_aux_graph, INVALID);
1218     
1219      Node first_node = last_two_nodes[0];
1220      Node second_node = last_two_nodes[1];
1221     
1222      _next->set((*_last)[first_node], (*_first)[second_node]);
1223      _first->set(new_node, (*_first)[first_node]);
1224      _last->set(new_node, (*_last)[second_node]);
1225
1226      Value current_cut = 0;     
1227      for (IncEdgeIt it(*_aux_graph, first_node); it != INVALID; ++it) {
1228        Node node = _aux_graph->runningNode(it);
1229        current_cut += (*_aux_capacity)[it];
1230        if (node == second_node) continue;
1231        if (edges[node] == INVALID) {
1232          edges[node] = _aux_graph->addEdge(new_node, node);
1233          (*_aux_capacity)[edges[node]] = (*_aux_capacity)[it];
1234        } else {
1235          (*_aux_capacity)[edges[node]] += (*_aux_capacity)[it];         
1236        }
1237      }
1238
1239      if (_first_node == INVALID || current_cut < _min_cut) {
1240        _first_node = (*_first)[first_node];
1241        _last_node = (*_last)[first_node];
1242        _min_cut = current_cut;
1243      }
1244
1245      _aux_graph->erase(first_node);
1246
1247      for (IncEdgeIt it(*_aux_graph, second_node); it != INVALID; ++it) {
1248        Node node = _aux_graph->runningNode(it);
1249        if (edges[node] == INVALID) {
1250          edges[node] = _aux_graph->addEdge(new_node, node);
1251          (*_aux_capacity)[edges[node]] = (*_aux_capacity)[it];
1252        } else {
1253          (*_aux_capacity)[edges[node]] += (*_aux_capacity)[it];         
1254        }
1255      }
1256      _aux_graph->erase(second_node);
1257
1258      --_node_num;
1259      return _node_num == 1;
1260    }
1261
1262    /// \brief Executes the algorithm.
1263    ///
1264    /// Executes the algorithm.
1265    ///
1266    /// \pre init() must be called
1267    void start() {
1268      while (!processNextPhase());
1269    }
1270
1271
1272    /// \brief Runs %MinCut algorithm.
1273    ///
1274    /// This method runs the %Min cut algorithm
1275    ///
1276    /// \note mc.run(s) is just a shortcut of the following code.
1277    ///\code
1278    ///  mc.init();
1279    ///  mc.start();
1280    ///\endcode
1281    void run() {
1282      init();
1283      start();
1284    }
1285
1286    ///@}
1287
1288    /// \name Query Functions
1289    /// The result of the %MinCut algorithm can be obtained using these
1290    /// functions.\n
1291    /// Before the use of these functions,
1292    /// either run() or start() must be called.
1293   
1294    ///@{
1295
1296    /// \brief Returns the min cut value.
1297    ///
1298    /// Returns the min cut value if the algorithm finished.
1299    /// After the first processNextPhase() it is a value of a
1300    /// valid cut in the graph.
1301    Value minCut() const {
1302      return _min_cut;
1303    }
1304
1305    /// \brief Returns a min cut in a NodeMap.
1306    ///
1307    /// It sets the nodes of one of the two partitions to true in
1308    /// the given BoolNodeMap. The map contains a valid cut if the
1309    /// map have been set false previously.
1310    template <typename NodeMap>
1311    Value quickMinCut(NodeMap& nodeMap) const {
1312      for (typename Graph::Node it = _first_node;
1313           it != _last_node; it = (*_next)[it]) {
1314             nodeMap.set(it, true);
1315           }
1316      nodeMap.set(_last_node, true);
1317      return minCut();
1318    }
1319
1320    /// \brief Returns a min cut in a NodeMap.
1321    ///
1322    /// It sets the nodes of one of the two partitions to true and
1323    /// the other partition to false. The function first set all of the
1324    /// nodes to false and after it call the quickMinCut() member.
1325    template <typename NodeMap>
1326    Value minCut(NodeMap& nodeMap) const {
1327      for (typename Graph::NodeIt it(*_graph); it != INVALID; ++it) {
1328        nodeMap.set(it, false);     
1329      }
1330      quickMinCut(nodeMap);
1331      return minCut();
1332    }
1333
1334    /// \brief Returns a min cut in an EdgeMap.
1335    ///
1336    /// If an undirected edge is in a min cut then it will be
1337    /// set to true and the others will be set to false in the given map.
1338    template <typename EdgeMap>
1339    Value cutEdges(EdgeMap& edgeMap) const {
1340      typename Graph::template NodeMap<bool> cut(*_graph, false);
1341      quickMinCut(cut);
1342      for (typename Graph::EdgeIt it(*_graph); it != INVALID; ++it) {
1343        edgeMap.set(it, cut[_graph->source(it)] ^ cut[_graph->target(it)]);
1344      }
1345      return minCut();
1346    }
1347
1348    ///@}
1349
1350  };
1351}
1352
1353#endif
Note: See TracBrowser for help on using the repository browser.