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 marci@510: #include marci@559: //#include marci@762: #include marci@510: marci@559: namespace hugo { marci@510: marci@559: // template marci@559: // class MaxMatching : public MaxFlow, marci@559: // stGraphWrapper:: EdgeMapWrapper, stGraphWrapper::EdgeMapWrapper > { marci@559: // typedef MaxFlow, marci@559: // stGraphWrapper::EdgeMapWrapper, marci@559: // stGraphWrapper::EdgeMapWrapper > marci@559: // Parent; marci@559: // protected: marci@559: // stGraphWrapper gw; marci@559: // stGraphWrapper::EdgeMapWrapper cap; marci@559: // stGraphWrapper::EdgeMapWrapper 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 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 stGW; marci@559: stGW stgw; marci@559: typedef typename stGW::template EdgeMapWrapper CapMap; marci@559: CapMap cap; marci@559: NodeFlow* node_flow; marci@559: typedef typename stGW::template EdgeMapWrapper FlowMap; marci@559: FlowMap flow; marci@768: typedef MaxFlow 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