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 |
}
|