12 #include <leda_graph_wrapper.h> |
12 #include <leda_graph_wrapper.h> |
13 #include <sage_graph.h> |
13 #include <sage_graph.h> |
14 //#include <smart_graph.h> |
14 //#include <smart_graph.h> |
15 //#include <dimacs.h> |
15 //#include <dimacs.h> |
16 #include <hugo/time_measure.h> |
16 #include <hugo/time_measure.h> |
17 #include <hugo/for_each_macros.h> |
17 #include <for_each_macros.h> |
18 #include <hugo/graph_wrapper.h> |
18 #include <hugo/graph_wrapper.h> |
19 #include <bipartite_graph_wrapper.h> |
19 #include <bipartite_graph_wrapper.h> |
20 #include <hugo/maps.h> |
20 #include <hugo/maps.h> |
21 #include <max_flow.h> |
21 #include <hugo/max_flow.h> |
22 |
22 |
23 /** |
23 using std::cout; |
24 * Inicializalja a veletlenszamgeneratort. |
24 using std::endl; |
25 * Figyelem, ez nem jo igazi random szamokhoz, |
|
26 * erre ne bizzad a titkaidat! |
|
27 */ |
|
28 void random_init() |
|
29 { |
|
30 unsigned int seed = getpid(); |
|
31 seed |= seed << 15; |
|
32 seed ^= time(0); |
|
33 |
|
34 srand(seed); |
|
35 } |
|
36 |
|
37 /** |
|
38 * Egy veletlen int-et ad vissza 0 es m-1 kozott. |
|
39 */ |
|
40 int random(int m) |
|
41 { |
|
42 return int( double(m) * rand() / (RAND_MAX + 1.0) ); |
|
43 } |
|
44 |
25 |
45 using namespace hugo; |
26 using namespace hugo; |
46 |
27 |
47 int main() { |
28 int main() { |
48 //for leda graph |
29 //for leda graph |
63 |
44 |
64 std::vector<Graph::Node> s_nodes; |
45 std::vector<Graph::Node> s_nodes; |
65 std::vector<Graph::Node> t_nodes; |
46 std::vector<Graph::Node> t_nodes; |
66 |
47 |
67 int a; |
48 int a; |
68 std::cout << "number of nodes in the first color class="; |
49 cout << "number of nodes in the first color class="; |
69 std::cin >> a; |
50 std::cin >> a; |
70 int b; |
51 int b; |
71 std::cout << "number of nodes in the second color class="; |
52 cout << "number of nodes in the second color class="; |
72 std::cin >> b; |
53 std::cin >> b; |
73 int m; |
54 int m; |
74 std::cout << "number of edges="; |
55 cout << "number of edges="; |
75 std::cin >> m; |
56 std::cin >> m; |
76 int k; |
57 int k; |
77 std::cout << "A bipartite graph is a random group graph if the color classes \nA and B are partitiones to A_0, A_1, ..., A_{k-1} and B_0, B_1, ..., B_{k-1} \nas equally as possible \nand the edges from A_i goes to A_{i-1 mod k} and A_{i+1 mod k}.\n"; |
58 cout << "A bipartite graph is a random group graph if the color classes \nA and B are partitiones to A_0, A_1, ..., A_{k-1} and B_0, B_1, ..., B_{k-1} \nas equally as possible \nand the edges from A_i goes to A_{i-1 mod k} and A_{i+1 mod k}.\n"; |
78 std::cout << "number of groups in LEDA random group graph="; |
59 cout << "number of groups in LEDA random group graph="; |
79 std::cin >> k; |
60 std::cin >> k; |
80 std::cout << std::endl; |
61 cout << endl; |
81 |
62 |
82 leda_list<leda_node> lS; |
63 leda_list<leda_node> lS; |
83 leda_list<leda_node> lT; |
64 leda_list<leda_node> lT; |
84 random_bigraph(lg, a, b, m, lS, lT, k); |
65 random_bigraph(lg, a, b, m, lS, lT, k); |
85 |
66 |
107 ts.reset(); |
88 ts.reset(); |
108 FOR_EACH_LOC(stGW::EdgeIt, e, stgw) flow.set(e, 0); |
89 FOR_EACH_LOC(stGW::EdgeIt, e, stgw) flow.set(e, 0); |
109 MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> > |
90 MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> > |
110 max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow/*, true*/); |
91 max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow/*, true*/); |
111 max_flow_test.run(); |
92 max_flow_test.run(); |
112 std::cout << "HUGO max matching algorithm based on preflow." << std::endl |
93 cout << "HUGO max matching algorithm based on preflow." << endl |
113 << "Size of matching: " |
94 << "Size of matching: " |
114 << max_flow_test.flowValue() << std::endl; |
95 << max_flow_test.flowValue() << endl; |
115 std::cout << "elapsed time: " << ts << std::endl << std::endl; |
96 cout << "elapsed time: " << ts << endl << endl; |
116 |
97 |
117 ts.reset(); |
98 ts.reset(); |
118 leda_list<leda_edge> ml=MAX_CARD_BIPARTITE_MATCHING(lg); |
99 leda_list<leda_edge> ml=MAX_CARD_BIPARTITE_MATCHING(lg); |
119 std::cout << "LEDA max matching algorithm." << std::endl |
100 cout << "LEDA max matching algorithm." << endl |
120 << "Size of matching: " |
101 << "Size of matching: " |
121 << ml.size() << std::endl; |
102 << ml.size() << endl; |
122 std::cout << "elapsed time: " << ts << std::endl << std::endl; |
103 cout << "elapsed time: " << ts << endl << endl; |
123 |
104 |
124 // ts.reset(); |
105 // ts.reset(); |
125 // FOR_EACH_LOC(stGW::EdgeIt, e, stgw) flow.set(e, 0); |
106 // FOR_EACH_LOC(stGW::EdgeIt, e, stgw) flow.set(e, 0); |
126 // typedef SageGraph MutableGraph; |
107 // typedef SageGraph MutableGraph; |
127 // while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { } |
108 // while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { } |
128 // std::cout << "HUGO max matching algorithm based on blocking flow augmentation." |
109 // cout << "HUGO max matching algorithm based on blocking flow augmentation." |
129 // << std::endl << "Matching size: " |
110 // << endl << "Matching size: " |
130 // << max_flow_test.flowValue() << std::endl; |
111 // << max_flow_test.flowValue() << endl; |
131 // std::cout << "elapsed time: " << ts << std::endl << std::endl; |
112 // cout << "elapsed time: " << ts << endl << endl; |
132 |
113 |
133 { |
114 { |
134 SageGraph hg; |
115 SageGraph hg; |
135 SageGraph::Node s=hg.addNode(); |
116 SageGraph::Node s=hg.addNode(); |
136 SageGraph::Node t=hg.addNode(); |
117 SageGraph::Node t=hg.addNode(); |
157 ts.reset(); |
138 ts.reset(); |
158 MaxFlow<SageGraph, int, ConstMap<SageGraph::Edge, int>, |
139 MaxFlow<SageGraph, int, ConstMap<SageGraph::Edge, int>, |
159 SageGraph::EdgeMap<int> > |
140 SageGraph::EdgeMap<int> > |
160 max_flow_test(hg, s, t, cm, flow); |
141 max_flow_test(hg, s, t, cm, flow); |
161 max_flow_test.run(); |
142 max_flow_test.run(); |
162 std::cout << "HUGO max matching algorithm on SageGraph by copying the graph, based on preflow." |
143 cout << "HUGO max matching algorithm on SageGraph by copying the graph, based on preflow." |
163 << std::endl |
144 << endl |
164 << "Size of matching: " |
145 << "Size of matching: " |
165 << max_flow_test.flowValue() << std::endl; |
146 << max_flow_test.flowValue() << endl; |
166 std::cout << "elapsed time: " << ts << std::endl << std::endl; |
147 cout << "elapsed time: " << ts << endl << endl; |
167 } |
148 } |
168 |
149 |
169 return 0; |
150 return 0; |
170 } |
151 } |