source: lemon-0.x/src/work/marci/max_bipartite_matching.h @ 1062:8226427845bc

// -*- c++ -*-
#ifndef LEMON_MAX_BIPARTITE_MATCHING_H
#define LEMON_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 <lemon/maps.h>
#include <lemon/max_flow.h>

namespace lemon {

  // 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  stBipartiteGraphWrapper<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;
    typedef MaxFlow<stGW, int, CapMap, FlowMap> MaxFlow;
    MaxFlow mf;
    //graph* g;
    //EdgeCap* edge_cap;
    //EdgeFlow* edge_flow;
  public:
    enum MatchingEnum{
      ZERO_MATCHING,
      GEN_MATCHING,
      GEN_MATCHING_WITH_GOOD_NODE_FLOW,
      NO_MATCHING
    };
    /// 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(MatchingEnum me=ZERO_MATCHING) { 
      switch (me) {
        case ZERO_MATCHING:
          mf.run(MaxFlow::ZERO_FLOW);
          break;
        case GEN_MATCHING:
        {
          typename stGW::OutEdgeIt e;
          for (stgw.first(e, stgw.S_NODE); stgw.valid(e); stgw.next(e)) 
            flow.set(e, cap[e]);
        }
        {
          typename stGW::InEdgeIt e;
          for (stgw.first(e, stgw.T_NODE); stgw.valid(e); stgw.next(e)) 
            flow.set(e, 0);
        }
        mf.run(MaxFlow::PRE_FLOW);
        break;
        case GEN_MATCHING_WITH_GOOD_NODE_FLOW:
          mf.run(MaxFlow::GEN_FLOW);
          break;
        case NO_MATCHING:
          mf.run(MaxFlow::NO_FLOW);
          break;
      }
    } 
    /// The matching value after running \c run.
    int matchingValue() const { return mf.flowValue(); }
  };

} //namespace lemon

#endif //LEMON_MAX_BIPARTITE_MATCHING_H