1.1 --- a/src/work/marci/max_bipartite_matching_demo.cc Mon Aug 23 11:28:26 2004 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,218 +0,0 @@
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 -}