COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/nagamochi_ibaraki.h @ 2287:16954ac69517

Last change on this file since 2287:16954ac69517 was 2284:05ff57dc401d, checked in by Balazs Dezso, 17 years ago

Renaming MinCut?

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