1.1 --- a/src/work/marci/bipartite_matching_try_3.cc Thu Aug 19 11:34:48 2004 +0000
1.2 +++ b/src/work/marci/bipartite_matching_try_3.cc Mon Aug 23 11:06:00 2004 +0000
1.3 @@ -17,6 +17,9 @@
1.4
1.5 using namespace hugo;
1.6
1.7 +using std::cout;
1.8 +using std::endl;
1.9 +
1.10 int main() {
1.11 //typedef UndirListGraph Graph;
1.12 typedef BipartiteGraph<SageGraph> Graph;
1.13 @@ -30,53 +33,54 @@
1.14 Graph g;
1.15
1.16 int a;
1.17 - std::cout << "number of nodes in the first color class=";
1.18 + cout << "number of nodes in the first color class=";
1.19 std::cin >> a;
1.20 int b;
1.21 - std::cout << "number of nodes in the second color class=";
1.22 + cout << "number of nodes in the second color class=";
1.23 std::cin >> b;
1.24 int m;
1.25 - std::cout << "number of edges=";
1.26 + cout << "number of edges=";
1.27 std::cin >> m;
1.28
1.29 - std::cout << "Generatig a random bipartite graph..." << std::endl;
1.30 + cout << "Generatig a random bipartite graph..." << endl;
1.31 random_init();
1.32 randomBipartiteGraph(g, a, b, m);
1.33
1.34 -// std::cout << "Edges of the bipartite graph:" << std::endl;
1.35 -// FOR_EACH_LOC(EdgeIt, e, g) std::cout << e << " ";
1.36 -// std::cout << std::endl;
1.37 +// cout << "Edges of the bipartite graph:" << endl;
1.38 +// FOR_EACH_LOC(EdgeIt, e, g) cout << e << " ";
1.39 +// cout << endl;
1.40
1.41 -// std::cout << "Nodes:" << std::endl;
1.42 -// FOR_EACH_LOC(Graph::NodeIt, v, g) std::cout << v << " ";
1.43 -// std::cout << std::endl;
1.44 -// std::cout << "Nodes in T:" << std::endl;
1.45 -// FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::T_CLASS) std::cout << v << " ";
1.46 -// std::cout << std::endl;
1.47 -// std::cout << "Nodes in S:" << std::endl;
1.48 -// FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::S_CLASS) std::cout << v << " ";
1.49 -// std::cout << std::endl;
1.50 +// cout << "Nodes:" << endl;
1.51 +// FOR_EACH_LOC(Graph::NodeIt, v, g) cout << v << " ";
1.52 +// cout << endl;
1.53 +// cout << "Nodes in T:" << endl;
1.54 +// FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::T_CLASS) cout << v << " ";
1.55 +// cout << endl;
1.56 +// cout << "Nodes in S:" << endl;
1.57 +// FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::S_CLASS) cout << v << " ";
1.58 +// cout << endl;
1.59
1.60 -// std::cout << "Erasing the first node..." << std::endl;
1.61 +// cout << "Erasing the first node..." << endl;
1.62 // NodeIt n;
1.63 // g.first(n);
1.64 // g.erase(n);
1.65 -// std::cout << "Nodes of the bipartite graph:" << std::endl;
1.66 -// FOR_EACH_GLOB(n, g) std::cout << n << " ";
1.67 -// std::cout << std::endl;
1.68 +// cout << "Nodes of the bipartite graph:" << endl;
1.69 +// FOR_EACH_GLOB(n, g) cout << n << " ";
1.70 +// cout << endl;
1.71
1.72 -// std::cout << "Nodes in T:" << std::endl;
1.73 -// FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::T_CLASS) std::cout << v << " ";
1.74 -// std::cout << std::endl;
1.75 -// std::cout << "Nodes in S:" << std::endl;
1.76 -// FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::S_CLASS) std::cout << v << " ";
1.77 -// std::cout << std::endl;
1.78 +// cout << "Nodes in T:" << endl;
1.79 +// FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::T_CLASS) cout << v << " ";
1.80 +// cout << endl;
1.81 +// cout << "Nodes in S:" << endl;
1.82 +// FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::S_CLASS) cout << v << " ";
1.83 +// cout << endl;
1.84
1.85 - typedef stGraphWrapper<Graph> stGW;
1.86 + typedef stBipartiteGraphWrapper<Graph> stGW;
1.87 stGW stgw(g);
1.88 ConstMap<stGW::Edge, int> const1map(1);
1.89
1.90 Timer ts;
1.91 + cout << "max bipartite matching with stGraphWrapper..." << endl;
1.92 ts.reset();
1.93 stGW::EdgeMap<int> flow(stgw);
1.94 MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> >
1.95 @@ -86,14 +90,14 @@
1.96 // typedef ListGraph MutableGraph;
1.97 // while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) {
1.98 // while (max_flow_test.augmentOnBlockingFlow2()) {
1.99 -// std::cout << max_flow_test.flowValue() << std::endl;
1.100 +// cout << max_flow_test.flowValue() << endl;
1.101 // }
1.102 - std::cout << "max flow value: " << max_flow_test.flowValue() << std::endl;
1.103 - std::cout << "elapsed time: " << ts << std::endl;
1.104 + cout << "matching value: " << max_flow_test.flowValue() << endl;
1.105 + cout << "elapsed time: " << ts << endl;
1.106 // FOR_EACH_LOC(stGW::EdgeIt, e, stgw) {
1.107 -// if (flow[e]) std::cout << e << std::endl;
1.108 +// if (flow[e]) cout << e << endl;
1.109 // }
1.110 - std::cout << std::endl;
1.111 + cout << endl;
1.112
1.113 typedef ConstMap<Graph::Edge, int> EdgeCap;
1.114 EdgeCap ge1(1);
1.115 @@ -104,12 +108,13 @@
1.116 typedef Graph::NodeMap<int> NodeFlow;
1.117 NodeFlow gnf(g); //0
1.118
1.119 - typedef stGraphWrapper<Graph>::EdgeMapWrapper<EdgeCap, NodeCap> CapMap;
1.120 - typedef stGraphWrapper<Graph>::EdgeMapWrapper<EdgeFlow, NodeFlow> FlowMap;
1.121 + typedef stGW::EdgeMapWrapper<EdgeCap, NodeCap> CapMap;
1.122 + typedef stGW::EdgeMapWrapper<EdgeFlow, NodeFlow> FlowMap;
1.123 CapMap cm(ge1, gn1);
1.124 FlowMap fm(gef, gnf);
1.125
1.126 //Timer ts;
1.127 + cout << "max bipartite matching with stGraphWrapper..." << endl;
1.128 ts.reset();
1.129 //stGW::EdgeMap<int> flow(stgw);
1.130 MaxFlow<stGW, int, CapMap, FlowMap>
1.131 @@ -119,15 +124,16 @@
1.132 // typedef ListGraph MutableGraph;
1.133 // while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) {
1.134 // while (max_flow_test.augmentOnBlockingFlow2()) {
1.135 -// std::cout << max_flow_test.flowValue() << std::endl;
1.136 +// cout << max_flow_test.flowValue() << endl;
1.137 // }
1.138 - std::cout << "max flow value: " << max_flow_test1.flowValue() << std::endl;
1.139 - std::cout << "elapsed time: " << ts << std::endl;
1.140 + cout << "matching value: " << max_flow_test1.flowValue() << endl;
1.141 + cout << "elapsed time: " << ts << endl;
1.142 // FOR_EACH_LOC(Graph::EdgeIt, e, g) {
1.143 -// if (gef[e]) std::cout << e << std::endl;
1.144 +// if (gef[e]) cout << e << endl;
1.145 // }
1.146 - std::cout << std::endl;
1.147 + cout << endl;
1.148
1.149 + cout << "max bipartite matching with stGraphWrapper..." << endl;
1.150 ts.reset();
1.151 FOR_EACH_LOC(Graph::EdgeIt, e, g) gef.set(e, 0);
1.152 FOR_EACH_LOC(Graph::NodeIt, n, g) gnf.set(n, 0);
1.153 @@ -136,27 +142,41 @@
1.154 matching_test(g, ge1, gn1, gef, gnf);
1.155 matching_test.run();
1.156
1.157 - std::cout << "max flow value: " << matching_test.matchingValue() << std::endl;
1.158 - std::cout << "elapsed time: " << ts << std::endl;
1.159 + cout << "matching value: " << matching_test.matchingValue() << endl;
1.160 + cout << "elapsed time: " << ts << endl;
1.161 // FOR_EACH_LOC(Graph::EdgeIt, e, g) {
1.162 -// if (gef[e]) std::cout << e << std::endl;
1.163 +// if (gef[e]) cout << e << endl;
1.164 // }
1.165 - std::cout << std::endl;
1.166 + cout << endl;
1.167
1.168 + cout << "max bipartite matching with MaxBipartiteMatching..." << endl;
1.169 ts.reset();
1.170 FOR_EACH_LOC(Graph::EdgeIt, e, g) gef.set(e, 0);
1.171 //FOR_EACH_LOC(Graph::NodeIt, n, g) gnf.set(n, 0);
1.172 - MaxBipartiteMatching<Graph, ConstMap<Graph::Edge, int>, ConstMap<Graph::Node, int>,
1.173 - Graph::EdgeMap<int>, Graph::NodeMap<int> >
1.174 - matching_test_1(g, ge1, gn1, gef/*, gnf*/);
1.175 + typedef MaxBipartiteMatching<Graph, ConstMap<Graph::Edge, int>,
1.176 + ConstMap<Graph::Node, int>,
1.177 + Graph::EdgeMap<int>, Graph::NodeMap<int> > MaxBipartiteMatching;
1.178 + MaxBipartiteMatching matching_test_1(g, ge1, gn1, gef/*, gnf*/);
1.179 matching_test_1.run();
1.180
1.181 - std::cout << "max flow value: " << matching_test_1.matchingValue() << std::endl;
1.182 - std::cout << "elapsed time: " << ts << std::endl;
1.183 + cout << "matching value: " << matching_test_1.matchingValue() << endl;
1.184 + cout << "elapsed time: " << ts << endl;
1.185 // FOR_EACH_LOC(Graph::EdgeIt, e, g) {
1.186 -// if (gef[e]) std::cout << e << std::endl;
1.187 +// if (gef[e]) cout << e << endl;
1.188 // }
1.189 - std::cout << std::endl;
1.190 + cout << endl;
1.191 +
1.192 + cout << "testing optimality with MaxBipartiteMatching..." << endl;
1.193 + ts.reset();
1.194 + matching_test_1.run(MaxBipartiteMatching::GEN_MATCHING);
1.195 + cout << "matching value: " << matching_test_1.matchingValue() << endl;
1.196 + cout << "elapsed time: " << ts << endl;
1.197 +
1.198 + cout << "testing optimality with MaxBipartiteMatching..." << endl;
1.199 + ts.reset();
1.200 + matching_test_1.run(MaxBipartiteMatching::GEN_MATCHING_WITH_GOOD_NODE_FLOW);
1.201 + cout << "matching value: " << matching_test_1.matchingValue() << endl;
1.202 + cout << "elapsed time: " << ts << endl;
1.203
1.204 return 0;
1.205 }