source: lemon-0.x/src/work/marci/max_bipartite_matching.h @ 681:06a3cba90f94

// -*- c++ -*-
#ifndef HUGO_MAX_BIPARTITE_MATCHING_H
#define HUGO_MAX_BIPARTITE_MATCHING_H

/// \ingroup galgs
/// \file
/// \brief Maximum bipartite matchings, b-matchings and 
/// capacitated b-matchings.
///
/// This file contains a class for bipartite maximum matching, b-matchings 
/// and capacitated b-matching computations.
///
// /// \author Marton Makai

//#include <for_each_macros.h>
#include <bipartite_graph_wrapper.h>
//#include <hugo/maps.h>
#include <max_flow.h>

namespace hugo {

  // template <typename Graph, typename EdgeCap, typename NodeCap, 
  //      typename EdgeFlow, typename NodeFlow>
  // class MaxMatching : public MaxFlow<stGraphWrapper<Graph>, 
  //                               stGraphWrapper<Graph>:: EdgeMapWrapper<EdgeCan, NodeCap>, stGraphWrapper<Graph>::EdgeMapWrapper<EdgeFlow, NodeFlow> > {
  //   typedef MaxFlow<stGraphWrapper<Graph>, 
  //              stGraphWrapper<Graph>::EdgeMapWrapper<EdgeCan, NodeCap>, 
  //              stGraphWrapper<Graph>::EdgeMapWrapper<EdgeFlow, NodeFlow> >
  //   Parent;
  // protected:
  //   stGraphWrapper<Graph> gw;
  //   stGraphWrapper<Graph>::EdgeMapWrapper<EdgeCap, NodeCap> cap;
  //   stGraphWrapper<Graph>::EdgeMapWrapper<EdgeFlow, NodeFlow> flow;
  //   //graph* g;
  //   //EdgeCap* edge_cap;
  //   //EdgeFlow* edge_flow;
  // public:
  //   MaxMatching(Graph& _g, EdgeCap& _edge_cap, NodeCap& _node_cap, 
  //          EdgeFlow& _edge_flow, NodeFlow& _node_flow) : 
  //     MaxFlow(), gw(_g), 
  //     cap(_edge_cap, _node_cap), flow(_edge_flow, _node_flow) {
  //     Parent::set(gw, cap, flow);
  //   }
  // };

  /// \brief A bipartite matching class.
  ///
  /// This class reduces the matching problem to a flow problem and 
  /// a preflow is used on a wrapper. Such a generic approach means that 
  /// matchings, b-matchings an capacitated b-matchings can be handled in 
  /// a similar way. Due to the efficiency of the preflow algorithm, an 
  /// efficient matching framework is obtained.
  /// \ingroup galgs
  template <typename Graph, typename EdgeCap, typename NodeCap, 
            typename EdgeFlow, typename NodeFlow>
  class MaxBipartiteMatching {
  protected:
    //   EdgeCap* edge_cap;
    //   NodeCap* node_cap;
    //   EdgeFlow* edge_flow;
    //   NodeFlow* node_flow;
    typedef  stGraphWrapper<Graph> stGW;
    stGW stgw;
    typedef typename stGW::template EdgeMapWrapper<EdgeCap, NodeCap> CapMap; 
    CapMap cap;
    NodeFlow* node_flow;
    typedef typename stGW::template EdgeMapWrapper<EdgeFlow, NodeFlow> FlowMap;
    FlowMap flow;
    MaxFlow<stGW, int, CapMap, FlowMap> mf;
    //graph* g;
    //EdgeCap* edge_cap;
    //EdgeFlow* edge_flow;
  public:
    /// For capacitated b-matchings, edge-caoacities and node-capacities 
    /// have to be given. After running \c run the matching is is given 
    /// back in the edge-map \c _edge_flow and \c _node_map can be used 
    /// to obtain saturation information about nodes.
    ///\bug Note that the values in _edge_flow and _node_flow have 
    /// to form a flow.
    MaxBipartiteMatching(Graph& _g, EdgeCap& _edge_cap, NodeCap& _node_cap, 
                EdgeFlow& _edge_flow, NodeFlow& _node_flow) : 
      stgw(_g), 
      cap(_edge_cap, _node_cap), 
      node_flow(0), 
      flow(_edge_flow, _node_flow), 
      mf(stgw, stgw.S_NODE, stgw.T_NODE, cap, flow) { }
    /// If the saturation information of nodes is not needed that the use of 
    /// this constructor is more comfortable.
    ///\bug Note that the values in _edge_flow and _node_flow have 
    /// to form a flow.
    MaxBipartiteMatching(Graph& _g, EdgeCap& _edge_cap, NodeCap& _node_cap, 
                EdgeFlow& _edge_flow/*, NodeFlow& _node_flow*/) : 
      stgw(_g), 
      cap(_edge_cap, _node_cap), 
      node_flow(new NodeFlow(_g)), 
      flow(_edge_flow, *node_flow), 
      mf(stgw, stgw.S_NODE, stgw.T_NODE, cap, flow) { }
    /// The class have a nontrivial destructor.
    ~MaxBipartiteMatching() { if (node_flow) delete node_flow; }
    /// run computes the max matching.
    void run() { mf.run(); } 
    /// The matching value after running \c run.
    int matchingValue() { return mf.flowValue(); }
  };

} //namespace hugo

#endif //HUGO_MAX_BIPARTITE_MATCHING_H