1 #include <iostream> |
|
2 #include <fstream> |
|
3 |
|
4 #include <lemon/list_graph.h> |
|
5 #include <lemon/smart_graph.h> |
|
6 #include <lemon/dimacs.h> |
|
7 #include <lemon/preflow.h> |
|
8 #include <lemon/full_graph.h> |
|
9 #include <merge_node_graph_wrapper.h> |
|
10 |
|
11 #include<lemon/concept_check.h> |
|
12 #include<lemon/concept/graph.h> |
|
13 |
|
14 using std::cout; |
|
15 using std::endl; |
|
16 |
|
17 using namespace lemon; |
|
18 using namespace lemon::concept; |
|
19 |
|
20 class Graph3 : ListGraph { |
|
21 public: |
|
22 class Node : public ListGraph::Node { }; |
|
23 class Edge { }; |
|
24 }; |
|
25 |
|
26 template <typename Graph> |
|
27 void printGraph(const Graph& g) { |
|
28 cout << " nodes:" << endl; |
|
29 for (typename Graph::NodeIt n(g); n!=INVALID; ++n) { |
|
30 cout << " " << g.id(n) << ": out edges:" << endl; |
|
31 for (typename Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) |
|
32 cout << " " << g.id(g.source(e)) << "->" << g.id(g.target(e)) << endl; |
|
33 } |
|
34 cout << " edges:" << endl; |
|
35 for (typename Graph::EdgeIt e(g); e!=INVALID; ++e) { |
|
36 cout << " " << g.id(e) << ": " |
|
37 << g.id(g.source(e)) << "->" << g.id(g.target(e)) << endl; |
|
38 } |
|
39 } |
|
40 |
|
41 int main() { |
|
42 { |
|
43 cout << "FIRST TEST" << endl; |
|
44 //typedef SmartGraph Graph1; |
|
45 typedef ListGraph Graph1; |
|
46 typedef ListGraph Graph2; |
|
47 typedef SmartGraph Graph3; |
|
48 |
|
49 // { |
|
50 // checkConcept<StaticGraph, MergeEdgeGraphWrapper<Graph1, Graph2> >(); |
|
51 // MergeEdgeGraphWrapper<Graph1, Graph2>::printNode(); |
|
52 // MergeEdgeGraphWrapper<Graph1, Graph2>::printEdge(); |
|
53 // checkConcept<StaticGraph, MergeEdgeGraphWrapper<Graph1, Graph1> >(); |
|
54 // MergeEdgeGraphWrapper<Graph1, Graph1>::printNode(); |
|
55 // MergeEdgeGraphWrapper<Graph1, Graph1>::printEdge(); |
|
56 // typedef ResGraphWrapper<Graph1, int, |
|
57 // ConstMap<Graph1, int>, ConstMap<Graph1, int> > Graph4; |
|
58 // checkConcept<StaticGraph, MergeEdgeGraphWrapper<Graph1, Graph4> >(); |
|
59 // MergeEdgeGraphWrapper<Graph1, Graph4>::printNode(); |
|
60 // MergeEdgeGraphWrapper<Graph1, Graph4>::printEdge(); |
|
61 // checkConcept<StaticGraph, MergeEdgeGraphWrapper<Graph4, Graph1> >(); |
|
62 // MergeEdgeGraphWrapper<Graph4, Graph1>::printNode(); |
|
63 // MergeEdgeGraphWrapper<Graph4, Graph1>::printEdge(); |
|
64 // } |
|
65 |
|
66 Graph1 g1; |
|
67 Graph2 g2; |
|
68 typedef MergeEdgeGraphWrapper<Graph1, Graph2> GW; |
|
69 GW gw(g1, g2); |
|
70 Graph1::Node s1, t1; |
|
71 Graph2::Node s2, t2; |
|
72 Graph1::EdgeMap<int> cap1(g1); |
|
73 Graph2::EdgeMap<int> cap2(g2); |
|
74 |
|
75 std::ifstream f1("graph1.dim"); |
|
76 std::ifstream f2("graph2.dim"); |
|
77 readDimacs(f1, g1); |
|
78 readDimacs(f2, g2); |
|
79 |
|
80 // GW::NodeMap<int> ize(gw, 8); |
|
81 // for (GW::NodeIt n(gw); n!=INVALID; ++n) ize.set(n, 9); |
|
82 // GW::EdgeMap<int> mize(gw, 8); |
|
83 // for (GW::EdgeIt n(gw); n!=INVALID; ++n) mize.set(n, 7); |
|
84 |
|
85 // std::ifstream f1("flow-1.dim"); |
|
86 // std::ifstream f2("flow2.dim"); |
|
87 // readDimacs(f1, g1, cap1, s1, t1); |
|
88 // readDimacs(f2, g2, cap2, s2, t2); |
|
89 |
|
90 // GW::EdgeMap<int> cap(gw); |
|
91 // for (GW::EdgeIt e(gw); e!=INVALID; ++e) { |
|
92 // if (gw.forward(e)) cap.set(e, cap1[e]); |
|
93 // if (gw.backward(e)) cap.set(e, cap2[e]); |
|
94 // } |
|
95 |
|
96 // { |
|
97 // GW::EdgeMap<int> flow(gw, 0); |
|
98 // Preflow<GW, int> preflow(gw, GW::Node(s1, INVALID, false), |
|
99 // GW::Node(t1, INVALID, false), cap, flow); |
|
100 // preflow.run(); |
|
101 // std::cout << "s1->t1: " << preflow.flowValue() << std::endl; |
|
102 // } |
|
103 // { |
|
104 // GW::EdgeMap<int> flow(gw, 0); |
|
105 // Preflow<GW, int> preflow(gw, GW::Node(INVALID, s2, true), |
|
106 // GW::Node(INVALID, t2, true), cap, flow); |
|
107 // preflow.run(); |
|
108 // std::cout << "s2->t2: " << preflow.flowValue() << std::endl; |
|
109 // } |
|
110 // { |
|
111 // GW::EdgeMap<int> flow(gw, 0); |
|
112 // Preflow<GW, int> preflow(gw, GW::Node(s1, INVALID, false), |
|
113 // GW::Node(INVALID, t2, true), cap, flow); |
|
114 // preflow.run(); |
|
115 // std::cout << "s1->t2: " << preflow.flowValue() << std::endl; |
|
116 // } |
|
117 // { |
|
118 // GW::EdgeMap<int> flow(gw, 0); |
|
119 // Preflow<GW, int> preflow(gw, GW::Node(INVALID, s2, true), |
|
120 // GW::Node(s1, INVALID, false), cap, flow); |
|
121 // preflow.run(); |
|
122 // std::cout << "s2->t1: " << preflow.flowValue() << std::endl; |
|
123 // } |
|
124 cout << "1st graph" << endl; |
|
125 printGraph(g1); |
|
126 |
|
127 cout << "2nd graph" << endl; |
|
128 printGraph(g2); |
|
129 |
|
130 cout << "merged graph" << endl; |
|
131 printGraph(gw); |
|
132 |
|
133 // for (GW::NodeIt n(gw); n!=INVALID; ++n) |
|
134 // std::cout << ize[n] << std::endl; |
|
135 // for (GW::EdgeIt n(gw); n!=INVALID; ++n) |
|
136 // std::cout << mize[n] << std::endl; |
|
137 |
|
138 typedef NewEdgeSetGraphWrapper2<GW, Graph3> GWW; |
|
139 // { |
|
140 // checkConcept<StaticGraph, GWW>(); |
|
141 // } |
|
142 |
|
143 GWW gww(gw); |
|
144 |
|
145 cout << "new edges graph" << endl; |
|
146 printGraph(gww); |
|
147 |
|
148 GWW::NodeIt n(gww); |
|
149 GWW::Node n1=n; |
|
150 ++n; |
|
151 GWW::Node n2=n; |
|
152 gww.addEdge(n1, n2); |
|
153 // gww.addNode(); |
|
154 // gww.addNode(); |
|
155 |
|
156 cout << "new edges graph" << endl; |
|
157 printGraph(gww); |
|
158 |
|
159 typedef AugmentingGraphWrapper<GW, GWW> GWWW; |
|
160 // { |
|
161 // checkConcept<StaticGraph, GWWW>(); |
|
162 // } |
|
163 GWWW gwww(gw, gww); |
|
164 |
|
165 cout << "fully merged graph" << endl; |
|
166 printGraph(gwww); |
|
167 } |
|
168 |
|
169 |
|
170 { |
|
171 cout << "SECOND TEST" << endl; |
|
172 typedef SmartGraph Graph1; |
|
173 // { |
|
174 // checkConcept<StaticGraph, Graph1>(); |
|
175 // } |
|
176 |
|
177 Graph1 g1; |
|
178 |
|
179 FullGraph pre_g2(2); |
|
180 ConstMap<FullGraph::Edge, bool> const_false_map(false); |
|
181 typedef EdgeSubGraphWrapper<FullGraph, ConstMap<FullGraph::Edge, bool> > |
|
182 Graph2; |
|
183 // { |
|
184 // checkConcept<StaticGraph, Graph2>(); |
|
185 // } |
|
186 |
|
187 Graph2 g2(pre_g2, const_false_map); |
|
188 |
|
189 typedef MergeEdgeGraphWrapper<Graph1, Graph2> GW; |
|
190 // { |
|
191 // checkConcept<StaticGraph, GW>(); |
|
192 // } |
|
193 GW gw(g1, g2); |
|
194 GW::Node sw; |
|
195 GW::Node tw; |
|
196 { |
|
197 Graph2::NodeIt k(g2); |
|
198 sw=GW::Node(INVALID, k, true); |
|
199 ++k; |
|
200 tw=GW::Node(INVALID, k, true); |
|
201 } |
|
202 |
|
203 std::ifstream f1("graph2.dim"); |
|
204 readDimacs(f1, g1); |
|
205 |
|
206 cout << "1st graph" << endl; |
|
207 printGraph(g1); |
|
208 |
|
209 cout << "2nd graph" << endl; |
|
210 printGraph(g2); |
|
211 |
|
212 cout << "merged graph" << endl; |
|
213 printGraph(gw); |
|
214 |
|
215 typedef ListGraph Graph3; |
|
216 //typedef SmartGraph Graph3; |
|
217 Graph3 g3; |
|
218 GW::NodeMap<Graph3::Node> gwn(gw); |
|
219 Graph3::NodeMap<GW::Node> g3n(g3); |
|
220 for (GW::NodeIt n(gw); n!=INVALID; ++n) { |
|
221 Graph3::Node m=g3.addNode(); |
|
222 gwn.set(n, m); |
|
223 g3n.set(m, n); |
|
224 } |
|
225 |
|
226 typedef NewEdgeSetGraphWrapper<GW, Graph3> GWW; |
|
227 // { |
|
228 // checkConcept<StaticGraph, GWW>(); |
|
229 // } |
|
230 |
|
231 GWW gww(gw, g3, gwn, g3n); |
|
232 |
|
233 for (Graph1::NodeIt n(g1); n!=INVALID; ++n) { |
|
234 g3.addEdge(gwn[sw], gwn[GW::Node(n,INVALID,false)]); |
|
235 } |
|
236 |
|
237 // for (Graph1::NodeIt n(g1); n!=INVALID; ++n) { |
|
238 // gww.addEdge(sw, GW::Node(n,INVALID,false)); |
|
239 // } |
|
240 |
|
241 cout << "new edges" << endl; |
|
242 printGraph(g3); |
|
243 |
|
244 cout << "new edges in the new graph" << endl; |
|
245 printGraph(gww); |
|
246 |
|
247 typedef AugmentingGraphWrapper<GW, GWW> GWWW; |
|
248 // { |
|
249 // checkConcept<StaticGraph, GWWW>(); |
|
250 // } |
|
251 GWWW gwww(gw, gww); |
|
252 |
|
253 cout << "new edges merged into the original graph" << endl; |
|
254 printGraph(gwww); |
|
255 |
|
256 } |
|
257 |
|
258 } |
|