8 #include <LEDA/mcb_matching.h> |
8 #include <LEDA/mcb_matching.h> |
9 #include <LEDA/list.h> |
9 #include <LEDA/list.h> |
10 #include <LEDA/graph_gen.h> |
10 #include <LEDA/graph_gen.h> |
11 |
11 |
12 #include <leda_graph_wrapper.h> |
12 #include <leda_graph_wrapper.h> |
13 #include <list_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 <for_each_macros.h> |
17 #include <hugo/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 <max_flow.h> |
22 |
22 |
49 leda::graph lg; |
49 leda::graph lg; |
50 //lg.make_undirected(); |
50 //lg.make_undirected(); |
51 typedef LedaGraphWrapper<leda::graph> Graph; |
51 typedef LedaGraphWrapper<leda::graph> Graph; |
52 Graph g(lg); |
52 Graph g(lg); |
53 |
53 |
54 //for UndirListGraph |
54 //for UndirSageGraph |
55 //typedef UndirListGraph Graph; |
55 //typedef UndirSageGraph Graph; |
56 //Graph g; |
56 //Graph g; |
57 |
57 |
58 typedef Graph::Node Node; |
58 typedef Graph::Node Node; |
59 typedef Graph::NodeIt NodeIt; |
59 typedef Graph::NodeIt NodeIt; |
60 typedef Graph::Edge Edge; |
60 typedef Graph::Edge Edge; |
121 << ml.size() << std::endl; |
121 << ml.size() << std::endl; |
122 std::cout << "elapsed time: " << ts << std::endl << std::endl; |
122 std::cout << "elapsed time: " << ts << std::endl << std::endl; |
123 |
123 |
124 // ts.reset(); |
124 // ts.reset(); |
125 // FOR_EACH_LOC(stGW::EdgeIt, e, stgw) flow.set(e, 0); |
125 // FOR_EACH_LOC(stGW::EdgeIt, e, stgw) flow.set(e, 0); |
126 // typedef ListGraph MutableGraph; |
126 // typedef SageGraph MutableGraph; |
127 // while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { } |
127 // while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { } |
128 // std::cout << "HUGO max matching algorithm based on blocking flow augmentation." |
128 // std::cout << "HUGO max matching algorithm based on blocking flow augmentation." |
129 // << std::endl << "Matching size: " |
129 // << std::endl << "Matching size: " |
130 // << max_flow_test.flowValue() << std::endl; |
130 // << max_flow_test.flowValue() << std::endl; |
131 // std::cout << "elapsed time: " << ts << std::endl << std::endl; |
131 // std::cout << "elapsed time: " << ts << std::endl << std::endl; |
132 |
132 |
133 { |
133 { |
134 ListGraph hg; |
134 SageGraph hg; |
135 ListGraph::Node s=hg.addNode(); |
135 SageGraph::Node s=hg.addNode(); |
136 ListGraph::Node t=hg.addNode(); |
136 SageGraph::Node t=hg.addNode(); |
137 BGW::NodeMap<ListGraph::Node> b_s_nodes(bgw); |
137 BGW::NodeMap<SageGraph::Node> b_s_nodes(bgw); |
138 BGW::NodeMap<ListGraph::Node> b_t_nodes(bgw); |
138 BGW::NodeMap<SageGraph::Node> b_t_nodes(bgw); |
139 |
139 |
140 FOR_EACH_INC_LOC(BGW::ClassNodeIt, n, bgw, BGW::S_CLASS) { |
140 FOR_EACH_INC_LOC(BGW::ClassNodeIt, n, bgw, BGW::S_CLASS) { |
141 b_s_nodes.set(n, hg.addNode()); |
141 b_s_nodes.set(n, hg.addNode()); |
142 hg.addEdge(s, b_s_nodes[n]); |
142 hg.addEdge(s, b_s_nodes[n]); |
143 } |
143 } |
147 } |
147 } |
148 |
148 |
149 FOR_EACH_LOC(BGW::EdgeIt, e, bgw) |
149 FOR_EACH_LOC(BGW::EdgeIt, e, bgw) |
150 hg.addEdge(b_s_nodes[bgw.tail(e)], b_t_nodes[bgw.head(e)]); |
150 hg.addEdge(b_s_nodes[bgw.tail(e)], b_t_nodes[bgw.head(e)]); |
151 |
151 |
152 ConstMap<ListGraph::Edge, int> cm(1); |
152 ConstMap<SageGraph::Edge, int> cm(1); |
153 ListGraph::EdgeMap<int> flow(hg); //0 |
153 SageGraph::EdgeMap<int> flow(hg); //0 |
154 |
154 |
155 Timer ts; |
155 Timer ts; |
156 |
156 |
157 ts.reset(); |
157 ts.reset(); |
158 MaxFlow<ListGraph, int, ConstMap<ListGraph::Edge, int>, |
158 MaxFlow<SageGraph, int, ConstMap<SageGraph::Edge, int>, |
159 ListGraph::EdgeMap<int> > |
159 SageGraph::EdgeMap<int> > |
160 max_flow_test(hg, s, t, cm, flow); |
160 max_flow_test(hg, s, t, cm, flow); |
161 max_flow_test.run(); |
161 max_flow_test.run(); |
162 std::cout << "HUGO max matching algorithm on ListGraph by copying the graph, based on preflow." |
162 std::cout << "HUGO max matching algorithm on SageGraph by copying the graph, based on preflow." |
163 << std::endl |
163 << std::endl |
164 << "Size of matching: " |
164 << "Size of matching: " |
165 << max_flow_test.flowValue() << std::endl; |
165 << max_flow_test.flowValue() << std::endl; |
166 std::cout << "elapsed time: " << ts << std::endl << std::endl; |
166 std::cout << "elapsed time: " << ts << std::endl << std::endl; |
167 } |
167 } |