1.1 --- a/src/work/marci/bipartite_matching_try_3.cc Mon May 03 10:27:20 2004 +0000
1.2 +++ b/src/work/marci/bipartite_matching_try_3.cc Mon May 03 11:43:27 2004 +0000
1.3 @@ -43,12 +43,6 @@
1.4 template <typename Graph, typename EdgeCap, typename NodeCap,
1.5 typename EdgeFlow, typename NodeFlow>
1.6 class MaxMatching {
1.7 -// : public MaxFlow<stGraphWrapper<Graph>,
1.8 -// stGraphWrapper<Graph>:: EdgeMapWrapper<EdgeCan, NodeCap>, stGraphWrapper<Graph>::EdgeMapWrapper<EdgeFlow, NodeFlow> > {
1.9 -// typedef MaxFlow<stGraphWrapper<Graph>,
1.10 -// stGraphWrapper<Graph>::EdgeMapWrapper<EdgeCan, NodeCap>,
1.11 -// stGraphWrapper<Graph>::EdgeMapWrapper<EdgeFlow, NodeFlow> >
1.12 -// Parent;
1.13 protected:
1.14 // EdgeCap* edge_cap;
1.15 // NodeCap* node_cap;
1.16 @@ -58,6 +52,7 @@
1.17 stGW stgw;
1.18 typedef typename stGW::template EdgeMapWrapper<EdgeCap, NodeCap> CapMap;
1.19 CapMap cap;
1.20 + NodeFlow* node_flow;
1.21 typedef typename stGW::template EdgeMapWrapper<EdgeFlow, NodeFlow> FlowMap;
1.22 FlowMap flow;
1.23 MaxFlow<stGW, int, CapMap, FlowMap> mf;
1.24 @@ -68,8 +63,18 @@
1.25 MaxMatching(Graph& _g, EdgeCap& _edge_cap, NodeCap& _node_cap,
1.26 EdgeFlow& _edge_flow, NodeFlow& _node_flow) :
1.27 stgw(_g),
1.28 - cap(_edge_cap, _node_cap), flow(_edge_flow, _node_flow),
1.29 + cap(_edge_cap, _node_cap),
1.30 + node_flow(0),
1.31 + flow(_edge_flow, _node_flow),
1.32 mf(stgw, stgw.S_NODE, stgw.T_NODE, cap, flow) { }
1.33 + MaxMatching(Graph& _g, EdgeCap& _edge_cap, NodeCap& _node_cap,
1.34 + EdgeFlow& _edge_flow/*, NodeFlow& _node_flow*/) :
1.35 + stgw(_g),
1.36 + cap(_edge_cap, _node_cap),
1.37 + node_flow(new NodeFlow(_g)),
1.38 + flow(_edge_flow, *node_flow),
1.39 + mf(stgw, stgw.S_NODE, stgw.T_NODE, cap, flow) { }
1.40 + ~MaxMatching() { if (node_flow) delete node_flow; }
1.41 void run() { mf.run(); }
1.42 int matchingValue() { return mf.flowValue(); }
1.43 };
1.44 @@ -130,34 +135,34 @@
1.45 g.addEdge(s_nodes[random(a)], t_nodes[random(b)]);
1.46 }
1.47
1.48 - std::cout << "Edges of the bipartite graph:" << std::endl;
1.49 - FOR_EACH_LOC(EdgeIt, e, g) std::cout << e << " ";
1.50 - std::cout << std::endl;
1.51 +// std::cout << "Edges of the bipartite graph:" << std::endl;
1.52 +// FOR_EACH_LOC(EdgeIt, e, g) std::cout << e << " ";
1.53 +// std::cout << std::endl;
1.54
1.55 - std::cout << "Nodes:" << std::endl;
1.56 - FOR_EACH_LOC(Graph::NodeIt, v, g) std::cout << v << " ";
1.57 - std::cout << std::endl;
1.58 - std::cout << "Nodes in T:" << std::endl;
1.59 - FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::T_CLASS) std::cout << v << " ";
1.60 - std::cout << std::endl;
1.61 - std::cout << "Nodes in S:" << std::endl;
1.62 - FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::S_CLASS) std::cout << v << " ";
1.63 - std::cout << std::endl;
1.64 +// std::cout << "Nodes:" << std::endl;
1.65 +// FOR_EACH_LOC(Graph::NodeIt, v, g) std::cout << v << " ";
1.66 +// std::cout << std::endl;
1.67 +// std::cout << "Nodes in T:" << std::endl;
1.68 +// FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::T_CLASS) std::cout << v << " ";
1.69 +// std::cout << std::endl;
1.70 +// std::cout << "Nodes in S:" << std::endl;
1.71 +// FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::S_CLASS) std::cout << v << " ";
1.72 +// std::cout << std::endl;
1.73
1.74 - std::cout << "Erasing the first node..." << std::endl;
1.75 - NodeIt n;
1.76 - g.first(n);
1.77 - g.erase(n);
1.78 - std::cout << "Nodes of the bipartite graph:" << std::endl;
1.79 - FOR_EACH_GLOB(n, g) std::cout << n << " ";
1.80 - std::cout << std::endl;
1.81 +// std::cout << "Erasing the first node..." << std::endl;
1.82 +// NodeIt n;
1.83 +// g.first(n);
1.84 +// g.erase(n);
1.85 +// std::cout << "Nodes of the bipartite graph:" << std::endl;
1.86 +// FOR_EACH_GLOB(n, g) std::cout << n << " ";
1.87 +// std::cout << std::endl;
1.88
1.89 - std::cout << "Nodes in T:" << std::endl;
1.90 - FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::T_CLASS) std::cout << v << " ";
1.91 - std::cout << std::endl;
1.92 - std::cout << "Nodes in S:" << std::endl;
1.93 - FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::S_CLASS) std::cout << v << " ";
1.94 - std::cout << std::endl;
1.95 +// std::cout << "Nodes in T:" << std::endl;
1.96 +// FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::T_CLASS) std::cout << v << " ";
1.97 +// std::cout << std::endl;
1.98 +// std::cout << "Nodes in S:" << std::endl;
1.99 +// FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::S_CLASS) std::cout << v << " ";
1.100 +// std::cout << std::endl;
1.101
1.102 typedef stGraphWrapper<Graph> stGW;
1.103 stGW stgw(g);
1.104 @@ -177,9 +182,9 @@
1.105 // }
1.106 std::cout << "max flow value: " << max_flow_test.flowValue() << std::endl;
1.107 std::cout << "elapsed time: " << ts << std::endl;
1.108 - FOR_EACH_LOC(stGW::EdgeIt, e, stgw) {
1.109 - if (flow[e]) std::cout << e << std::endl;
1.110 - }
1.111 +// FOR_EACH_LOC(stGW::EdgeIt, e, stgw) {
1.112 +// if (flow[e]) std::cout << e << std::endl;
1.113 +// }
1.114 std::cout << std::endl;
1.115
1.116 typedef ConstMap<Graph::Edge, int> EdgeCap;
1.117 @@ -229,5 +234,21 @@
1.118 // if (gef[e]) std::cout << e << std::endl;
1.119 // }
1.120 std::cout << std::endl;
1.121 +
1.122 + ts.reset();
1.123 + FOR_EACH_LOC(Graph::EdgeIt, e, g) gef.set(e, 0);
1.124 + //FOR_EACH_LOC(Graph::NodeIt, n, g) gnf.set(n, 0);
1.125 + MaxMatching<Graph, ConstMap<Graph::Edge, int>, ConstMap<Graph::Node, int>,
1.126 + Graph::EdgeMap<int>, Graph::NodeMap<int> >
1.127 + matching_test_1(g, ge1, gn1, gef/*, gnf*/);
1.128 + matching_test_1.run();
1.129 +
1.130 + std::cout << "max flow value: " << matching_test_1.matchingValue() << std::endl;
1.131 + std::cout << "elapsed time: " << ts << std::endl;
1.132 +// FOR_EACH_LOC(Graph::EdgeIt, e, g) {
1.133 +// if (gef[e]) std::cout << e << std::endl;
1.134 +// }
1.135 + std::cout << std::endl;
1.136 +
1.137 return 0;
1.138 }