// -*- 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