1.1 --- a/src/work/marci/bipartite_matching_try_3.cc Thu May 06 17:22:11 2004 +0000
1.2 +++ b/src/work/marci/bipartite_matching_try_3.cc Thu May 06 17:45:12 2004 +0000
1.3 @@ -13,73 +13,10 @@
1.4 #include <hugo/maps.h>
1.5 #include <max_flow.h>
1.6 #include <graph_gen.h>
1.7 +#include <max_bipartite_matching.h>
1.8
1.9 using namespace hugo;
1.10
1.11 -// template <typename Graph, typename EdgeCap, typename NodeCap,
1.12 -// typename EdgeFlow, typename NodeFlow>
1.13 -// class MaxMatching : public MaxFlow<stGraphWrapper<Graph>,
1.14 -// stGraphWrapper<Graph>:: EdgeMapWrapper<EdgeCan, NodeCap>, stGraphWrapper<Graph>::EdgeMapWrapper<EdgeFlow, NodeFlow> > {
1.15 -// typedef MaxFlow<stGraphWrapper<Graph>,
1.16 -// stGraphWrapper<Graph>::EdgeMapWrapper<EdgeCan, NodeCap>,
1.17 -// stGraphWrapper<Graph>::EdgeMapWrapper<EdgeFlow, NodeFlow> >
1.18 -// Parent;
1.19 -// protected:
1.20 -// stGraphWrapper<Graph> gw;
1.21 -// stGraphWrapper<Graph>::EdgeMapWrapper<EdgeCap, NodeCap> cap;
1.22 -// stGraphWrapper<Graph>::EdgeMapWrapper<EdgeFlow, NodeFlow> flow;
1.23 -// //graph* g;
1.24 -// //EdgeCap* edge_cap;
1.25 -// //EdgeFlow* edge_flow;
1.26 -// public:
1.27 -// MaxMatching(Graph& _g, EdgeCap& _edge_cap, NodeCap& _node_cap,
1.28 -// EdgeFlow& _edge_flow, NodeFlow& _node_flow) :
1.29 -// MaxFlow(), gw(_g),
1.30 -// cap(_edge_cap, _node_cap), flow(_edge_flow, _node_flow) {
1.31 -// Parent::set(gw, cap, flow);
1.32 -// }
1.33 -// };
1.34 -
1.35 -template <typename Graph, typename EdgeCap, typename NodeCap,
1.36 - typename EdgeFlow, typename NodeFlow>
1.37 -class MaxMatching {
1.38 -protected:
1.39 -// EdgeCap* edge_cap;
1.40 -// NodeCap* node_cap;
1.41 -// EdgeFlow* edge_flow;
1.42 -// NodeFlow* node_flow;
1.43 - typedef stGraphWrapper<Graph> stGW;
1.44 - stGW stgw;
1.45 - typedef typename stGW::template EdgeMapWrapper<EdgeCap, NodeCap> CapMap;
1.46 - CapMap cap;
1.47 - NodeFlow* node_flow;
1.48 - typedef typename stGW::template EdgeMapWrapper<EdgeFlow, NodeFlow> FlowMap;
1.49 - FlowMap flow;
1.50 - MaxFlow<stGW, int, CapMap, FlowMap> mf;
1.51 - //graph* g;
1.52 - //EdgeCap* edge_cap;
1.53 - //EdgeFlow* edge_flow;
1.54 -public:
1.55 - MaxMatching(Graph& _g, EdgeCap& _edge_cap, NodeCap& _node_cap,
1.56 - EdgeFlow& _edge_flow, NodeFlow& _node_flow) :
1.57 - stgw(_g),
1.58 - cap(_edge_cap, _node_cap),
1.59 - node_flow(0),
1.60 - flow(_edge_flow, _node_flow),
1.61 - mf(stgw, stgw.S_NODE, stgw.T_NODE, cap, flow) { }
1.62 - MaxMatching(Graph& _g, EdgeCap& _edge_cap, NodeCap& _node_cap,
1.63 - EdgeFlow& _edge_flow/*, NodeFlow& _node_flow*/) :
1.64 - stgw(_g),
1.65 - cap(_edge_cap, _node_cap),
1.66 - node_flow(new NodeFlow(_g)),
1.67 - flow(_edge_flow, *node_flow),
1.68 - mf(stgw, stgw.S_NODE, stgw.T_NODE, cap, flow) { }
1.69 - ~MaxMatching() { if (node_flow) delete node_flow; }
1.70 - void run() { mf.run(); }
1.71 - int matchingValue() { return mf.flowValue(); }
1.72 -};
1.73 -
1.74 -
1.75 int main() {
1.76 //typedef UndirListGraph Graph;
1.77 typedef BipartiteGraph<ListGraph> Graph;
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/src/work/marci/max_bipartite_matching.h Thu May 06 17:45:12 2004 +0000
2.3 @@ -0,0 +1,96 @@
2.4 +// -*- c++ -*-
2.5 +#ifndef HUGO_MAX_BIPARTITE_MATCHING_H
2.6 +#define HUGO_MAX_BIPARTITE_MATCHING_H
2.7 +
2.8 +//#include <for_each_macros.h>
2.9 +#include <bipartite_graph_wrapper.h>
2.10 +//#include <hugo/maps.h>
2.11 +#include <max_flow.h>
2.12 +
2.13 +namespace hugo {
2.14 +
2.15 + // template <typename Graph, typename EdgeCap, typename NodeCap,
2.16 + // typename EdgeFlow, typename NodeFlow>
2.17 + // class MaxMatching : public MaxFlow<stGraphWrapper<Graph>,
2.18 + // stGraphWrapper<Graph>:: EdgeMapWrapper<EdgeCan, NodeCap>, stGraphWrapper<Graph>::EdgeMapWrapper<EdgeFlow, NodeFlow> > {
2.19 + // typedef MaxFlow<stGraphWrapper<Graph>,
2.20 + // stGraphWrapper<Graph>::EdgeMapWrapper<EdgeCan, NodeCap>,
2.21 + // stGraphWrapper<Graph>::EdgeMapWrapper<EdgeFlow, NodeFlow> >
2.22 + // Parent;
2.23 + // protected:
2.24 + // stGraphWrapper<Graph> gw;
2.25 + // stGraphWrapper<Graph>::EdgeMapWrapper<EdgeCap, NodeCap> cap;
2.26 + // stGraphWrapper<Graph>::EdgeMapWrapper<EdgeFlow, NodeFlow> flow;
2.27 + // //graph* g;
2.28 + // //EdgeCap* edge_cap;
2.29 + // //EdgeFlow* edge_flow;
2.30 + // public:
2.31 + // MaxMatching(Graph& _g, EdgeCap& _edge_cap, NodeCap& _node_cap,
2.32 + // EdgeFlow& _edge_flow, NodeFlow& _node_flow) :
2.33 + // MaxFlow(), gw(_g),
2.34 + // cap(_edge_cap, _node_cap), flow(_edge_flow, _node_flow) {
2.35 + // Parent::set(gw, cap, flow);
2.36 + // }
2.37 + // };
2.38 +
2.39 + /// A bipartite matching class.
2.40 + /// This class reduces the matching problem to a flow problem and
2.41 + /// a preflow is used on a wrapper. Such a generic approach means that
2.42 + /// matchings, b-matchings an capacitated b-matchings can be handled in
2.43 + /// a similar way. Due to the efficiency of the preflow algorithm, an
2.44 + /// efficient matching framework is obtained.
2.45 + template <typename Graph, typename EdgeCap, typename NodeCap,
2.46 + typename EdgeFlow, typename NodeFlow>
2.47 + class MaxMatching {
2.48 + protected:
2.49 + // EdgeCap* edge_cap;
2.50 + // NodeCap* node_cap;
2.51 + // EdgeFlow* edge_flow;
2.52 + // NodeFlow* node_flow;
2.53 + typedef stGraphWrapper<Graph> stGW;
2.54 + stGW stgw;
2.55 + typedef typename stGW::template EdgeMapWrapper<EdgeCap, NodeCap> CapMap;
2.56 + CapMap cap;
2.57 + NodeFlow* node_flow;
2.58 + typedef typename stGW::template EdgeMapWrapper<EdgeFlow, NodeFlow> FlowMap;
2.59 + FlowMap flow;
2.60 + MaxFlow<stGW, int, CapMap, FlowMap> mf;
2.61 + //graph* g;
2.62 + //EdgeCap* edge_cap;
2.63 + //EdgeFlow* edge_flow;
2.64 + public:
2.65 + /// For capacitated b-matchings, edge-caoacities and node-capacities
2.66 + /// have to be given. After running \c run the matching is is given
2.67 + /// back in the edge-map \c _edge_flow and \c _node_map can be used
2.68 + /// to obtain saturation information about nodes.
2.69 + ///\bug Note that the values in _edge_flow and _node_flow have
2.70 + /// to form a flow.
2.71 + MaxMatching(Graph& _g, EdgeCap& _edge_cap, NodeCap& _node_cap,
2.72 + EdgeFlow& _edge_flow, NodeFlow& _node_flow) :
2.73 + stgw(_g),
2.74 + cap(_edge_cap, _node_cap),
2.75 + node_flow(0),
2.76 + flow(_edge_flow, _node_flow),
2.77 + mf(stgw, stgw.S_NODE, stgw.T_NODE, cap, flow) { }
2.78 + /// If the saturation information of nodes is not needed that the use of
2.79 + /// this constructor is more comfortable.
2.80 + ///\bug Note that the values in _edge_flow and _node_flow have
2.81 + /// to form a flow.
2.82 + MaxMatching(Graph& _g, EdgeCap& _edge_cap, NodeCap& _node_cap,
2.83 + EdgeFlow& _edge_flow/*, NodeFlow& _node_flow*/) :
2.84 + stgw(_g),
2.85 + cap(_edge_cap, _node_cap),
2.86 + node_flow(new NodeFlow(_g)),
2.87 + flow(_edge_flow, *node_flow),
2.88 + mf(stgw, stgw.S_NODE, stgw.T_NODE, cap, flow) { }
2.89 + /// The class have a nontrivial destructor.
2.90 + ~MaxMatching() { if (node_flow) delete node_flow; }
2.91 + /// run computes the max matching.
2.92 + void run() { mf.run(); }
2.93 + /// The matching value after running \c run.
2.94 + int matchingValue() { return mf.flowValue(); }
2.95 + };
2.96 +
2.97 +} //namespace hugo
2.98 +
2.99 +#endif //HUGO_MAX_BIPARTITE_MATCHING_H