COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/min_cut.h @ 2036:9d0c8a205e58

Last change on this file since 2036:9d0c8a205e58 was 1993:2115143eceea, checked in by Balazs Dezso, 18 years ago

utility, invalid and traits moved to bits

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