1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/work/marci/max_bipartite_matching.h Thu May 06 17:45:12 2004 +0000
1.3 @@ -0,0 +1,96 @@
1.4 +// -*- c++ -*-
1.5 +#ifndef HUGO_MAX_BIPARTITE_MATCHING_H
1.6 +#define HUGO_MAX_BIPARTITE_MATCHING_H
1.7 +
1.8 +//#include <for_each_macros.h>
1.9 +#include <bipartite_graph_wrapper.h>
1.10 +//#include <hugo/maps.h>
1.11 +#include <max_flow.h>
1.12 +
1.13 +namespace hugo {
1.14 +
1.15 + // template <typename Graph, typename EdgeCap, typename NodeCap,
1.16 + // typename EdgeFlow, typename NodeFlow>
1.17 + // class MaxMatching : public MaxFlow<stGraphWrapper<Graph>,
1.18 + // stGraphWrapper<Graph>:: EdgeMapWrapper<EdgeCan, NodeCap>, stGraphWrapper<Graph>::EdgeMapWrapper<EdgeFlow, NodeFlow> > {
1.19 + // typedef MaxFlow<stGraphWrapper<Graph>,
1.20 + // stGraphWrapper<Graph>::EdgeMapWrapper<EdgeCan, NodeCap>,
1.21 + // stGraphWrapper<Graph>::EdgeMapWrapper<EdgeFlow, NodeFlow> >
1.22 + // Parent;
1.23 + // protected:
1.24 + // stGraphWrapper<Graph> gw;
1.25 + // stGraphWrapper<Graph>::EdgeMapWrapper<EdgeCap, NodeCap> cap;
1.26 + // stGraphWrapper<Graph>::EdgeMapWrapper<EdgeFlow, NodeFlow> flow;
1.27 + // //graph* g;
1.28 + // //EdgeCap* edge_cap;
1.29 + // //EdgeFlow* edge_flow;
1.30 + // public:
1.31 + // MaxMatching(Graph& _g, EdgeCap& _edge_cap, NodeCap& _node_cap,
1.32 + // EdgeFlow& _edge_flow, NodeFlow& _node_flow) :
1.33 + // MaxFlow(), gw(_g),
1.34 + // cap(_edge_cap, _node_cap), flow(_edge_flow, _node_flow) {
1.35 + // Parent::set(gw, cap, flow);
1.36 + // }
1.37 + // };
1.38 +
1.39 + /// A bipartite matching class.
1.40 + /// This class reduces the matching problem to a flow problem and
1.41 + /// a preflow is used on a wrapper. Such a generic approach means that
1.42 + /// matchings, b-matchings an capacitated b-matchings can be handled in
1.43 + /// a similar way. Due to the efficiency of the preflow algorithm, an
1.44 + /// efficient matching framework is obtained.
1.45 + template <typename Graph, typename EdgeCap, typename NodeCap,
1.46 + typename EdgeFlow, typename NodeFlow>
1.47 + class MaxMatching {
1.48 + protected:
1.49 + // EdgeCap* edge_cap;
1.50 + // NodeCap* node_cap;
1.51 + // EdgeFlow* edge_flow;
1.52 + // NodeFlow* node_flow;
1.53 + typedef stGraphWrapper<Graph> stGW;
1.54 + stGW stgw;
1.55 + typedef typename stGW::template EdgeMapWrapper<EdgeCap, NodeCap> CapMap;
1.56 + CapMap cap;
1.57 + NodeFlow* node_flow;
1.58 + typedef typename stGW::template EdgeMapWrapper<EdgeFlow, NodeFlow> FlowMap;
1.59 + FlowMap flow;
1.60 + MaxFlow<stGW, int, CapMap, FlowMap> mf;
1.61 + //graph* g;
1.62 + //EdgeCap* edge_cap;
1.63 + //EdgeFlow* edge_flow;
1.64 + public:
1.65 + /// For capacitated b-matchings, edge-caoacities and node-capacities
1.66 + /// have to be given. After running \c run the matching is is given
1.67 + /// back in the edge-map \c _edge_flow and \c _node_map can be used
1.68 + /// to obtain saturation information about nodes.
1.69 + ///\bug Note that the values in _edge_flow and _node_flow have
1.70 + /// to form a flow.
1.71 + MaxMatching(Graph& _g, EdgeCap& _edge_cap, NodeCap& _node_cap,
1.72 + EdgeFlow& _edge_flow, NodeFlow& _node_flow) :
1.73 + stgw(_g),
1.74 + cap(_edge_cap, _node_cap),
1.75 + node_flow(0),
1.76 + flow(_edge_flow, _node_flow),
1.77 + mf(stgw, stgw.S_NODE, stgw.T_NODE, cap, flow) { }
1.78 + /// If the saturation information of nodes is not needed that the use of
1.79 + /// this constructor is more comfortable.
1.80 + ///\bug Note that the values in _edge_flow and _node_flow have
1.81 + /// to form a flow.
1.82 + MaxMatching(Graph& _g, EdgeCap& _edge_cap, NodeCap& _node_cap,
1.83 + EdgeFlow& _edge_flow/*, NodeFlow& _node_flow*/) :
1.84 + stgw(_g),
1.85 + cap(_edge_cap, _node_cap),
1.86 + node_flow(new NodeFlow(_g)),
1.87 + flow(_edge_flow, *node_flow),
1.88 + mf(stgw, stgw.S_NODE, stgw.T_NODE, cap, flow) { }
1.89 + /// The class have a nontrivial destructor.
1.90 + ~MaxMatching() { if (node_flow) delete node_flow; }
1.91 + /// run computes the max matching.
1.92 + void run() { mf.run(); }
1.93 + /// The matching value after running \c run.
1.94 + int matchingValue() { return mf.flowValue(); }
1.95 + };
1.96 +
1.97 +} //namespace hugo
1.98 +
1.99 +#endif //HUGO_MAX_BIPARTITE_MATCHING_H