1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/work/marci/leda/max_bipartite_matching_demo.cc Mon Aug 23 11:44:36 2004 +0000
1.3 @@ -0,0 +1,218 @@
1.4 +// -*- c++ -*-
1.5 +#include <iostream>
1.6 +#include <fstream>
1.7 +#include <vector>
1.8 +#include <cstdlib>
1.9 +
1.10 +#include <LEDA/graph.h>
1.11 +#include <LEDA/mcb_matching.h>
1.12 +#include <LEDA/list.h>
1.13 +
1.14 +#include <leda_graph_wrapper.h>
1.15 +#include <sage_graph.h>
1.16 +#include <dimacs.h>
1.17 +#include <time_measure.h>
1.18 +#include <edmonds_karp.h>
1.19 +
1.20 +/**
1.21 + * Inicializalja a veletlenszamgeneratort.
1.22 + * Figyelem, ez nem jo igazi random szamokhoz,
1.23 + * erre ne bizzad a titkaidat!
1.24 + */
1.25 +void random_init()
1.26 +{
1.27 + unsigned int seed = getpid();
1.28 + seed |= seed << 15;
1.29 + seed ^= time(0);
1.30 +
1.31 + srand(seed);
1.32 +}
1.33 +
1.34 +/**
1.35 + * Egy veletlen int-et ad vissza 0 es m-1 kozott.
1.36 + */
1.37 +int random(int m)
1.38 +{
1.39 + return int( double(m) * rand() / (RAND_MAX + 1.0) );
1.40 +}
1.41 +
1.42 +using namespace hugo;
1.43 +
1.44 +using std::cout;
1.45 +using std::cin;
1.46 +using std::endl;
1.47 +
1.48 +int main() {
1.49 + leda::graph g;
1.50 + typedef LedaGraphWrapper<leda::graph> Graph;
1.51 + Graph G(g);
1.52 +// typedef ListGraph Graph;
1.53 +// Graph G;
1.54 +
1.55 + typedef Graph::Node Node;
1.56 + typedef Graph::NodeIt NodeIt;
1.57 + typedef Graph::Edge Edge;
1.58 + typedef Graph::EdgeIt EdgeIt;
1.59 + typedef Graph::OutEdgeIt OutEdgeIt;
1.60 + typedef Graph::InEdgeIt InEdgeIt;
1.61 +
1.62 + //Node s, t;
1.63 + //Graph::EdgeMap<int> cap(G);
1.64 + //readDimacsMaxFlow(std::cin, G, s, t, cap);
1.65 + std::vector<Node> s_nodes;
1.66 + std::vector<Node> t_nodes;
1.67 +
1.68 + int a;
1.69 + cout << "number of nodes in the first color class=";
1.70 + cin >> a;
1.71 + int b;
1.72 + cout << "number of nodes in the second color class=";
1.73 + cin >> b;
1.74 + int m;
1.75 + cout << "number of edges=";
1.76 + cin >> m;
1.77 +
1.78 + for(int i=0; i<a; ++i) {
1.79 + s_nodes.push_back(G.addNode());
1.80 + }
1.81 + for(int i=0; i<a; ++i) {
1.82 + t_nodes.push_back(G.addNode());
1.83 + }
1.84 + random_init();
1.85 + for(int i=0; i<m; ++i) {
1.86 + G.addEdge(s_nodes[random(a)], t_nodes[random(b)]);
1.87 + }
1.88 +
1.89 +// G.addEdge(s_nodes[1], t_nodes[5-4]);
1.90 +// G.addEdge(s_nodes[1], t_nodes[5-4]);
1.91 +// G.addEdge(s_nodes[1], t_nodes[4-4]);
1.92 +// G.addEdge(s_nodes[1], t_nodes[4-4]);
1.93 +// G.addEdge(s_nodes[2], t_nodes[4-4]);
1.94 +// G.addEdge(s_nodes[3], t_nodes[4-4]);
1.95 +
1.96 + leda_list<leda_node> A;
1.97 + leda_list<leda_node> B;
1.98 + Graph::NodeMap<bool> s_map(G); //false
1.99 + Graph::NodeMap<bool> t_map(G); //false
1.100 +
1.101 + for(int i=0; i<a; ++i) { s_map.set(s_nodes[i], true); A+=s_nodes[i]; }
1.102 + for(int i=0; i<b; ++i) { t_map.set(t_nodes[i], true); B+=t_nodes[i]; }
1.103 +
1.104 +// cout << "bfs and dfs iterator demo on the directed graph" << endl;
1.105 +// for(NodeIt n=G.first<NodeIt>(); G.valid(n); G.next(n)) {
1.106 +// cout << G.id(n) << ": ";
1.107 +// cout << "out edges: ";
1.108 +// for(OutEdgeIt e=G.first<OutEdgeIt>(n); G.valid(e); G.next(e))
1.109 +// cout << G.id(G.tail(e)) << "->" << G.id(G.head(e)) << " ";
1.110 +// cout << "in edges: ";
1.111 +// for(InEdgeIt e=G.first<InEdgeIt>(n); G.valid(e); G.next(e))
1.112 +// cout << G.id(G.tail(e)) << "->" << G.id(G.head(e)) << " ";
1.113 +// cout << endl;
1.114 +// }
1.115 +
1.116 +
1.117 + {
1.118 + std::cout << "on-the-fly max bipartite matching (Edmonds-Karp) demo on wrapped leda graph..." << std::endl;
1.119 + Graph::EdgeMap<int> flow(G); //0 flow
1.120 + Graph::EdgeMap<int> cap(G, 1);
1.121 +
1.122 + Timer ts;
1.123 + ts.reset();
1.124 +
1.125 + MaxMatching<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s_map, t_map, flow, cap);
1.126 + int i=0;
1.127 + while (max_flow_test.augmentOnShortestPath()) {
1.128 +// for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))
1.129 +// std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
1.130 +// std::cout<<std::endl;
1.131 + ++i;
1.132 + }
1.133 +
1.134 +// std::cout << "maximum matching: "<< std::endl;
1.135 +// for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))
1.136 +// if (flow.get(e))
1.137 +// std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
1.138 +// std::cout<<std::endl;
1.139 +// std::cout << "edges which are not in this maximum matching: "<< std::endl;
1.140 +// for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))
1.141 +// if (!flow.get(e))
1.142 +// std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
1.143 +// std::cout<<std::endl;
1.144 +
1.145 + std::cout << "elapsed time: " << ts << std::endl;
1.146 + std::cout << "number of augmentation phases: " << i << std::endl;
1.147 + std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
1.148 + }
1.149 +
1.150 +// {
1.151 +// std::cout << "on-the-fly max bipartite matching demo (Hopcroft-Karp) on wrapped leda graph..." << std::endl;
1.152 +// Graph::EdgeMap<int> flow(G); //0 flow
1.153 +// Graph::EdgeMap<int> cap(G, 1);
1.154 +
1.155 +// Timer ts;
1.156 +// ts.reset();
1.157 +
1.158 +// MaxMatching<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s_map, t_map, flow, cap);
1.159 +// int i=0;
1.160 +// while (max_flow_test.augmentOnBlockingFlow2()) {
1.161 +// // for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))
1.162 +// // std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
1.163 +// // std::cout<<std::endl;
1.164 +// ++i;
1.165 +// }
1.166 +
1.167 +// // std::cout << "maximum matching: "<< std::endl;
1.168 +// // for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))
1.169 +// // if (flow.get(e))
1.170 +// // std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
1.171 +// // std::cout<<std::endl;
1.172 +// // std::cout << "edges which are not in this maximum matching: "<< std::endl;
1.173 +// // for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))
1.174 +// // if (!flow.get(e))
1.175 +// // std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
1.176 +// // std::cout<<std::endl;
1.177 +
1.178 +// std::cout << "elapsed time: " << ts << std::endl;
1.179 +// std::cout << "number of augmentation phases: " << i << std::endl;
1.180 +// std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
1.181 +// }
1.182 +
1.183 + {
1.184 + std::cout << "max bipartite matching (LEDA)..." << std::endl;
1.185 + //Graph::EdgeMap<int> flow(G); //0 flow
1.186 + //Graph::EdgeMap<int> cap(G, 1);
1.187 +
1.188 + leda_node_array<bool> NC(g);
1.189 +
1.190 + Timer ts;
1.191 + ts.reset();
1.192 +
1.193 + //MaxMatching<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s_map, t_map, flow, cap);
1.194 + //int i=0;
1.195 + //while (max_flow_test.augmentOnShortestPath()) { ++i; }
1.196 +
1.197 + //leda_list<leda_edge> l=MAX_CARD_BIPARTITE_MATCHING_HK(g, A, B, NC, false);
1.198 + leda_list<leda_edge> l=MAX_CARD_BIPARTITE_MATCHING(g);
1.199 +
1.200 +
1.201 +// std::cout << "maximum matching: "<< std::endl;
1.202 +// for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))
1.203 +// if (flow.get(e))
1.204 +// std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
1.205 +// std::cout<<std::endl;
1.206 +// std::cout << "edges which are not in this maximum matching: "<< std::endl;
1.207 +// for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))
1.208 +// if (!flow.get(e))
1.209 +// std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
1.210 +// std::cout<<std::endl;
1.211 +
1.212 +
1.213 + std::cout << "elapsed time: " << ts << std::endl;
1.214 + //std::cout << "number of augmentation phases: " << i << std::endl;
1.215 + std::cout << "flow value: "<< l.size() << std::endl;
1.216 + }
1.217 +
1.218 +
1.219 +
1.220 + return 0;
1.221 +}