Index: lemon/max_cardinality_search.h
===================================================================
--- lemon/max_cardinality_search.h	(revision 1129)
+++ lemon/max_cardinality_search.h	(revision 1270)
@@ -1,7 +1,7 @@
-/* -*- C++ -*-
+/* -*- mode: C++; indent-tabs-mode: nil; -*-
  *
- * This file is a part of LEMON, a generic C++ optimization library
+ * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2010
+ * Copyright (C) 2003-2013
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -22,5 +22,5 @@
 
 /// \ingroup search
-/// \file 
+/// \file
 /// \brief Maximum cardinality search in undirected digraphs.
 
@@ -42,5 +42,5 @@
   template <typename GR, typename CAP>
   struct MaxCardinalitySearchDefaultTraits {
-    /// The digraph type the algorithm runs on. 
+    /// The digraph type the algorithm runs on.
     typedef GR Digraph;
 
@@ -51,5 +51,5 @@
 
       static CapacityMap *createCapacityMap(const Digraph& g) {
-	return new CapacityMap(g);
+        return new CapacityMap(g);
       }
     };
@@ -61,5 +61,5 @@
 
       static CapacityMap *createCapacityMap(const Digraph&) {
-	return new CapacityMap;
+        return new CapacityMap;
       }
     };
@@ -91,15 +91,15 @@
     /// \brief Instantiates a HeapCrossRef.
     ///
-    /// This function instantiates a \ref HeapCrossRef. 
-    /// \param digraph is the digraph, to which we would like to define the 
+    /// This function instantiates a \ref HeapCrossRef.
+    /// \param digraph is the digraph, to which we would like to define the
     /// HeapCrossRef.
     static HeapCrossRef *createHeapCrossRef(const Digraph &digraph) {
       return new HeapCrossRef(digraph);
     }
-    
+
     template <typename CapacityMap>
     struct HeapSelector {
       template <typename Value, typename Ref>
-      struct Selector { 
+      struct Selector {
         typedef BinHeap<Value, Ref, std::greater<Value> > Heap;
       };
@@ -129,5 +129,5 @@
     /// \brief Instantiates a Heap.
     ///
-    /// This function instantiates a \ref Heap. 
+    /// This function instantiates a \ref Heap.
     /// \param crossref The cross reference of the heap.
     static Heap *createHeap(HeapCrossRef& crossref) {
@@ -144,5 +144,5 @@
     /// \brief Instantiates a ProcessedMap.
     ///
-    /// This function instantiates a \ref ProcessedMap. 
+    /// This function instantiates a \ref ProcessedMap.
     /// \param digraph is the digraph, to which
     /// we would like to define the \ref ProcessedMap
@@ -157,5 +157,5 @@
 
     /// \brief The type of the map that stores the cardinalities of the nodes.
-    /// 
+    ///
     /// The type of the map that stores the cardinalities of the nodes.
     /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
@@ -164,6 +164,6 @@
     /// \brief Instantiates a CardinalityMap.
     ///
-    /// This function instantiates a \ref CardinalityMap. 
-    /// \param digraph is the digraph, to which we would like to define the \ref 
+    /// This function instantiates a \ref CardinalityMap.
+    /// \param digraph is the digraph, to which we would like to define the \ref
     /// CardinalityMap
     static CardinalityMap *createCardinalityMap(const Digraph &digraph) {
@@ -173,11 +173,11 @@
 
   };
-  
+
   /// \ingroup search
   ///
   /// \brief Maximum Cardinality Search algorithm class.
   ///
-  /// This class provides an efficient implementation of Maximum Cardinality 
-  /// Search algorithm. The maximum cardinality search first chooses any 
+  /// This class provides an efficient implementation of Maximum Cardinality
+  /// Search algorithm. The maximum cardinality search first chooses any
   /// node of the digraph. Then every time it chooses one unprocessed node
   /// with maximum cardinality, i.e the sum of capacities on out arcs to the nodes
@@ -187,8 +187,8 @@
 
   /// The arc capacities are passed to the algorithm using a
-  /// \ref concepts::ReadMap "ReadMap", so it is easy to change it to any 
+  /// \ref concepts::ReadMap "ReadMap", so it is easy to change it to any
   /// kind of capacity.
   ///
-  /// The type of the capacity is determined by the \ref 
+  /// The type of the capacity is determined by the \ref
   /// concepts::ReadMap::Value "Value" of the capacity map.
   ///
@@ -197,18 +197,18 @@
   ///
   /// \param GR The digraph type the algorithm runs on. The value of
-  /// Digraph is not used directly by the search algorithm, it 
+  /// Digraph is not used directly by the search algorithm, it
   /// is only passed to \ref MaxCardinalitySearchDefaultTraits.
-  /// \param CAP This read-only ArcMap determines the capacities of 
+  /// \param CAP This read-only ArcMap determines the capacities of
   /// the arcs. It is read once for each arc, so the map may involve in
   /// relatively time consuming process to compute the arc capacity if
   /// it is necessary. The default map type is \ref
   /// ConstMap "ConstMap<concepts::Digraph::Arc, Const<int,1> >". The value
-  /// of CapacityMap is not used directly by search algorithm, it is only 
-  /// passed to \ref MaxCardinalitySearchDefaultTraits.  
-  /// \param TR Traits class to set various data types used by the 
-  /// algorithm.  The default traits class is 
-  /// \ref MaxCardinalitySearchDefaultTraits 
-  /// "MaxCardinalitySearchDefaultTraits<GR, CAP>".  
-  /// See \ref MaxCardinalitySearchDefaultTraits 
+  /// of CapacityMap is not used directly by search algorithm, it is only
+  /// passed to \ref MaxCardinalitySearchDefaultTraits.
+  /// \param TR Traits class to set various data types used by the
+  /// algorithm.  The default traits class is
+  /// \ref MaxCardinalitySearchDefaultTraits
+  /// "MaxCardinalitySearchDefaultTraits<GR, CAP>".
+  /// See \ref MaxCardinalitySearchDefaultTraits
   /// for the documentation of a MaxCardinalitySearch traits class.
 
@@ -216,7 +216,7 @@
   template <typename GR, typename CAP, typename TR>
 #else
-  template <typename GR, typename CAP = 
-	    ConstMap<typename GR::Arc, Const<int,1> >,
-	    typename TR = 
+  template <typename GR, typename CAP =
+            ConstMap<typename GR::Arc, Const<int,1> >,
+            typename TR =
             MaxCardinalitySearchDefaultTraits<GR, CAP> >
 #endif
@@ -227,5 +227,5 @@
     ///The type of the underlying digraph.
     typedef typename Traits::Digraph Digraph;
-    
+
     ///The type of the capacity of the arcs.
     typedef typename Traits::CapacityMap::Value Value;
@@ -267,5 +267,5 @@
 
     typedef MaxCardinalitySearch Create;
- 
+
     ///\name Named template parameters
 
@@ -276,9 +276,9 @@
       typedef T CapacityMap;
       static CapacityMap *createCapacityMap(const Digraph &) {
-       	LEMON_ASSERT(false,"Uninitialized parameter.");
-	return 0;
-      }
-    };
-    /// \brief \ref named-templ-param "Named parameter" for setting 
+               LEMON_ASSERT(false,"Uninitialized parameter.");
+        return 0;
+      }
+    };
+    /// \brief \ref named-templ-param "Named parameter" for setting
     /// CapacityMap type
     ///
@@ -286,8 +286,8 @@
     /// for the algorithm.
     template <class T>
-    struct SetCapacityMap 
-      : public MaxCardinalitySearch<Digraph, CapacityMap, 
-                                    DefCapacityMapTraits<T> > { 
-      typedef MaxCardinalitySearch<Digraph, CapacityMap, 
+    struct SetCapacityMap
+      : public MaxCardinalitySearch<Digraph, CapacityMap,
+                                    DefCapacityMapTraits<T> > {
+      typedef MaxCardinalitySearch<Digraph, CapacityMap,
                                    DefCapacityMapTraits<T> > Create;
     };
@@ -296,32 +296,32 @@
     struct DefCardinalityMapTraits : public Traits {
       typedef T CardinalityMap;
-      static CardinalityMap *createCardinalityMap(const Digraph &) 
+      static CardinalityMap *createCardinalityMap(const Digraph &)
       {
-	LEMON_ASSERT(false,"Uninitialized parameter.");
-	return 0;
-      }
-    };
-    /// \brief \ref named-templ-param "Named parameter" for setting 
+        LEMON_ASSERT(false,"Uninitialized parameter.");
+        return 0;
+      }
+    };
+    /// \brief \ref named-templ-param "Named parameter" for setting
     /// CardinalityMap type
     ///
-    /// \ref named-templ-param "Named parameter" for setting CardinalityMap 
+    /// \ref named-templ-param "Named parameter" for setting CardinalityMap
     /// type for the algorithm.
     template <class T>
-    struct SetCardinalityMap 
-      : public MaxCardinalitySearch<Digraph, CapacityMap, 
-                                    DefCardinalityMapTraits<T> > { 
-      typedef MaxCardinalitySearch<Digraph, CapacityMap, 
+    struct SetCardinalityMap
+      : public MaxCardinalitySearch<Digraph, CapacityMap,
+                                    DefCardinalityMapTraits<T> > {
+      typedef MaxCardinalitySearch<Digraph, CapacityMap,
                                    DefCardinalityMapTraits<T> > Create;
     };
-    
+
     template <class T>
     struct DefProcessedMapTraits : public Traits {
       typedef T ProcessedMap;
       static ProcessedMap *createProcessedMap(const Digraph &) {
-       	LEMON_ASSERT(false,"Uninitialized parameter.");
-	return 0;
-      }
-    };
-    /// \brief \ref named-templ-param "Named parameter" for setting 
+               LEMON_ASSERT(false,"Uninitialized parameter.");
+        return 0;
+      }
+    };
+    /// \brief \ref named-templ-param "Named parameter" for setting
     /// ProcessedMap type
     ///
@@ -329,11 +329,11 @@
     /// for the algorithm.
     template <class T>
-    struct SetProcessedMap 
-      : public MaxCardinalitySearch<Digraph, CapacityMap, 
-                                    DefProcessedMapTraits<T> > { 
-      typedef MaxCardinalitySearch<Digraph, CapacityMap, 
+    struct SetProcessedMap
+      : public MaxCardinalitySearch<Digraph, CapacityMap,
+                                    DefProcessedMapTraits<T> > {
+      typedef MaxCardinalitySearch<Digraph, CapacityMap,
                                    DefProcessedMapTraits<T> > Create;
     };
-    
+
     template <class H, class CR>
     struct DefHeapTraits : public Traits {
@@ -341,22 +341,22 @@
       typedef H Heap;
       static HeapCrossRef *createHeapCrossRef(const Digraph &) {
-     	LEMON_ASSERT(false,"Uninitialized parameter.");
-	return 0;
+             LEMON_ASSERT(false,"Uninitialized parameter.");
+        return 0;
       }
       static Heap *createHeap(HeapCrossRef &) {
-       	LEMON_ASSERT(false,"Uninitialized parameter.");
-	return 0;
-      }
-    };
-    /// \brief \ref named-templ-param "Named parameter" for setting heap 
+               LEMON_ASSERT(false,"Uninitialized parameter.");
+        return 0;
+      }
+    };
+    /// \brief \ref named-templ-param "Named parameter" for setting heap
     /// and cross reference type
     ///
-    /// \ref named-templ-param "Named parameter" for setting heap and cross 
+    /// \ref named-templ-param "Named parameter" for setting heap and cross
     /// reference type for the algorithm.
     template <class H, class CR = typename Digraph::template NodeMap<int> >
     struct SetHeap
-      : public MaxCardinalitySearch<Digraph, CapacityMap, 
-                                    DefHeapTraits<H, CR> > { 
-      typedef MaxCardinalitySearch< Digraph, CapacityMap, 
+      : public MaxCardinalitySearch<Digraph, CapacityMap,
+                                    DefHeapTraits<H, CR> > {
+      typedef MaxCardinalitySearch< Digraph, CapacityMap,
                                     DefHeapTraits<H, CR> > Create;
     };
@@ -367,27 +367,27 @@
       typedef H Heap;
       static HeapCrossRef *createHeapCrossRef(const Digraph &digraph) {
-	return new HeapCrossRef(digraph);
+        return new HeapCrossRef(digraph);
       }
       static Heap *createHeap(HeapCrossRef &crossref) {
-	return new Heap(crossref);
-      }
-    };
-
-    /// \brief \ref named-templ-param "Named parameter" for setting heap and 
+        return new Heap(crossref);
+      }
+    };
+
+    /// \brief \ref named-templ-param "Named parameter" for setting heap and
     /// cross reference type with automatic allocation
     ///
-    /// \ref named-templ-param "Named parameter" for setting heap and cross 
-    /// reference type. It can allocate the heap and the cross reference 
-    /// object if the cross reference's constructor waits for the digraph as 
+    /// \ref named-templ-param "Named parameter" for setting heap and cross
+    /// reference type. It can allocate the heap and the cross reference
+    /// object if the cross reference's constructor waits for the digraph as
     /// parameter and the heap's constructor waits for the cross reference.
     template <class H, class CR = typename Digraph::template NodeMap<int> >
     struct SetStandardHeap
-      : public MaxCardinalitySearch<Digraph, CapacityMap, 
-                                    DefStandardHeapTraits<H, CR> > { 
-      typedef MaxCardinalitySearch<Digraph, CapacityMap, 
-                                   DefStandardHeapTraits<H, CR> > 
+      : public MaxCardinalitySearch<Digraph, CapacityMap,
+                                    DefStandardHeapTraits<H, CR> > {
+      typedef MaxCardinalitySearch<Digraph, CapacityMap,
+                                   DefStandardHeapTraits<H, CR> >
       Create;
     };
-    
+
     ///@}
 
@@ -397,6 +397,6 @@
     MaxCardinalitySearch() {}
 
-  public:      
-    
+  public:
+
     /// \brief Constructor.
     ///
@@ -404,5 +404,5 @@
     ///\param capacity the capacity map used by the algorithm.
     MaxCardinalitySearch(const Digraph& digraph,
-			 const CapacityMap& capacity) :
+                         const CapacityMap& capacity) :
       _graph(&digraph),
       _capacity(&capacity), local_capacity(false),
@@ -442,6 +442,6 @@
     MaxCardinalitySearch &capacityMap(const CapacityMap &m) {
       if (local_capacity) {
-	delete _capacity;
-	local_capacity=false;
+        delete _capacity;
+        local_capacity=false;
       }
       _capacity=&m;
@@ -457,5 +457,5 @@
     }
 
-    /// \brief Sets the map storing the cardinalities calculated by the 
+    /// \brief Sets the map storing the cardinalities calculated by the
     /// algorithm.
     ///
@@ -467,6 +467,6 @@
     MaxCardinalitySearch &cardinalityMap(CardinalityMap &m) {
       if(local_cardinality) {
-	delete _cardinality;
-	local_cardinality=false;
+        delete _cardinality;
+        local_cardinality=false;
       }
       _cardinality = &m;
@@ -481,9 +481,9 @@
     /// automatically allocated map, of course.
     /// \return <tt> (*this) </tt>
-    MaxCardinalitySearch &processedMap(ProcessedMap &m) 
+    MaxCardinalitySearch &processedMap(ProcessedMap &m)
     {
       if(local_processed) {
-	delete _processed;
-	local_processed=false;
+        delete _processed;
+        local_processed=false;
       }
       _processed = &m;
@@ -508,11 +508,11 @@
     MaxCardinalitySearch &heap(Heap& hp, HeapCrossRef &cr) {
       if(local_heap_cross_ref) {
-	delete _heap_cross_ref;
-	local_heap_cross_ref = false;
+        delete _heap_cross_ref;
+        local_heap_cross_ref = false;
       }
       _heap_cross_ref = &cr;
       if(local_heap) {
-	delete _heap;
-	local_heap = false;
+        delete _heap;
+        local_heap = false;
       }
       _heap = &hp;
@@ -545,25 +545,25 @@
     void create_maps() {
       if(!_capacity) {
-	local_capacity = true;
-	_capacity = Traits::createCapacityMap(*_graph);
+        local_capacity = true;
+        _capacity = Traits::createCapacityMap(*_graph);
       }
       if(!_cardinality) {
-	local_cardinality = true;
-	_cardinality = Traits::createCardinalityMap(*_graph);
+        local_cardinality = true;
+        _cardinality = Traits::createCardinalityMap(*_graph);
       }
       if(!_processed) {
-	local_processed = true;
-	_processed = Traits::createProcessedMap(*_graph);
+        local_processed = true;
+        _processed = Traits::createProcessedMap(*_graph);
       }
       if (!_heap_cross_ref) {
-	local_heap_cross_ref = true;
-	_heap_cross_ref = Traits::createHeapCrossRef(*_graph);
+        local_heap_cross_ref = true;
+        _heap_cross_ref = Traits::createHeapCrossRef(*_graph);
       }
       if (!_heap) {
-	local_heap = true;
-	_heap = Traits::createHeap(*_heap_cross_ref);
-      }
-    }
-    
+        local_heap = true;
+        _heap = Traits::createHeap(*_heap_cross_ref);
+      }
+    }
+
     void finalizeNodeData(Node node, Value capacity) {
       _processed->set(node, true);
@@ -590,11 +590,11 @@
       _heap->clear();
       for (NodeIt it(*_graph) ; it != INVALID ; ++it) {
-	_processed->set(it, false);
-	_heap_cross_ref->set(it, Heap::PRE_HEAP);
-      }
-    }
-    
+        _processed->set(it, false);
+        _heap_cross_ref->set(it, Heap::PRE_HEAP);
+      }
+    }
+
     /// \brief Adds a new source node.
-    /// 
+    ///
     /// Adds a new source node to the priority heap.
     ///
@@ -602,8 +602,8 @@
     void addSource(Node source, Value capacity = 0) {
       if(_heap->state(source) == Heap::PRE_HEAP) {
-	_heap->push(source, capacity);
-      } 
-    }
-    
+        _heap->push(source, capacity);
+      }
+    }
+
     /// \brief Processes the next node in the priority heap
     ///
@@ -614,20 +614,20 @@
     /// \warning The priority heap must not be empty!
     Node processNextNode() {
-      Node node = _heap->top(); 
+      Node node = _heap->top();
       finalizeNodeData(node, _heap->prio());
       _heap->pop();
-      
+
       for (InArcIt it(*_graph, node); it != INVALID; ++it) {
-	Node source = _graph->source(it);
-	switch (_heap->state(source)) {
-	case Heap::PRE_HEAP:
-	  _heap->push(source, (*_capacity)[it]);
-	  break;
-	case Heap::IN_HEAP:
-	  _heap->decrease(source, (*_heap)[source] + (*_capacity)[it]);
-	  break;
-	case Heap::POST_HEAP:
-	  break;
-	}
+        Node source = _graph->source(it);
+        switch (_heap->state(source)) {
+        case Heap::PRE_HEAP:
+          _heap->push(source, (*_capacity)[it]);
+          break;
+        case Heap::IN_HEAP:
+          _heap->decrease(source, (*_heap)[source] + (*_capacity)[it]);
+          break;
+        case Heap::POST_HEAP:
+          break;
+        }
       }
       return node;
@@ -638,10 +638,10 @@
     /// Next node to be processed.
     ///
-    /// \return The next node to be processed or INVALID if the 
+    /// \return The next node to be processed or INVALID if the
     /// priority heap is empty.
-    Node nextNode() { 
+    Node nextNode() {
       return !_heap->empty() ? _heap->top() : INVALID;
     }
- 
+
     /// \brief Returns \c false if there are nodes
     /// to be processed in the priority heap
@@ -650,10 +650,10 @@
     /// to be processed in the priority heap
     bool emptyQueue() { return _heap->empty(); }
-    /// \brief Returns the number of the nodes to be processed 
+    /// \brief Returns the number of the nodes to be processed
     /// in the priority heap
     ///
     /// Returns the number of the nodes to be processed in the priority heap
     int emptySize() { return _heap->size(); }
-    
+
     /// \brief Executes the algorithm.
     ///
@@ -663,10 +663,10 @@
     /// with addSource() before using this function.
     ///
-    /// This method runs the Maximum Cardinality Search algorithm from the 
+    /// This method runs the Maximum Cardinality Search algorithm from the
     /// source node(s).
     void start() {
       while ( !_heap->empty() ) processNextNode();
     }
-    
+
     /// \brief Executes the algorithm until \c dest is reached.
     ///
@@ -676,5 +676,5 @@
     /// with addSource() before using this function.
     ///
-    /// This method runs the %MaxCardinalitySearch algorithm from the source 
+    /// This method runs the %MaxCardinalitySearch algorithm from the source
     /// nodes.
     void start(Node dest) {
@@ -682,5 +682,5 @@
       if ( !_heap->empty() ) finalizeNodeData(_heap->top(), _heap->prio());
     }
-    
+
     /// \brief Executes the algorithm until a condition is met.
     ///
@@ -697,8 +697,8 @@
       if ( !_heap->empty() ) finalizeNodeData(_heap->top(),_heap->prio());
     }
-    
+
     /// \brief Runs the maximum cardinality search algorithm from node \c s.
     ///
-    /// This method runs the %MaxCardinalitySearch algorithm from a root 
+    /// This method runs the %MaxCardinalitySearch algorithm from a root
     /// node \c s.
     ///
@@ -715,8 +715,8 @@
     }
 
-    /// \brief Runs the maximum cardinality search algorithm for the 
+    /// \brief Runs the maximum cardinality search algorithm for the
     /// whole digraph.
     ///
-    /// This method runs the %MaxCardinalitySearch algorithm from all 
+    /// This method runs the %MaxCardinalitySearch algorithm from all
     /// unprocessed node of the digraph.
     ///
@@ -740,14 +740,14 @@
       }
     }
-    
+
     ///@}
 
     /// \name Query Functions
-    /// The results of the maximum cardinality search algorithm can be 
+    /// The results of the maximum cardinality search algorithm can be
     /// obtained using these functions.
     /// \n
-    /// Before the use of these functions, either run() or start() must be 
+    /// Before the use of these functions, either run() or start() must be
     /// called.
-    
+
     ///@{
 
@@ -768,8 +768,8 @@
     /// \brief Returns a reference to the NodeMap of cardinalities.
     ///
-    /// Returns a reference to the NodeMap of cardinalities. \pre \ref run() 
+    /// Returns a reference to the NodeMap of cardinalities. \pre \ref run()
     /// must be called before using this function.
     const CardinalityMap &cardinalityMap() const { return *_cardinality;}
- 
+
     /// \brief Checks if a node is reachable from the root.
     ///
@@ -785,5 +785,5 @@
     /// \pre \ref run() must be called before using this function.
     bool processed(Node v) { return (*_heap_cross_ref)[v] == Heap::POST_HEAP; }
-    
+
     ///@}
   };
