1.1 --- a/src/work/marci/bipartite_matching_demo.cc Sun Apr 17 18:57:22 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,183 +0,0 @@
1.4 -// -*- c++ -*-
1.5 -#include <iostream>
1.6 -#include <fstream>
1.7 -#include <vector>
1.8 -
1.9 -#include <sage_graph.h>
1.10 -//#include <smart_graph.h>
1.11 -//#include <dimacs.h>
1.12 -#include <lemon/time_measure.h>
1.13 -#include <for_each_macros.h>
1.14 -#include <bfs_dfs.h>
1.15 -#include <bipartite_graph_wrapper.h>
1.16 -#include <lemon/maps.h>
1.17 -#include <lemon/max_flow.h>
1.18 -#include <graph_gen.h>
1.19 -#include <max_bipartite_matching.h>
1.20 -
1.21 -using namespace lemon;
1.22 -
1.23 -using std::cin;
1.24 -using std::cout;
1.25 -using std::endl;
1.26 -
1.27 -int main() {
1.28 - //typedef UndirListGraph Graph;
1.29 - typedef BipartiteGraph<SageGraph> Graph;
1.30 -
1.31 - typedef Graph::Node Node;
1.32 - typedef Graph::NodeIt NodeIt;
1.33 - typedef Graph::Edge Edge;
1.34 - typedef Graph::EdgeIt EdgeIt;
1.35 - typedef Graph::OutEdgeIt OutEdgeIt;
1.36 -
1.37 - Graph g;
1.38 -
1.39 - int a;
1.40 - cout << "number of nodes in the first color class=";
1.41 - cin >> a;
1.42 - int b;
1.43 - cout << "number of nodes in the second color class=";
1.44 - cin >> b;
1.45 - int m;
1.46 - cout << "number of edges=";
1.47 - cin >> m;
1.48 -
1.49 - cout << "Generatig a random bipartite graph..." << endl;
1.50 - random_init();
1.51 - randomBipartiteGraph(g, a, b, m);
1.52 -
1.53 -// cout << "Edges of the bipartite graph:" << endl;
1.54 -// FOR_EACH_LOC(EdgeIt, e, g) cout << e << " ";
1.55 -// cout << endl;
1.56 -
1.57 -// cout << "Nodes:" << endl;
1.58 -// FOR_EACH_LOC(Graph::NodeIt, v, g) cout << v << " ";
1.59 -// cout << endl;
1.60 -// cout << "Nodes in T:" << endl;
1.61 -// FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::T_CLASS) cout << v << " ";
1.62 -// cout << endl;
1.63 -// cout << "Nodes in S:" << endl;
1.64 -// FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::S_CLASS) cout << v << " ";
1.65 -// cout << endl;
1.66 -
1.67 -// cout << "Erasing the first node..." << endl;
1.68 -// NodeIt n;
1.69 -// g.first(n);
1.70 -// g.erase(n);
1.71 -// cout << "Nodes of the bipartite graph:" << endl;
1.72 -// FOR_EACH_GLOB(n, g) cout << n << " ";
1.73 -// cout << endl;
1.74 -
1.75 -// cout << "Nodes in T:" << endl;
1.76 -// FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::T_CLASS) cout << v << " ";
1.77 -// cout << endl;
1.78 -// cout << "Nodes in S:" << endl;
1.79 -// FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::S_CLASS) cout << v << " ";
1.80 -// cout << endl;
1.81 -
1.82 - typedef stBipartiteGraphWrapper<Graph> stGW;
1.83 - stGW stgw(g);
1.84 - ConstMap<stGW::Edge, int> const1map(1);
1.85 -
1.86 - Timer ts;
1.87 - cout << "max bipartite matching with stGraphWrapper..." << endl;
1.88 - ts.reset();
1.89 - stGW::EdgeMap<int> flow(stgw);
1.90 - MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> >
1.91 - max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow);
1.92 - max_flow_test.run();
1.93 -// while (max_flow_test.augmentOnShortestPath()) { }
1.94 -// typedef ListGraph MutableGraph;
1.95 -// while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) {
1.96 -// while (max_flow_test.augmentOnBlockingFlow2()) {
1.97 -// cout << max_flow_test.flowValue() << endl;
1.98 -// }
1.99 - cout << "matching value: " << max_flow_test.flowValue() << endl;
1.100 - cout << "elapsed time: " << ts << endl;
1.101 -// FOR_EACH_LOC(stGW::EdgeIt, e, stgw) {
1.102 -// if (flow[e]) cout << e << endl;
1.103 -// }
1.104 - cout << endl;
1.105 -
1.106 - typedef ConstMap<Graph::Edge, int> EdgeCap;
1.107 - EdgeCap ge1(1);
1.108 - typedef ConstMap<Graph::Node, int> NodeCap;
1.109 - NodeCap gn1(1);
1.110 - typedef Graph::EdgeMap<int> EdgeFlow;
1.111 - EdgeFlow gef(g); //0
1.112 - typedef Graph::NodeMap<int> NodeFlow;
1.113 - NodeFlow gnf(g); //0
1.114 -
1.115 - typedef stGW::EdgeMapWrapper<EdgeCap, NodeCap> CapMap;
1.116 - typedef stGW::EdgeMapWrapper<EdgeFlow, NodeFlow> FlowMap;
1.117 - CapMap cm(ge1, gn1);
1.118 - FlowMap fm(gef, gnf);
1.119 -
1.120 - //Timer ts;
1.121 - cout << "max bipartite matching with stGraphWrapper..." << endl;
1.122 - ts.reset();
1.123 - //stGW::EdgeMap<int> flow(stgw);
1.124 - MaxFlow<stGW, int, CapMap, FlowMap>
1.125 - max_flow_test1(stgw, stgw.S_NODE, stgw.T_NODE, cm, fm);
1.126 - max_flow_test1.run();
1.127 -// while (max_flow_test.augmentOnShortestPath()) { }
1.128 -// typedef ListGraph MutableGraph;
1.129 -// while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) {
1.130 -// while (max_flow_test.augmentOnBlockingFlow2()) {
1.131 -// cout << max_flow_test.flowValue() << endl;
1.132 -// }
1.133 - cout << "matching value: " << max_flow_test1.flowValue() << endl;
1.134 - cout << "elapsed time: " << ts << endl;
1.135 -// FOR_EACH_LOC(Graph::EdgeIt, e, g) {
1.136 -// if (gef[e]) cout << e << endl;
1.137 -// }
1.138 - cout << endl;
1.139 -
1.140 - cout << "max bipartite matching with stGraphWrapper..." << endl;
1.141 - ts.reset();
1.142 - FOR_EACH_LOC(Graph::EdgeIt, e, g) gef.set(e, 0);
1.143 - FOR_EACH_LOC(Graph::NodeIt, n, g) gnf.set(n, 0);
1.144 - MaxBipartiteMatching<Graph, ConstMap<Graph::Edge, int>, ConstMap<Graph::Node, int>,
1.145 - Graph::EdgeMap<int>, Graph::NodeMap<int> >
1.146 - matching_test(g, ge1, gn1, gef, gnf);
1.147 - matching_test.run();
1.148 -
1.149 - cout << "matching value: " << matching_test.matchingValue() << endl;
1.150 - cout << "elapsed time: " << ts << endl;
1.151 -// FOR_EACH_LOC(Graph::EdgeIt, e, g) {
1.152 -// if (gef[e]) cout << e << endl;
1.153 -// }
1.154 - cout << endl;
1.155 -
1.156 - cout << "max bipartite matching with MaxBipartiteMatching..." << endl;
1.157 - ts.reset();
1.158 - FOR_EACH_LOC(Graph::EdgeIt, e, g) gef.set(e, 0);
1.159 - //FOR_EACH_LOC(Graph::NodeIt, n, g) gnf.set(n, 0);
1.160 - typedef MaxBipartiteMatching<Graph, ConstMap<Graph::Edge, int>,
1.161 - ConstMap<Graph::Node, int>,
1.162 - Graph::EdgeMap<int>, Graph::NodeMap<int> > MaxBipartiteMatching;
1.163 - MaxBipartiteMatching matching_test_1(g, ge1, gn1, gef/*, gnf*/);
1.164 - matching_test_1.run();
1.165 -
1.166 - cout << "matching value: " << matching_test_1.matchingValue() << endl;
1.167 - cout << "elapsed time: " << ts << endl;
1.168 -// FOR_EACH_LOC(Graph::EdgeIt, e, g) {
1.169 -// if (gef[e]) cout << e << endl;
1.170 -// }
1.171 - cout << endl;
1.172 -
1.173 - cout << "testing optimality with MaxBipartiteMatching..." << endl;
1.174 - ts.reset();
1.175 - matching_test_1.run(MaxBipartiteMatching::GEN_MATCHING);
1.176 - cout << "matching value: " << matching_test_1.matchingValue() << endl;
1.177 - cout << "elapsed time: " << ts << endl;
1.178 -
1.179 - cout << "testing optimality with MaxBipartiteMatching..." << endl;
1.180 - ts.reset();
1.181 - matching_test_1.run(MaxBipartiteMatching::GEN_MATCHING_WITH_GOOD_NODE_FLOW);
1.182 - cout << "matching value: " << matching_test_1.matchingValue() << endl;
1.183 - cout << "elapsed time: " << ts << endl;
1.184 -
1.185 - return 0;
1.186 -}