|
1 /* -*- mode: C++; indent-tabs-mode: nil; -*- |
|
2 * |
|
3 * This file is a part of LEMON, a generic C++ optimization library. |
|
4 * |
|
5 * Copyright (C) 2015-2017 |
|
6 * EMAXA Kutato-fejleszto Kft. (EMAXA Research Ltd.) |
|
7 * |
|
8 * Permission to use, modify and distribute this software is granted |
|
9 * provided that this copyright notice appears in all copies. For |
|
10 * precise terms see the accompanying LICENSE file. |
|
11 * |
|
12 * This software is provided "AS IS" with no warranty of any kind, |
|
13 * express or implied, and with no claim as to its suitability for any |
|
14 * purpose. |
|
15 * |
|
16 */ |
|
17 |
|
18 #include <lemon/vf2pp.h> |
|
19 #include <lemon/concepts/digraph.h> |
|
20 #include <lemon/smart_graph.h> |
|
21 #include <lemon/lgf_reader.h> |
|
22 #include <lemon/concepts/maps.h> |
|
23 #include <lemon/maps.h> |
|
24 #include <lemon/list_graph.h> |
|
25 |
|
26 #include <test/test_tools.h> |
|
27 #include <sstream> |
|
28 |
|
29 using namespace lemon; |
|
30 |
|
31 char petersen_lgf[] = |
|
32 "@nodes\n" |
|
33 "label col1 col2\n" |
|
34 "0 1 1\n" |
|
35 "1 1 2\n" |
|
36 "2 1 3\n" |
|
37 "3 1 4\n" |
|
38 "4 2 5\n" |
|
39 "5 2 1\n" |
|
40 "6 2 2\n" |
|
41 "7 2 3\n" |
|
42 "8 2 4\n" |
|
43 "9 2 5\n" |
|
44 "@arcs\n" |
|
45 " -\n" |
|
46 "0 1\n" |
|
47 "1 2\n" |
|
48 "2 3\n" |
|
49 "3 4\n" |
|
50 "4 0\n" |
|
51 "0 5\n" |
|
52 "1 6\n" |
|
53 "2 7\n" |
|
54 "3 8\n" |
|
55 "4 9\n" |
|
56 "5 8\n" |
|
57 "5 7\n" |
|
58 "9 6\n" |
|
59 "9 7\n" |
|
60 "6 8\n"; |
|
61 |
|
62 char c5_lgf[] = |
|
63 "@nodes\n" |
|
64 "label col\n" |
|
65 "0 1\n" |
|
66 "1 2\n" |
|
67 "2 3\n" |
|
68 "3 4\n" |
|
69 "4 5\n" |
|
70 "@arcs\n" |
|
71 " -\n" |
|
72 "0 1\n" |
|
73 "1 2\n" |
|
74 "2 3\n" |
|
75 "3 4\n" |
|
76 "4 0\n"; |
|
77 |
|
78 char c7_lgf[] = |
|
79 "@nodes\n" |
|
80 "label\n" |
|
81 "0\n" |
|
82 "1\n" |
|
83 "2\n" |
|
84 "3\n" |
|
85 "4\n" |
|
86 "5\n" |
|
87 "6\n" |
|
88 "@arcs\n" |
|
89 " -\n" |
|
90 "0 1\n" |
|
91 "1 2\n" |
|
92 "2 3\n" |
|
93 "3 4\n" |
|
94 "4 5\n" |
|
95 "5 6\n" |
|
96 "6 0\n"; |
|
97 |
|
98 char c10_lgf[] = |
|
99 "@nodes\n" |
|
100 "label\n" |
|
101 "0\n" |
|
102 "1\n" |
|
103 "2\n" |
|
104 "3\n" |
|
105 "4\n" |
|
106 "5\n" |
|
107 "6\n" |
|
108 "7\n" |
|
109 "8\n" |
|
110 "9\n" |
|
111 "@arcs\n" |
|
112 " -\n" |
|
113 "0 1\n" |
|
114 "1 2\n" |
|
115 "2 3\n" |
|
116 "3 4\n" |
|
117 "4 5\n" |
|
118 "5 6\n" |
|
119 "6 7\n" |
|
120 "7 8\n" |
|
121 "8 9\n" |
|
122 "9 0\n"; |
|
123 |
|
124 char p10_lgf[] = |
|
125 "@nodes\n" |
|
126 "label\n" |
|
127 "0\n" |
|
128 "1\n" |
|
129 "2\n" |
|
130 "3\n" |
|
131 "4\n" |
|
132 "5\n" |
|
133 "6\n" |
|
134 "7\n" |
|
135 "8\n" |
|
136 "9\n" |
|
137 "@arcs\n" |
|
138 " -\n" |
|
139 "0 1\n" |
|
140 "1 2\n" |
|
141 "2 3\n" |
|
142 "3 4\n" |
|
143 "4 5\n" |
|
144 "5 6\n" |
|
145 "6 7\n" |
|
146 "7 8\n" |
|
147 "8 9\n"; |
|
148 |
|
149 SmartGraph petersen, c5, c7, c10, p10; |
|
150 SmartGraph::NodeMap<int> petersen_col1(petersen); |
|
151 SmartGraph::NodeMap<int> petersen_col2(petersen); |
|
152 SmartGraph::NodeMap<int> c5_col(c5); |
|
153 |
|
154 void make_graphs(){ |
|
155 std::stringstream ss(petersen_lgf); |
|
156 graphReader(petersen, ss) |
|
157 .nodeMap("col1",petersen_col1) |
|
158 .nodeMap("col2",petersen_col2) |
|
159 .run(); |
|
160 |
|
161 ss.clear(); |
|
162 ss.str(""); |
|
163 ss<<c5_lgf; |
|
164 |
|
165 graphReader(c5, ss) |
|
166 .nodeMap("col",c5_col) |
|
167 .run(); |
|
168 |
|
169 ss.clear(); |
|
170 ss.str(""); |
|
171 ss<<c7_lgf; |
|
172 graphReader(c7, ss).run(); |
|
173 |
|
174 ss.clear(); |
|
175 ss.str(""); |
|
176 ss<<c10_lgf; |
|
177 graphReader(c10, ss).run(); |
|
178 |
|
179 ss.clear(); |
|
180 ss.str(""); |
|
181 ss<<p10_lgf; |
|
182 graphReader(p10, ss).run(); |
|
183 |
|
184 } |
|
185 |
|
186 class IntConvertible1{ |
|
187 public: |
|
188 operator int(){ |
|
189 return 0; |
|
190 } |
|
191 }; |
|
192 |
|
193 class IntConvertible2{ |
|
194 public: |
|
195 operator int(){ |
|
196 return 0; |
|
197 } |
|
198 }; |
|
199 |
|
200 template<class G1,class G2> |
|
201 void checkVf2Compile() { |
|
202 G1 g; |
|
203 G2 h; |
|
204 concepts::ReadWriteMap<typename G1::Node, typename G2::Node> r; |
|
205 bool succ; |
|
206 ::lemon::ignore_unused_variable_warning(succ); |
|
207 |
|
208 succ = vf2pp(g,h).run(); |
|
209 succ = vf2pp(g,h).induced().run(); |
|
210 succ = vf2pp(g,h).iso().run(); |
|
211 succ = vf2pp(g,h).mapping(r).run(); |
|
212 succ = vf2pp(g,h).induced().mapping(r).run(); |
|
213 succ = vf2pp(g,h).iso().mapping(r).run(); |
|
214 |
|
215 |
|
216 concepts::ReadMap<typename G1::Node, int> c1; |
|
217 concepts::ReadMap<typename G2::Node, int> c2; |
|
218 Vf2pp<G1,G2,concepts::ReadWriteMap<typename G1::Node, typename G2::Node>, |
|
219 concepts::ReadMap<typename G1::Node, int>, |
|
220 concepts::ReadMap<typename G2::Node, int> > |
|
221 myVf2pp(g,h,r,c1,c2); |
|
222 myVf2pp.find(); |
|
223 |
|
224 succ = vf2pp(g,h).nodeLabels(c1,c2).mapping(r).run(); |
|
225 succ = vf2pp(g,h).nodeLabels(c1,c2) |
|
226 .mapping(r).run(); |
|
227 |
|
228 |
|
229 concepts::ReadMap<typename G1::Node, char> c1_c; |
|
230 concepts::ReadMap<typename G2::Node, char> c2_c; |
|
231 Vf2pp<G1,G2,concepts::ReadWriteMap<typename G1::Node, typename G2::Node>, |
|
232 concepts::ReadMap<typename G1::Node, char>, |
|
233 concepts::ReadMap<typename G2::Node, char> > |
|
234 myVf2pp_c(g,h,r,c1_c,c2_c); |
|
235 myVf2pp_c.find(); |
|
236 |
|
237 succ = vf2pp(g,h).nodeLabels(c1_c,c2_c).mapping(r).run(); |
|
238 succ = vf2pp(g,h).nodeLabels(c1_c,c2_c) |
|
239 .mapping(r).run(); |
|
240 |
|
241 |
|
242 concepts::ReadMap<typename G1::Node, IntConvertible1> c1_IntConv; |
|
243 concepts::ReadMap<typename G2::Node, IntConvertible2> c2_IntConv; |
|
244 Vf2pp<G1,G2,concepts::ReadWriteMap<typename G1::Node, typename G2::Node>, |
|
245 concepts::ReadMap<typename G1::Node, IntConvertible1>, |
|
246 concepts::ReadMap<typename G2::Node, IntConvertible2> > |
|
247 myVf2pp_IntConv(g,h,r,c1_IntConv,c2_IntConv); |
|
248 myVf2pp_IntConv.find(); |
|
249 |
|
250 succ = vf2pp(g,h).nodeLabels(c1_IntConv,c2_IntConv).mapping(r).run(); |
|
251 succ = vf2pp(g,h).nodeLabels(c1_IntConv,c2_IntConv) |
|
252 .mapping(r).run(); |
|
253 } |
|
254 |
|
255 void justCompile() { |
|
256 checkVf2Compile<concepts::Graph,concepts::Graph>(); |
|
257 checkVf2Compile<concepts::Graph,SmartGraph>(); |
|
258 checkVf2Compile<SmartGraph,concepts::Graph>(); |
|
259 } |
|
260 |
|
261 template<class G1, class G2, class I> |
|
262 void checkSub(const G1 &g1, const G2 &g2, const I &i) { |
|
263 { |
|
264 std::set<typename G2::Node> image; |
|
265 for(typename G1::NodeIt n(g1);n!=INVALID;++n){ |
|
266 check(i[n]!=INVALID, "Wrong isomorphism: incomplete mapping."); |
|
267 check(image.count(i[n])==0,"Wrong isomorphism: not injective."); |
|
268 image.insert(i[n]); |
|
269 } |
|
270 } |
|
271 for(typename G1::EdgeIt e(g1);e!=INVALID;++e) |
|
272 check(findEdge(g2,i[g1.u(e)],i[g1.v(e)])!=INVALID, |
|
273 "Wrong isomorphism: missing edge(checkSub)."); |
|
274 } |
|
275 |
|
276 template<class G1, class G2, class I> |
|
277 void checkInd(const G1 &g1, const G2 &g2, const I &i) { |
|
278 std::set<typename G2::Node> image; |
|
279 for(typename G1::NodeIt n(g1);n!=INVALID;++n) { |
|
280 check(i[n]!=INVALID, "Wrong isomorphism: incomplete mapping."); |
|
281 check(image.count(i[n])==0,"Wrong isomorphism: not injective."); |
|
282 image.insert(i[n]); |
|
283 } |
|
284 for(typename G1::NodeIt n(g1); n!=INVALID; ++n) |
|
285 for(typename G1::NodeIt m(g1); m!=INVALID; ++m) |
|
286 if((findEdge(g1,n,m)==INVALID) != (findEdge(g2,i[n],i[m])==INVALID)) { |
|
287 std::cout << "Wrong isomorphism: edge mismatch"; |
|
288 exit(1); |
|
289 } |
|
290 } |
|
291 |
|
292 template<class G1,class G2> |
|
293 int checkSub(const G1 &g1, const G2 &g2) { |
|
294 typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID); |
|
295 if(vf2pp(g1,g2).mapping(iso).run()){ |
|
296 checkSub(g1,g2,iso); |
|
297 return true; |
|
298 } |
|
299 else |
|
300 return false; |
|
301 } |
|
302 |
|
303 template<class G1,class G2> |
|
304 int checkInd(const G1 &g1, const G2 &g2) { |
|
305 typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID); |
|
306 if(vf2pp(g1,g2).induced().mapping(iso).run()) { |
|
307 checkInd(g1,g2,iso); |
|
308 return true; |
|
309 } |
|
310 else |
|
311 return false; |
|
312 } |
|
313 |
|
314 template<class G1,class G2> |
|
315 int checkIso(const G1 &g1, const G2 &g2) { |
|
316 typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID); |
|
317 if(vf2pp(g1,g2).iso().mapping(iso).run()) { |
|
318 check(countNodes(g1)==countNodes(g2), |
|
319 "Wrong iso alg.: they are not isomophic."); |
|
320 checkInd(g1,g2,iso); |
|
321 return true; |
|
322 } |
|
323 else |
|
324 return false; |
|
325 } |
|
326 |
|
327 template<class G1, class G2, class L1, class L2, class I> |
|
328 void checkLabel(const G1 &g1, const G2 &, |
|
329 const L1 &l1, const L2 &l2,const I &i) { |
|
330 for(typename G1::NodeIt n(g1);n!=INVALID;++n) |
|
331 check(l1[n]==l2[i[n]],"Wrong isomorphism: label mismatch."); |
|
332 } |
|
333 |
|
334 template<class G1,class G2,class L1,class L2> |
|
335 int checkSub(const G1 &g1, const G2 &g2, const L1 &l1, const L2 &l2) { |
|
336 typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID); |
|
337 if(vf2pp(g1,g2).nodeLabels(l1,l2).mapping(iso).run()) { |
|
338 checkSub(g1,g2,iso); |
|
339 checkLabel(g1,g2,l1,l2,iso); |
|
340 return true; |
|
341 } |
|
342 else |
|
343 return false; |
|
344 } |
|
345 |
|
346 int main() { |
|
347 make_graphs(); |
|
348 // justCompile(); |
|
349 check(checkSub(c5,petersen), "There should exist a C5->Petersen mapping."); |
|
350 check(!checkSub(c7,petersen), |
|
351 "There should not exist a C7->Petersen mapping."); |
|
352 check(checkSub(p10,petersen), "There should exist a P10->Petersen mapping."); |
|
353 check(!checkSub(c10,petersen), |
|
354 "There should not exist a C10->Petersen mapping."); |
|
355 check(checkSub(petersen,petersen), |
|
356 "There should exist a Petersen->Petersen mapping."); |
|
357 |
|
358 check(checkInd(c5,petersen), |
|
359 "There should exist a C5->Petersen spanned mapping."); |
|
360 check(!checkInd(c7,petersen), |
|
361 "There should exist a C7->Petersen spanned mapping."); |
|
362 check(!checkInd(p10,petersen), |
|
363 "There should not exist a P10->Petersen spanned mapping."); |
|
364 check(!checkInd(c10,petersen), |
|
365 "There should not exist a C10->Petersen spanned mapping."); |
|
366 check(checkInd(petersen,petersen), |
|
367 "There should exist a Petersen->Petersen spanned mapping."); |
|
368 |
|
369 check(!checkSub(petersen,c10), |
|
370 "There should not exist a Petersen->C10 mapping."); |
|
371 check(checkSub(p10,c10), |
|
372 "There should exist a P10->C10 mapping."); |
|
373 check(!checkInd(p10,c10), |
|
374 "There should not exist a P10->C10 spanned mapping."); |
|
375 check(!checkSub(c10,p10), |
|
376 "There should not exist a C10->P10 mapping."); |
|
377 |
|
378 check(!checkIso(p10,c10), |
|
379 "P10 and C10 are not isomorphic."); |
|
380 check(checkIso(c10,c10), |
|
381 "C10 and C10 are isomorphic."); |
|
382 |
|
383 check(!vf2pp(p10,c10).iso().run(), |
|
384 "P10 and C10 are not isomorphic."); |
|
385 check(vf2pp(c10,c10).iso().run(), |
|
386 "C10 and C10 are isomorphic."); |
|
387 |
|
388 check(!checkSub(c5,petersen,c5_col,petersen_col1), |
|
389 "There should exist a C5->Petersen mapping."); |
|
390 check(checkSub(c5,petersen,c5_col,petersen_col2), |
|
391 "There should exist a C5->Petersen mapping."); |
|
392 } |