COIN-OR::LEMON - Graph Library

source: lemon/test/vf2pp_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: 9.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/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
29using namespace lemon;
30
31char 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
62char 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
78char 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
98char 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
124char 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
149SmartGraph petersen, c5, c7, c10, p10;
150SmartGraph::NodeMap<int> petersen_col1(petersen);
151SmartGraph::NodeMap<int> petersen_col2(petersen);
152SmartGraph::NodeMap<int> c5_col(c5);
153
154void 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
186class IntConvertible1{
187public:
188  operator int(){
189    return 0;
190  }
191};
192
193class IntConvertible2{
194public:
195  operator int(){
196    return 0;
197  }
198};
199
200template<class G1,class G2>
201void 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
255void justCompile() {
256  checkVf2Compile<concepts::Graph,concepts::Graph>();
257  checkVf2Compile<concepts::Graph,SmartGraph>();
258  checkVf2Compile<SmartGraph,concepts::Graph>();
259}
260
261template<class G1, class G2, class I>
262void 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
276template<class G1, class G2, class I>
277void 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
292template<class G1,class G2>
293int 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
303template<class G1,class G2>
304int 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
314template<class G1,class G2>
315int 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
327template<class G1, class G2, class L1, class L2, class I>
328void 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
334template<class G1,class G2,class L1,class L2>
335int 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
346int 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}
Note: See TracBrowser for help on using the repository browser.