1.1 --- a/src/work/marci/max_bipartite_matching.h Sun Apr 17 18:57:22 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,140 +0,0 @@
1.4 -// -*- c++ -*-
1.5 -#ifndef LEMON_MAX_BIPARTITE_MATCHING_H
1.6 -#define LEMON_MAX_BIPARTITE_MATCHING_H
1.7 -
1.8 -/// \ingroup galgs
1.9 -/// \file
1.10 -/// \brief Maximum bipartite matchings, b-matchings and
1.11 -/// capacitated b-matchings.
1.12 -///
1.13 -/// This file contains a class for bipartite maximum matching, b-matchings
1.14 -/// and capacitated b-matching computations.
1.15 -///
1.16 -// /// \author Marton Makai
1.17 -
1.18 -//#include <for_each_macros.h>
1.19 -#include <bipartite_graph_wrapper.h>
1.20 -//#include <lemon/maps.h>
1.21 -#include <lemon/max_flow.h>
1.22 -
1.23 -namespace lemon {
1.24 -
1.25 - // template <typename Graph, typename EdgeCap, typename NodeCap,
1.26 - // typename EdgeFlow, typename NodeFlow>
1.27 - // class MaxMatching : public MaxFlow<stGraphWrapper<Graph>,
1.28 - // stGraphWrapper<Graph>:: EdgeMapWrapper<EdgeCan, NodeCap>, stGraphWrapper<Graph>::EdgeMapWrapper<EdgeFlow, NodeFlow> > {
1.29 - // typedef MaxFlow<stGraphWrapper<Graph>,
1.30 - // stGraphWrapper<Graph>::EdgeMapWrapper<EdgeCan, NodeCap>,
1.31 - // stGraphWrapper<Graph>::EdgeMapWrapper<EdgeFlow, NodeFlow> >
1.32 - // Parent;
1.33 - // protected:
1.34 - // stGraphWrapper<Graph> gw;
1.35 - // stGraphWrapper<Graph>::EdgeMapWrapper<EdgeCap, NodeCap> cap;
1.36 - // stGraphWrapper<Graph>::EdgeMapWrapper<EdgeFlow, NodeFlow> flow;
1.37 - // //graph* g;
1.38 - // //EdgeCap* edge_cap;
1.39 - // //EdgeFlow* edge_flow;
1.40 - // public:
1.41 - // MaxMatching(Graph& _g, EdgeCap& _edge_cap, NodeCap& _node_cap,
1.42 - // EdgeFlow& _edge_flow, NodeFlow& _node_flow) :
1.43 - // MaxFlow(), gw(_g),
1.44 - // cap(_edge_cap, _node_cap), flow(_edge_flow, _node_flow) {
1.45 - // Parent::set(gw, cap, flow);
1.46 - // }
1.47 - // };
1.48 -
1.49 - /// \brief A bipartite matching class.
1.50 - ///
1.51 - /// This class reduces the matching problem to a flow problem and
1.52 - /// a preflow is used on a wrapper. Such a generic approach means that
1.53 - /// matchings, b-matchings an capacitated b-matchings can be handled in
1.54 - /// a similar way. Due to the efficiency of the preflow algorithm, an
1.55 - /// efficient matching framework is obtained.
1.56 - /// \ingroup galgs
1.57 - template <typename Graph, typename EdgeCap, typename NodeCap,
1.58 - typename EdgeFlow, typename NodeFlow>
1.59 - class MaxBipartiteMatching {
1.60 - protected:
1.61 - // EdgeCap* edge_cap;
1.62 - // NodeCap* node_cap;
1.63 - // EdgeFlow* edge_flow;
1.64 - // NodeFlow* node_flow;
1.65 - typedef stBipartiteGraphWrapper<Graph> stGW;
1.66 - stGW stgw;
1.67 - typedef typename stGW::template EdgeMapWrapper<EdgeCap, NodeCap> CapMap;
1.68 - CapMap cap;
1.69 - NodeFlow* node_flow;
1.70 - typedef typename stGW::template EdgeMapWrapper<EdgeFlow, NodeFlow> FlowMap;
1.71 - FlowMap flow;
1.72 - typedef MaxFlow<stGW, int, CapMap, FlowMap> MaxFlow;
1.73 - MaxFlow mf;
1.74 - //graph* g;
1.75 - //EdgeCap* edge_cap;
1.76 - //EdgeFlow* edge_flow;
1.77 - public:
1.78 - enum MatchingEnum{
1.79 - ZERO_MATCHING,
1.80 - GEN_MATCHING,
1.81 - GEN_MATCHING_WITH_GOOD_NODE_FLOW,
1.82 - NO_MATCHING
1.83 - };
1.84 - /// For capacitated b-matchings, edge-caoacities and node-capacities
1.85 - /// have to be given. After running \c run the matching is is given
1.86 - /// back in the edge-map \c _edge_flow and \c _node_map can be used
1.87 - /// to obtain saturation information about nodes.
1.88 - ///\bug Note that the values in _edge_flow and _node_flow have
1.89 - /// to form a flow.
1.90 - MaxBipartiteMatching(Graph& _g, EdgeCap& _edge_cap, NodeCap& _node_cap,
1.91 - EdgeFlow& _edge_flow, NodeFlow& _node_flow) :
1.92 - stgw(_g),
1.93 - cap(_edge_cap, _node_cap),
1.94 - node_flow(0),
1.95 - flow(_edge_flow, _node_flow),
1.96 - mf(stgw, stgw.S_NODE, stgw.T_NODE, cap, flow) { }
1.97 - /// If the saturation information of nodes is not needed that the use of
1.98 - /// this constructor is more comfortable.
1.99 - ///\bug Note that the values in _edge_flow and _node_flow have
1.100 - /// to form a flow.
1.101 - MaxBipartiteMatching(Graph& _g, EdgeCap& _edge_cap, NodeCap& _node_cap,
1.102 - EdgeFlow& _edge_flow/*, NodeFlow& _node_flow*/) :
1.103 - stgw(_g),
1.104 - cap(_edge_cap, _node_cap),
1.105 - node_flow(new NodeFlow(_g)),
1.106 - flow(_edge_flow, *node_flow),
1.107 - mf(stgw, stgw.S_NODE, stgw.T_NODE, cap, flow) { }
1.108 - /// The class have a nontrivial destructor.
1.109 - ~MaxBipartiteMatching() { if (node_flow) delete node_flow; }
1.110 - /// run computes the max matching.
1.111 - void run(MatchingEnum me=ZERO_MATCHING) {
1.112 - switch (me) {
1.113 - case ZERO_MATCHING:
1.114 - mf.run(MaxFlow::ZERO_FLOW);
1.115 - break;
1.116 - case GEN_MATCHING:
1.117 - {
1.118 - typename stGW::OutEdgeIt e;
1.119 - for (stgw.first(e, stgw.S_NODE); stgw.valid(e); stgw.next(e))
1.120 - flow.set(e, cap[e]);
1.121 - }
1.122 - {
1.123 - typename stGW::InEdgeIt e;
1.124 - for (stgw.first(e, stgw.T_NODE); stgw.valid(e); stgw.next(e))
1.125 - flow.set(e, 0);
1.126 - }
1.127 - mf.run(MaxFlow::PRE_FLOW);
1.128 - break;
1.129 - case GEN_MATCHING_WITH_GOOD_NODE_FLOW:
1.130 - mf.run(MaxFlow::GEN_FLOW);
1.131 - break;
1.132 - case NO_MATCHING:
1.133 - mf.run(MaxFlow::NO_FLOW);
1.134 - break;
1.135 - }
1.136 - }
1.137 - /// The matching value after running \c run.
1.138 - int matchingValue() const { return mf.flowValue(); }
1.139 - };
1.140 -
1.141 -} //namespace lemon
1.142 -
1.143 -#endif //LEMON_MAX_BIPARTITE_MATCHING_H