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;