author | jacint |
Thu, 13 May 2004 10:29:13 +0000 | |
changeset 629 | 6620dfc606af |
child 921 | 818510fa3d99 |
permissions | -rw-r--r-- |
jacint@581 | 1 |
// -*- c++ -*- |
jacint@581 | 2 |
#include <iostream> |
jacint@581 | 3 |
#include <fstream> |
jacint@581 | 4 |
#include <vector> |
jacint@581 | 5 |
#include <cstdlib> |
jacint@581 | 6 |
|
jacint@581 | 7 |
#include <LEDA/graph.h> |
jacint@581 | 8 |
#include <LEDA/mc_matching.h> |
jacint@581 | 9 |
#include <LEDA/list.h> |
jacint@581 | 10 |
#include <LEDA/graph_gen.h> |
jacint@581 | 11 |
|
jacint@581 | 12 |
#include <leda_graph_wrapper.h> |
jacint@581 | 13 |
#include <list_graph.h> |
jacint@581 | 14 |
#include <dimacs.h> |
jacint@581 | 15 |
#include <time_measure.h> |
jacint@581 | 16 |
#include <for_each_macros.h> |
jacint@581 | 17 |
#include <graph_wrapper.h> |
jacint@581 | 18 |
#include <bipartite_graph_wrapper.h> |
jacint@581 | 19 |
#include <maps.h> |
jacint@581 | 20 |
#include <max_matching.h> |
jacint@581 | 21 |
|
jacint@581 | 22 |
// /** |
jacint@581 | 23 |
// * Inicializalja a veletlenszamgeneratort. |
jacint@581 | 24 |
// * Figyelem, ez nem jo igazi random szamokhoz, |
jacint@581 | 25 |
// * erre ne bizzad a titkaidat! |
jacint@581 | 26 |
// */ |
jacint@581 | 27 |
// void random_init() |
jacint@581 | 28 |
// { |
jacint@581 | 29 |
// unsigned int seed = getpid(); |
jacint@581 | 30 |
// seed |= seed << 15; |
jacint@581 | 31 |
// seed ^= time(0); |
jacint@581 | 32 |
|
jacint@581 | 33 |
// srand(seed); |
jacint@581 | 34 |
// } |
jacint@581 | 35 |
|
jacint@581 | 36 |
// /** |
jacint@581 | 37 |
// * Egy veletlen int-et ad vissza 0 es m-1 kozott. |
jacint@581 | 38 |
// */ |
jacint@581 | 39 |
// int random(int m) |
jacint@581 | 40 |
// { |
jacint@581 | 41 |
// return int( double(m) * rand() / (RAND_MAX + 1.0) ); |
jacint@581 | 42 |
// } |
jacint@581 | 43 |
|
jacint@581 | 44 |
using namespace hugo; |
jacint@581 | 45 |
|
jacint@581 | 46 |
int main() { |
jacint@581 | 47 |
|
jacint@581 | 48 |
//for leda graph |
jacint@581 | 49 |
leda::graph lg; |
jacint@581 | 50 |
//lg.make_undirected(); |
jacint@581 | 51 |
typedef LedaGraphWrapper<leda::graph> Graph; |
jacint@581 | 52 |
Graph g(lg); |
jacint@581 | 53 |
|
jacint@581 | 54 |
//for UndirListGraph |
jacint@581 | 55 |
//typedef UndirListGraph Graph; |
jacint@581 | 56 |
//Graph g; |
jacint@581 | 57 |
|
jacint@581 | 58 |
typedef Graph::Node Node; |
jacint@581 | 59 |
typedef Graph::NodeIt NodeIt; |
jacint@581 | 60 |
typedef Graph::Edge Edge; |
jacint@581 | 61 |
typedef Graph::EdgeIt EdgeIt; |
jacint@581 | 62 |
typedef Graph::OutEdgeIt OutEdgeIt; |
jacint@581 | 63 |
|
jacint@581 | 64 |
std::vector<Graph::Node> s_nodes; |
jacint@581 | 65 |
std::vector<Graph::Node> t_nodes; |
jacint@581 | 66 |
|
jacint@581 | 67 |
int n; |
jacint@581 | 68 |
std::cout << "Number of nodes="; |
jacint@581 | 69 |
std::cin >> n; |
jacint@581 | 70 |
int m; |
jacint@581 | 71 |
std::cout << "number of edges="; |
jacint@581 | 72 |
std::cin >> m; |
jacint@581 | 73 |
std::cout << std::endl; |
jacint@581 | 74 |
|
jacint@581 | 75 |
random_graph(lg, n, m); |
jacint@581 | 76 |
|
jacint@581 | 77 |
Timer ts; |
jacint@581 | 78 |
|
jacint@581 | 79 |
// writeDimacs(std::cout, g); //for check |
jacint@581 | 80 |
|
jacint@581 | 81 |
MaxMatching<Graph> max_matching(g); |
jacint@581 | 82 |
std::cout << |
jacint@581 | 83 |
"Running the edmonds algorithm run()... " |
jacint@581 | 84 |
<<std::endl; |
jacint@581 | 85 |
ts.reset(); |
jacint@581 | 86 |
max_matching.run(); |
jacint@581 | 87 |
std::cout<<"Elapsed time: "<<ts<<std::endl; |
jacint@581 | 88 |
int s=0; |
jacint@581 | 89 |
Graph::NodeMap<Node> mate(g,INVALID); |
jacint@581 | 90 |
max_matching.writeNMapNode(mate); |
jacint@581 | 91 |
NodeIt v; |
jacint@581 | 92 |
for(g.first(v); g.valid(v); g.next(v) ) { |
jacint@581 | 93 |
if ( g.valid(mate[v]) ) { |
jacint@581 | 94 |
++s; |
jacint@581 | 95 |
} |
jacint@581 | 96 |
} |
jacint@581 | 97 |
int size=(int)s/2; //size will be used as the size of a maxmatching |
jacint@581 | 98 |
std::cout << size << " is the size of the matching found by run(),"<<std::endl; |
jacint@581 | 99 |
if ( size == max_matching.size() ) { |
jacint@581 | 100 |
std::cout<< "which equals to the size of the actual matching reported by size().\n"<< std::endl; |
jacint@581 | 101 |
} else { |
jacint@581 | 102 |
std::cout<< "which does not equal to the size of the actual matching reported by size()!\n"<< std::endl; |
jacint@581 | 103 |
} |
jacint@581 | 104 |
|
jacint@581 | 105 |
|
jacint@581 | 106 |
|
jacint@581 | 107 |
|
jacint@581 | 108 |
ts.reset(); |
jacint@581 | 109 |
leda_list<leda_edge> ml=MAX_CARD_MATCHING(lg); |
jacint@581 | 110 |
std::cout << "LEDA max matching algorithm." << std::endl |
jacint@581 | 111 |
<< "Size of matching: " |
jacint@581 | 112 |
<< ml.size() << std::endl; |
jacint@581 | 113 |
std::cout << "elapsed time: " << ts << std::endl; |
jacint@581 | 114 |
std::cout << "\n"; |
jacint@581 | 115 |
|
jacint@581 | 116 |
return 0; |
jacint@581 | 117 |
} |