COIN-OR::LEMON - Graph Library

source: lemon-main/test/vf2_test.cc @ 1141:a037254714b3

Last change on this file since 1141:a037254714b3 was 1141:a037254714b3, checked in by Peter Madarasi <madarasip@…>, 9 years ago

VF2 algorithm added (#597)

The implementation of this feature was sponsored by QuantumBio? Inc.

File size: 7.9 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
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&) { return false; }
187};
188
189template<class A, class B>
190class EqClass {
191public:
192  bool operator()(A, B) { return false; }
193};
194
195template<class G1,class G2>
196void 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
217void justCompile()
218{
219  checkVf2Compile<concepts::Graph,concepts::Graph>();
220  checkVf2Compile<concepts::Graph,SmartGraph>();
221  checkVf2Compile<SmartGraph,concepts::Graph>();
222}
223
224template<class G1, class G2, class I>
225void 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
241template<class G1, class G2, class I>
242void 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
260template<class G1,class G2>
261int 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
272template<class G1,class G2>
273int 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
284template<class G1,class G2>
285int 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
298template<class G1, class G2, class L1, class L2, class I>
299void 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
308template<class G1,class G2,class L1,class L2>
309int 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
321int 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}
Note: See TracBrowser for help on using the repository browser.