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