marci@510
|
1 |
// -*- c++ -*-
|
marci@510
|
2 |
#include <iostream>
|
marci@510
|
3 |
#include <fstream>
|
marci@510
|
4 |
#include <vector>
|
marci@510
|
5 |
|
marci@510
|
6 |
#include <list_graph.h>
|
marci@510
|
7 |
//#include <smart_graph.h>
|
marci@510
|
8 |
//#include <dimacs.h>
|
marci@555
|
9 |
#include <hugo/time_measure.h>
|
marci@640
|
10 |
#include <hugo/for_each_macros.h>
|
marci@602
|
11 |
#include <bfs_dfs.h>
|
marci@510
|
12 |
#include <bipartite_graph_wrapper.h>
|
marci@555
|
13 |
#include <hugo/maps.h>
|
marci@510
|
14 |
#include <max_flow.h>
|
marci@558
|
15 |
#include <graph_gen.h>
|
marci@559
|
16 |
#include <max_bipartite_matching.h>
|
marci@510
|
17 |
|
marci@510
|
18 |
using namespace hugo;
|
marci@510
|
19 |
|
marci@510
|
20 |
int main() {
|
marci@510
|
21 |
//typedef UndirListGraph Graph;
|
marci@510
|
22 |
typedef BipartiteGraph<ListGraph> Graph;
|
marci@510
|
23 |
|
marci@510
|
24 |
typedef Graph::Node Node;
|
marci@510
|
25 |
typedef Graph::NodeIt NodeIt;
|
marci@510
|
26 |
typedef Graph::Edge Edge;
|
marci@510
|
27 |
typedef Graph::EdgeIt EdgeIt;
|
marci@510
|
28 |
typedef Graph::OutEdgeIt OutEdgeIt;
|
marci@510
|
29 |
|
marci@510
|
30 |
Graph g;
|
marci@510
|
31 |
|
marci@510
|
32 |
int a;
|
marci@510
|
33 |
std::cout << "number of nodes in the first color class=";
|
marci@510
|
34 |
std::cin >> a;
|
marci@510
|
35 |
int b;
|
marci@510
|
36 |
std::cout << "number of nodes in the second color class=";
|
marci@510
|
37 |
std::cin >> b;
|
marci@510
|
38 |
int m;
|
marci@510
|
39 |
std::cout << "number of edges=";
|
marci@510
|
40 |
std::cin >> m;
|
marci@510
|
41 |
|
marci@510
|
42 |
std::cout << "Generatig a random bipartite graph..." << std::endl;
|
marci@510
|
43 |
random_init();
|
marci@558
|
44 |
randomBipartiteGraph(g, a, b, m);
|
marci@510
|
45 |
|
marci@512
|
46 |
// std::cout << "Edges of the bipartite graph:" << std::endl;
|
marci@512
|
47 |
// FOR_EACH_LOC(EdgeIt, e, g) std::cout << e << " ";
|
marci@512
|
48 |
// std::cout << std::endl;
|
marci@510
|
49 |
|
marci@512
|
50 |
// std::cout << "Nodes:" << std::endl;
|
marci@512
|
51 |
// FOR_EACH_LOC(Graph::NodeIt, v, g) std::cout << v << " ";
|
marci@512
|
52 |
// std::cout << std::endl;
|
marci@512
|
53 |
// std::cout << "Nodes in T:" << std::endl;
|
marci@512
|
54 |
// FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::T_CLASS) std::cout << v << " ";
|
marci@512
|
55 |
// std::cout << std::endl;
|
marci@512
|
56 |
// std::cout << "Nodes in S:" << std::endl;
|
marci@512
|
57 |
// FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::S_CLASS) std::cout << v << " ";
|
marci@512
|
58 |
// std::cout << std::endl;
|
marci@510
|
59 |
|
marci@512
|
60 |
// std::cout << "Erasing the first node..." << std::endl;
|
marci@512
|
61 |
// NodeIt n;
|
marci@512
|
62 |
// g.first(n);
|
marci@512
|
63 |
// g.erase(n);
|
marci@512
|
64 |
// std::cout << "Nodes of the bipartite graph:" << std::endl;
|
marci@512
|
65 |
// FOR_EACH_GLOB(n, g) std::cout << n << " ";
|
marci@512
|
66 |
// std::cout << std::endl;
|
marci@510
|
67 |
|
marci@512
|
68 |
// std::cout << "Nodes in T:" << std::endl;
|
marci@512
|
69 |
// FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::T_CLASS) std::cout << v << " ";
|
marci@512
|
70 |
// std::cout << std::endl;
|
marci@512
|
71 |
// std::cout << "Nodes in S:" << std::endl;
|
marci@512
|
72 |
// FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::S_CLASS) std::cout << v << " ";
|
marci@512
|
73 |
// std::cout << std::endl;
|
marci@510
|
74 |
|
marci@510
|
75 |
typedef stGraphWrapper<Graph> stGW;
|
marci@510
|
76 |
stGW stgw(g);
|
marci@510
|
77 |
ConstMap<stGW::Edge, int> const1map(1);
|
marci@510
|
78 |
|
marci@510
|
79 |
Timer ts;
|
marci@510
|
80 |
ts.reset();
|
marci@510
|
81 |
stGW::EdgeMap<int> flow(stgw);
|
marci@510
|
82 |
MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> >
|
marci@510
|
83 |
max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow);
|
marci@510
|
84 |
max_flow_test.run();
|
marci@510
|
85 |
// while (max_flow_test.augmentOnShortestPath()) { }
|
marci@510
|
86 |
// typedef ListGraph MutableGraph;
|
marci@510
|
87 |
// while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) {
|
marci@510
|
88 |
// while (max_flow_test.augmentOnBlockingFlow2()) {
|
marci@510
|
89 |
// std::cout << max_flow_test.flowValue() << std::endl;
|
marci@510
|
90 |
// }
|
marci@510
|
91 |
std::cout << "max flow value: " << max_flow_test.flowValue() << std::endl;
|
marci@510
|
92 |
std::cout << "elapsed time: " << ts << std::endl;
|
marci@512
|
93 |
// FOR_EACH_LOC(stGW::EdgeIt, e, stgw) {
|
marci@512
|
94 |
// if (flow[e]) std::cout << e << std::endl;
|
marci@512
|
95 |
// }
|
marci@510
|
96 |
std::cout << std::endl;
|
marci@510
|
97 |
|
marci@510
|
98 |
typedef ConstMap<Graph::Edge, int> EdgeCap;
|
marci@510
|
99 |
EdgeCap ge1(1);
|
marci@510
|
100 |
typedef ConstMap<Graph::Node, int> NodeCap;
|
marci@510
|
101 |
NodeCap gn1(1);
|
marci@510
|
102 |
typedef Graph::EdgeMap<int> EdgeFlow;
|
marci@510
|
103 |
EdgeFlow gef(g); //0
|
marci@510
|
104 |
typedef Graph::NodeMap<int> NodeFlow;
|
marci@510
|
105 |
NodeFlow gnf(g); //0
|
marci@510
|
106 |
|
marci@510
|
107 |
typedef stGraphWrapper<Graph>::EdgeMapWrapper<EdgeCap, NodeCap> CapMap;
|
marci@510
|
108 |
typedef stGraphWrapper<Graph>::EdgeMapWrapper<EdgeFlow, NodeFlow> FlowMap;
|
marci@510
|
109 |
CapMap cm(ge1, gn1);
|
marci@510
|
110 |
FlowMap fm(gef, gnf);
|
marci@510
|
111 |
|
marci@510
|
112 |
//Timer ts;
|
marci@510
|
113 |
ts.reset();
|
marci@510
|
114 |
//stGW::EdgeMap<int> flow(stgw);
|
marci@510
|
115 |
MaxFlow<stGW, int, CapMap, FlowMap>
|
marci@510
|
116 |
max_flow_test1(stgw, stgw.S_NODE, stgw.T_NODE, cm, fm);
|
marci@510
|
117 |
max_flow_test1.run();
|
marci@510
|
118 |
// while (max_flow_test.augmentOnShortestPath()) { }
|
marci@510
|
119 |
// typedef ListGraph MutableGraph;
|
marci@510
|
120 |
// while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) {
|
marci@510
|
121 |
// while (max_flow_test.augmentOnBlockingFlow2()) {
|
marci@510
|
122 |
// std::cout << max_flow_test.flowValue() << std::endl;
|
marci@510
|
123 |
// }
|
marci@510
|
124 |
std::cout << "max flow value: " << max_flow_test1.flowValue() << std::endl;
|
marci@510
|
125 |
std::cout << "elapsed time: " << ts << std::endl;
|
marci@510
|
126 |
// FOR_EACH_LOC(Graph::EdgeIt, e, g) {
|
marci@510
|
127 |
// if (gef[e]) std::cout << e << std::endl;
|
marci@510
|
128 |
// }
|
marci@510
|
129 |
std::cout << std::endl;
|
marci@510
|
130 |
|
marci@510
|
131 |
ts.reset();
|
marci@510
|
132 |
FOR_EACH_LOC(Graph::EdgeIt, e, g) gef.set(e, 0);
|
marci@510
|
133 |
FOR_EACH_LOC(Graph::NodeIt, n, g) gnf.set(n, 0);
|
marci@613
|
134 |
MaxBipartiteMatching<Graph, ConstMap<Graph::Edge, int>, ConstMap<Graph::Node, int>,
|
marci@510
|
135 |
Graph::EdgeMap<int>, Graph::NodeMap<int> >
|
marci@510
|
136 |
matching_test(g, ge1, gn1, gef, gnf);
|
marci@510
|
137 |
matching_test.run();
|
marci@510
|
138 |
|
marci@510
|
139 |
std::cout << "max flow value: " << matching_test.matchingValue() << std::endl;
|
marci@510
|
140 |
std::cout << "elapsed time: " << ts << std::endl;
|
marci@510
|
141 |
// FOR_EACH_LOC(Graph::EdgeIt, e, g) {
|
marci@510
|
142 |
// if (gef[e]) std::cout << e << std::endl;
|
marci@510
|
143 |
// }
|
marci@510
|
144 |
std::cout << std::endl;
|
marci@512
|
145 |
|
marci@512
|
146 |
ts.reset();
|
marci@512
|
147 |
FOR_EACH_LOC(Graph::EdgeIt, e, g) gef.set(e, 0);
|
marci@512
|
148 |
//FOR_EACH_LOC(Graph::NodeIt, n, g) gnf.set(n, 0);
|
marci@613
|
149 |
MaxBipartiteMatching<Graph, ConstMap<Graph::Edge, int>, ConstMap<Graph::Node, int>,
|
marci@512
|
150 |
Graph::EdgeMap<int>, Graph::NodeMap<int> >
|
marci@512
|
151 |
matching_test_1(g, ge1, gn1, gef/*, gnf*/);
|
marci@512
|
152 |
matching_test_1.run();
|
marci@512
|
153 |
|
marci@512
|
154 |
std::cout << "max flow value: " << matching_test_1.matchingValue() << std::endl;
|
marci@512
|
155 |
std::cout << "elapsed time: " << ts << std::endl;
|
marci@512
|
156 |
// FOR_EACH_LOC(Graph::EdgeIt, e, g) {
|
marci@512
|
157 |
// if (gef[e]) std::cout << e << std::endl;
|
marci@512
|
158 |
// }
|
marci@512
|
159 |
std::cout << std::endl;
|
marci@512
|
160 |
|
marci@510
|
161 |
return 0;
|
marci@510
|
162 |
}
|