1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/work/marci/bipartite_matching_demo.cc Mon Aug 23 11:44:36 2004 +0000
1.3 @@ -0,0 +1,183 @@
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 <hugo/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 <hugo/maps.h>
1.17 +#include <hugo/max_flow.h>
1.18 +#include <graph_gen.h>
1.19 +#include <max_bipartite_matching.h>
1.20 +
1.21 +using namespace hugo;
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 +}
2.1 --- a/src/work/marci/bipartite_matching_try.cc Mon Aug 23 11:28:26 2004 +0000
2.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
2.3 @@ -1,195 +0,0 @@
2.4 -// -*- c++ -*-
2.5 -#include <iostream>
2.6 -#include <fstream>
2.7 -#include <vector>
2.8 -#include <cstdlib>
2.9 -
2.10 -#include <sage_graph.h>
2.11 -//#include <smart_graph.h>
2.12 -//#include <dimacs.h>
2.13 -#include <hugo/time_measure.h>
2.14 -#include <for_each_macros.h>
2.15 -#include <bfs_dfs.h>
2.16 -#include <hugo/graph_wrapper.h>
2.17 -#include <bipartite_graph_wrapper.h>
2.18 -#include <hugo/maps.h>
2.19 -#include <hugo/max_flow.h>
2.20 -#include <augmenting_flow.h>
2.21 -
2.22 -/**
2.23 - * Inicializalja a veletlenszamgeneratort.
2.24 - * Figyelem, ez nem jo igazi random szamokhoz,
2.25 - * erre ne bizzad a titkaidat!
2.26 - */
2.27 -void random_init()
2.28 -{
2.29 - unsigned int seed = getpid();
2.30 - seed |= seed << 15;
2.31 - seed ^= time(0);
2.32 -
2.33 - srand(seed);
2.34 -}
2.35 -
2.36 -/**
2.37 - * Egy veletlen int-et ad vissza 0 es m-1 kozott.
2.38 - */
2.39 -int random(int m)
2.40 -{
2.41 - return int( double(m) * rand() / (RAND_MAX + 1.0) );
2.42 -}
2.43 -
2.44 -using namespace hugo;
2.45 -
2.46 -int main() {
2.47 - typedef UndirSageGraph Graph;
2.48 - typedef Graph::Node Node;
2.49 - typedef Graph::NodeIt NodeIt;
2.50 - typedef Graph::Edge Edge;
2.51 - typedef Graph::EdgeIt EdgeIt;
2.52 - typedef Graph::OutEdgeIt OutEdgeIt;
2.53 -
2.54 - Graph g;
2.55 -
2.56 - std::vector<Graph::Node> s_nodes;
2.57 - std::vector<Graph::Node> t_nodes;
2.58 -
2.59 - int a;
2.60 - std::cout << "number of nodes in the first color class=";
2.61 - std::cin >> a;
2.62 - int b;
2.63 - std::cout << "number of nodes in the second color class=";
2.64 - std::cin >> b;
2.65 - int m;
2.66 - std::cout << "number of edges=";
2.67 - std::cin >> m;
2.68 -
2.69 -
2.70 - for (int i=0; i<a; ++i) s_nodes.push_back(g.addNode());
2.71 - for (int i=0; i<b; ++i) t_nodes.push_back(g.addNode());
2.72 -
2.73 - random_init();
2.74 - for(int i=0; i<m; ++i) {
2.75 - g.addEdge(s_nodes[random(a)], t_nodes[random(b)]);
2.76 - }
2.77 -
2.78 - Graph::NodeMap<int> ref_map(g, -1);
2.79 -
2.80 - IterableBoolMap< Graph::NodeMap<int> > bipartite_map(ref_map);
2.81 - for (int i=0; i<a; ++i) bipartite_map.insert(s_nodes[i], false);
2.82 - for (int i=0; i<b; ++i) bipartite_map.insert(t_nodes[i], true);
2.83 -
2.84 -// Graph::Node u;
2.85 -// std::cout << "These nodes will be in S:\n";
2.86 -// //FIXME azert kellene ++, es invalid vizsgalat u-bol, hogy ezt le lehessen
2.87 -// //irni 1etlen FOR_EACH-csel.
2.88 -// for (bipartite_map.first(u, false); g.valid(u); bipartite_map.next(u))
2.89 -// std::cout << u << " ";
2.90 -// std::cout << "\n";
2.91 -// std::cout << "These nodes will be in T:\n";
2.92 -// for (bipartite_map.first(u, true); g.valid(u); bipartite_map.next(u))
2.93 -// std::cout << u << " ";
2.94 -// std::cout << "\n";
2.95 -
2.96 - typedef BipartiteGraphWrapper<Graph> BGW;
2.97 - BGW bgw(g, bipartite_map);
2.98 -
2.99 -// std::cout << "Nodes by NodeIt:\n";
2.100 -// FOR_EACH_LOC(BGW::NodeIt, n, bgw) {
2.101 -// std::cout << n << " ";
2.102 -// }
2.103 -// std::cout << "\n";
2.104 -// std::cout << "Nodes in S by ClassNodeIt:\n";
2.105 -// FOR_EACH_INC_LOC(BGW::ClassNodeIt, n, bgw, bgw.S_CLASS) {
2.106 -// std::cout << n << " ";
2.107 -// }
2.108 -// std::cout << "\n";
2.109 -// std::cout << "Nodes in T by ClassNodeIt:\n";
2.110 -// FOR_EACH_INC_LOC(BGW::ClassNodeIt, n, bgw, bgw.T_CLASS) {
2.111 -// std::cout << n << " ";
2.112 -// }
2.113 -// std::cout << "\n";
2.114 -// std::cout << "Edges of the bipartite graph:\n";
2.115 -// FOR_EACH_LOC(BGW::EdgeIt, e, bgw) {
2.116 -// std::cout << bgw.tail(e) << "->" << bgw.head(e) << std::endl;
2.117 -// }
2.118 -
2.119 -// BGW::NodeMap<int> dbyj(bgw);
2.120 -// BGW::EdgeMap<int> dbyxcj(bgw);
2.121 -
2.122 - typedef stBipartiteGraphWrapper<BGW> stGW;
2.123 - stGW stgw(bgw);
2.124 - ConstMap<stGW::Edge, int> const1map(1);
2.125 -// stGW::NodeMap<int> ize(stgw);
2.126 -
2.127 -// BfsIterator< BGW, BGW::NodeMap<bool> > bfs(bgw);
2.128 -// Graph::NodeIt si;
2.129 -// Graph::Node s;
2.130 -// s=g.first(si);
2.131 -// bfs.pushAndSetReached(BGW::Node(s));
2.132 -// while (!bfs.finished()) { ++bfs; }
2.133 -
2.134 -// FOR_EACH_LOC(stGW::NodeIt, n, stgw) {
2.135 -// std::cout << "out-edges of " << n << ":\n";
2.136 -// FOR_EACH_INC_LOC(stGW::OutEdgeIt, e, stgw, n) {
2.137 -// std::cout << " " << e << "\n";
2.138 -// std::cout << " aNode: " << stgw.aNode(e) << "\n";
2.139 -// std::cout << " bNode: " << stgw.bNode(e) << "\n";
2.140 -// }
2.141 -// std::cout << "in-edges of " << n << ":\n";
2.142 -// FOR_EACH_INC_LOC(stGW::InEdgeIt, e, stgw, n) {
2.143 -// std::cout << " " << e << "\n";
2.144 -// std::cout << " aNode: " << stgw.aNode(e) << "\n";
2.145 -// std::cout << " bNode: " << stgw.bNode(e) << "\n";
2.146 -// }
2.147 -// }
2.148 -// std::cout << "Edges of the stGraphWrapper:\n";
2.149 -// FOR_EACH_LOC(stGW::EdgeIt, n, stgw) {
2.150 -// std::cout << " " << n << "\n";
2.151 -// }
2.152 -
2.153 -// stGW::NodeMap<bool> b(stgw);
2.154 -// FOR_EACH_LOC(stGW::NodeIt, n, stgw) {
2.155 -// std::cout << n << ": " << b[n] <<"\n";
2.156 -// }
2.157 -
2.158 -// std::cout << "Bfs from s: \n";
2.159 -// BfsIterator< stGW, stGW::NodeMap<bool> > bfs_stgw(stgw);
2.160 -// bfs_stgw.pushAndSetReached(stgw.S_NODE);
2.161 -// while (!bfs_stgw.finished()) {
2.162 -// std::cout << " " << stGW::OutEdgeIt(bfs_stgw) << "\n";
2.163 -// ++bfs_stgw;
2.164 -// }
2.165 -
2.166 -
2.167 - Timer ts;
2.168 - ts.reset();
2.169 - stGW::EdgeMap<int> max_flow(stgw);
2.170 - AugmentingFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> >
2.171 - max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, max_flow);
2.172 -// while (max_flow_test.augmentOnShortestPath()) { }
2.173 - typedef SageGraph MutableGraph;
2.174 -// while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) {
2.175 - while (max_flow_test.augmentOnBlockingFlow2()) {
2.176 - std::cout << max_flow_test.flowValue() << std::endl;
2.177 - }
2.178 - std::cout << "max flow value: " << max_flow_test.flowValue() << std::endl;
2.179 - std::cout << "elapsed time: " << ts << std::endl;
2.180 -// FOR_EACH_LOC(stGW::EdgeIt, e, stgw) {
2.181 -// std::cout << e << ": " << max_flow[e] << "\n";
2.182 -// }
2.183 -// std::cout << "\n";
2.184 -
2.185 - ts.reset();
2.186 - stGW::EdgeMap<int> pre_flow(stgw);
2.187 - MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> >
2.188 - pre_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, pre_flow/*, true*/);
2.189 - pre_flow_test.run();
2.190 - std::cout << "pre flow value: " << max_flow_test.flowValue() << std::endl;
2.191 - std::cout << "elapsed time: " << ts << std::endl;
2.192 -// FOR_EACH_LOC(stGW::EdgeIt, e, stgw) {
2.193 -// std::cout << e << ": " << pre_flow[e] << "\n";
2.194 -// }
2.195 -// std::cout << "\n";
2.196 -
2.197 - return 0;
2.198 -}
3.1 --- a/src/work/marci/bipartite_matching_try_3.cc Mon Aug 23 11:28:26 2004 +0000
3.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
3.3 @@ -1,182 +0,0 @@
3.4 -// -*- c++ -*-
3.5 -#include <iostream>
3.6 -#include <fstream>
3.7 -#include <vector>
3.8 -
3.9 -#include <sage_graph.h>
3.10 -//#include <smart_graph.h>
3.11 -//#include <dimacs.h>
3.12 -#include <hugo/time_measure.h>
3.13 -#include <for_each_macros.h>
3.14 -#include <bfs_dfs.h>
3.15 -#include <bipartite_graph_wrapper.h>
3.16 -#include <hugo/maps.h>
3.17 -#include <hugo/max_flow.h>
3.18 -#include <graph_gen.h>
3.19 -#include <max_bipartite_matching.h>
3.20 -
3.21 -using namespace hugo;
3.22 -
3.23 -using std::cout;
3.24 -using std::endl;
3.25 -
3.26 -int main() {
3.27 - //typedef UndirListGraph Graph;
3.28 - typedef BipartiteGraph<SageGraph> Graph;
3.29 -
3.30 - typedef Graph::Node Node;
3.31 - typedef Graph::NodeIt NodeIt;
3.32 - typedef Graph::Edge Edge;
3.33 - typedef Graph::EdgeIt EdgeIt;
3.34 - typedef Graph::OutEdgeIt OutEdgeIt;
3.35 -
3.36 - Graph g;
3.37 -
3.38 - int a;
3.39 - cout << "number of nodes in the first color class=";
3.40 - std::cin >> a;
3.41 - int b;
3.42 - cout << "number of nodes in the second color class=";
3.43 - std::cin >> b;
3.44 - int m;
3.45 - cout << "number of edges=";
3.46 - std::cin >> m;
3.47 -
3.48 - cout << "Generatig a random bipartite graph..." << endl;
3.49 - random_init();
3.50 - randomBipartiteGraph(g, a, b, m);
3.51 -
3.52 -// cout << "Edges of the bipartite graph:" << endl;
3.53 -// FOR_EACH_LOC(EdgeIt, e, g) cout << e << " ";
3.54 -// cout << endl;
3.55 -
3.56 -// cout << "Nodes:" << endl;
3.57 -// FOR_EACH_LOC(Graph::NodeIt, v, g) cout << v << " ";
3.58 -// cout << endl;
3.59 -// cout << "Nodes in T:" << endl;
3.60 -// FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::T_CLASS) cout << v << " ";
3.61 -// cout << endl;
3.62 -// cout << "Nodes in S:" << endl;
3.63 -// FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::S_CLASS) cout << v << " ";
3.64 -// cout << endl;
3.65 -
3.66 -// cout << "Erasing the first node..." << endl;
3.67 -// NodeIt n;
3.68 -// g.first(n);
3.69 -// g.erase(n);
3.70 -// cout << "Nodes of the bipartite graph:" << endl;
3.71 -// FOR_EACH_GLOB(n, g) cout << n << " ";
3.72 -// cout << endl;
3.73 -
3.74 -// cout << "Nodes in T:" << endl;
3.75 -// FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::T_CLASS) cout << v << " ";
3.76 -// cout << endl;
3.77 -// cout << "Nodes in S:" << endl;
3.78 -// FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::S_CLASS) cout << v << " ";
3.79 -// cout << endl;
3.80 -
3.81 - typedef stBipartiteGraphWrapper<Graph> stGW;
3.82 - stGW stgw(g);
3.83 - ConstMap<stGW::Edge, int> const1map(1);
3.84 -
3.85 - Timer ts;
3.86 - cout << "max bipartite matching with stGraphWrapper..." << endl;
3.87 - ts.reset();
3.88 - stGW::EdgeMap<int> flow(stgw);
3.89 - MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> >
3.90 - max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow);
3.91 - max_flow_test.run();
3.92 -// while (max_flow_test.augmentOnShortestPath()) { }
3.93 -// typedef ListGraph MutableGraph;
3.94 -// while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) {
3.95 -// while (max_flow_test.augmentOnBlockingFlow2()) {
3.96 -// cout << max_flow_test.flowValue() << endl;
3.97 -// }
3.98 - cout << "matching value: " << max_flow_test.flowValue() << endl;
3.99 - cout << "elapsed time: " << ts << endl;
3.100 -// FOR_EACH_LOC(stGW::EdgeIt, e, stgw) {
3.101 -// if (flow[e]) cout << e << endl;
3.102 -// }
3.103 - cout << endl;
3.104 -
3.105 - typedef ConstMap<Graph::Edge, int> EdgeCap;
3.106 - EdgeCap ge1(1);
3.107 - typedef ConstMap<Graph::Node, int> NodeCap;
3.108 - NodeCap gn1(1);
3.109 - typedef Graph::EdgeMap<int> EdgeFlow;
3.110 - EdgeFlow gef(g); //0
3.111 - typedef Graph::NodeMap<int> NodeFlow;
3.112 - NodeFlow gnf(g); //0
3.113 -
3.114 - typedef stGW::EdgeMapWrapper<EdgeCap, NodeCap> CapMap;
3.115 - typedef stGW::EdgeMapWrapper<EdgeFlow, NodeFlow> FlowMap;
3.116 - CapMap cm(ge1, gn1);
3.117 - FlowMap fm(gef, gnf);
3.118 -
3.119 - //Timer ts;
3.120 - cout << "max bipartite matching with stGraphWrapper..." << endl;
3.121 - ts.reset();
3.122 - //stGW::EdgeMap<int> flow(stgw);
3.123 - MaxFlow<stGW, int, CapMap, FlowMap>
3.124 - max_flow_test1(stgw, stgw.S_NODE, stgw.T_NODE, cm, fm);
3.125 - max_flow_test1.run();
3.126 -// while (max_flow_test.augmentOnShortestPath()) { }
3.127 -// typedef ListGraph MutableGraph;
3.128 -// while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) {
3.129 -// while (max_flow_test.augmentOnBlockingFlow2()) {
3.130 -// cout << max_flow_test.flowValue() << endl;
3.131 -// }
3.132 - cout << "matching value: " << max_flow_test1.flowValue() << endl;
3.133 - cout << "elapsed time: " << ts << endl;
3.134 -// FOR_EACH_LOC(Graph::EdgeIt, e, g) {
3.135 -// if (gef[e]) cout << e << endl;
3.136 -// }
3.137 - cout << endl;
3.138 -
3.139 - cout << "max bipartite matching with stGraphWrapper..." << endl;
3.140 - ts.reset();
3.141 - FOR_EACH_LOC(Graph::EdgeIt, e, g) gef.set(e, 0);
3.142 - FOR_EACH_LOC(Graph::NodeIt, n, g) gnf.set(n, 0);
3.143 - MaxBipartiteMatching<Graph, ConstMap<Graph::Edge, int>, ConstMap<Graph::Node, int>,
3.144 - Graph::EdgeMap<int>, Graph::NodeMap<int> >
3.145 - matching_test(g, ge1, gn1, gef, gnf);
3.146 - matching_test.run();
3.147 -
3.148 - cout << "matching value: " << matching_test.matchingValue() << endl;
3.149 - cout << "elapsed time: " << ts << endl;
3.150 -// FOR_EACH_LOC(Graph::EdgeIt, e, g) {
3.151 -// if (gef[e]) cout << e << endl;
3.152 -// }
3.153 - cout << endl;
3.154 -
3.155 - cout << "max bipartite matching with MaxBipartiteMatching..." << endl;
3.156 - ts.reset();
3.157 - FOR_EACH_LOC(Graph::EdgeIt, e, g) gef.set(e, 0);
3.158 - //FOR_EACH_LOC(Graph::NodeIt, n, g) gnf.set(n, 0);
3.159 - typedef MaxBipartiteMatching<Graph, ConstMap<Graph::Edge, int>,
3.160 - ConstMap<Graph::Node, int>,
3.161 - Graph::EdgeMap<int>, Graph::NodeMap<int> > MaxBipartiteMatching;
3.162 - MaxBipartiteMatching matching_test_1(g, ge1, gn1, gef/*, gnf*/);
3.163 - matching_test_1.run();
3.164 -
3.165 - cout << "matching value: " << matching_test_1.matchingValue() << endl;
3.166 - cout << "elapsed time: " << ts << endl;
3.167 -// FOR_EACH_LOC(Graph::EdgeIt, e, g) {
3.168 -// if (gef[e]) cout << e << endl;
3.169 -// }
3.170 - cout << endl;
3.171 -
3.172 - cout << "testing optimality with MaxBipartiteMatching..." << endl;
3.173 - ts.reset();
3.174 - matching_test_1.run(MaxBipartiteMatching::GEN_MATCHING);
3.175 - cout << "matching value: " << matching_test_1.matchingValue() << endl;
3.176 - cout << "elapsed time: " << ts << endl;
3.177 -
3.178 - cout << "testing optimality with MaxBipartiteMatching..." << endl;
3.179 - ts.reset();
3.180 - matching_test_1.run(MaxBipartiteMatching::GEN_MATCHING_WITH_GOOD_NODE_FLOW);
3.181 - cout << "matching value: " << matching_test_1.matchingValue() << endl;
3.182 - cout << "elapsed time: " << ts << endl;
3.183 -
3.184 - return 0;
3.185 -}
4.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
4.2 +++ b/src/work/marci/leda/bipartite_matching_comparison.cc Mon Aug 23 11:44:36 2004 +0000
4.3 @@ -0,0 +1,152 @@
4.4 +// -*- c++ -*-
4.5 +#include <iostream>
4.6 +#include <fstream>
4.7 +#include <vector>
4.8 +#include <cstdlib>
4.9 +
4.10 +#include <LEDA/graph.h>
4.11 +#include <LEDA/mcb_matching.h>
4.12 +#include <LEDA/list.h>
4.13 +#include <LEDA/graph_gen.h>
4.14 +
4.15 +#include <leda_graph_wrapper.h>
4.16 +#include <sage_graph.h>
4.17 +//#include <smart_graph.h>
4.18 +//#include <dimacs.h>
4.19 +#include <hugo/time_measure.h>
4.20 +#include <for_each_macros.h>
4.21 +#include <hugo/graph_wrapper.h>
4.22 +#include <bipartite_graph_wrapper.h>
4.23 +#include <hugo/maps.h>
4.24 +#include <hugo/max_flow.h>
4.25 +
4.26 +using std::cin;
4.27 +using std::cout;
4.28 +using std::endl;
4.29 +
4.30 +using namespace hugo;
4.31 +
4.32 +int main() {
4.33 + //for leda graph
4.34 + leda::graph lg;
4.35 + //lg.make_undirected();
4.36 + typedef LedaGraphWrapper<leda::graph> Graph;
4.37 + Graph g(lg);
4.38 +
4.39 + //for UndirSageGraph
4.40 + //typedef UndirSageGraph Graph;
4.41 + //Graph g;
4.42 +
4.43 + typedef Graph::Node Node;
4.44 + typedef Graph::NodeIt NodeIt;
4.45 + typedef Graph::Edge Edge;
4.46 + typedef Graph::EdgeIt EdgeIt;
4.47 + typedef Graph::OutEdgeIt OutEdgeIt;
4.48 +
4.49 + std::vector<Graph::Node> s_nodes;
4.50 + std::vector<Graph::Node> t_nodes;
4.51 +
4.52 + int a;
4.53 + cout << "number of nodes in the first color class=";
4.54 + cin >> a;
4.55 + int b;
4.56 + cout << "number of nodes in the second color class=";
4.57 + cin >> b;
4.58 + int m;
4.59 + cout << "number of edges=";
4.60 + cin >> m;
4.61 + int k;
4.62 + cout << "A bipartite graph is a random group graph if the color classes \nA and B are partitiones to A_0, A_1, ..., A_{k-1} and B_0, B_1, ..., B_{k-1} \nas equally as possible \nand the edges from A_i goes to A_{i-1 mod k} and A_{i+1 mod k}.\n";
4.63 + cout << "number of groups in LEDA random group graph=";
4.64 + cin >> k;
4.65 + cout << endl;
4.66 +
4.67 + leda_list<leda_node> lS;
4.68 + leda_list<leda_node> lT;
4.69 + random_bigraph(lg, a, b, m, lS, lT, k);
4.70 +
4.71 + Graph::NodeMap<int> ref_map(g, -1);
4.72 + IterableBoolMap< Graph::NodeMap<int> > bipartite_map(ref_map);
4.73 +
4.74 + //generating leda random group graph
4.75 + leda_node ln;
4.76 + forall(ln, lS) bipartite_map.insert(ln, false);
4.77 + forall(ln, lT) bipartite_map.insert(ln, true);
4.78 +
4.79 + //making bipartite graph
4.80 + typedef BipartiteGraphWrapper<Graph> BGW;
4.81 + BGW bgw(g, bipartite_map);
4.82 +
4.83 +
4.84 + //st-wrapper
4.85 + typedef stBipartiteGraphWrapper<BGW> stGW;
4.86 + stGW stgw(bgw);
4.87 + ConstMap<stGW::Edge, int> const1map(1);
4.88 + stGW::EdgeMap<int> flow(stgw);
4.89 +
4.90 + Timer ts;
4.91 +
4.92 + ts.reset();
4.93 + FOR_EACH_LOC(stGW::EdgeIt, e, stgw) flow.set(e, 0);
4.94 + MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> >
4.95 + max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow/*, true*/);
4.96 + max_flow_test.run();
4.97 + cout << "HUGO max matching algorithm based on preflow." << endl
4.98 + << "Size of matching: "
4.99 + << max_flow_test.flowValue() << endl;
4.100 + cout << "elapsed time: " << ts << endl << endl;
4.101 +
4.102 + ts.reset();
4.103 + leda_list<leda_edge> ml=MAX_CARD_BIPARTITE_MATCHING(lg);
4.104 + cout << "LEDA max matching algorithm." << endl
4.105 + << "Size of matching: "
4.106 + << ml.size() << endl;
4.107 + cout << "elapsed time: " << ts << endl << endl;
4.108 +
4.109 +// ts.reset();
4.110 +// FOR_EACH_LOC(stGW::EdgeIt, e, stgw) flow.set(e, 0);
4.111 +// typedef SageGraph MutableGraph;
4.112 +// while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { }
4.113 +// cout << "HUGO max matching algorithm based on blocking flow augmentation."
4.114 +// << endl << "Matching size: "
4.115 +// << max_flow_test.flowValue() << endl;
4.116 +// cout << "elapsed time: " << ts << endl << endl;
4.117 +
4.118 + {
4.119 + SageGraph hg;
4.120 + SageGraph::Node s=hg.addNode();
4.121 + SageGraph::Node t=hg.addNode();
4.122 + BGW::NodeMap<SageGraph::Node> b_s_nodes(bgw);
4.123 + BGW::NodeMap<SageGraph::Node> b_t_nodes(bgw);
4.124 +
4.125 + FOR_EACH_INC_LOC(BGW::ClassNodeIt, n, bgw, BGW::S_CLASS) {
4.126 + b_s_nodes.set(n, hg.addNode());
4.127 + hg.addEdge(s, b_s_nodes[n]);
4.128 + }
4.129 + FOR_EACH_INC_LOC(BGW::ClassNodeIt, n, bgw, BGW::T_CLASS) {
4.130 + b_t_nodes.set(n, hg.addNode());
4.131 + hg.addEdge(b_t_nodes[n], t);
4.132 + }
4.133 +
4.134 + FOR_EACH_LOC(BGW::EdgeIt, e, bgw)
4.135 + hg.addEdge(b_s_nodes[bgw.tail(e)], b_t_nodes[bgw.head(e)]);
4.136 +
4.137 + ConstMap<SageGraph::Edge, int> cm(1);
4.138 + SageGraph::EdgeMap<int> flow(hg); //0
4.139 +
4.140 + Timer ts;
4.141 +
4.142 + ts.reset();
4.143 + MaxFlow<SageGraph, int, ConstMap<SageGraph::Edge, int>,
4.144 + SageGraph::EdgeMap<int> >
4.145 + max_flow_test(hg, s, t, cm, flow);
4.146 + max_flow_test.run();
4.147 + cout << "HUGO max matching algorithm on SageGraph by copying the graph, based on preflow."
4.148 + << endl
4.149 + << "Size of matching: "
4.150 + << max_flow_test.flowValue() << endl;
4.151 + cout << "elapsed time: " << ts << endl << endl;
4.152 + }
4.153 +
4.154 + return 0;
4.155 +}
5.1 --- a/src/work/marci/leda/comparison.cc Mon Aug 23 11:28:26 2004 +0000
5.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
5.3 @@ -1,152 +0,0 @@
5.4 -// -*- c++ -*-
5.5 -#include <iostream>
5.6 -#include <fstream>
5.7 -#include <vector>
5.8 -#include <cstdlib>
5.9 -
5.10 -#include <LEDA/graph.h>
5.11 -#include <LEDA/mcb_matching.h>
5.12 -#include <LEDA/list.h>
5.13 -#include <LEDA/graph_gen.h>
5.14 -
5.15 -#include <leda_graph_wrapper.h>
5.16 -#include <sage_graph.h>
5.17 -//#include <smart_graph.h>
5.18 -//#include <dimacs.h>
5.19 -#include <hugo/time_measure.h>
5.20 -#include <for_each_macros.h>
5.21 -#include <hugo/graph_wrapper.h>
5.22 -#include <bipartite_graph_wrapper.h>
5.23 -#include <hugo/maps.h>
5.24 -#include <hugo/max_flow.h>
5.25 -
5.26 -using std::cin;
5.27 -using std::cout;
5.28 -using std::endl;
5.29 -
5.30 -using namespace hugo;
5.31 -
5.32 -int main() {
5.33 - //for leda graph
5.34 - leda::graph lg;
5.35 - //lg.make_undirected();
5.36 - typedef LedaGraphWrapper<leda::graph> Graph;
5.37 - Graph g(lg);
5.38 -
5.39 - //for UndirSageGraph
5.40 - //typedef UndirSageGraph Graph;
5.41 - //Graph g;
5.42 -
5.43 - typedef Graph::Node Node;
5.44 - typedef Graph::NodeIt NodeIt;
5.45 - typedef Graph::Edge Edge;
5.46 - typedef Graph::EdgeIt EdgeIt;
5.47 - typedef Graph::OutEdgeIt OutEdgeIt;
5.48 -
5.49 - std::vector<Graph::Node> s_nodes;
5.50 - std::vector<Graph::Node> t_nodes;
5.51 -
5.52 - int a;
5.53 - cout << "number of nodes in the first color class=";
5.54 - cin >> a;
5.55 - int b;
5.56 - cout << "number of nodes in the second color class=";
5.57 - cin >> b;
5.58 - int m;
5.59 - cout << "number of edges=";
5.60 - cin >> m;
5.61 - int k;
5.62 - cout << "A bipartite graph is a random group graph if the color classes \nA and B are partitiones to A_0, A_1, ..., A_{k-1} and B_0, B_1, ..., B_{k-1} \nas equally as possible \nand the edges from A_i goes to A_{i-1 mod k} and A_{i+1 mod k}.\n";
5.63 - cout << "number of groups in LEDA random group graph=";
5.64 - cin >> k;
5.65 - cout << endl;
5.66 -
5.67 - leda_list<leda_node> lS;
5.68 - leda_list<leda_node> lT;
5.69 - random_bigraph(lg, a, b, m, lS, lT, k);
5.70 -
5.71 - Graph::NodeMap<int> ref_map(g, -1);
5.72 - IterableBoolMap< Graph::NodeMap<int> > bipartite_map(ref_map);
5.73 -
5.74 - //generating leda random group graph
5.75 - leda_node ln;
5.76 - forall(ln, lS) bipartite_map.insert(ln, false);
5.77 - forall(ln, lT) bipartite_map.insert(ln, true);
5.78 -
5.79 - //making bipartite graph
5.80 - typedef BipartiteGraphWrapper<Graph> BGW;
5.81 - BGW bgw(g, bipartite_map);
5.82 -
5.83 -
5.84 - //st-wrapper
5.85 - typedef stBipartiteGraphWrapper<BGW> stGW;
5.86 - stGW stgw(bgw);
5.87 - ConstMap<stGW::Edge, int> const1map(1);
5.88 - stGW::EdgeMap<int> flow(stgw);
5.89 -
5.90 - Timer ts;
5.91 -
5.92 - ts.reset();
5.93 - FOR_EACH_LOC(stGW::EdgeIt, e, stgw) flow.set(e, 0);
5.94 - MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> >
5.95 - max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow/*, true*/);
5.96 - max_flow_test.run();
5.97 - cout << "HUGO max matching algorithm based on preflow." << endl
5.98 - << "Size of matching: "
5.99 - << max_flow_test.flowValue() << endl;
5.100 - cout << "elapsed time: " << ts << endl << endl;
5.101 -
5.102 - ts.reset();
5.103 - leda_list<leda_edge> ml=MAX_CARD_BIPARTITE_MATCHING(lg);
5.104 - cout << "LEDA max matching algorithm." << endl
5.105 - << "Size of matching: "
5.106 - << ml.size() << endl;
5.107 - cout << "elapsed time: " << ts << endl << endl;
5.108 -
5.109 -// ts.reset();
5.110 -// FOR_EACH_LOC(stGW::EdgeIt, e, stgw) flow.set(e, 0);
5.111 -// typedef SageGraph MutableGraph;
5.112 -// while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { }
5.113 -// cout << "HUGO max matching algorithm based on blocking flow augmentation."
5.114 -// << endl << "Matching size: "
5.115 -// << max_flow_test.flowValue() << endl;
5.116 -// cout << "elapsed time: " << ts << endl << endl;
5.117 -
5.118 - {
5.119 - SageGraph hg;
5.120 - SageGraph::Node s=hg.addNode();
5.121 - SageGraph::Node t=hg.addNode();
5.122 - BGW::NodeMap<SageGraph::Node> b_s_nodes(bgw);
5.123 - BGW::NodeMap<SageGraph::Node> b_t_nodes(bgw);
5.124 -
5.125 - FOR_EACH_INC_LOC(BGW::ClassNodeIt, n, bgw, BGW::S_CLASS) {
5.126 - b_s_nodes.set(n, hg.addNode());
5.127 - hg.addEdge(s, b_s_nodes[n]);
5.128 - }
5.129 - FOR_EACH_INC_LOC(BGW::ClassNodeIt, n, bgw, BGW::T_CLASS) {
5.130 - b_t_nodes.set(n, hg.addNode());
5.131 - hg.addEdge(b_t_nodes[n], t);
5.132 - }
5.133 -
5.134 - FOR_EACH_LOC(BGW::EdgeIt, e, bgw)
5.135 - hg.addEdge(b_s_nodes[bgw.tail(e)], b_t_nodes[bgw.head(e)]);
5.136 -
5.137 - ConstMap<SageGraph::Edge, int> cm(1);
5.138 - SageGraph::EdgeMap<int> flow(hg); //0
5.139 -
5.140 - Timer ts;
5.141 -
5.142 - ts.reset();
5.143 - MaxFlow<SageGraph, int, ConstMap<SageGraph::Edge, int>,
5.144 - SageGraph::EdgeMap<int> >
5.145 - max_flow_test(hg, s, t, cm, flow);
5.146 - max_flow_test.run();
5.147 - cout << "HUGO max matching algorithm on SageGraph by copying the graph, based on preflow."
5.148 - << endl
5.149 - << "Size of matching: "
5.150 - << max_flow_test.flowValue() << endl;
5.151 - cout << "elapsed time: " << ts << endl << endl;
5.152 - }
5.153 -
5.154 - return 0;
5.155 -}
6.1 --- a/src/work/marci/leda/makefile Mon Aug 23 11:28:26 2004 +0000
6.2 +++ b/src/work/marci/leda/makefile Mon Aug 23 11:44:36 2004 +0000
6.3 @@ -4,7 +4,7 @@
6.4 INCLUDEDIRS ?= -I. -I../.. -I../../{marci,jacint,alpar,klao,akos,athos} -I$(LEDAROOT)/incl -I../../..
6.5 LDFLAGS = -L$(LEDAROOT) -lG -lL -lm
6.6
6.7 -BINARIES = bipartite_matching_leda bipartite_matching_leda_gen comparison
6.8 +BINARIES = bipartite_matching_leda bipartite_matching_leda_gen bipartite_matching_comparison
6.9
6.10 include ../../makefile
6.11
7.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
7.2 +++ b/src/work/marci/leda/max_bipartite_matching_demo.cc Mon Aug 23 11:44:36 2004 +0000
7.3 @@ -0,0 +1,218 @@
7.4 +// -*- c++ -*-
7.5 +#include <iostream>
7.6 +#include <fstream>
7.7 +#include <vector>
7.8 +#include <cstdlib>
7.9 +
7.10 +#include <LEDA/graph.h>
7.11 +#include <LEDA/mcb_matching.h>
7.12 +#include <LEDA/list.h>
7.13 +
7.14 +#include <leda_graph_wrapper.h>
7.15 +#include <sage_graph.h>
7.16 +#include <dimacs.h>
7.17 +#include <time_measure.h>
7.18 +#include <edmonds_karp.h>
7.19 +
7.20 +/**
7.21 + * Inicializalja a veletlenszamgeneratort.
7.22 + * Figyelem, ez nem jo igazi random szamokhoz,
7.23 + * erre ne bizzad a titkaidat!
7.24 + */
7.25 +void random_init()
7.26 +{
7.27 + unsigned int seed = getpid();
7.28 + seed |= seed << 15;
7.29 + seed ^= time(0);
7.30 +
7.31 + srand(seed);
7.32 +}
7.33 +
7.34 +/**
7.35 + * Egy veletlen int-et ad vissza 0 es m-1 kozott.
7.36 + */
7.37 +int random(int m)
7.38 +{
7.39 + return int( double(m) * rand() / (RAND_MAX + 1.0) );
7.40 +}
7.41 +
7.42 +using namespace hugo;
7.43 +
7.44 +using std::cout;
7.45 +using std::cin;
7.46 +using std::endl;
7.47 +
7.48 +int main() {
7.49 + leda::graph g;
7.50 + typedef LedaGraphWrapper<leda::graph> Graph;
7.51 + Graph G(g);
7.52 +// typedef ListGraph Graph;
7.53 +// Graph G;
7.54 +
7.55 + typedef Graph::Node Node;
7.56 + typedef Graph::NodeIt NodeIt;
7.57 + typedef Graph::Edge Edge;
7.58 + typedef Graph::EdgeIt EdgeIt;
7.59 + typedef Graph::OutEdgeIt OutEdgeIt;
7.60 + typedef Graph::InEdgeIt InEdgeIt;
7.61 +
7.62 + //Node s, t;
7.63 + //Graph::EdgeMap<int> cap(G);
7.64 + //readDimacsMaxFlow(std::cin, G, s, t, cap);
7.65 + std::vector<Node> s_nodes;
7.66 + std::vector<Node> t_nodes;
7.67 +
7.68 + int a;
7.69 + cout << "number of nodes in the first color class=";
7.70 + cin >> a;
7.71 + int b;
7.72 + cout << "number of nodes in the second color class=";
7.73 + cin >> b;
7.74 + int m;
7.75 + cout << "number of edges=";
7.76 + cin >> m;
7.77 +
7.78 + for(int i=0; i<a; ++i) {
7.79 + s_nodes.push_back(G.addNode());
7.80 + }
7.81 + for(int i=0; i<a; ++i) {
7.82 + t_nodes.push_back(G.addNode());
7.83 + }
7.84 + random_init();
7.85 + for(int i=0; i<m; ++i) {
7.86 + G.addEdge(s_nodes[random(a)], t_nodes[random(b)]);
7.87 + }
7.88 +
7.89 +// G.addEdge(s_nodes[1], t_nodes[5-4]);
7.90 +// G.addEdge(s_nodes[1], t_nodes[5-4]);
7.91 +// G.addEdge(s_nodes[1], t_nodes[4-4]);
7.92 +// G.addEdge(s_nodes[1], t_nodes[4-4]);
7.93 +// G.addEdge(s_nodes[2], t_nodes[4-4]);
7.94 +// G.addEdge(s_nodes[3], t_nodes[4-4]);
7.95 +
7.96 + leda_list<leda_node> A;
7.97 + leda_list<leda_node> B;
7.98 + Graph::NodeMap<bool> s_map(G); //false
7.99 + Graph::NodeMap<bool> t_map(G); //false
7.100 +
7.101 + for(int i=0; i<a; ++i) { s_map.set(s_nodes[i], true); A+=s_nodes[i]; }
7.102 + for(int i=0; i<b; ++i) { t_map.set(t_nodes[i], true); B+=t_nodes[i]; }
7.103 +
7.104 +// cout << "bfs and dfs iterator demo on the directed graph" << endl;
7.105 +// for(NodeIt n=G.first<NodeIt>(); G.valid(n); G.next(n)) {
7.106 +// cout << G.id(n) << ": ";
7.107 +// cout << "out edges: ";
7.108 +// for(OutEdgeIt e=G.first<OutEdgeIt>(n); G.valid(e); G.next(e))
7.109 +// cout << G.id(G.tail(e)) << "->" << G.id(G.head(e)) << " ";
7.110 +// cout << "in edges: ";
7.111 +// for(InEdgeIt e=G.first<InEdgeIt>(n); G.valid(e); G.next(e))
7.112 +// cout << G.id(G.tail(e)) << "->" << G.id(G.head(e)) << " ";
7.113 +// cout << endl;
7.114 +// }
7.115 +
7.116 +
7.117 + {
7.118 + std::cout << "on-the-fly max bipartite matching (Edmonds-Karp) demo on wrapped leda graph..." << std::endl;
7.119 + Graph::EdgeMap<int> flow(G); //0 flow
7.120 + Graph::EdgeMap<int> cap(G, 1);
7.121 +
7.122 + Timer ts;
7.123 + ts.reset();
7.124 +
7.125 + MaxMatching<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s_map, t_map, flow, cap);
7.126 + int i=0;
7.127 + while (max_flow_test.augmentOnShortestPath()) {
7.128 +// for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))
7.129 +// std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
7.130 +// std::cout<<std::endl;
7.131 + ++i;
7.132 + }
7.133 +
7.134 +// std::cout << "maximum matching: "<< std::endl;
7.135 +// for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))
7.136 +// if (flow.get(e))
7.137 +// std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
7.138 +// std::cout<<std::endl;
7.139 +// std::cout << "edges which are not in this maximum matching: "<< std::endl;
7.140 +// for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))
7.141 +// if (!flow.get(e))
7.142 +// std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
7.143 +// std::cout<<std::endl;
7.144 +
7.145 + std::cout << "elapsed time: " << ts << std::endl;
7.146 + std::cout << "number of augmentation phases: " << i << std::endl;
7.147 + std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
7.148 + }
7.149 +
7.150 +// {
7.151 +// std::cout << "on-the-fly max bipartite matching demo (Hopcroft-Karp) on wrapped leda graph..." << std::endl;
7.152 +// Graph::EdgeMap<int> flow(G); //0 flow
7.153 +// Graph::EdgeMap<int> cap(G, 1);
7.154 +
7.155 +// Timer ts;
7.156 +// ts.reset();
7.157 +
7.158 +// MaxMatching<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s_map, t_map, flow, cap);
7.159 +// int i=0;
7.160 +// while (max_flow_test.augmentOnBlockingFlow2()) {
7.161 +// // for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))
7.162 +// // std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
7.163 +// // std::cout<<std::endl;
7.164 +// ++i;
7.165 +// }
7.166 +
7.167 +// // std::cout << "maximum matching: "<< std::endl;
7.168 +// // for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))
7.169 +// // if (flow.get(e))
7.170 +// // std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
7.171 +// // std::cout<<std::endl;
7.172 +// // std::cout << "edges which are not in this maximum matching: "<< std::endl;
7.173 +// // for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))
7.174 +// // if (!flow.get(e))
7.175 +// // std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
7.176 +// // std::cout<<std::endl;
7.177 +
7.178 +// std::cout << "elapsed time: " << ts << std::endl;
7.179 +// std::cout << "number of augmentation phases: " << i << std::endl;
7.180 +// std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
7.181 +// }
7.182 +
7.183 + {
7.184 + std::cout << "max bipartite matching (LEDA)..." << std::endl;
7.185 + //Graph::EdgeMap<int> flow(G); //0 flow
7.186 + //Graph::EdgeMap<int> cap(G, 1);
7.187 +
7.188 + leda_node_array<bool> NC(g);
7.189 +
7.190 + Timer ts;
7.191 + ts.reset();
7.192 +
7.193 + //MaxMatching<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s_map, t_map, flow, cap);
7.194 + //int i=0;
7.195 + //while (max_flow_test.augmentOnShortestPath()) { ++i; }
7.196 +
7.197 + //leda_list<leda_edge> l=MAX_CARD_BIPARTITE_MATCHING_HK(g, A, B, NC, false);
7.198 + leda_list<leda_edge> l=MAX_CARD_BIPARTITE_MATCHING(g);
7.199 +
7.200 +
7.201 +// std::cout << "maximum matching: "<< std::endl;
7.202 +// for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))
7.203 +// if (flow.get(e))
7.204 +// std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
7.205 +// std::cout<<std::endl;
7.206 +// std::cout << "edges which are not in this maximum matching: "<< std::endl;
7.207 +// for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))
7.208 +// if (!flow.get(e))
7.209 +// std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
7.210 +// std::cout<<std::endl;
7.211 +
7.212 +
7.213 + std::cout << "elapsed time: " << ts << std::endl;
7.214 + //std::cout << "number of augmentation phases: " << i << std::endl;
7.215 + std::cout << "flow value: "<< l.size() << std::endl;
7.216 + }
7.217 +
7.218 +
7.219 +
7.220 + return 0;
7.221 +}
8.1 --- a/src/work/marci/makefile Mon Aug 23 11:28:26 2004 +0000
8.2 +++ b/src/work/marci/makefile Mon Aug 23 11:44:36 2004 +0000
8.3 @@ -4,7 +4,7 @@
8.4 INCLUDEDIRS ?= -I../{jacint,marci,alpar,klao,akos,athos} -I../.. -I.. -I$(BOOSTROOT)
8.5
8.6 LEDABINARIES = leda_graph_demo leda_bfs_dfs max_bipartite_matching_demo
8.7 -BINARIES = max_flow_demo iterator_bfs_demo macro_test lg_vs_sg_vs_sg bfsit_vs_byhand bipartite_graph_wrapper_test bipartite_matching_try bipartite_matching_try_3 top_sort_test max_flow_1
8.8 +BINARIES = max_flow_demo iterator_bfs_demo macro_test lg_vs_sg_vs_sg bfsit_vs_byhand bipartite_graph_wrapper_test bipartite_matching_demo top_sort_test max_flow_1
8.9 #BINARIES = preflow_bug
8.10 #gw_vs_not preflow_demo_boost edmonds_karp_demo_boost preflow_demo_jacint preflow_demo_athos edmonds_karp_demo_alpar preflow_demo_leda
8.11
9.1 --- a/src/work/marci/max_bipartite_matching_demo.cc Mon Aug 23 11:28:26 2004 +0000
9.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
9.3 @@ -1,218 +0,0 @@
9.4 -// -*- c++ -*-
9.5 -#include <iostream>
9.6 -#include <fstream>
9.7 -#include <vector>
9.8 -#include <cstdlib>
9.9 -
9.10 -#include <LEDA/graph.h>
9.11 -#include <LEDA/mcb_matching.h>
9.12 -#include <LEDA/list.h>
9.13 -
9.14 -#include <leda_graph_wrapper.h>
9.15 -#include <sage_graph.h>
9.16 -#include <dimacs.h>
9.17 -#include <time_measure.h>
9.18 -#include <edmonds_karp.h>
9.19 -
9.20 -/**
9.21 - * Inicializalja a veletlenszamgeneratort.
9.22 - * Figyelem, ez nem jo igazi random szamokhoz,
9.23 - * erre ne bizzad a titkaidat!
9.24 - */
9.25 -void random_init()
9.26 -{
9.27 - unsigned int seed = getpid();
9.28 - seed |= seed << 15;
9.29 - seed ^= time(0);
9.30 -
9.31 - srand(seed);
9.32 -}
9.33 -
9.34 -/**
9.35 - * Egy veletlen int-et ad vissza 0 es m-1 kozott.
9.36 - */
9.37 -int random(int m)
9.38 -{
9.39 - return int( double(m) * rand() / (RAND_MAX + 1.0) );
9.40 -}
9.41 -
9.42 -using namespace hugo;
9.43 -
9.44 -using std::cout;
9.45 -using std::cin;
9.46 -using std::endl;
9.47 -
9.48 -int main() {
9.49 - leda::graph g;
9.50 - typedef LedaGraphWrapper<leda::graph> Graph;
9.51 - Graph G(g);
9.52 -// typedef ListGraph Graph;
9.53 -// Graph G;
9.54 -
9.55 - typedef Graph::Node Node;
9.56 - typedef Graph::NodeIt NodeIt;
9.57 - typedef Graph::Edge Edge;
9.58 - typedef Graph::EdgeIt EdgeIt;
9.59 - typedef Graph::OutEdgeIt OutEdgeIt;
9.60 - typedef Graph::InEdgeIt InEdgeIt;
9.61 -
9.62 - //Node s, t;
9.63 - //Graph::EdgeMap<int> cap(G);
9.64 - //readDimacsMaxFlow(std::cin, G, s, t, cap);
9.65 - std::vector<Node> s_nodes;
9.66 - std::vector<Node> t_nodes;
9.67 -
9.68 - int a;
9.69 - cout << "number of nodes in the first color class=";
9.70 - cin >> a;
9.71 - int b;
9.72 - cout << "number of nodes in the second color class=";
9.73 - cin >> b;
9.74 - int m;
9.75 - cout << "number of edges=";
9.76 - cin >> m;
9.77 -
9.78 - for(int i=0; i<a; ++i) {
9.79 - s_nodes.push_back(G.addNode());
9.80 - }
9.81 - for(int i=0; i<a; ++i) {
9.82 - t_nodes.push_back(G.addNode());
9.83 - }
9.84 - random_init();
9.85 - for(int i=0; i<m; ++i) {
9.86 - G.addEdge(s_nodes[random(a)], t_nodes[random(b)]);
9.87 - }
9.88 -
9.89 -// G.addEdge(s_nodes[1], t_nodes[5-4]);
9.90 -// G.addEdge(s_nodes[1], t_nodes[5-4]);
9.91 -// G.addEdge(s_nodes[1], t_nodes[4-4]);
9.92 -// G.addEdge(s_nodes[1], t_nodes[4-4]);
9.93 -// G.addEdge(s_nodes[2], t_nodes[4-4]);
9.94 -// G.addEdge(s_nodes[3], t_nodes[4-4]);
9.95 -
9.96 - leda_list<leda_node> A;
9.97 - leda_list<leda_node> B;
9.98 - Graph::NodeMap<bool> s_map(G); //false
9.99 - Graph::NodeMap<bool> t_map(G); //false
9.100 -
9.101 - for(int i=0; i<a; ++i) { s_map.set(s_nodes[i], true); A+=s_nodes[i]; }
9.102 - for(int i=0; i<b; ++i) { t_map.set(t_nodes[i], true); B+=t_nodes[i]; }
9.103 -
9.104 -// cout << "bfs and dfs iterator demo on the directed graph" << endl;
9.105 -// for(NodeIt n=G.first<NodeIt>(); G.valid(n); G.next(n)) {
9.106 -// cout << G.id(n) << ": ";
9.107 -// cout << "out edges: ";
9.108 -// for(OutEdgeIt e=G.first<OutEdgeIt>(n); G.valid(e); G.next(e))
9.109 -// cout << G.id(G.tail(e)) << "->" << G.id(G.head(e)) << " ";
9.110 -// cout << "in edges: ";
9.111 -// for(InEdgeIt e=G.first<InEdgeIt>(n); G.valid(e); G.next(e))
9.112 -// cout << G.id(G.tail(e)) << "->" << G.id(G.head(e)) << " ";
9.113 -// cout << endl;
9.114 -// }
9.115 -
9.116 -
9.117 - {
9.118 - std::cout << "on-the-fly max bipartite matching (Edmonds-Karp) demo on wrapped leda graph..." << std::endl;
9.119 - Graph::EdgeMap<int> flow(G); //0 flow
9.120 - Graph::EdgeMap<int> cap(G, 1);
9.121 -
9.122 - Timer ts;
9.123 - ts.reset();
9.124 -
9.125 - MaxMatching<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s_map, t_map, flow, cap);
9.126 - int i=0;
9.127 - while (max_flow_test.augmentOnShortestPath()) {
9.128 -// for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))
9.129 -// std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
9.130 -// std::cout<<std::endl;
9.131 - ++i;
9.132 - }
9.133 -
9.134 -// std::cout << "maximum matching: "<< std::endl;
9.135 -// for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))
9.136 -// if (flow.get(e))
9.137 -// std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
9.138 -// std::cout<<std::endl;
9.139 -// std::cout << "edges which are not in this maximum matching: "<< std::endl;
9.140 -// for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))
9.141 -// if (!flow.get(e))
9.142 -// std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
9.143 -// std::cout<<std::endl;
9.144 -
9.145 - std::cout << "elapsed time: " << ts << std::endl;
9.146 - std::cout << "number of augmentation phases: " << i << std::endl;
9.147 - std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
9.148 - }
9.149 -
9.150 -// {
9.151 -// std::cout << "on-the-fly max bipartite matching demo (Hopcroft-Karp) on wrapped leda graph..." << std::endl;
9.152 -// Graph::EdgeMap<int> flow(G); //0 flow
9.153 -// Graph::EdgeMap<int> cap(G, 1);
9.154 -
9.155 -// Timer ts;
9.156 -// ts.reset();
9.157 -
9.158 -// MaxMatching<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s_map, t_map, flow, cap);
9.159 -// int i=0;
9.160 -// while (max_flow_test.augmentOnBlockingFlow2()) {
9.161 -// // for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))
9.162 -// // std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
9.163 -// // std::cout<<std::endl;
9.164 -// ++i;
9.165 -// }
9.166 -
9.167 -// // std::cout << "maximum matching: "<< std::endl;
9.168 -// // for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))
9.169 -// // if (flow.get(e))
9.170 -// // std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
9.171 -// // std::cout<<std::endl;
9.172 -// // std::cout << "edges which are not in this maximum matching: "<< std::endl;
9.173 -// // for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))
9.174 -// // if (!flow.get(e))
9.175 -// // std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
9.176 -// // std::cout<<std::endl;
9.177 -
9.178 -// std::cout << "elapsed time: " << ts << std::endl;
9.179 -// std::cout << "number of augmentation phases: " << i << std::endl;
9.180 -// std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
9.181 -// }
9.182 -
9.183 - {
9.184 - std::cout << "max bipartite matching (LEDA)..." << std::endl;
9.185 - //Graph::EdgeMap<int> flow(G); //0 flow
9.186 - //Graph::EdgeMap<int> cap(G, 1);
9.187 -
9.188 - leda_node_array<bool> NC(g);
9.189 -
9.190 - Timer ts;
9.191 - ts.reset();
9.192 -
9.193 - //MaxMatching<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s_map, t_map, flow, cap);
9.194 - //int i=0;
9.195 - //while (max_flow_test.augmentOnShortestPath()) { ++i; }
9.196 -
9.197 - //leda_list<leda_edge> l=MAX_CARD_BIPARTITE_MATCHING_HK(g, A, B, NC, false);
9.198 - leda_list<leda_edge> l=MAX_CARD_BIPARTITE_MATCHING(g);
9.199 -
9.200 -
9.201 -// std::cout << "maximum matching: "<< std::endl;
9.202 -// for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))
9.203 -// if (flow.get(e))
9.204 -// std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
9.205 -// std::cout<<std::endl;
9.206 -// std::cout << "edges which are not in this maximum matching: "<< std::endl;
9.207 -// for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))
9.208 -// if (!flow.get(e))
9.209 -// std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
9.210 -// std::cout<<std::endl;
9.211 -
9.212 -
9.213 - std::cout << "elapsed time: " << ts << std::endl;
9.214 - //std::cout << "number of augmentation phases: " << i << std::endl;
9.215 - std::cout << "flow value: "<< l.size() << std::endl;
9.216 - }
9.217 -
9.218 -
9.219 -
9.220 - return 0;
9.221 -}