COIN-OR::LEMON - Graph Library

source: lemon/test/vf2_test.cc @ 1405:3feba0ea1bda

Last change on this file since 1405:3feba0ea1bda was 1405:3feba0ea1bda, checked in by Peter Madarasi <madarasip@…>, 2 years ago

Vf2 improvements and Vf2pp implementation (#597)

File size: 8.2 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/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
27using namespace lemon;
28
29char 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
60char 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
76char 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
96char 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
122char 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
147SmartGraph petersen, c5, c7, c10, p10;
148SmartGraph::NodeMap<int> petersen_col1(petersen);
149SmartGraph::NodeMap<int> petersen_col2(petersen);
150SmartGraph::NodeMap<int> c5_col(c5);
151
152void 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
184class EqComparable {
185public:
186  bool operator==(const EqComparable&) {
187    return false;
188  }
189};
190
191template<class A, class B>
192class EqClass {
193public:
194  bool operator()(A, B){
195    return false;
196  }
197};
198
199template<class G1,class G2>
200void checkVf2Compile() {
201  G1 g;
202  G2 h;
203  concepts::ReadWriteMap<typename G1::Node, typename G2::Node> r;
204  bool succ;
205  ::lemon::ignore_unused_variable_warning(succ);
206
207  succ = vf2(g,h).run();
208  succ = vf2(g,h).induced().run();
209  succ = vf2(g,h).iso().run();
210  succ = vf2(g,h).mapping(r).run();
211
212  Vf2<G1,G2,concepts::ReadWriteMap<typename G1::Node, typename G2::Node>,
213      EqClass<typename G1::Node,typename G2::Node> >
214    myVf2(g,h,r,EqClass<typename G1::Node,typename G2::Node>());
215  myVf2.find();
216
217  succ = vf2(g,h).induced().mapping(r).run();
218  succ = vf2(g,h).iso().mapping(r).run();
219
220  concepts::ReadMap<typename G1::Node, EqComparable> l1;
221  concepts::ReadMap<typename G2::Node, EqComparable> l2;
222  succ = vf2(g,h).nodeLabels(l1,l2).mapping(r).run();
223  succ = vf2(g,h).nodeEq(EqClass<typename G1::Node,typename G2::Node>())
224    .mapping(r).run();
225}
226
227void justCompile() {
228  checkVf2Compile<concepts::Graph,concepts::Graph>();
229  checkVf2Compile<concepts::Graph,SmartGraph>();
230  checkVf2Compile<SmartGraph,concepts::Graph>();
231}
232
233template<class G1, class G2, class I>
234void checkSub(const G1 &g1, const G2 &g2, const I &i) {
235  {
236    std::set<typename G2::Node> image;
237    for(typename G1::NodeIt n(g1);n!=INVALID;++n){
238      check(i[n]!=INVALID, "Wrong isomorphism: incomplete mapping.");
239      check(image.count(i[n])==0,"Wrong isomorphism: not injective.");
240      image.insert(i[n]);
241    }
242  }
243  for(typename G1::EdgeIt e(g1);e!=INVALID;++e)
244    check(findEdge(g2,i[g1.u(e)],i[g1.v(e)])!=INVALID,
245          "Wrong isomorphism: missing edge(checkSub).");
246}
247
248template<class G1, class G2, class I>
249void checkInd(const G1 &g1, const G2 &g2, const I &i) {
250  std::set<typename G2::Node> image;
251  for(typename G1::NodeIt n(g1);n!=INVALID;++n) {
252    check(i[n]!=INVALID, "Wrong isomorphism: incomplete mapping.");
253    check(image.count(i[n])==0,"Wrong isomorphism: not injective.");
254    image.insert(i[n]);
255  }
256  for(typename G1::NodeIt n(g1); n!=INVALID; ++n)
257    for(typename G1::NodeIt m(g1); m!=INVALID; ++m)
258      if((findEdge(g1,n,m)==INVALID) != (findEdge(g2,i[n],i[m])==INVALID)) {
259        std::cout << "Wrong isomorphism: edge mismatch";
260        exit(1);
261      }
262}
263
264template<class G1,class G2>
265int checkSub(const G1 &g1, const G2 &g2) {
266  typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
267  if(vf2(g1,g2).mapping(iso).run()) {
268    checkSub(g1,g2,iso);
269    return true;
270  }
271  else
272    return false;
273}
274
275template<class G1,class G2>
276int checkInd(const G1 &g1, const G2 &g2) {
277  typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
278  if(vf2(g1,g2).induced().mapping(iso).run()) {
279    checkInd(g1,g2,iso);
280    return true;
281  }
282  else
283    return false;
284}
285
286template<class G1,class G2>
287int checkIso(const G1 &g1, const G2 &g2) {
288  typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
289  if(vf2(g1,g2).iso().mapping(iso).run()) {
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
296    return false;
297}
298
299template<class G1, class G2, class L1, class L2, class I>
300void checkLabel(const G1 &g1, const G2 &,
301                const L1 &l1, const L2 &l2,const I &i) {
302  for(typename G1::NodeIt n(g1);n!=INVALID;++n)
303    check(l1[n]==l2[i[n]],"Wrong isomorphism: label mismatch.");
304}
305
306template<class G1,class G2,class L1,class L2>
307int checkSub(const G1 &g1, const G2 &g2, const L1 &l1, const L2 &l2) {
308  typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
309  if(vf2(g1,g2).nodeLabels(l1,l2).mapping(iso).run()){
310    checkSub(g1,g2,iso);
311    checkLabel(g1,g2,l1,l2,iso);
312    return true;
313  }
314  else
315    return false;
316}
317
318int main() {
319  make_graphs();
320  //   justCompile();
321  check(checkSub(c5,petersen), "There should exist a C5->Petersen mapping.");
322  check(!checkSub(c7,petersen),
323        "There should not exist a C7->Petersen mapping.");
324  check(checkSub(p10,petersen), "There should exist a P10->Petersen mapping.");
325  check(!checkSub(c10,petersen),
326        "There should not exist a C10->Petersen mapping.");
327  check(checkSub(petersen,petersen),
328        "There should exist a Petersen->Petersen mapping.");
329
330  check(checkInd(c5,petersen),
331        "There should exist a C5->Petersen spanned mapping.");
332  check(!checkInd(c7,petersen),
333        "There should exist a C7->Petersen spanned mapping.");
334  check(!checkInd(p10,petersen),
335        "There should not exist a P10->Petersen spanned mapping.");
336  check(!checkInd(c10,petersen),
337        "There should not exist a C10->Petersen spanned mapping.");
338  check(checkInd(petersen,petersen),
339        "There should exist a Petersen->Petersen spanned mapping.");
340
341  check(!checkSub(petersen,c10),
342        "There should not exist a Petersen->C10 mapping.");
343  check(checkSub(p10,c10),
344        "There should exist a P10->C10 mapping.");
345  check(!checkInd(p10,c10),
346        "There should not exist a P10->C10 spanned mapping.");
347  check(!checkSub(c10,p10),
348        "There should not exist a C10->P10 mapping.");
349
350  check(!checkIso(p10,c10),
351        "P10 and C10 are not isomorphic.");
352  check(checkIso(c10,c10),
353        "C10 and C10 are isomorphic.");
354
355  check(!vf2(p10,c10).iso().run(),
356        "P10 and C10 are not isomorphic.");
357  check(vf2(c10,c10).iso().run(),
358        "C10 and C10 are isomorphic.");
359
360  check(!checkSub(c5,petersen,c5_col,petersen_col1),
361        "There should exist a C5->Petersen mapping.");
362  check(checkSub(c5,petersen,c5_col,petersen_col2),
363        "There should exist a C5->Petersen mapping.");
364}
Note: See TracBrowser for help on using the repository browser.