marci@510: // -*- c++ -*-
marci@559: #ifndef HUGO_MAX_BIPARTITE_MATCHING_H
marci@559: #define HUGO_MAX_BIPARTITE_MATCHING_H
marci@510: 
marci@615: /// \ingroup galgs
marci@615: /// \file
marci@615: /// \brief Maximum bipartite matchings, b-matchings and 
marci@615: /// capacitated b-matchings.
marci@615: ///
marci@615: /// This file contains a class for bipartite maximum matching, b-matchings 
marci@615: /// and capacitated b-matching computations.
marci@615: ///
marci@615: // /// \author Marton Makai
marci@615: 
marci@559: //#include <for_each_macros.h>
marci@510: #include <bipartite_graph_wrapper.h>
marci@559: //#include <hugo/maps.h>
marci@762: #include <hugo/max_flow.h>
marci@510: 
marci@559: namespace hugo {
marci@510: 
marci@559:   // template <typename Graph, typename EdgeCap, typename NodeCap, 
marci@559:   // 	  typename EdgeFlow, typename NodeFlow>
marci@559:   // class MaxMatching : public MaxFlow<stGraphWrapper<Graph>, 
marci@559:   // 				   stGraphWrapper<Graph>:: EdgeMapWrapper<EdgeCan, NodeCap>, stGraphWrapper<Graph>::EdgeMapWrapper<EdgeFlow, NodeFlow> > {
marci@559:   //   typedef MaxFlow<stGraphWrapper<Graph>, 
marci@559:   // 		  stGraphWrapper<Graph>::EdgeMapWrapper<EdgeCan, NodeCap>, 
marci@559:   // 		  stGraphWrapper<Graph>::EdgeMapWrapper<EdgeFlow, NodeFlow> >
marci@559:   //   Parent;
marci@559:   // protected:
marci@559:   //   stGraphWrapper<Graph> gw;
marci@559:   //   stGraphWrapper<Graph>::EdgeMapWrapper<EdgeCap, NodeCap> cap;
marci@559:   //   stGraphWrapper<Graph>::EdgeMapWrapper<EdgeFlow, NodeFlow> flow;
marci@559:   //   //graph* g;
marci@559:   //   //EdgeCap* edge_cap;
marci@559:   //   //EdgeFlow* edge_flow;
marci@559:   // public:
marci@559:   //   MaxMatching(Graph& _g, EdgeCap& _edge_cap, NodeCap& _node_cap, 
marci@559:   // 	      EdgeFlow& _edge_flow, NodeFlow& _node_flow) : 
marci@559:   //     MaxFlow(), gw(_g), 
marci@559:   //     cap(_edge_cap, _node_cap), flow(_edge_flow, _node_flow) {
marci@559:   //     Parent::set(gw, cap, flow);
marci@559:   //   }
marci@559:   // };
marci@510: 
marci@613:   /// \brief A bipartite matching class.
marci@613:   ///
marci@559:   /// This class reduces the matching problem to a flow problem and 
marci@559:   /// a preflow is used on a wrapper. Such a generic approach means that 
marci@559:   /// matchings, b-matchings an capacitated b-matchings can be handled in 
marci@559:   /// a similar way. Due to the efficiency of the preflow algorithm, an 
marci@559:   /// efficient matching framework is obtained.
marci@613:   /// \ingroup galgs
marci@559:   template <typename Graph, typename EdgeCap, typename NodeCap, 
marci@559: 	    typename EdgeFlow, typename NodeFlow>
marci@613:   class MaxBipartiteMatching {
marci@559:   protected:
marci@559:     //   EdgeCap* edge_cap;
marci@559:     //   NodeCap* node_cap;
marci@559:     //   EdgeFlow* edge_flow;
marci@559:     //   NodeFlow* node_flow;
marci@768:     typedef  stBipartiteGraphWrapper<Graph> stGW;
marci@559:     stGW stgw;
marci@559:     typedef typename stGW::template EdgeMapWrapper<EdgeCap, NodeCap> CapMap; 
marci@559:     CapMap cap;
marci@559:     NodeFlow* node_flow;
marci@559:     typedef typename stGW::template EdgeMapWrapper<EdgeFlow, NodeFlow> FlowMap;
marci@559:     FlowMap flow;
marci@768:     typedef MaxFlow<stGW, int, CapMap, FlowMap> MaxFlow;
marci@768:     MaxFlow mf;
marci@559:     //graph* g;
marci@559:     //EdgeCap* edge_cap;
marci@559:     //EdgeFlow* edge_flow;
marci@559:   public:
marci@768:     enum MatchingEnum{
marci@768:       ZERO_MATCHING,
marci@768:       GEN_MATCHING,
marci@768:       GEN_MATCHING_WITH_GOOD_NODE_FLOW,
marci@768:       NO_MATCHING
marci@768:     };
marci@559:     /// For capacitated b-matchings, edge-caoacities and node-capacities 
marci@559:     /// have to be given. After running \c run the matching is is given 
marci@559:     /// back in the edge-map \c _edge_flow and \c _node_map can be used 
marci@559:     /// to obtain saturation information about nodes.
marci@559:     ///\bug Note that the values in _edge_flow and _node_flow have 
marci@559:     /// to form a flow.
marci@613:     MaxBipartiteMatching(Graph& _g, EdgeCap& _edge_cap, NodeCap& _node_cap, 
marci@559: 		EdgeFlow& _edge_flow, NodeFlow& _node_flow) : 
marci@559:       stgw(_g), 
marci@559:       cap(_edge_cap, _node_cap), 
marci@559:       node_flow(0), 
marci@559:       flow(_edge_flow, _node_flow), 
marci@559:       mf(stgw, stgw.S_NODE, stgw.T_NODE, cap, flow) { }
marci@559:     /// If the saturation information of nodes is not needed that the use of 
marci@559:     /// this constructor is more comfortable.
marci@559:     ///\bug Note that the values in _edge_flow and _node_flow have 
marci@559:     /// to form a flow.
marci@613:     MaxBipartiteMatching(Graph& _g, EdgeCap& _edge_cap, NodeCap& _node_cap, 
marci@559: 		EdgeFlow& _edge_flow/*, NodeFlow& _node_flow*/) : 
marci@559:       stgw(_g), 
marci@559:       cap(_edge_cap, _node_cap), 
marci@559:       node_flow(new NodeFlow(_g)), 
marci@559:       flow(_edge_flow, *node_flow), 
marci@559:       mf(stgw, stgw.S_NODE, stgw.T_NODE, cap, flow) { }
marci@559:     /// The class have a nontrivial destructor.
marci@613:     ~MaxBipartiteMatching() { if (node_flow) delete node_flow; }
marci@559:     /// run computes the max matching.
marci@768:     void run(MatchingEnum me=ZERO_MATCHING) { 
marci@768:       switch (me) {
marci@768: 	case ZERO_MATCHING:
marci@768: 	  mf.run(MaxFlow::ZERO_FLOW);
marci@768: 	  break;
marci@768: 	case GEN_MATCHING:
marci@768: 	{
marci@768: 	  typename stGW::OutEdgeIt e;
marci@768: 	  for (stgw.first(e, stgw.S_NODE); stgw.valid(e); stgw.next(e)) 
marci@768: 	    flow.set(e, cap[e]);
marci@768: 	}
marci@768: 	{
marci@768: 	  typename stGW::InEdgeIt e;
marci@768: 	  for (stgw.first(e, stgw.T_NODE); stgw.valid(e); stgw.next(e)) 
marci@768: 	    flow.set(e, 0);
marci@768: 	}
marci@768: 	mf.run(MaxFlow::PRE_FLOW);
marci@768: 	break;
marci@768: 	case GEN_MATCHING_WITH_GOOD_NODE_FLOW:
marci@768: 	  mf.run(MaxFlow::GEN_FLOW);
marci@768: 	  break;
marci@768: 	case NO_MATCHING:
marci@768: 	  mf.run(MaxFlow::NO_FLOW);
marci@768: 	  break;
marci@768:       }
marci@768:     } 
marci@559:     /// The matching value after running \c run.
marci@768:     int matchingValue() const { return mf.flowValue(); }
marci@559:   };
marci@510: 
marci@559: } //namespace hugo
marci@510: 
marci@559: #endif //HUGO_MAX_BIPARTITE_MATCHING_H