lemon-0.x: src/work/marci/max_bipartite

     1 // -*- c++ -*-

     2 #ifndef HUGO_MAX_BIPARTITE_MATCHING_H

     3 #define HUGO_MAX_BIPARTITE_MATCHING_H

     5 /// \ingroup galgs

     6 /// \file

     7 /// \brief Maximum bipartite matchings, b-matchings and

     8 /// capacitated b-matchings.

     9 ///

    10 /// This file contains a class for bipartite maximum matching, b-matchings

    11 /// and capacitated b-matching computations.

    12 ///

    13 // /// \author Marton Makai

    15 //#include <for_each_macros.h>

    16 #include <bipartite_graph_wrapper.h>

    17 //#include <hugo/maps.h>

    18 #include <hugo/max_flow.h>

    20 namespace hugo {

    22   // template <typename Graph, typename EdgeCap, typename NodeCap,

    23   // 	  typename EdgeFlow, typename NodeFlow>

    24   // class MaxMatching : public MaxFlow<stGraphWrapper<Graph>,

    25   // 				   stGraphWrapper<Graph>:: EdgeMapWrapper<EdgeCan, NodeCap>, stGraphWrapper<Graph>::EdgeMapWrapper<EdgeFlow, NodeFlow> > {

    26   //   typedef MaxFlow<stGraphWrapper<Graph>,

    27   // 		  stGraphWrapper<Graph>::EdgeMapWrapper<EdgeCan, NodeCap>,

    28   // 		  stGraphWrapper<Graph>::EdgeMapWrapper<EdgeFlow, NodeFlow> >

    29   //   Parent;

    30   // protected:

    31   //   stGraphWrapper<Graph> gw;

    32   //   stGraphWrapper<Graph>::EdgeMapWrapper<EdgeCap, NodeCap> cap;

    33   //   stGraphWrapper<Graph>::EdgeMapWrapper<EdgeFlow, NodeFlow> flow;

    34   //   //graph* g;

    35   //   //EdgeCap* edge_cap;

    36   //   //EdgeFlow* edge_flow;

    37   // public:

    38   //   MaxMatching(Graph& _g, EdgeCap& _edge_cap, NodeCap& _node_cap,

    39   // 	      EdgeFlow& _edge_flow, NodeFlow& _node_flow) :

    40   //     MaxFlow(), gw(_g),

    41   //     cap(_edge_cap, _node_cap), flow(_edge_flow, _node_flow) {

    42   //     Parent::set(gw, cap, flow);

    43   //   }

    44   // };

    46   /// \brief A bipartite matching class.

    47   ///

    48   /// This class reduces the matching problem to a flow problem and

    49   /// a preflow is used on a wrapper. Such a generic approach means that

    50   /// matchings, b-matchings an capacitated b-matchings can be handled in

    51   /// a similar way. Due to the efficiency of the preflow algorithm, an

    52   /// efficient matching framework is obtained.

    53   /// \ingroup galgs

    54   template <typename Graph, typename EdgeCap, typename NodeCap,

    55 	    typename EdgeFlow, typename NodeFlow>

    56   class MaxBipartiteMatching {

    57   protected:

    58     //   EdgeCap* edge_cap;

    59     //   NodeCap* node_cap;

    60     //   EdgeFlow* edge_flow;

    61     //   NodeFlow* node_flow;

    62     typedef  stBipartiteGraphWrapper<Graph> stGW;

    63     stGW stgw;

    64     typedef typename stGW::template EdgeMapWrapper<EdgeCap, NodeCap> CapMap;

    65     CapMap cap;

    66     NodeFlow* node_flow;

    67     typedef typename stGW::template EdgeMapWrapper<EdgeFlow, NodeFlow> FlowMap;

    68     FlowMap flow;

    69     typedef MaxFlow<stGW, int, CapMap, FlowMap> MaxFlow;

    70     MaxFlow mf;

    71     //graph* g;

    72     //EdgeCap* edge_cap;

    73     //EdgeFlow* edge_flow;

    74   public:

    75     enum MatchingEnum{

    76       ZERO_MATCHING,

    77       GEN_MATCHING,

    78       GEN_MATCHING_WITH_GOOD_NODE_FLOW,

    79       NO_MATCHING

    80     };

    81     /// For capacitated b-matchings, edge-caoacities and node-capacities

    82     /// have to be given. After running \c run the matching is is given

    83     /// back in the edge-map \c _edge_flow and \c _node_map can be used

    84     /// to obtain saturation information about nodes.

    85     ///\bug Note that the values in _edge_flow and _node_flow have

    86     /// to form a flow.

    87     MaxBipartiteMatching(Graph& _g, EdgeCap& _edge_cap, NodeCap& _node_cap,

    88 		EdgeFlow& _edge_flow, NodeFlow& _node_flow) :

    89       stgw(_g),

    90       cap(_edge_cap, _node_cap),

    91       node_flow(0),

    92       flow(_edge_flow, _node_flow),

    93       mf(stgw, stgw.S_NODE, stgw.T_NODE, cap, flow) { }

    94     /// If the saturation information of nodes is not needed that the use of

    95     /// this constructor is more comfortable.

    96     ///\bug Note that the values in _edge_flow and _node_flow have

    97     /// to form a flow.

    98     MaxBipartiteMatching(Graph& _g, EdgeCap& _edge_cap, NodeCap& _node_cap,

    99 		EdgeFlow& _edge_flow/*, NodeFlow& _node_flow*/) :

   100       stgw(_g),

   101       cap(_edge_cap, _node_cap),

   102       node_flow(new NodeFlow(_g)),

   103       flow(_edge_flow, *node_flow),

   104       mf(stgw, stgw.S_NODE, stgw.T_NODE, cap, flow) { }

   105     /// The class have a nontrivial destructor.

   106     ~MaxBipartiteMatching() { if (node_flow) delete node_flow; }

   107     /// run computes the max matching.

   108     void run(MatchingEnum me=ZERO_MATCHING) {

   109       switch (me) {

   110 	case ZERO_MATCHING:

   111 	  mf.run(MaxFlow::ZERO_FLOW);

   112 	  break;

   113 	case GEN_MATCHING:

   114 	{

   115 	  typename stGW::OutEdgeIt e;

   116 	  for (stgw.first(e, stgw.S_NODE); stgw.valid(e); stgw.next(e))

   117 	    flow.set(e, cap[e]);

   118 	}

   119 	{

   120 	  typename stGW::InEdgeIt e;

   121 	  for (stgw.first(e, stgw.T_NODE); stgw.valid(e); stgw.next(e))

   122 	    flow.set(e, 0);

   123 	}

   124 	mf.run(MaxFlow::PRE_FLOW);

   125 	break;

   126 	case GEN_MATCHING_WITH_GOOD_NODE_FLOW:

   127 	  mf.run(MaxFlow::GEN_FLOW);

   128 	  break;

   129 	case NO_MATCHING:

   130 	  mf.run(MaxFlow::NO_FLOW);

   131 	  break;

   132       }

   133     }

   134     /// The matching value after running \c run.

   135     int matchingValue() const { return mf.flowValue(); }

   136   };

   138 } //namespace hugo

   140 #endif //HUGO_MAX_BIPARTITE_MATCHING_H

author	deba
	Wed, 08 Sep 2004 12:06:45 +0000 (2004-09-08)
changeset 822	88226d9fe821
parent 762	511200bdb71f
child 921	818510fa3d99
permissions	-rw-r--r--