1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
3 * This file is a part of LEMON, a generic C++ optimization library.
5 * Copyright (C) 2015-2017
6 * EMAXA Kutato-fejleszto Kft. (EMAXA Research Ltd.)
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.
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
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>
24 #include <test/test_tools.h>
27 using namespace lemon;
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);
153 std::stringstream ss(petersen_lgf);
154 graphReader(petersen, ss)
155 .nodeMap("col1",petersen_col1)
156 .nodeMap("col2",petersen_col2)
162 //std::stringstream ss2(c5_lgf);
164 .nodeMap("col",c5_col)
170 graphReader(c7, ss).run();
175 graphReader(c10, ss).run();
180 graphReader(p10, ss).run();
186 bool operator==(const EqComparable&) {
191 template<class A, class B>
194 bool operator()(A, B){
199 template<class G1,class G2>
200 void checkVf2Compile() {
203 concepts::ReadWriteMap<typename G1::Node, typename G2::Node> r;
205 ::lemon::ignore_unused_variable_warning(succ);
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();
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>());
217 succ = vf2(g,h).induced().mapping(r).run();
218 succ = vf2(g,h).iso().mapping(r).run();
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>())
228 checkVf2Compile<concepts::Graph,concepts::Graph>();
229 checkVf2Compile<concepts::Graph,SmartGraph>();
230 checkVf2Compile<SmartGraph,concepts::Graph>();
233 template<class G1, class G2, class I>
234 void checkSub(const G1 &g1, const G2 &g2, const I &i) {
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.");
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).");
248 template<class G1, class G2, class I>
249 void 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.");
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";
264 template<class G1,class G2>
265 int 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()) {
275 template<class G1,class G2>
276 int 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()) {
286 template<class G1,class G2>
287 int 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.");
299 template<class G1, class G2, class L1, class L2, class I>
300 void 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.");
306 template<class G1,class G2,class L1,class L2>
307 int 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()){
311 checkLabel(g1,g2,l1,l2,iso);
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.");
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.");
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.");
350 check(!checkIso(p10,c10),
351 "P10 and C10 are not isomorphic.");
352 check(checkIso(c10,c10),
353 "C10 and C10 are isomorphic.");
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.");
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.");