source: lemon-0.x/lemon/bipartite_matching.h @ 2051:08652c1763f6

/* -*- C++ -*-
 *
 * This file is a part of LEMON, a generic C++ optimization library
 *
 * Copyright (C) 2003-2006
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
 *
 * Permission to use, modify and distribute this software is granted
 * provided that this copyright notice appears in all copies. For
 * precise terms see the accompanying LICENSE file.
 *
 * This software is provided "AS IS" with no warranty of any kind,
 * express or implied, and with no claim as to its suitability for any
 * purpose.
 *
 */

#ifndef LEMON_BIPARTITE_MATCHING
#define LEMON_BIPARTITE_MATCHING

#include <functional>

#include <lemon/bin_heap.h>
#include <lemon/maps.h>

#include <iostream>

///\ingroup matching
///\file
///\brief Maximum matching algorithms in bipartite graphs.

namespace lemon {

  /// \ingroup matching
  ///
  /// \brief Bipartite Max Cardinality Matching algorithm
  ///
  /// Bipartite Max Cardinality Matching algorithm. This class implements
  /// the Hopcroft-Karp algorithm which has \f$ O(e\sqrt{n}) \f$ time
  /// complexity.
  template <typename BpUGraph>
  class MaxBipartiteMatching {
  protected:

    typedef BpUGraph Graph;

    typedef typename Graph::Node Node;
    typedef typename Graph::ANodeIt ANodeIt;
    typedef typename Graph::BNodeIt BNodeIt;
    typedef typename Graph::UEdge UEdge;
    typedef typename Graph::UEdgeIt UEdgeIt;
    typedef typename Graph::IncEdgeIt IncEdgeIt;

    typedef typename BpUGraph::template ANodeMap<UEdge> ANodeMatchingMap;
    typedef typename BpUGraph::template BNodeMap<UEdge> BNodeMatchingMap;


  public:

    /// \brief Constructor.
    ///
    /// Constructor of the algorithm. 
    MaxBipartiteMatching(const BpUGraph& _graph) 
      : anode_matching(_graph), bnode_matching(_graph), graph(&_graph) {}

    /// \name Execution control
    /// The simplest way to execute the algorithm is to use
    /// one of the member functions called \c run().
    /// \n
    /// If you need more control on the execution,
    /// first you must call \ref init() or one alternative for it.
    /// Finally \ref start() will perform the matching computation or
    /// with step-by-step execution you can augment the solution.

    /// @{

    /// \brief Initalize the data structures.
    ///
    /// It initalizes the data structures and creates an empty matching.
    void init() {
      for (ANodeIt it(*graph); it != INVALID; ++it) {
        anode_matching[it] = INVALID;
      }
      for (BNodeIt it(*graph); it != INVALID; ++it) {
        bnode_matching[it] = INVALID;
      }
      matching_size = 0;
    }

    /// \brief Initalize the data structures.
    ///
    /// It initalizes the data structures and creates a greedy
    /// matching.  From this matching sometimes it is faster to get
    /// the matching than from the initial empty matching.
    void greedyInit() {
      matching_size = 0;
      for (BNodeIt it(*graph); it != INVALID; ++it) {
        bnode_matching[it] = INVALID;
      }
      for (ANodeIt it(*graph); it != INVALID; ++it) {
        anode_matching[it] = INVALID;
        for (IncEdgeIt jt(*graph, it); jt != INVALID; ++jt) {
          if (bnode_matching[graph->bNode(jt)] == INVALID) {
            anode_matching[it] = jt;
            bnode_matching[graph->bNode(jt)] = jt;
            ++matching_size;
            break;
          }
        }
      }
    }

    /// \brief Initalize the data structures with an initial matching.
    ///
    /// It initalizes the data structures with an initial matching.
    template <typename MatchingMap>
    void matchingInit(const MatchingMap& matching) {
      for (ANodeIt it(*graph); it != INVALID; ++it) {
        anode_matching[it] = INVALID;
      }
      for (BNodeIt it(*graph); it != INVALID; ++it) {
        bnode_matching[it] = INVALID;
      }
      matching_size = 0;
      for (UEdgeIt it(*graph); it != INVALID; ++it) {
        if (matching[it]) {
          ++matching_size;
          anode_matching[graph->aNode(it)] = it;
          bnode_matching[graph->bNode(it)] = it;
        }
      }
    }

    /// \brief Initalize the data structures with an initial matching.
    ///
    /// It initalizes the data structures with an initial matching.
    /// \return %True when the given map contains really a matching.
    template <typename MatchingMap>
    void checkedMatchingInit(const MatchingMap& matching) {
      for (ANodeIt it(*graph); it != INVALID; ++it) {
        anode_matching[it] = INVALID;
      }
      for (BNodeIt it(*graph); it != INVALID; ++it) {
        bnode_matching[it] = INVALID;
      }
      matching_size = 0;
      for (UEdgeIt it(*graph); it != INVALID; ++it) {
        if (matching[it]) {
          ++matching_size;
          if (anode_matching[graph->aNode(it)] != INVALID) {
            return false;
          }
          anode_matching[graph->aNode(it)] = it;
          if (bnode_matching[graph->aNode(it)] != INVALID) {
            return false;
          }
          bnode_matching[graph->bNode(it)] = it;
        }
      }
      return false;
    }

    /// \brief An augmenting phase of the Hopcroft-Karp algorithm
    ///
    /// It runs an augmenting phase of the Hopcroft-Karp
    /// algorithm. The phase finds maximum count of edge disjoint
    /// augmenting paths and augments on these paths. The algorithm
    /// consists at most of \f$ O(\sqrt{n}) \f$ phase and one phase is
    /// \f$ O(e) \f$ long.
    bool augment() {

      typename Graph::template ANodeMap<bool> areached(*graph, false);
      typename Graph::template BNodeMap<bool> breached(*graph, false);

      typename Graph::template BNodeMap<UEdge> bpred(*graph, INVALID);

      std::vector<Node> queue, bqueue;
      for (ANodeIt it(*graph); it != INVALID; ++it) {
        if (anode_matching[it] == INVALID) {
          queue.push_back(it);
          areached[it] = true;
        }
      }

      bool success = false;

      while (!success && !queue.empty()) {
        std::vector<Node> newqueue;
        for (int i = 0; i < (int)queue.size(); ++i) {
          Node anode = queue[i];
          for (IncEdgeIt jt(*graph, anode); jt != INVALID; ++jt) {
            Node bnode = graph->bNode(jt);
            if (breached[bnode]) continue;
            breached[bnode] = true;
            bpred[bnode] = jt;
            if (bnode_matching[bnode] == INVALID) {
              bqueue.push_back(bnode);
              success = true;
            } else {           
              Node newanode = graph->aNode(bnode_matching[bnode]);
              if (!areached[newanode]) {
                areached[newanode] = true;
                newqueue.push_back(newanode);
              }
            }
          }
        }
        queue.swap(newqueue);
      }

      if (success) {

        typename Graph::template ANodeMap<bool> aused(*graph, false);
        
        for (int i = 0; i < (int)bqueue.size(); ++i) {
          Node bnode = bqueue[i];

          bool used = false;

          while (bnode != INVALID) {
            UEdge uedge = bpred[bnode];
            Node anode = graph->aNode(uedge);
            
            if (aused[anode]) {
              used = true;
              break;
            }
            
            bnode = anode_matching[anode] != INVALID ? 
              graph->bNode(anode_matching[anode]) : INVALID;
            
          }
          
          if (used) continue;

          bnode = bqueue[i];
          while (bnode != INVALID) {
            UEdge uedge = bpred[bnode];
            Node anode = graph->aNode(uedge);
            
            bnode_matching[bnode] = uedge;

            bnode = anode_matching[anode] != INVALID ? 
              graph->bNode(anode_matching[anode]) : INVALID;
            
            anode_matching[anode] = uedge;

            aused[anode] = true;
          }
          ++matching_size;

        }
      }
      return success;
    }

    /// \brief An augmenting phase of the Ford-Fulkerson algorithm
    ///
    /// It runs an augmenting phase of the Ford-Fulkerson
    /// algorithm. The phase finds only one augmenting path and 
    /// augments only on this paths. The algorithm consists at most 
    /// of \f$ O(n) \f$ simple phase and one phase is at most 
    /// \f$ O(e) \f$ long.
    bool simpleAugment() {

      typename Graph::template ANodeMap<bool> areached(*graph, false);
      typename Graph::template BNodeMap<bool> breached(*graph, false);

      typename Graph::template BNodeMap<UEdge> bpred(*graph, INVALID);

      std::vector<Node> queue;
      for (ANodeIt it(*graph); it != INVALID; ++it) {
        if (anode_matching[it] == INVALID) {
          queue.push_back(it);
          areached[it] = true;
        }
      }

      while (!queue.empty()) {
        std::vector<Node> newqueue;
        for (int i = 0; i < (int)queue.size(); ++i) {
          Node anode = queue[i];
          for (IncEdgeIt jt(*graph, anode); jt != INVALID; ++jt) {
            Node bnode = graph->bNode(jt);
            if (breached[bnode]) continue;
            breached[bnode] = true;
            bpred[bnode] = jt;
            if (bnode_matching[bnode] == INVALID) {
              while (bnode != INVALID) {
                UEdge uedge = bpred[bnode];
                anode = graph->aNode(uedge);
                
                bnode_matching[bnode] = uedge;
                
                bnode = anode_matching[anode] != INVALID ? 
                  graph->bNode(anode_matching[anode]) : INVALID;
                
                anode_matching[anode] = uedge;
                
              }
              ++matching_size;
              return true;
            } else {           
              Node newanode = graph->aNode(bnode_matching[bnode]);
              if (!areached[newanode]) {
                areached[newanode] = true;
                newqueue.push_back(newanode);
              }
            }
          }
        }
        queue.swap(newqueue);
      }
      
      return false;
    }

    /// \brief Starts the algorithm.
    ///
    /// Starts the algorithm. It runs augmenting phases until the optimal
    /// solution reached.
    void start() {
      while (augment()) {}
    }

    /// \brief Runs the algorithm.
    ///
    /// It just initalize the algorithm and then start it.
    void run() {
      init();
      start();
    }

    /// @}

    /// \name Query Functions
    /// The result of the %Matching algorithm can be obtained using these
    /// functions.\n
    /// Before the use of these functions,
    /// either run() or start() must be called.
    
    ///@{

    /// \brief Returns an minimum covering of the nodes.
    ///
    /// The minimum covering set problem is the dual solution of the
    /// maximum bipartite matching. It provides an solution for this
    /// problem what is proof of the optimality of the matching.
    /// \return The size of the cover set.
    template <typename CoverMap>
    int coverSet(CoverMap& covering) {

      typename Graph::template ANodeMap<bool> areached(*graph, false);
      typename Graph::template BNodeMap<bool> breached(*graph, false);
      
      std::vector<Node> queue;
      for (ANodeIt it(*graph); it != INVALID; ++it) {
        if (anode_matching[it] == INVALID) {
          queue.push_back(it);
        }
      }

      while (!queue.empty()) {
        std::vector<Node> newqueue;
        for (int i = 0; i < (int)queue.size(); ++i) {
          Node anode = queue[i];
          for (IncEdgeIt jt(*graph, anode); jt != INVALID; ++jt) {
            Node bnode = graph->bNode(jt);
            if (breached[bnode]) continue;
            breached[bnode] = true;
            if (bnode_matching[bnode] != INVALID) {
              Node newanode = graph->aNode(bnode_matching[bnode]);
              if (!areached[newanode]) {
                areached[newanode] = true;
                newqueue.push_back(newanode);
              }
            }
          }
        }
        queue.swap(newqueue);
      }

      int size = 0;
      for (ANodeIt it(*graph); it != INVALID; ++it) {
        covering[it] = !areached[it] && anode_matching[it] != INVALID;
        if (!areached[it] && anode_matching[it] != INVALID) {
          ++size;
        }
      }
      for (BNodeIt it(*graph); it != INVALID; ++it) {
        covering[it] = breached[it];
        if (breached[it]) {
          ++size;
        }
      }
      return size;
    }

    /// \brief Set true all matching uedge in the map.
    /// 
    /// Set true all matching uedge in the map. It does not change the
    /// value mapped to the other uedges.
    /// \return The number of the matching edges.
    template <typename MatchingMap>
    int quickMatching(MatchingMap& matching) {
      for (ANodeIt it(*graph); it != INVALID; ++it) {
        if (anode_matching[it] != INVALID) {
          matching[anode_matching[it]] = true;
        }
      }
      return matching_size;
    }

    /// \brief Set true all matching uedge in the map and the others to false.
    /// 
    /// Set true all matching uedge in the map and the others to false.
    /// \return The number of the matching edges.
    template <typename MatchingMap>
    int matching(MatchingMap& matching) {
      for (UEdgeIt it(*graph); it != INVALID; ++it) {
        matching[it] = it == anode_matching[graph->aNode(it)];
      }
      return matching_size;
    }


    /// \brief Return true if the given uedge is in the matching.
    /// 
    /// It returns true if the given uedge is in the matching.
    bool matchingEdge(const UEdge& edge) {
      return anode_matching[graph->aNode(edge)] == edge;
    }

    /// \brief Returns the matching edge from the node.
    /// 
    /// Returns the matching edge from the node. If there is not such
    /// edge it gives back \c INVALID.
    UEdge matchingEdge(const Node& node) {
      if (graph->aNode(node)) {
        return anode_matching[node];
      } else {
        return bnode_matching[node];
      }
    }

    /// \brief Gives back the number of the matching edges.
    ///
    /// Gives back the number of the matching edges.
    int matchingSize() const {
      return matching_size;
    }

    /// @}

  private:

    ANodeMatchingMap anode_matching;
    BNodeMatchingMap bnode_matching;
    const Graph *graph;

    int matching_size;
  
  };

  /// \brief Default traits class for weighted bipartite matching algoritms.
  ///
  /// Default traits class for weighted bipartite matching algoritms.
  /// \param _BpUGraph The bipartite undirected graph type.
  /// \param _WeightMap Type of weight map.
  template <typename _BpUGraph, typename _WeightMap>
  struct WeightedBipartiteMatchingDefaultTraits {
    /// \brief The type of the weight of the undirected edges.
    typedef typename _WeightMap::Value Value;

    /// The undirected bipartite graph type the algorithm runs on. 
    typedef _BpUGraph BpUGraph;

    /// The map of the edges weights
    typedef _WeightMap WeightMap;

    /// \brief The cross reference type used by heap.
    ///
    /// The cross reference type used by heap.
    /// Usually it is \c Graph::NodeMap<int>.
    typedef typename BpUGraph::template NodeMap<int> HeapCrossRef;

    /// \brief Instantiates a HeapCrossRef.
    ///
    /// This function instantiates a \ref HeapCrossRef. 
    /// \param graph is the graph, to which we would like to define the 
    /// HeapCrossRef.
    static HeapCrossRef *createHeapCrossRef(const BpUGraph &graph) {
      return new HeapCrossRef(graph);
    }
    
    /// \brief The heap type used by weighted matching algorithms.
    ///
    /// The heap type used by weighted matching algorithms. It should
    /// minimize the priorities and the heap's key type is the graph's
    /// anode graph's node.
    ///
    /// \sa BinHeap
    typedef BinHeap<typename BpUGraph::Node, Value, HeapCrossRef> Heap;
    
    /// \brief Instantiates a Heap.
    ///
    /// This function instantiates a \ref Heap. 
    /// \param crossref The cross reference of the heap.
    static Heap *createHeap(HeapCrossRef& crossref) {
      return new Heap(crossref);
    }

  };


  /// \ingroup matching
  ///
  /// \brief Bipartite Max Weighted Matching algorithm
  ///
  /// This class implements the bipartite Max Weighted Matching
  /// algorithm.  It uses the successive shortest path algorithm to
  /// calculate the maximum weighted matching in the bipartite
  /// graph. The algorithm can be used also to calculate the maximum
  /// cardinality maximum weighted matching. The time complexity
  /// of the algorithm is \f$ O(ne\log(n)) \f$ with the default binary
  /// heap implementation but this can be improved to 
  /// \f$ O(n^2\log(n)+ne) \f$ if we use fibonacci heaps.
  ///
  /// The algorithm also provides a potential function on the nodes
  /// which a dual solution of the matching algorithm and it can be
  /// used to proof the optimality of the given pimal solution.
#ifdef DOXYGEN
  template <typename _BpUGraph, typename _WeightMap, typename _Traits>
#else
  template <typename _BpUGraph, 
            typename _WeightMap = typename _BpUGraph::template UEdgeMap<int>,
            typename _Traits = WeightedBipartiteMatchingDefaultTraits<_BpUGraph, _WeightMap> >
#endif
  class MaxWeightedBipartiteMatching {
  public:

    typedef _Traits Traits;
    typedef typename Traits::BpUGraph BpUGraph;
    typedef typename Traits::WeightMap WeightMap;
    typedef typename Traits::Value Value;

  protected:

    typedef typename Traits::HeapCrossRef HeapCrossRef;
    typedef typename Traits::Heap Heap; 

    
    typedef typename BpUGraph::Node Node;
    typedef typename BpUGraph::ANodeIt ANodeIt;
    typedef typename BpUGraph::BNodeIt BNodeIt;
    typedef typename BpUGraph::UEdge UEdge;
    typedef typename BpUGraph::UEdgeIt UEdgeIt;
    typedef typename BpUGraph::IncEdgeIt IncEdgeIt;

    typedef typename BpUGraph::template ANodeMap<UEdge> ANodeMatchingMap;
    typedef typename BpUGraph::template BNodeMap<UEdge> BNodeMatchingMap;

    typedef typename BpUGraph::template ANodeMap<Value> ANodePotentialMap;
    typedef typename BpUGraph::template BNodeMap<Value> BNodePotentialMap;


  public:

    /// \brief \ref Exception for uninitialized parameters.
    ///
    /// This error represents problems in the initialization
    /// of the parameters of the algorithms.
    class UninitializedParameter : public lemon::UninitializedParameter {
    public:
      virtual const char* exceptionName() const {
        return "lemon::MaxWeightedBipartiteMatching::UninitializedParameter";
      }
    };

    ///\name Named template parameters

    ///@{

    template <class H, class CR>
    struct DefHeapTraits : public Traits {
      typedef CR HeapCrossRef;
      typedef H Heap;
      static HeapCrossRef *createHeapCrossRef(const BpUGraph &) {
        throw UninitializedParameter();
      }
      static Heap *createHeap(HeapCrossRef &) {
        throw UninitializedParameter();
      }
    };

    /// \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 
    /// reference type
    template <class H, class CR = typename BpUGraph::template NodeMap<int> >
    struct DefHeap
      : public MaxWeightedBipartiteMatching<BpUGraph, WeightMap, 
                                            DefHeapTraits<H, CR> > { 
      typedef MaxWeightedBipartiteMatching<BpUGraph, WeightMap, 
                                           DefHeapTraits<H, CR> > Create;
    };

    template <class H, class CR>
    struct DefStandardHeapTraits : public Traits {
      typedef CR HeapCrossRef;
      typedef H Heap;
      static HeapCrossRef *createHeapCrossRef(const BpUGraph &graph) {
        return new HeapCrossRef(graph);
      }
      static Heap *createHeap(HeapCrossRef &crossref) {
        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 graph as 
    /// parameter and the heap's constructor waits for the cross reference.
    template <class H, class CR = typename BpUGraph::template NodeMap<int> >
    struct DefStandardHeap
      : public MaxWeightedBipartiteMatching<BpUGraph, WeightMap, 
                                            DefStandardHeapTraits<H, CR> > { 
      typedef MaxWeightedBipartiteMatching<BpUGraph, WeightMap, 
                                           DefStandardHeapTraits<H, CR> > 
      Create;
    };

    ///@}


    /// \brief Constructor.
    ///
    /// Constructor of the algorithm. 
    MaxWeightedBipartiteMatching(const BpUGraph& _graph, 
                                 const WeightMap& _weight) 
      : graph(&_graph), weight(&_weight),
        anode_matching(_graph), bnode_matching(_graph),
        anode_potential(_graph), bnode_potential(_graph),
        _heap_cross_ref(0), local_heap_cross_ref(false),
        _heap(0), local_heap(0) {}

    /// \brief Destructor.
    ///
    /// Destructor of the algorithm.
    ~MaxWeightedBipartiteMatching() {
      destroyStructures();
    }

    /// \brief Sets the heap and the cross reference used by algorithm.
    ///
    /// Sets the heap and the cross reference used by algorithm.
    /// If you don't use this function before calling \ref run(),
    /// it will allocate one. The destuctor deallocates this
    /// automatically allocated map, of course.
    /// \return \c (*this)
    MaxWeightedBipartiteMatching& heap(Heap& heap, HeapCrossRef &crossRef) {
      if(local_heap_cross_ref) {
        delete _heap_cross_ref;
        local_heap_cross_ref = false;
      }
      _heap_cross_ref = &crossRef;
      if(local_heap) {
        delete _heap;
        local_heap = false;
      }
      _heap = &heap;
      return *this;
    }

    /// \name Execution control
    /// The simplest way to execute the algorithm is to use
    /// one of the member functions called \c run().
    /// \n
    /// If you need more control on the execution,
    /// first you must call \ref init() or one alternative for it.
    /// Finally \ref start() will perform the matching computation or
    /// with step-by-step execution you can augment the solution.

    /// @{

    /// \brief Initalize the data structures.
    ///
    /// It initalizes the data structures and creates an empty matching.
    void init() {
      initStructures();
      for (ANodeIt it(*graph); it != INVALID; ++it) {
        anode_matching[it] = INVALID;
        anode_potential[it] = 0;
      }
      for (BNodeIt it(*graph); it != INVALID; ++it) {
        bnode_matching[it] = INVALID;
        bnode_potential[it] = 0;
        for (IncEdgeIt jt(*graph, it); jt != INVALID; ++jt) {
          if (-(*weight)[jt] <= bnode_potential[it]) {
            bnode_potential[it] = -(*weight)[jt];
          }
        }
      }
      matching_value = 0;
      matching_size = 0;
    }


    /// \brief An augmenting phase of the weighted matching algorithm
    ///
    /// It runs an augmenting phase of the weighted matching 
    /// algorithm. The phase finds the best augmenting path and 
    /// augments only on this paths. 
    ///
    /// The algorithm consists at most 
    /// of \f$ O(n) \f$ phase and one phase is \f$ O(n\log(n)+e) \f$ 
    /// long with Fibonacci heap or \f$ O((n+e)\log(n)) \f$ long 
    /// with binary heap.
    /// \param decrease If the given parameter true the matching value
    /// can be decreased in the augmenting phase. If we would like
    /// to calculate the maximum cardinality maximum weighted matching
    /// then we should let the algorithm to decrease the matching
    /// value in order to increase the number of the matching edges.
    bool augment(bool decrease = false) {

      typename BpUGraph::template BNodeMap<Value> bdist(*graph);
      typename BpUGraph::template BNodeMap<UEdge> bpred(*graph, INVALID);

      Node bestNode = INVALID;
      Value bestValue = 0;

      _heap->clear();
      for (ANodeIt it(*graph); it != INVALID; ++it) {
        (*_heap_cross_ref)[it] = Heap::PRE_HEAP;
      }

      for (ANodeIt it(*graph); it != INVALID; ++it) {
        if (anode_matching[it] == INVALID) {
          _heap->push(it, 0);
        }
      }

      Value bdistMax = 0;
      while (!_heap->empty()) {
        Node anode = _heap->top();
        Value avalue = _heap->prio();
        _heap->pop();
        for (IncEdgeIt jt(*graph, anode); jt != INVALID; ++jt) {
          if (jt == anode_matching[anode]) continue;
          Node bnode = graph->bNode(jt);
          Value bvalue = avalue + anode_potential[anode] - 
            bnode_potential[bnode] - (*weight)[jt];
          if (bpred[bnode] == INVALID || bvalue < bdist[bnode]) {
            bdist[bnode] = bvalue;
            bpred[bnode] = jt;
          }
          if (bvalue > bdistMax) {
            bdistMax = bvalue;
          }
          if (bnode_matching[bnode] != INVALID) {
            Node newanode = graph->aNode(bnode_matching[bnode]);
            switch (_heap->state(newanode)) {
            case Heap::PRE_HEAP:
              _heap->push(newanode, bvalue);
              break;
            case Heap::IN_HEAP:
              if (bvalue < (*_heap)[newanode]) {
                _heap->decrease(newanode, bvalue);
              }
              break;
            case Heap::POST_HEAP:
              break;
            }
          } else {
            if (bestNode == INVALID || 
                - bvalue - bnode_potential[bnode] > bestValue) {
              bestValue = - bvalue - bnode_potential[bnode];
              bestNode = bnode;
            }
          }
        }
      }

      if (bestNode == INVALID || (!decrease && bestValue < 0)) {
        return false;
      }

      matching_value += bestValue;
      ++matching_size;

      for (BNodeIt it(*graph); it != INVALID; ++it) {
        if (bpred[it] != INVALID) {
          bnode_potential[it] += bdist[it];
        } else {
          bnode_potential[it] += bdistMax;
        }
      }
      for (ANodeIt it(*graph); it != INVALID; ++it) {
        if (anode_matching[it] != INVALID) {
          Node bnode = graph->bNode(anode_matching[it]);
          if (bpred[bnode] != INVALID) {
            anode_potential[it] += bdist[bnode];
          } else {
            anode_potential[it] += bdistMax;
          }
        }
      }

      while (bestNode != INVALID) {
        UEdge uedge = bpred[bestNode];
        Node anode = graph->aNode(uedge);
        
        bnode_matching[bestNode] = uedge;
        if (anode_matching[anode] != INVALID) {
          bestNode = graph->bNode(anode_matching[anode]);
        } else {
          bestNode = INVALID;
        }
        anode_matching[anode] = uedge;
      }


      return true;
    }

    /// \brief Starts the algorithm.
    ///
    /// Starts the algorithm. It runs augmenting phases until the
    /// optimal solution reached.
    ///
    /// \param maxCardinality If the given value is true it will
    /// calculate the maximum cardinality maximum matching instead of
    /// the maximum matching.
    void start(bool maxCardinality = false) {
      while (augment(maxCardinality)) {}
    }

    /// \brief Runs the algorithm.
    ///
    /// It just initalize the algorithm and then start it.
    ///
    /// \param maxCardinality If the given value is true it will
    /// calculate the maximum cardinality maximum matching instead of
    /// the maximum matching.
    void run(bool maxCardinality = false) {
      init();
      start(maxCardinality);
    }

    /// @}

    /// \name Query Functions
    /// The result of the %Matching algorithm can be obtained using these
    /// functions.\n
    /// Before the use of these functions,
    /// either run() or start() must be called.
    
    ///@{

    /// \brief Gives back the potential in the NodeMap
    ///
    /// Gives back the potential in the NodeMap. The potential
    /// is feasible if \f$ \pi(a) - \pi(b) - w(ab) = 0 \f$ for
    /// each matching edges and \f$ \pi(a) - \pi(b) - w(ab) \ge 0 \f$
    /// for each edges.
    template <typename PotentialMap>
    void potential(PotentialMap& potential) {
      for (ANodeIt it(*graph); it != INVALID; ++it) {
        potential[it] = anode_potential[it];
      }
      for (BNodeIt it(*graph); it != INVALID; ++it) {
        potential[it] = bnode_potential[it];
      }
    }

    /// \brief Set true all matching uedge in the map.
    /// 
    /// Set true all matching uedge in the map. It does not change the
    /// value mapped to the other uedges.
    /// \return The number of the matching edges.
    template <typename MatchingMap>
    int quickMatching(MatchingMap& matching) {
      for (ANodeIt it(*graph); it != INVALID; ++it) {
        if (anode_matching[it] != INVALID) {
          matching[anode_matching[it]] = true;
        }
      }
      return matching_size;
    }

    /// \brief Set true all matching uedge in the map and the others to false.
    /// 
    /// Set true all matching uedge in the map and the others to false.
    /// \return The number of the matching edges.
    template <typename MatchingMap>
    int matching(MatchingMap& matching) {
      for (UEdgeIt it(*graph); it != INVALID; ++it) {
        matching[it] = it == anode_matching[graph->aNode(it)];
      }
      return matching_size;
    }


    /// \brief Return true if the given uedge is in the matching.
    /// 
    /// It returns true if the given uedge is in the matching.
    bool matchingEdge(const UEdge& edge) {
      return anode_matching[graph->aNode(edge)] == edge;
    }

    /// \brief Returns the matching edge from the node.
    /// 
    /// Returns the matching edge from the node. If there is not such
    /// edge it gives back \c INVALID.
    UEdge matchingEdge(const Node& node) {
      if (graph->aNode(node)) {
        return anode_matching[node];
      } else {
        return bnode_matching[node];
      }
    }

    /// \brief Gives back the sum of weights of the matching edges.
    ///
    /// Gives back the sum of weights of the matching edges.
    Value matchingValue() const {
      return matching_value;
    }

    /// \brief Gives back the number of the matching edges.
    ///
    /// Gives back the number of the matching edges.
    int matchingSize() const {
      return matching_size;
    }

    /// @}

  private:

    void initStructures() {
      if (!_heap_cross_ref) {
        local_heap_cross_ref = true;
        _heap_cross_ref = Traits::createHeapCrossRef(*graph);
      }
      if (!_heap) {
        local_heap = true;
        _heap = Traits::createHeap(*_heap_cross_ref);
      }
    }

    void destroyStructures() {
      if (local_heap_cross_ref) delete _heap_cross_ref;
      if (local_heap) delete _heap;
    }


  private:
    
    const BpUGraph *graph;
    const WeightMap* weight;

    ANodeMatchingMap anode_matching;
    BNodeMatchingMap bnode_matching;

    ANodePotentialMap anode_potential;
    BNodePotentialMap bnode_potential;

    Value matching_value;
    int matching_size;

    HeapCrossRef *_heap_cross_ref;
    bool local_heap_cross_ref;

    Heap *_heap;
    bool local_heap;
  
  };

  /// \brief Default traits class for minimum cost bipartite matching
  /// algoritms.
  ///
  /// Default traits class for minimum cost bipartite matching
  /// algoritms.  
  ///
  /// \param _BpUGraph The bipartite undirected graph
  /// type.  
  ///
  /// \param _CostMap Type of cost map.
  template <typename _BpUGraph, typename _CostMap>
  struct MinCostMaxBipartiteMatchingDefaultTraits {
    /// \brief The type of the cost of the undirected edges.
    typedef typename _CostMap::Value Value;

    /// The undirected bipartite graph type the algorithm runs on. 
    typedef _BpUGraph BpUGraph;

    /// The map of the edges costs
    typedef _CostMap CostMap;

    /// \brief The cross reference type used by heap.
    ///
    /// The cross reference type used by heap.
    /// Usually it is \c Graph::NodeMap<int>.
    typedef typename BpUGraph::template NodeMap<int> HeapCrossRef;

    /// \brief Instantiates a HeapCrossRef.
    ///
    /// This function instantiates a \ref HeapCrossRef. 
    /// \param graph is the graph, to which we would like to define the 
    /// HeapCrossRef.
    static HeapCrossRef *createHeapCrossRef(const BpUGraph &graph) {
      return new HeapCrossRef(graph);
    }
    
    /// \brief The heap type used by costed matching algorithms.
    ///
    /// The heap type used by costed matching algorithms. It should
    /// minimize the priorities and the heap's key type is the graph's
    /// anode graph's node.
    ///
    /// \sa BinHeap
    typedef BinHeap<typename BpUGraph::Node, Value, HeapCrossRef> Heap;
    
    /// \brief Instantiates a Heap.
    ///
    /// This function instantiates a \ref Heap. 
    /// \param crossref The cross reference of the heap.
    static Heap *createHeap(HeapCrossRef& crossref) {
      return new Heap(crossref);
    }

  };


  /// \ingroup matching
  ///
  /// \brief Bipartite Min Cost Matching algorithm
  ///
  /// This class implements the bipartite Min Cost Matching algorithm.
  /// It uses the successive shortest path algorithm to calculate the
  /// minimum cost maximum matching in the bipartite graph. The time
  /// complexity of the algorithm is \f$ O(ne\log(n)) \f$ with the
  /// default binary heap implementation but this can be improved to
  /// \f$ O(n^2\log(n)+ne) \f$ if we use fibonacci heaps.
  ///
  /// The algorithm also provides a potential function on the nodes
  /// which a dual solution of the matching algorithm and it can be
  /// used to proof the optimality of the given pimal solution.
#ifdef DOXYGEN
  template <typename _BpUGraph, typename _CostMap, typename _Traits>
#else
  template <typename _BpUGraph, 
            typename _CostMap = typename _BpUGraph::template UEdgeMap<int>,
            typename _Traits = MinCostMaxBipartiteMatchingDefaultTraits<_BpUGraph, _CostMap> >
#endif
  class MinCostMaxBipartiteMatching {
  public:

    typedef _Traits Traits;
    typedef typename Traits::BpUGraph BpUGraph;
    typedef typename Traits::CostMap CostMap;
    typedef typename Traits::Value Value;

  protected:

    typedef typename Traits::HeapCrossRef HeapCrossRef;
    typedef typename Traits::Heap Heap; 

    
    typedef typename BpUGraph::Node Node;
    typedef typename BpUGraph::ANodeIt ANodeIt;
    typedef typename BpUGraph::BNodeIt BNodeIt;
    typedef typename BpUGraph::UEdge UEdge;
    typedef typename BpUGraph::UEdgeIt UEdgeIt;
    typedef typename BpUGraph::IncEdgeIt IncEdgeIt;

    typedef typename BpUGraph::template ANodeMap<UEdge> ANodeMatchingMap;
    typedef typename BpUGraph::template BNodeMap<UEdge> BNodeMatchingMap;

    typedef typename BpUGraph::template ANodeMap<Value> ANodePotentialMap;
    typedef typename BpUGraph::template BNodeMap<Value> BNodePotentialMap;


  public:

    /// \brief \ref Exception for uninitialized parameters.
    ///
    /// This error represents problems in the initialization
    /// of the parameters of the algorithms.
    class UninitializedParameter : public lemon::UninitializedParameter {
    public:
      virtual const char* exceptionName() const {
        return "lemon::MinCostMaxBipartiteMatching::UninitializedParameter";
      }
    };

    ///\name Named template parameters

    ///@{

    template <class H, class CR>
    struct DefHeapTraits : public Traits {
      typedef CR HeapCrossRef;
      typedef H Heap;
      static HeapCrossRef *createHeapCrossRef(const BpUGraph &) {
        throw UninitializedParameter();
      }
      static Heap *createHeap(HeapCrossRef &) {
        throw UninitializedParameter();
      }
    };

    /// \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 
    /// reference type
    template <class H, class CR = typename BpUGraph::template NodeMap<int> >
    struct DefHeap
      : public MinCostMaxBipartiteMatching<BpUGraph, CostMap, 
                                            DefHeapTraits<H, CR> > { 
      typedef MinCostMaxBipartiteMatching<BpUGraph, CostMap, 
                                           DefHeapTraits<H, CR> > Create;
    };

    template <class H, class CR>
    struct DefStandardHeapTraits : public Traits {
      typedef CR HeapCrossRef;
      typedef H Heap;
      static HeapCrossRef *createHeapCrossRef(const BpUGraph &graph) {
        return new HeapCrossRef(graph);
      }
      static Heap *createHeap(HeapCrossRef &crossref) {
        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 graph as 
    /// parameter and the heap's constructor waits for the cross reference.
    template <class H, class CR = typename BpUGraph::template NodeMap<int> >
    struct DefStandardHeap
      : public MinCostMaxBipartiteMatching<BpUGraph, CostMap, 
                                            DefStandardHeapTraits<H, CR> > { 
      typedef MinCostMaxBipartiteMatching<BpUGraph, CostMap, 
                                           DefStandardHeapTraits<H, CR> > 
      Create;
    };

    ///@}


    /// \brief Constructor.
    ///
    /// Constructor of the algorithm. 
    MinCostMaxBipartiteMatching(const BpUGraph& _graph, 
                                 const CostMap& _cost) 
      : graph(&_graph), cost(&_cost),
        anode_matching(_graph), bnode_matching(_graph),
        anode_potential(_graph), bnode_potential(_graph),
        _heap_cross_ref(0), local_heap_cross_ref(false),
        _heap(0), local_heap(0) {}

    /// \brief Destructor.
    ///
    /// Destructor of the algorithm.
    ~MinCostMaxBipartiteMatching() {
      destroyStructures();
    }

    /// \brief Sets the heap and the cross reference used by algorithm.
    ///
    /// Sets the heap and the cross reference used by algorithm.
    /// If you don't use this function before calling \ref run(),
    /// it will allocate one. The destuctor deallocates this
    /// automatically allocated map, of course.
    /// \return \c (*this)
    MinCostMaxBipartiteMatching& heap(Heap& heap, HeapCrossRef &crossRef) {
      if(local_heap_cross_ref) {
        delete _heap_cross_ref;
        local_heap_cross_ref = false;
      }
      _heap_cross_ref = &crossRef;
      if(local_heap) {
        delete _heap;
        local_heap = false;
      }
      _heap = &heap;
      return *this;
    }

    /// \name Execution control
    /// The simplest way to execute the algorithm is to use
    /// one of the member functions called \c run().
    /// \n
    /// If you need more control on the execution,
    /// first you must call \ref init() or one alternative for it.
    /// Finally \ref start() will perform the matching computation or
    /// with step-by-step execution you can augment the solution.

    /// @{

    /// \brief Initalize the data structures.
    ///
    /// It initalizes the data structures and creates an empty matching.
    void init() {
      initStructures();
      for (ANodeIt it(*graph); it != INVALID; ++it) {
        anode_matching[it] = INVALID;
        anode_potential[it] = 0;
      }
      for (BNodeIt it(*graph); it != INVALID; ++it) {
        bnode_matching[it] = INVALID;
        bnode_potential[it] = 0;
      }
      matching_cost = 0;
      matching_size = 0;
    }


    /// \brief An augmenting phase of the costed matching algorithm
    ///
    /// It runs an augmenting phase of the matching algorithm. The
    /// phase finds the best augmenting path and augments only on this
    /// paths.
    ///
    /// The algorithm consists at most 
    /// of \f$ O(n) \f$ phase and one phase is \f$ O(n\log(n)+e) \f$ 
    /// long with Fibonacci heap or \f$ O((n+e)\log(n)) \f$ long 
    /// with binary heap.
    bool augment() {

      typename BpUGraph::template BNodeMap<Value> bdist(*graph);
      typename BpUGraph::template BNodeMap<UEdge> bpred(*graph, INVALID);

      Node bestNode = INVALID;
      Value bestValue = 0;

      _heap->clear();
      for (ANodeIt it(*graph); it != INVALID; ++it) {
        (*_heap_cross_ref)[it] = Heap::PRE_HEAP;
      }

      for (ANodeIt it(*graph); it != INVALID; ++it) {
        if (anode_matching[it] == INVALID) {
          _heap->push(it, 0);
        }
      }

      while (!_heap->empty()) {
        Node anode = _heap->top();
        Value avalue = _heap->prio();
        _heap->pop();
        for (IncEdgeIt jt(*graph, anode); jt != INVALID; ++jt) {
          if (jt == anode_matching[anode]) continue;
          Node bnode = graph->bNode(jt);
          Value bvalue = avalue + (*cost)[jt] + 
            anode_potential[anode] - bnode_potential[bnode];
          if (bpred[bnode] == INVALID || bvalue < bdist[bnode]) {
            bdist[bnode] = bvalue;
            bpred[bnode] = jt;
          }
          if (bnode_matching[bnode] != INVALID) {
            Node newanode = graph->aNode(bnode_matching[bnode]);
            switch (_heap->state(newanode)) {
            case Heap::PRE_HEAP:
              _heap->push(newanode, bvalue);
              break;
            case Heap::IN_HEAP:
              if (bvalue < (*_heap)[newanode]) {
                _heap->decrease(newanode, bvalue);
              }
              break;
            case Heap::POST_HEAP:
              break;
            }
          } else {
            if (bestNode == INVALID || 
                bvalue + bnode_potential[bnode] < bestValue) {
              bestValue = bvalue + bnode_potential[bnode];
              bestNode = bnode;
            }
          }
        }
      }

      if (bestNode == INVALID) {
        return false;
      }

      matching_cost += bestValue;
      ++matching_size;

      for (BNodeIt it(*graph); it != INVALID; ++it) {
        if (bpred[it] != INVALID) {
          bnode_potential[it] += bdist[it];
        }
      }
      for (ANodeIt it(*graph); it != INVALID; ++it) {
        if (anode_matching[it] != INVALID) {
          Node bnode = graph->bNode(anode_matching[it]);
          if (bpred[bnode] != INVALID) {
            anode_potential[it] += bdist[bnode];
          }
        }
      }

      while (bestNode != INVALID) {
        UEdge uedge = bpred[bestNode];
        Node anode = graph->aNode(uedge);
        
        bnode_matching[bestNode] = uedge;
        if (anode_matching[anode] != INVALID) {
          bestNode = graph->bNode(anode_matching[anode]);
        } else {
          bestNode = INVALID;
        }
        anode_matching[anode] = uedge;
      }


      return true;
    }

    /// \brief Starts the algorithm.
    ///
    /// Starts the algorithm. It runs augmenting phases until the
    /// optimal solution reached.
    void start() {
      while (augment()) {}
    }

    /// \brief Runs the algorithm.
    ///
    /// It just initalize the algorithm and then start it.
    void run() {
      init();
      start();
    }

    /// @}

    /// \name Query Functions
    /// The result of the %Matching algorithm can be obtained using these
    /// functions.\n
    /// Before the use of these functions,
    /// either run() or start() must be called.
    
    ///@{

    /// \brief Gives back the potential in the NodeMap
    ///
    /// Gives back the potential in the NodeMap. The potential
    /// is feasible if \f$ \pi(a) - \pi(b) + w(ab) = 0 \f$ for
    /// each matching edges and \f$ \pi(a) - \pi(b) + w(ab) \ge 0 \f$
    /// for each edges.
    template <typename PotentialMap>
    void potential(PotentialMap& potential) {
      for (ANodeIt it(*graph); it != INVALID; ++it) {
        potential[it] = anode_potential[it];
      }
      for (BNodeIt it(*graph); it != INVALID; ++it) {
        potential[it] = bnode_potential[it];
      }
    }

    /// \brief Set true all matching uedge in the map.
    /// 
    /// Set true all matching uedge in the map. It does not change the
    /// value mapped to the other uedges.
    /// \return The number of the matching edges.
    template <typename MatchingMap>
    int quickMatching(MatchingMap& matching) {
      for (ANodeIt it(*graph); it != INVALID; ++it) {
        if (anode_matching[it] != INVALID) {
          matching[anode_matching[it]] = true;
        }
      }
      return matching_size;
    }

    /// \brief Set true all matching uedge in the map and the others to false.
    /// 
    /// Set true all matching uedge in the map and the others to false.
    /// \return The number of the matching edges.
    template <typename MatchingMap>
    int matching(MatchingMap& matching) {
      for (UEdgeIt it(*graph); it != INVALID; ++it) {
        matching[it] = it == anode_matching[graph->aNode(it)];
      }
      return matching_size;
    }


    /// \brief Return true if the given uedge is in the matching.
    /// 
    /// It returns true if the given uedge is in the matching.
    bool matchingEdge(const UEdge& edge) {
      return anode_matching[graph->aNode(edge)] == edge;
    }

    /// \brief Returns the matching edge from the node.
    /// 
    /// Returns the matching edge from the node. If there is not such
    /// edge it gives back \c INVALID.
    UEdge matchingEdge(const Node& node) {
      if (graph->aNode(node)) {
        return anode_matching[node];
      } else {
        return bnode_matching[node];
      }
    }

    /// \brief Gives back the sum of costs of the matching edges.
    ///
    /// Gives back the sum of costs of the matching edges.
    Value matchingCost() const {
      return matching_cost;
    }

    /// \brief Gives back the number of the matching edges.
    ///
    /// Gives back the number of the matching edges.
    int matchingSize() const {
      return matching_size;
    }

    /// @}

  private:

    void initStructures() {
      if (!_heap_cross_ref) {
        local_heap_cross_ref = true;
        _heap_cross_ref = Traits::createHeapCrossRef(*graph);
      }
      if (!_heap) {
        local_heap = true;
        _heap = Traits::createHeap(*_heap_cross_ref);
      }
    }

    void destroyStructures() {
      if (local_heap_cross_ref) delete _heap_cross_ref;
      if (local_heap) delete _heap;
    }


  private:
    
    const BpUGraph *graph;
    const CostMap* cost;

    ANodeMatchingMap anode_matching;
    BNodeMatchingMap bnode_matching;

    ANodePotentialMap anode_potential;
    BNodePotentialMap bnode_potential;

    Value matching_cost;
    int matching_size;

    HeapCrossRef *_heap_cross_ref;
    bool local_heap_cross_ref;

    Heap *_heap;
    bool local_heap;
  
  };

}

#endif