COIN-OR::LEMON - Graph Library

source: lemon/test/vf2_test.cc @ 1406:120b9031eada

Last change on this file since 1406:120b9031eada was 1406:120b9031eada, checked in by Peter Kovacs <kpeter@…>, 4 years ago

Merge tests of VF2 and VF2++ (#597)

File size: 11.5 KB
Line 
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/vf2.h>
19#include <lemon/vf2pp.h>
20#include <lemon/concepts/digraph.h>
21#include <lemon/smart_graph.h>
22#include <lemon/lgf_reader.h>
23#include <lemon/concepts/maps.h>
24
25#include <test/test_tools.h>
26#include <sstream>
27
28using namespace lemon;
29
30char petersen_lgf[] =
31  "@nodes\n"
32  "label col1 col2\n"
33  "0 1 1\n"
34  "1 1 2\n"
35  "2 1 3\n"
36  "3 1 4\n"
37  "4 2 5\n"
38  "5 2 1\n"
39  "6 2 2\n"
40  "7 2 3\n"
41  "8 2 4\n"
42  "9 2 5\n"
43  "@arcs\n"
44  "     -\n"
45  "0 1\n"
46  "1 2\n"
47  "2 3\n"
48  "3 4\n"
49  "4 0\n"
50  "0 5\n"
51  "1 6\n"
52  "2 7\n"
53  "3 8\n"
54  "4 9\n"
55  "5 8\n"
56  "5 7\n"
57  "9 6\n"
58  "9 7\n"
59  "6 8\n";
60
61char c5_lgf[] =
62  "@nodes\n"
63  "label col\n"
64  "0 1\n"
65  "1 2\n"
66  "2 3\n"
67  "3 4\n"
68  "4 5\n"
69  "@arcs\n"
70  "     -\n"
71  "0 1\n"
72  "1 2\n"
73  "2 3\n"
74  "3 4\n"
75  "4 0\n";
76
77char c7_lgf[] =
78  "@nodes\n"
79  "label\n"
80  "0\n"
81  "1\n"
82  "2\n"
83  "3\n"
84  "4\n"
85  "5\n"
86  "6\n"
87  "@arcs\n"
88  "     -\n"
89  "0 1\n"
90  "1 2\n"
91  "2 3\n"
92  "3 4\n"
93  "4 5\n"
94  "5 6\n"
95  "6 0\n";
96
97char c10_lgf[] =
98  "@nodes\n"
99  "label\n"
100  "0\n"
101  "1\n"
102  "2\n"
103  "3\n"
104  "4\n"
105  "5\n"
106  "6\n"
107  "7\n"
108  "8\n"
109  "9\n"
110  "@arcs\n"
111  "     -\n"
112  "0 1\n"
113  "1 2\n"
114  "2 3\n"
115  "3 4\n"
116  "4 5\n"
117  "5 6\n"
118  "6 7\n"
119  "7 8\n"
120  "8 9\n"
121  "9 0\n";
122
123char p10_lgf[] =
124  "@nodes\n"
125  "label\n"
126  "0\n"
127  "1\n"
128  "2\n"
129  "3\n"
130  "4\n"
131  "5\n"
132  "6\n"
133  "7\n"
134  "8\n"
135  "9\n"
136  "@arcs\n"
137  "     -\n"
138  "0 1\n"
139  "1 2\n"
140  "2 3\n"
141  "3 4\n"
142  "4 5\n"
143  "5 6\n"
144  "6 7\n"
145  "7 8\n"
146  "8 9\n";
147
148SmartGraph petersen, c5, c7, c10, p10;
149SmartGraph::NodeMap<int> petersen_col1(petersen);
150SmartGraph::NodeMap<int> petersen_col2(petersen);
151SmartGraph::NodeMap<int> c5_col(c5);
152
153void make_graphs() {
154  std::stringstream ss(petersen_lgf);
155  graphReader(petersen, ss)
156    .nodeMap("col1", petersen_col1)
157    .nodeMap("col2", petersen_col2)
158    .run();
159
160  ss.clear();
161  ss.str("");
162  ss << c5_lgf;
163  //std::stringstream ss2(c5_lgf);
164  graphReader(c5, ss)
165    .nodeMap("col", c5_col)
166    .run();
167
168  ss.clear();
169  ss.str("");
170  ss << c7_lgf;
171  graphReader(c7, ss).run();
172
173  ss.clear();
174  ss.str("");
175  ss << c10_lgf;
176  graphReader(c10, ss).run();
177
178  ss.clear();
179  ss.str("");
180  ss << p10_lgf;
181  graphReader(p10, ss).run();
182
183}
184
185class EqComparable {
186public:
187  bool operator==(const EqComparable&) {
188    return false;
189  }
190};
191
192template<class A, class B>
193class EqClass {
194public:
195  bool operator()(A, B){
196    return false;
197  }
198};
199
200class IntConvertible1 {
201public:
202  operator int() {
203    return 0;
204  }
205};
206
207class IntConvertible2 {
208public:
209  operator int() {
210    return 0;
211  }
212};
213
214template<class G1,class G2>
215void checkVf2Compile() {
216  G1 g;
217  G2 h;
218  concepts::ReadWriteMap<typename G1::Node, typename G2::Node> r;
219  bool succ;
220  ::lemon::ignore_unused_variable_warning(succ);
221
222  succ = vf2(g,h).run();
223  succ = vf2(g,h).induced().run();
224  succ = vf2(g,h).iso().run();
225  succ = vf2(g,h).mapping(r).run();
226
227  Vf2<G1,G2,concepts::ReadWriteMap<typename G1::Node, typename G2::Node>,
228      EqClass<typename G1::Node,typename G2::Node> >
229    myVf2(g,h,r,EqClass<typename G1::Node,typename G2::Node>());
230  myVf2.find();
231
232  succ = vf2(g,h).induced().mapping(r).run();
233  succ = vf2(g,h).iso().mapping(r).run();
234
235  concepts::ReadMap<typename G1::Node, EqComparable> l1;
236  concepts::ReadMap<typename G2::Node, EqComparable> l2;
237  succ = vf2(g,h).nodeLabels(l1,l2).mapping(r).run();
238  succ = vf2(g,h).nodeEq(EqClass<typename G1::Node,typename G2::Node>())
239    .mapping(r).run();
240}
241
242void vf2Compile() {
243  checkVf2Compile<concepts::Graph,concepts::Graph>();
244  checkVf2Compile<concepts::Graph,SmartGraph>();
245  checkVf2Compile<SmartGraph,concepts::Graph>();
246}
247
248template<class G1,class G2>
249void checkVf2ppCompile() {
250  G1 g;
251  G2 h;
252  concepts::ReadWriteMap<typename G1::Node, typename G2::Node> r;
253  bool succ;
254  ::lemon::ignore_unused_variable_warning(succ);
255
256  succ = vf2pp(g,h).run();
257  succ = vf2pp(g,h).induced().run();
258  succ = vf2pp(g,h).iso().run();
259  succ = vf2pp(g,h).mapping(r).run();
260  succ = vf2pp(g,h).induced().mapping(r).run();
261  succ = vf2pp(g,h).iso().mapping(r).run();
262
263  concepts::ReadMap<typename G1::Node, int> c1;
264  concepts::ReadMap<typename G2::Node, int> c2;
265  Vf2pp<G1,G2,concepts::ReadWriteMap<typename G1::Node, typename G2::Node>,
266        concepts::ReadMap<typename G1::Node, int>,
267        concepts::ReadMap<typename G2::Node, int> >
268    myVf2pp(g,h,r,c1,c2);
269  myVf2pp.find();
270
271  succ = vf2pp(g,h).nodeLabels(c1,c2).mapping(r).run();
272  succ = vf2pp(g,h).nodeLabels(c1,c2).mapping(r).run();
273
274  concepts::ReadMap<typename G1::Node, char> c1_c;
275  concepts::ReadMap<typename G2::Node, char> c2_c;
276  Vf2pp<G1,G2,concepts::ReadWriteMap<typename G1::Node, typename G2::Node>,
277        concepts::ReadMap<typename G1::Node, char>,
278        concepts::ReadMap<typename G2::Node, char> >
279    myVf2pp_c(g,h,r,c1_c,c2_c);
280  myVf2pp_c.find();
281
282  succ = vf2pp(g,h).nodeLabels(c1_c,c2_c).mapping(r).run();
283  succ = vf2pp(g,h).nodeLabels(c1_c,c2_c).mapping(r).run();
284
285  concepts::ReadMap<typename G1::Node, IntConvertible1> c1_IntConv;
286  concepts::ReadMap<typename G2::Node, IntConvertible2> c2_IntConv;
287  Vf2pp<G1,G2,concepts::ReadWriteMap<typename G1::Node, typename G2::Node>,
288        concepts::ReadMap<typename G1::Node, IntConvertible1>,
289        concepts::ReadMap<typename G2::Node, IntConvertible2> >
290    myVf2pp_IntConv(g,h,r,c1_IntConv,c2_IntConv);
291  myVf2pp_IntConv.find();
292
293  succ = vf2pp(g,h).nodeLabels(c1_IntConv,c2_IntConv).mapping(r).run();
294  succ = vf2pp(g,h).nodeLabels(c1_IntConv,c2_IntConv).mapping(r).run();
295}
296
297void vf2ppCompile() {
298  checkVf2ppCompile<concepts::Graph,concepts::Graph>();
299  checkVf2ppCompile<concepts::Graph,SmartGraph>();
300  checkVf2ppCompile<SmartGraph,concepts::Graph>();
301}
302
303template<class G1, class G2, class I>
304void checkSubIso(const G1 &g1, const G2 &g2, const I &i) {
305  std::set<typename G2::Node> image;
306  for (typename G1::NodeIt n(g1);n!=INVALID;++n){
307    check(i[n]!=INVALID, "Wrong isomorphism: incomplete mapping.");
308    check(image.count(i[n])==0,"Wrong isomorphism: not injective.");
309    image.insert(i[n]);
310  }
311  for (typename G1::EdgeIt e(g1);e!=INVALID;++e) {
312    check(findEdge(g2,i[g1.u(e)],i[g1.v(e)])!=INVALID,
313          "Wrong isomorphism: missing edge(checkSub).");
314  }
315}
316
317template<class G1, class G2, class I>
318void checkIndIso(const G1 &g1, const G2 &g2, const I &i) {
319  std::set<typename G2::Node> image;
320  for (typename G1::NodeIt n(g1);n!=INVALID;++n) {
321    check(i[n]!=INVALID, "Wrong isomorphism: incomplete mapping.");
322    check(image.count(i[n])==0,"Wrong isomorphism: not injective.");
323    image.insert(i[n]);
324  }
325  for (typename G1::NodeIt n(g1); n!=INVALID; ++n) {
326    for (typename G1::NodeIt m(g1); m!=INVALID; ++m) {
327      if((findEdge(g1,n,m)==INVALID) != (findEdge(g2,i[n],i[m])==INVALID)) {
328        std::cout << "Wrong isomorphism: edge mismatch";
329        exit(1);
330      }
331    }
332  }
333}
334
335template<class G1,class G2,class T>
336bool checkSub(const G1 &g1, const G2 &g2, const T &vf2) {
337  typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
338  if (const_cast<T&>(vf2).mapping(iso).run()) {
339    checkSubIso(g1,g2,iso);
340    return true;
341  }
342  return false;
343}
344
345template<class G1,class G2,class T>
346bool checkInd(const G1 &g1, const G2 &g2, const T &vf2) {
347  typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
348  if (const_cast<T&>(vf2).induced().mapping(iso).run()) {
349    checkIndIso(g1,g2,iso);
350    return true;
351  }
352  return false;
353}
354
355template<class G1,class G2,class T>
356bool checkIso(const G1 &g1, const G2 &g2, const T &vf2) {
357  typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
358  if (const_cast<T&>(vf2).iso().mapping(iso).run()) {
359    check(countNodes(g1)==countNodes(g2),
360          "Wrong iso alg.: they are not isomophic.");
361    checkIndIso(g1,g2,iso);
362    return true;
363  }
364  return false;
365}
366
367template<class G1, class G2, class L1, class L2, class I>
368void checkLabel(const G1 &g1, const G2 &,
369                const L1 &l1, const L2 &l2, const I &i) {
370  for (typename G1::NodeIt n(g1);n!=INVALID;++n) {
371    check(l1[n]==l2[i[n]],"Wrong isomorphism: label mismatch.");
372  }
373}
374
375template<class G1,class G2,class L1,class L2,class T>
376bool checkSub(const G1 &g1, const G2 &g2, const L1 &l1, const L2 &l2, const T &vf2) {
377  typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
378  if (const_cast<T&>(vf2).nodeLabels(l1,l2).mapping(iso).run()){
379    checkSubIso(g1,g2,iso);
380    checkLabel(g1,g2,l1,l2,iso);
381    return true;
382  }
383  return false;
384}
385
386template<class G1,class G2>
387void checkSub(const G1 &g1, const G2 &g2, bool expected, const char* msg) {
388  check(checkSub(g1,g2,vf2(g1,g2)) == expected, msg);
389  check(checkSub(g1,g2,vf2pp(g1,g2)) == expected, msg);
390}
391
392template<class G1,class G2>
393void checkInd(const G1 &g1, const G2 &g2, bool expected, const char* msg) {
394  check(checkInd(g1,g2,vf2(g1,g2)) == expected, msg);
395  check(checkInd(g1,g2,vf2pp(g1,g2)) == expected, msg);
396}
397
398template<class G1,class G2>
399void checkIso(const G1 &g1, const G2 &g2, bool expected, const char* msg) {
400  check(checkIso(g1,g2,vf2(g1,g2)) == expected, msg);
401  check(checkIso(g1,g2,vf2pp(g1,g2)) == expected, msg);
402}
403
404template<class G1,class G2,class L1,class L2>
405void checkSub(const G1 &g1, const G2 &g2, const L1 &l1, const L2 &l2, bool expected, const char* msg) {
406  check(checkSub(g1,g2,l1,l2,vf2(g1,g2)) == expected, msg);
407  check(checkSub(g1,g2,l1,l2,vf2pp(g1,g2)) == expected, msg);
408}
409
410int main() {
411  make_graphs();
412
413  checkSub(c5,petersen,true,
414      "There should exist a C5->Petersen mapping.");
415  checkSub(c7,petersen,false,
416      "There should not exist a C7->Petersen mapping.");
417  checkSub(p10,petersen,true,
418      "There should exist a P10->Petersen mapping.");
419  checkSub(c10,petersen,false,
420      "There should not exist a C10->Petersen mapping.");
421  checkSub(petersen,petersen,true,
422      "There should exist a Petersen->Petersen mapping.");
423
424  checkInd(c5,petersen,true,
425      "There should exist a C5->Petersen spanned mapping.");
426  checkInd(c7,petersen,false,
427      "There should exist a C7->Petersen spanned mapping.");
428  checkInd(p10,petersen,false,
429      "There should not exist a P10->Petersen spanned mapping.");
430  checkInd(c10,petersen,false,
431      "There should not exist a C10->Petersen spanned mapping.");
432  checkInd(petersen,petersen,true,
433        "There should exist a Petersen->Petersen spanned mapping.");
434
435  checkSub(petersen,c10,false,
436      "There should not exist a Petersen->C10 mapping.");
437  checkSub(p10,c10,true,
438      "There should exist a P10->C10 mapping.");
439  checkInd(p10,c10,false,
440      "There should not exist a P10->C10 spanned mapping.");
441  checkSub(c10,p10,false,
442      "There should not exist a C10->P10 mapping.");
443
444  checkIso(p10,c10,false,
445      "P10 and C10 are not isomorphic.");
446  checkIso(c10,c10,true,
447      "C10 and C10 are isomorphic.");
448
449  checkSub(c5,petersen,c5_col,petersen_col1,false,
450      "There should exist a C5->Petersen mapping.");
451  checkSub(c5,petersen,c5_col,petersen_col2,true,
452      "There should exist a C5->Petersen mapping.");
453
454  check(!vf2(p10,c10).iso().run(), "P10 and C10 are not isomorphic.");
455  check(!vf2pp(p10,c10).iso().run(), "P10 and C10 are not isomorphic.");
456
457  check(vf2(c10,c10).iso().run(), "C10 and C10 are isomorphic.");
458  check(vf2pp(c10,c10).iso().run(), "C10 and C10 are isomorphic.");
459}
Note: See TracBrowser for help on using the repository browser.