|
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 |
|
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/vf2.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 |
|
24 #include <test/test_tools.h> |
|
25 #include <sstream> |
|
26 |
|
27 using namespace lemon; |
|
28 |
|
29 char petersen_lgf[] = |
|
30 "@nodes\n" |
|
31 "label col1 col2\n" |
|
32 "0 1 1\n" |
|
33 "1 1 2\n" |
|
34 "2 1 3\n" |
|
35 "3 1 4\n" |
|
36 "4 2 5\n" |
|
37 "5 2 1\n" |
|
38 "6 2 2\n" |
|
39 "7 2 3\n" |
|
40 "8 2 4\n" |
|
41 "9 2 5\n" |
|
42 "@arcs\n" |
|
43 " -\n" |
|
44 "0 1\n" |
|
45 "1 2\n" |
|
46 "2 3\n" |
|
47 "3 4\n" |
|
48 "4 0\n" |
|
49 "0 5\n" |
|
50 "1 6\n" |
|
51 "2 7\n" |
|
52 "3 8\n" |
|
53 "4 9\n" |
|
54 "5 8\n" |
|
55 "5 7\n" |
|
56 "9 6\n" |
|
57 "9 7\n" |
|
58 "6 8\n"; |
|
59 |
|
60 char c5_lgf[] = |
|
61 "@nodes\n" |
|
62 "label col\n" |
|
63 "0 1\n" |
|
64 "1 2\n" |
|
65 "2 3\n" |
|
66 "3 4\n" |
|
67 "4 5\n" |
|
68 "@arcs\n" |
|
69 " -\n" |
|
70 "0 1\n" |
|
71 "1 2\n" |
|
72 "2 3\n" |
|
73 "3 4\n" |
|
74 "4 0\n"; |
|
75 |
|
76 char c7_lgf[] = |
|
77 "@nodes\n" |
|
78 "label\n" |
|
79 "0\n" |
|
80 "1\n" |
|
81 "2\n" |
|
82 "3\n" |
|
83 "4\n" |
|
84 "5\n" |
|
85 "6\n" |
|
86 "@arcs\n" |
|
87 " -\n" |
|
88 "0 1\n" |
|
89 "1 2\n" |
|
90 "2 3\n" |
|
91 "3 4\n" |
|
92 "4 5\n" |
|
93 "5 6\n" |
|
94 "6 0\n"; |
|
95 |
|
96 char c10_lgf[] = |
|
97 "@nodes\n" |
|
98 "label\n" |
|
99 "0\n" |
|
100 "1\n" |
|
101 "2\n" |
|
102 "3\n" |
|
103 "4\n" |
|
104 "5\n" |
|
105 "6\n" |
|
106 "7\n" |
|
107 "8\n" |
|
108 "9\n" |
|
109 "@arcs\n" |
|
110 " -\n" |
|
111 "0 1\n" |
|
112 "1 2\n" |
|
113 "2 3\n" |
|
114 "3 4\n" |
|
115 "4 5\n" |
|
116 "5 6\n" |
|
117 "6 7\n" |
|
118 "7 8\n" |
|
119 "8 9\n" |
|
120 "9 0\n"; |
|
121 |
|
122 char p10_lgf[] = |
|
123 "@nodes\n" |
|
124 "label\n" |
|
125 "0\n" |
|
126 "1\n" |
|
127 "2\n" |
|
128 "3\n" |
|
129 "4\n" |
|
130 "5\n" |
|
131 "6\n" |
|
132 "7\n" |
|
133 "8\n" |
|
134 "9\n" |
|
135 "@arcs\n" |
|
136 " -\n" |
|
137 "0 1\n" |
|
138 "1 2\n" |
|
139 "2 3\n" |
|
140 "3 4\n" |
|
141 "4 5\n" |
|
142 "5 6\n" |
|
143 "6 7\n" |
|
144 "7 8\n" |
|
145 "8 9\n"; |
|
146 |
|
147 SmartGraph petersen, c5, c7, c10, p10; |
|
148 SmartGraph::NodeMap<int> petersen_col1(petersen); |
|
149 SmartGraph::NodeMap<int> petersen_col2(petersen); |
|
150 SmartGraph::NodeMap<int> c5_col(c5); |
|
151 |
|
152 void make_graphs() { |
|
153 std::stringstream ss(petersen_lgf); |
|
154 graphReader(petersen, ss) |
|
155 .nodeMap("col1",petersen_col1) |
|
156 .nodeMap("col2",petersen_col2) |
|
157 .run(); |
|
158 |
|
159 ss.clear(); |
|
160 ss.str(""); |
|
161 ss<<c5_lgf; |
|
162 //std::stringstream ss2(c5_lgf); |
|
163 graphReader(c5, ss) |
|
164 .nodeMap("col",c5_col) |
|
165 .run(); |
|
166 |
|
167 ss.clear(); |
|
168 ss.str(""); |
|
169 ss<<c7_lgf; |
|
170 graphReader(c7, ss).run(); |
|
171 |
|
172 ss.clear(); |
|
173 ss.str(""); |
|
174 ss<<c10_lgf; |
|
175 graphReader(c10, ss).run(); |
|
176 |
|
177 ss.clear(); |
|
178 ss.str(""); |
|
179 ss<<p10_lgf; |
|
180 graphReader(p10, ss).run(); |
|
181 |
|
182 } |
|
183 |
|
184 class EqComparable { |
|
185 public: |
|
186 bool operator==(const EqComparable&) { return false; } |
|
187 }; |
|
188 |
|
189 template<class A, class B> |
|
190 class EqClass { |
|
191 public: |
|
192 bool operator()(A, B) { return false; } |
|
193 }; |
|
194 |
|
195 template<class G1,class G2> |
|
196 void checkVf2Compile() |
|
197 { |
|
198 G1 g; |
|
199 G2 h; |
|
200 concepts::ReadWriteMap<typename G1::Node, typename G2::Node> r; |
|
201 bool succ; |
|
202 ::lemon::ignore_unused_variable_warning(succ); |
|
203 |
|
204 succ = vf2(g,h).run(); |
|
205 succ = vf2(g,h).induced().run(); |
|
206 succ = vf2(g,h).iso().run(); |
|
207 succ = vf2(g,h).mapping(r).run(); |
|
208 succ = vf2(g,h).induced().mapping(r).run(); |
|
209 succ = vf2(g,h).iso().mapping(r).run(); |
|
210 concepts::ReadMap<typename G1::Node, EqComparable> l1; |
|
211 concepts::ReadMap<typename G2::Node, EqComparable> l2; |
|
212 succ = vf2(g,h).nodeLabels(l1,l2).mapping(r).run(); |
|
213 succ = vf2(g,h).nodeEq(EqClass<typename G1::Node,typename G2::Node>()) |
|
214 .mapping(r).run(); |
|
215 } |
|
216 |
|
217 void justCompile() |
|
218 { |
|
219 checkVf2Compile<concepts::Graph,concepts::Graph>(); |
|
220 checkVf2Compile<concepts::Graph,SmartGraph>(); |
|
221 checkVf2Compile<SmartGraph,concepts::Graph>(); |
|
222 } |
|
223 |
|
224 template<class G1, class G2, class I> |
|
225 void checkSub(const G1 &g1, const G2 &g2, const I &i) |
|
226 { |
|
227 { |
|
228 std::set<typename G2::Node> image; |
|
229 for(typename G1::NodeIt n(g1);n!=INVALID;++n) |
|
230 { |
|
231 check(i[n]!=INVALID, "Wrong isomorphism: incomplete mapping."); |
|
232 check(image.count(i[n])==0,"Wrong isomorphism: not injective."); |
|
233 image.insert(i[n]); |
|
234 } |
|
235 } |
|
236 for(typename G1::EdgeIt e(g1);e!=INVALID;++e) |
|
237 check(findEdge(g2,i[g1.u(e)],i[g1.v(e)])!=INVALID, |
|
238 "Wrong isomorphism: missing edge(checkSub)."); |
|
239 } |
|
240 |
|
241 template<class G1, class G2, class I> |
|
242 void checkInd(const G1 &g1, const G2 &g2, const I &i) |
|
243 { |
|
244 std::set<typename G2::Node> image; |
|
245 for(typename G1::NodeIt n(g1);n!=INVALID;++n) |
|
246 { |
|
247 check(i[n]!=INVALID, "Wrong isomorphism: incomplete mapping."); |
|
248 check(image.count(i[n])==0,"Wrong isomorphism: not injective."); |
|
249 image.insert(i[n]); |
|
250 } |
|
251 for(typename G1::NodeIt n(g1); n!=INVALID; ++n) |
|
252 for(typename G1::NodeIt m(g1); m!=INVALID; ++m) |
|
253 if((findEdge(g1,n,m)==INVALID) != (findEdge(g2,i[n],i[m])==INVALID)) |
|
254 { |
|
255 std::cout << "Wrong isomorphism: edge mismatch"; |
|
256 exit(1); |
|
257 } |
|
258 } |
|
259 |
|
260 template<class G1,class G2> |
|
261 int checkSub(const G1 &g1, const G2 &g2) |
|
262 { |
|
263 typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID); |
|
264 if(vf2(g1,g2).mapping(iso).run()) |
|
265 { |
|
266 checkSub(g1,g2,iso); |
|
267 return true; |
|
268 } |
|
269 else return false; |
|
270 } |
|
271 |
|
272 template<class G1,class G2> |
|
273 int checkInd(const G1 &g1, const G2 &g2) |
|
274 { |
|
275 typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID); |
|
276 if(vf2(g1,g2).induced().mapping(iso).run()) |
|
277 { |
|
278 checkInd(g1,g2,iso); |
|
279 return true; |
|
280 } |
|
281 else return false; |
|
282 } |
|
283 |
|
284 template<class G1,class G2> |
|
285 int checkIso(const G1 &g1, const G2 &g2) |
|
286 { |
|
287 typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID); |
|
288 if(vf2(g1,g2).iso().mapping(iso).run()) |
|
289 { |
|
290 check(countNodes(g1)==countNodes(g2), |
|
291 "Wrong iso alg.: they are not isomophic."); |
|
292 checkInd(g1,g2,iso); |
|
293 return true; |
|
294 } |
|
295 else return false; |
|
296 } |
|
297 |
|
298 template<class G1, class G2, class L1, class L2, class I> |
|
299 void checkLabel(const G1 &g1, const G2 &, |
|
300 const L1 &l1, const L2 &l2,const I &i) |
|
301 { |
|
302 for(typename G1::NodeIt n(g1);n!=INVALID;++n) |
|
303 { |
|
304 check(l1[n]==l2[i[n]],"Wrong isomorphism: label mismatch."); |
|
305 } |
|
306 } |
|
307 |
|
308 template<class G1,class G2,class L1,class L2> |
|
309 int checkSub(const G1 &g1, const G2 &g2, const L1 &l1, const L2 &l2) |
|
310 { |
|
311 typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID); |
|
312 if(vf2(g1,g2).nodeLabels(l1,l2).mapping(iso).run()) |
|
313 { |
|
314 checkSub(g1,g2,iso); |
|
315 checkLabel(g1,g2,l1,l2,iso); |
|
316 return true; |
|
317 } |
|
318 else return false; |
|
319 } |
|
320 |
|
321 int main() { |
|
322 make_graphs(); |
|
323 check(checkSub(c5,petersen), "There should exist a C5->Petersen mapping."); |
|
324 check(!checkSub(c7,petersen), |
|
325 "There should not exist a C7->Petersen mapping."); |
|
326 check(checkSub(p10,petersen), "There should exist a P10->Petersen mapping."); |
|
327 check(!checkSub(c10,petersen), |
|
328 "There should not exist a C10->Petersen mapping."); |
|
329 check(checkSub(petersen,petersen), |
|
330 "There should exist a Petersen->Petersen mapping."); |
|
331 |
|
332 check(checkInd(c5,petersen), |
|
333 "There should exist a C5->Petersen spanned mapping."); |
|
334 check(!checkInd(c7,petersen), |
|
335 "There should exist a C7->Petersen spanned mapping."); |
|
336 check(!checkInd(p10,petersen), |
|
337 "There should not exist a P10->Petersen spanned mapping."); |
|
338 check(!checkInd(c10,petersen), |
|
339 "There should not exist a C10->Petersen spanned mapping."); |
|
340 check(checkInd(petersen,petersen), |
|
341 "There should exist a Petersen->Petersen spanned mapping."); |
|
342 |
|
343 check(!checkSub(petersen,c10), |
|
344 "There should not exist a Petersen->C10 mapping."); |
|
345 check(checkSub(p10,c10), |
|
346 "There should exist a P10->C10 mapping."); |
|
347 check(!checkInd(p10,c10), |
|
348 "There should not exist a P10->C10 spanned mapping."); |
|
349 check(!checkSub(c10,p10), |
|
350 "There should not exist a C10->P10 mapping."); |
|
351 |
|
352 check(!checkIso(p10,c10), |
|
353 "P10 and C10 are not isomorphic."); |
|
354 check(checkIso(c10,c10), |
|
355 "C10 and C10 are not isomorphic."); |
|
356 |
|
357 check(!checkSub(c5,petersen,c5_col,petersen_col1), |
|
358 "There should exist a C5->Petersen mapping."); |
|
359 check(checkSub(c5,petersen,c5_col,petersen_col2), |
|
360 "There should exist a C5->Petersen mapping."); |
|
361 } |