COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/min_cut.h @ 2096:dbe860a83dc9

Last change on this file since 2096:dbe860a83dc9 was 2094:3ae02034be53, checked in by Alpar Juttner, 14 years ago

Spellcheck

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::StaticGraph::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* exceptionName() const {
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 ErasableGraph
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 min cut in an undirected graph.
834  ///
835  /// Calculates the min cut in an undirected graph.
836  /// The algorithm separates the graph's nodes to two partitions with the
837  /// min sum of edge capacities between the two partitions. The
838  /// algorithm can be used to test the netaux reliability specifically
839  /// to test how many links have to be destroyed in the netaux to split it
840  /// at least two distinict subnetaux.
841  ///
842  /// The complexity of the algorithm is \f$ O(ne\log(n)) \f$ but with
843  /// Fibonacci heap it can be decreased to \f$ O(ne+n^2\log(n)) \f$. When
844  /// the neutral capacity map is used then it uses BucketHeap which
845  /// results \f$ O(ne) \f$ time complexity.
846#ifdef DOXYGEN
847  template <typename _Graph, typename _CapacityMap, typename _Traits>
848#else
849  template <typename _Graph = ListUGraph,
850            typename _CapacityMap = typename _Graph::template UEdgeMap<int>,
851            typename _Traits = MinCutDefaultTraits<_Graph, _CapacityMap> >
852#endif
853  class MinCut {
854  public:
855    /// \brief \ref Exception for uninitialized parameters.
856    ///
857    /// This error represents problems in the initialization
858    /// of the parameters of the algorithms.
859    class UninitializedParameter : public lemon::UninitializedParameter {
860    public:
861      virtual const char* exceptionName() const {
862        return "lemon::MinCut::UninitializedParameter";
863      }
864    };
865
866
867  private:
868
869    typedef _Traits Traits;
870    /// The type of the underlying graph.
871    typedef typename Traits::Graph Graph;
872   
873    /// The type of the capacity of the edges.
874    typedef typename Traits::CapacityMap::Value Value;
875    /// The type of the map that stores the edge capacities.
876    typedef typename Traits::CapacityMap CapacityMap;
877    /// The type of the aux graph
878    typedef typename Traits::AuxGraph AuxGraph;
879    /// The type of the aux capacity map
880    typedef typename Traits::AuxCapacityMap AuxCapacityMap;
881    /// The cross reference type used for the current heap.
882    typedef typename Traits::HeapCrossRef HeapCrossRef;
883    /// The heap type used by the max cardinality algorithm.
884    typedef typename Traits::Heap Heap;
885    /// The node refrefernces between the original and aux graph type.
886    typedef typename Traits::NodeRefMap NodeRefMap;
887    /// The list node refrefernces in the original graph type.
888    typedef typename Traits::ListRefMap ListRefMap;
889
890  public:
891
892    ///\name Named template parameters
893
894    ///@{
895
896    struct DefNeutralCapacityTraits : public Traits {
897      typedef ConstMap<typename Graph::UEdge, Const<int, 1> > CapacityMap;
898      static CapacityMap *createCapacityMap(const Graph&) {
899        return new CapacityMap();
900      }
901    };
902    /// \brief \ref named-templ-param "Named parameter" for setting 
903    /// the capacity type to constMap<UEdge, int, 1>()
904    ///
905    /// \ref named-templ-param "Named parameter" for setting
906    /// the capacity type to constMap<UEdge, int, 1>()
907    struct DefNeutralCapacity
908      : public MinCut<Graph, CapacityMap, DefNeutralCapacityTraits> {
909      typedef MinCut<Graph, CapacityMap, DefNeutralCapacityTraits> Create;
910    };
911
912
913    template <class H, class CR>
914    struct DefHeapTraits : public Traits {
915      typedef CR HeapCrossRef;
916      typedef H Heap;
917      static HeapCrossRef *createHeapCrossRef(const AuxGraph &) {
918        throw UninitializedParameter();
919      }
920      static Heap *createHeap(HeapCrossRef &) {
921        throw UninitializedParameter();
922      }
923    };
924    /// \brief \ref named-templ-param "Named parameter" for setting heap
925    /// and cross reference type
926    ///
927    /// \ref named-templ-param "Named parameter" for setting heap and cross
928    /// reference type
929    template <class H, class CR = typename Graph::template NodeMap<int> >
930    struct DefHeap
931      : public MinCut<Graph, CapacityMap, DefHeapTraits<H, CR> > {
932      typedef MinCut< Graph, CapacityMap, DefHeapTraits<H, CR> > Create;
933    };
934
935    template <class H, class CR>
936    struct DefStandardHeapTraits : public Traits {
937      typedef CR HeapCrossRef;
938      typedef H Heap;
939      static HeapCrossRef *createHeapCrossRef(const AuxGraph &graph) {
940        return new HeapCrossRef(graph);
941      }
942      static Heap *createHeap(HeapCrossRef &crossref) {
943        return new Heap(crossref);
944      }
945    };
946
947    /// \brief \ref named-templ-param "Named parameter" for setting heap and
948    /// cross reference type with automatic allocation
949    ///
950    /// \ref named-templ-param "Named parameter" for setting heap and cross
951    /// reference type. It can allocate the heap and the cross reference
952    /// object if the cross reference's constructor waits for the graph as
953    /// parameter and the heap's constructor waits for the cross reference.
954    template <class H, class CR = typename Graph::template NodeMap<int> >
955    struct DefStandardHeap
956      : public MinCut<Graph, CapacityMap, DefStandardHeapTraits<H, CR> > {
957      typedef MinCut<Graph, CapacityMap, DefStandardHeapTraits<H, CR> >
958      Create;
959    };
960
961    ///@}
962
963
964  private:
965    /// Pointer to the underlying graph.
966    const Graph *_graph;
967    /// Pointer to the capacity map
968    const CapacityMap *_capacity;
969    /// \brief Indicates if \ref _capacity is locally allocated
970    /// (\c true) or not.
971    bool local_capacity;
972
973    /// Pointer to the aux graph.
974    AuxGraph *_aux_graph;
975    /// \brief Indicates if \ref _aux_graph is locally allocated
976    /// (\c true) or not.
977    bool local_aux_graph;
978    /// Pointer to the aux capacity map
979    AuxCapacityMap *_aux_capacity;
980    /// \brief Indicates if \ref _aux_capacity is locally allocated
981    /// (\c true) or not.
982    bool local_aux_capacity;
983    /// Pointer to the heap cross references.
984    HeapCrossRef *_heap_cross_ref;
985    /// \brief Indicates if \ref _heap_cross_ref is locally allocated
986    /// (\c true) or not.
987    bool local_heap_cross_ref;
988    /// Pointer to the heap.
989    Heap *_heap;
990    /// Indicates if \ref _heap is locally allocated (\c true) or not.
991    bool local_heap;
992
993    /// The min cut value.
994    Value _min_cut;
995    /// The number of the nodes of the aux graph.
996    int _node_num;
997    /// The first and last node of the min cut in the next list;
998    typename Graph::Node _first_node, _last_node;
999
1000    /// \brief The first and last element in the list associated
1001    /// to the aux graph node.
1002    NodeRefMap *_first, *_last;
1003    /// \brief The next node in the node lists.
1004    ListRefMap *_next;
1005   
1006    void create_structures() {
1007      if (!_capacity) {
1008        local_capacity = true;
1009        _capacity = Traits::createCapacityMap(*_graph);
1010      }
1011      if(!_aux_graph) {
1012        local_aux_graph = true;
1013        _aux_graph = Traits::createAuxGraph();
1014      }
1015      if(!_aux_capacity) {
1016        local_aux_capacity = true;
1017        _aux_capacity = Traits::createAuxCapacityMap(*_aux_graph);
1018      }
1019
1020      _first = Traits::createNodeRefMap(*_aux_graph);
1021      _last = Traits::createNodeRefMap(*_aux_graph);
1022
1023      _next = Traits::createListRefMap(*_graph);
1024
1025      typename Graph::template NodeMap<typename AuxGraph::Node> ref(*_graph);
1026
1027      for (typename Graph::NodeIt it(*_graph); it != INVALID; ++it) {
1028        _next->set(it, INVALID);
1029        typename AuxGraph::Node node = _aux_graph->addNode();
1030        _first->set(node, it);
1031        _last->set(node, it);
1032        ref.set(it, node);
1033      }
1034
1035      for (typename Graph::UEdgeIt it(*_graph); it != INVALID; ++it) {
1036        if (_graph->source(it) == _graph->target(it)) continue;
1037        typename AuxGraph::UEdge uedge =
1038          _aux_graph->addEdge(ref[_graph->source(it)],
1039                               ref[_graph->target(it)]);
1040        _aux_capacity->set(uedge, (*_capacity)[it]);
1041       
1042      }
1043
1044      if (!_heap_cross_ref) {
1045        local_heap_cross_ref = true;
1046        _heap_cross_ref = Traits::createHeapCrossRef(*_aux_graph);
1047      }
1048      if (!_heap) {
1049        local_heap = true;
1050        _heap = Traits::createHeap(*_heap_cross_ref);
1051      }
1052    }
1053
1054  public :
1055
1056    typedef MinCut Create;
1057
1058
1059    /// \brief Constructor.
1060    ///
1061    ///\param graph the graph the algorithm will run on.
1062    ///\param capacity the capacity map used by the algorithm.
1063    MinCut(const Graph& graph, const CapacityMap& capacity)
1064      : _graph(&graph),
1065        _capacity(&capacity), local_capacity(false),
1066        _aux_graph(0), local_aux_graph(false),
1067        _aux_capacity(0), local_aux_capacity(false),
1068        _heap_cross_ref(0), local_heap_cross_ref(false),
1069        _heap(0), local_heap(false),
1070        _first(0), _last(0), _next(0) {}
1071
1072    /// \brief Constructor.
1073    ///
1074    /// This constructor can be used only when the Traits class
1075    /// defines how can we instantiate a local capacity map.
1076    /// If the DefNeutralCapacity used the algorithm automatically
1077    /// construct the capacity map.
1078    ///
1079    ///\param graph the graph the algorithm will run on.
1080    MinCut(const Graph& graph)
1081      : _graph(&graph),
1082        _capacity(0), local_capacity(false),
1083        _aux_graph(0), local_aux_graph(false),
1084        _aux_capacity(0), local_aux_capacity(false),
1085        _heap_cross_ref(0), local_heap_cross_ref(false),
1086        _heap(0), local_heap(false),
1087        _first(0), _last(0), _next(0) {}
1088
1089    /// \brief Destructor.
1090    ///
1091    /// Destructor.
1092    ~MinCut() {
1093      if (local_heap) delete _heap;
1094      if (local_heap_cross_ref) delete _heap_cross_ref;
1095      if (_first) delete _first;
1096      if (_last) delete _last;
1097      if (_next) delete _next;
1098      if (local_aux_capacity) delete _aux_capacity;
1099      if (local_aux_graph) delete _aux_graph;
1100      if (local_capacity) delete _capacity;
1101    }
1102
1103    /// \brief Sets the heap and the cross reference used by algorithm.
1104    ///
1105    /// Sets the heap and the cross reference used by algorithm.
1106    /// If you don't use this function before calling \ref run(),
1107    /// it will allocate one. The destuctor deallocates this
1108    /// automatically allocated heap and cross reference, of course.
1109    /// \return <tt> (*this) </tt>
1110    MinCut &heap(Heap& heap, HeapCrossRef &crossRef)
1111    {
1112      if (local_heap_cross_ref) {
1113        delete _heap_cross_ref;
1114        local_heap_cross_ref=false;
1115      }
1116      _heap_cross_ref = &crossRef;
1117      if (local_heap) {
1118        delete _heap;
1119        local_heap=false;
1120      }
1121      _heap = &heap;
1122      return *this;
1123    }
1124
1125    /// \brief Sets the aux graph.
1126    ///
1127    /// Sets the aux graph used by algorithm.
1128    /// If you don't use this function before calling \ref run(),
1129    /// it will allocate one. The destuctor deallocates this
1130    /// automatically allocated graph, of course.
1131    /// \return <tt> (*this) </tt>
1132    MinCut &auxGraph(AuxGraph& aux_graph)
1133    {
1134      if(local_aux_graph) {
1135        delete _aux_graph;
1136        local_aux_graph=false;
1137      }
1138      _aux_graph = &aux_graph;
1139      return *this;
1140    }
1141
1142    /// \brief Sets the aux capacity map.
1143    ///
1144    /// Sets the aux capacity map used by algorithm.
1145    /// If you don't use this function before calling \ref run(),
1146    /// it will allocate one. The destuctor deallocates this
1147    /// automatically allocated graph, of course.
1148    /// \return <tt> (*this) </tt>
1149    MinCut &auxCapacityMap(AuxCapacityMap& aux_capacity_map)
1150    {
1151      if(local_aux_capacity) {
1152        delete _aux_capacity;
1153        local_aux_capacity=false;
1154      }
1155      _aux_capacity = &aux_capacity_map;
1156      return *this;
1157    }
1158
1159    /// \name Execution control
1160    /// The simplest way to execute the algorithm is to use
1161    /// one of the member functions called \c run().
1162    /// \n
1163    /// If you need more control on the execution,
1164    /// first you must call \ref init() and then call the start()
1165    /// or proper times the processNextPhase() member functions.
1166
1167    ///@{
1168
1169    /// \brief Initializes the internal data structures.
1170    ///
1171    /// Initializes the internal data structures.
1172    void init() {
1173      create_structures();
1174      _first_node = _last_node = INVALID;
1175      _node_num = countNodes(*_graph);
1176    }
1177
1178    /// \brief Processes the next phase
1179    ///
1180    /// Processes the next phase in the algorithm. The function
1181    /// should be called countNodes(graph) - 1 times to get
1182    /// surely the min cut in the graph. The 
1183    ///
1184    ///\return %True when the algorithm finished.
1185    bool processNextPhase() {
1186      if (_node_num <= 1) return true;
1187      using namespace _min_cut_bits;
1188
1189      typedef typename AuxGraph::Node Node;
1190      typedef typename AuxGraph::NodeIt NodeIt;
1191      typedef typename AuxGraph::UEdge UEdge;
1192      typedef typename AuxGraph::IncEdgeIt IncEdgeIt;
1193     
1194      typedef typename MaxCardinalitySearch<AuxGraph, AuxCapacityMap>::
1195      template DefHeap<Heap, HeapCrossRef>::
1196      template DefCardinalityMap<NullMap<Node, Value> >::
1197      template DefProcessedMap<LastTwoMap<Node> >::
1198      Create MaxCardinalitySearch;
1199     
1200      MaxCardinalitySearch mcs(*_aux_graph, *_aux_capacity);
1201      for (NodeIt it(*_aux_graph); it != INVALID; ++it) {
1202        _heap_cross_ref->set(it, Heap::PRE_HEAP);
1203      }
1204      mcs.heap(*_heap, *_heap_cross_ref);
1205
1206      LastTwoMap<Node> last_two_nodes(_node_num);
1207      mcs.processedMap(last_two_nodes);
1208
1209      NullMap<Node, Value> cardinality;
1210      mcs.cardinalityMap(cardinality);
1211
1212      mcs.run();
1213
1214      Node new_node = _aux_graph->addNode();
1215
1216      typename AuxGraph::template NodeMap<UEdge> edges(*_aux_graph, INVALID);
1217     
1218      Node first_node = last_two_nodes[0];
1219      Node second_node = last_two_nodes[1];
1220     
1221      _next->set((*_last)[first_node], (*_first)[second_node]);
1222      _first->set(new_node, (*_first)[first_node]);
1223      _last->set(new_node, (*_last)[second_node]);
1224
1225      Value current_cut = 0;     
1226      for (IncEdgeIt it(*_aux_graph, first_node); it != INVALID; ++it) {
1227        Node node = _aux_graph->runningNode(it);
1228        current_cut += (*_aux_capacity)[it];
1229        if (node == second_node) continue;
1230        if (edges[node] == INVALID) {
1231          edges[node] = _aux_graph->addEdge(new_node, node);
1232          (*_aux_capacity)[edges[node]] = (*_aux_capacity)[it];
1233        } else {
1234          (*_aux_capacity)[edges[node]] += (*_aux_capacity)[it];         
1235        }
1236      }
1237
1238      if (_first_node == INVALID || current_cut < _min_cut) {
1239        _first_node = (*_first)[first_node];
1240        _last_node = (*_last)[first_node];
1241        _min_cut = current_cut;
1242      }
1243
1244      _aux_graph->erase(first_node);
1245
1246      for (IncEdgeIt it(*_aux_graph, second_node); it != INVALID; ++it) {
1247        Node node = _aux_graph->runningNode(it);
1248        if (edges[node] == INVALID) {
1249          edges[node] = _aux_graph->addEdge(new_node, node);
1250          (*_aux_capacity)[edges[node]] = (*_aux_capacity)[it];
1251        } else {
1252          (*_aux_capacity)[edges[node]] += (*_aux_capacity)[it];         
1253        }
1254      }
1255      _aux_graph->erase(second_node);
1256
1257      --_node_num;
1258      return _node_num == 1;
1259    }
1260
1261    /// \brief Executes the algorithm.
1262    ///
1263    /// Executes the algorithm.
1264    ///
1265    /// \pre init() must be called
1266    void start() {
1267      while (!processNextPhase());
1268    }
1269
1270
1271    /// \brief Runs %MinCut algorithm.
1272    ///
1273    /// This method runs the %Min cut algorithm
1274    ///
1275    /// \note mc.run(s) is just a shortcut of the following code.
1276    ///\code
1277    ///  mc.init();
1278    ///  mc.start();
1279    ///\endcode
1280    void run() {
1281      init();
1282      start();
1283    }
1284
1285    ///@}
1286
1287    /// \name Query Functions
1288    /// The result of the %MinCut algorithm can be obtained using these
1289    /// functions.\n
1290    /// Before the use of these functions,
1291    /// either run() or start() must be called.
1292   
1293    ///@{
1294
1295    /// \brief Returns the min cut value.
1296    ///
1297    /// Returns the min cut value if the algorithm finished.
1298    /// After the first processNextPhase() it is a value of a
1299    /// valid cut in the graph.
1300    Value minCut() const {
1301      return _min_cut;
1302    }
1303
1304    /// \brief Returns a min cut in a NodeMap.
1305    ///
1306    /// It sets the nodes of one of the two partitions to true in
1307    /// the given BoolNodeMap. The map contains a valid cut if the
1308    /// map have been set false previously.
1309    template <typename NodeMap>
1310    Value quickMinCut(NodeMap& nodeMap) const {
1311      for (typename Graph::Node it = _first_node;
1312           it != _last_node; it = (*_next)[it]) {
1313             nodeMap.set(it, true);
1314           }
1315      nodeMap.set(_last_node, true);
1316      return minCut();
1317    }
1318
1319    /// \brief Returns a min cut in a NodeMap.
1320    ///
1321    /// It sets the nodes of one of the two partitions to true and
1322    /// the other partition to false. The function first set all of the
1323    /// nodes to false and after it call the quickMinCut() member.
1324    template <typename NodeMap>
1325    Value minCut(NodeMap& nodeMap) const {
1326      for (typename Graph::NodeIt it(*_graph); it != INVALID; ++it) {
1327        nodeMap.set(it, false);     
1328      }
1329      quickMinCut(nodeMap);
1330      return minCut();
1331    }
1332
1333    /// \brief Returns a min cut in an EdgeMap.
1334    ///
1335    /// If an undirected edge is in a min cut then it will be
1336    /// set to true and the others will be set to false in the given map.
1337    template <typename EdgeMap>
1338    Value cutEdges(EdgeMap& edgeMap) const {
1339      typename Graph::template NodeMap<bool> cut(*_graph, false);
1340      quickMinCut(cut);
1341      for (typename Graph::EdgeIt it(*_graph); it != INVALID; ++it) {
1342        edgeMap.set(it, cut[_graph->source(it)] ^ cut[_graph->target(it)]);
1343      }
1344      return minCut();
1345    }
1346
1347    ///@}
1348
1349  };
1350}
1351
1352#endif
Note: See TracBrowser for help on using the repository browser.