1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/test/vf2_test.cc Mon Mar 30 17:42:30 2015 +0200
1.3 @@ -0,0 +1,361 @@
1.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library.
1.7 + *
1.8 + * Copyright (C) 2015
1.9 + * EMAXA Kutato-fejleszto Kft. (EMAXA Research Ltd.)
1.10 + *
1.11 + * Permission to use, modify and distribute this software is granted
1.12 + * provided that this copyright notice appears in all copies. For
1.13 + * precise terms see the accompanying LICENSE file.
1.14 + *
1.15 + * This software is provided "AS IS" with no warranty of any kind,
1.16 + * express or implied, and with no claim as to its suitability for any
1.17 + * purpose.
1.18 + *
1.19 + */
1.20 +
1.21 +#include <lemon/vf2.h>
1.22 +#include <lemon/concepts/digraph.h>
1.23 +#include <lemon/smart_graph.h>
1.24 +#include <lemon/lgf_reader.h>
1.25 +#include <lemon/concepts/maps.h>
1.26 +
1.27 +#include <test/test_tools.h>
1.28 +#include <sstream>
1.29 +
1.30 +using namespace lemon;
1.31 +
1.32 +char petersen_lgf[] =
1.33 + "@nodes\n"
1.34 + "label col1 col2\n"
1.35 + "0 1 1\n"
1.36 + "1 1 2\n"
1.37 + "2 1 3\n"
1.38 + "3 1 4\n"
1.39 + "4 2 5\n"
1.40 + "5 2 1\n"
1.41 + "6 2 2\n"
1.42 + "7 2 3\n"
1.43 + "8 2 4\n"
1.44 + "9 2 5\n"
1.45 + "@arcs\n"
1.46 + " -\n"
1.47 + "0 1\n"
1.48 + "1 2\n"
1.49 + "2 3\n"
1.50 + "3 4\n"
1.51 + "4 0\n"
1.52 + "0 5\n"
1.53 + "1 6\n"
1.54 + "2 7\n"
1.55 + "3 8\n"
1.56 + "4 9\n"
1.57 + "5 8\n"
1.58 + "5 7\n"
1.59 + "9 6\n"
1.60 + "9 7\n"
1.61 + "6 8\n";
1.62 +
1.63 +char c5_lgf[] =
1.64 + "@nodes\n"
1.65 + "label col\n"
1.66 + "0 1\n"
1.67 + "1 2\n"
1.68 + "2 3\n"
1.69 + "3 4\n"
1.70 + "4 5\n"
1.71 + "@arcs\n"
1.72 + " -\n"
1.73 + "0 1\n"
1.74 + "1 2\n"
1.75 + "2 3\n"
1.76 + "3 4\n"
1.77 + "4 0\n";
1.78 +
1.79 +char c7_lgf[] =
1.80 + "@nodes\n"
1.81 + "label\n"
1.82 + "0\n"
1.83 + "1\n"
1.84 + "2\n"
1.85 + "3\n"
1.86 + "4\n"
1.87 + "5\n"
1.88 + "6\n"
1.89 + "@arcs\n"
1.90 + " -\n"
1.91 + "0 1\n"
1.92 + "1 2\n"
1.93 + "2 3\n"
1.94 + "3 4\n"
1.95 + "4 5\n"
1.96 + "5 6\n"
1.97 + "6 0\n";
1.98 +
1.99 +char c10_lgf[] =
1.100 + "@nodes\n"
1.101 + "label\n"
1.102 + "0\n"
1.103 + "1\n"
1.104 + "2\n"
1.105 + "3\n"
1.106 + "4\n"
1.107 + "5\n"
1.108 + "6\n"
1.109 + "7\n"
1.110 + "8\n"
1.111 + "9\n"
1.112 + "@arcs\n"
1.113 + " -\n"
1.114 + "0 1\n"
1.115 + "1 2\n"
1.116 + "2 3\n"
1.117 + "3 4\n"
1.118 + "4 5\n"
1.119 + "5 6\n"
1.120 + "6 7\n"
1.121 + "7 8\n"
1.122 + "8 9\n"
1.123 + "9 0\n";
1.124 +
1.125 +char p10_lgf[] =
1.126 + "@nodes\n"
1.127 + "label\n"
1.128 + "0\n"
1.129 + "1\n"
1.130 + "2\n"
1.131 + "3\n"
1.132 + "4\n"
1.133 + "5\n"
1.134 + "6\n"
1.135 + "7\n"
1.136 + "8\n"
1.137 + "9\n"
1.138 + "@arcs\n"
1.139 + " -\n"
1.140 + "0 1\n"
1.141 + "1 2\n"
1.142 + "2 3\n"
1.143 + "3 4\n"
1.144 + "4 5\n"
1.145 + "5 6\n"
1.146 + "6 7\n"
1.147 + "7 8\n"
1.148 + "8 9\n";
1.149 +
1.150 +SmartGraph petersen, c5, c7, c10, p10;
1.151 +SmartGraph::NodeMap<int> petersen_col1(petersen);
1.152 +SmartGraph::NodeMap<int> petersen_col2(petersen);
1.153 +SmartGraph::NodeMap<int> c5_col(c5);
1.154 +
1.155 +void make_graphs() {
1.156 + std::stringstream ss(petersen_lgf);
1.157 + graphReader(petersen, ss)
1.158 + .nodeMap("col1",petersen_col1)
1.159 + .nodeMap("col2",petersen_col2)
1.160 + .run();
1.161 +
1.162 + ss.clear();
1.163 + ss.str("");
1.164 + ss<<c5_lgf;
1.165 + //std::stringstream ss2(c5_lgf);
1.166 + graphReader(c5, ss)
1.167 + .nodeMap("col",c5_col)
1.168 + .run();
1.169 +
1.170 + ss.clear();
1.171 + ss.str("");
1.172 + ss<<c7_lgf;
1.173 + graphReader(c7, ss).run();
1.174 +
1.175 + ss.clear();
1.176 + ss.str("");
1.177 + ss<<c10_lgf;
1.178 + graphReader(c10, ss).run();
1.179 +
1.180 + ss.clear();
1.181 + ss.str("");
1.182 + ss<<p10_lgf;
1.183 + graphReader(p10, ss).run();
1.184 +
1.185 +}
1.186 +
1.187 +class EqComparable {
1.188 +public:
1.189 + bool operator==(const EqComparable&) { return false; }
1.190 +};
1.191 +
1.192 +template<class A, class B>
1.193 +class EqClass {
1.194 +public:
1.195 + bool operator()(A, B) { return false; }
1.196 +};
1.197 +
1.198 +template<class G1,class G2>
1.199 +void checkVf2Compile()
1.200 +{
1.201 + G1 g;
1.202 + G2 h;
1.203 + concepts::ReadWriteMap<typename G1::Node, typename G2::Node> r;
1.204 + bool succ;
1.205 + ::lemon::ignore_unused_variable_warning(succ);
1.206 +
1.207 + succ = vf2(g,h).run();
1.208 + succ = vf2(g,h).induced().run();
1.209 + succ = vf2(g,h).iso().run();
1.210 + succ = vf2(g,h).mapping(r).run();
1.211 + succ = vf2(g,h).induced().mapping(r).run();
1.212 + succ = vf2(g,h).iso().mapping(r).run();
1.213 + concepts::ReadMap<typename G1::Node, EqComparable> l1;
1.214 + concepts::ReadMap<typename G2::Node, EqComparable> l2;
1.215 + succ = vf2(g,h).nodeLabels(l1,l2).mapping(r).run();
1.216 + succ = vf2(g,h).nodeEq(EqClass<typename G1::Node,typename G2::Node>())
1.217 + .mapping(r).run();
1.218 +}
1.219 +
1.220 +void justCompile()
1.221 +{
1.222 + checkVf2Compile<concepts::Graph,concepts::Graph>();
1.223 + checkVf2Compile<concepts::Graph,SmartGraph>();
1.224 + checkVf2Compile<SmartGraph,concepts::Graph>();
1.225 +}
1.226 +
1.227 +template<class G1, class G2, class I>
1.228 +void checkSub(const G1 &g1, const G2 &g2, const I &i)
1.229 +{
1.230 + {
1.231 + std::set<typename G2::Node> image;
1.232 + for(typename G1::NodeIt n(g1);n!=INVALID;++n)
1.233 + {
1.234 + check(i[n]!=INVALID, "Wrong isomorphism: incomplete mapping.");
1.235 + check(image.count(i[n])==0,"Wrong isomorphism: not injective.");
1.236 + image.insert(i[n]);
1.237 + }
1.238 + }
1.239 + for(typename G1::EdgeIt e(g1);e!=INVALID;++e)
1.240 + check(findEdge(g2,i[g1.u(e)],i[g1.v(e)])!=INVALID,
1.241 + "Wrong isomorphism: missing edge(checkSub).");
1.242 +}
1.243 +
1.244 +template<class G1, class G2, class I>
1.245 +void checkInd(const G1 &g1, const G2 &g2, const I &i)
1.246 + {
1.247 + std::set<typename G2::Node> image;
1.248 + for(typename G1::NodeIt n(g1);n!=INVALID;++n)
1.249 + {
1.250 + check(i[n]!=INVALID, "Wrong isomorphism: incomplete mapping.");
1.251 + check(image.count(i[n])==0,"Wrong isomorphism: not injective.");
1.252 + image.insert(i[n]);
1.253 + }
1.254 + for(typename G1::NodeIt n(g1); n!=INVALID; ++n)
1.255 + for(typename G1::NodeIt m(g1); m!=INVALID; ++m)
1.256 + if((findEdge(g1,n,m)==INVALID) != (findEdge(g2,i[n],i[m])==INVALID))
1.257 + {
1.258 + std::cout << "Wrong isomorphism: edge mismatch";
1.259 + exit(1);
1.260 + }
1.261 + }
1.262 +
1.263 +template<class G1,class G2>
1.264 +int checkSub(const G1 &g1, const G2 &g2)
1.265 +{
1.266 + typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
1.267 + if(vf2(g1,g2).mapping(iso).run())
1.268 + {
1.269 + checkSub(g1,g2,iso);
1.270 + return true;
1.271 + }
1.272 + else return false;
1.273 +}
1.274 +
1.275 +template<class G1,class G2>
1.276 +int checkInd(const G1 &g1, const G2 &g2)
1.277 +{
1.278 + typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
1.279 + if(vf2(g1,g2).induced().mapping(iso).run())
1.280 + {
1.281 + checkInd(g1,g2,iso);
1.282 + return true;
1.283 + }
1.284 + else return false;
1.285 +}
1.286 +
1.287 +template<class G1,class G2>
1.288 +int checkIso(const G1 &g1, const G2 &g2)
1.289 +{
1.290 + typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
1.291 + if(vf2(g1,g2).iso().mapping(iso).run())
1.292 + {
1.293 + check(countNodes(g1)==countNodes(g2),
1.294 + "Wrong iso alg.: they are not isomophic.");
1.295 + checkInd(g1,g2,iso);
1.296 + return true;
1.297 + }
1.298 + else return false;
1.299 +}
1.300 +
1.301 +template<class G1, class G2, class L1, class L2, class I>
1.302 +void checkLabel(const G1 &g1, const G2 &,
1.303 + const L1 &l1, const L2 &l2,const I &i)
1.304 +{
1.305 + for(typename G1::NodeIt n(g1);n!=INVALID;++n)
1.306 + {
1.307 + check(l1[n]==l2[i[n]],"Wrong isomorphism: label mismatch.");
1.308 + }
1.309 +}
1.310 +
1.311 +template<class G1,class G2,class L1,class L2>
1.312 +int checkSub(const G1 &g1, const G2 &g2, const L1 &l1, const L2 &l2)
1.313 +{
1.314 + typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
1.315 + if(vf2(g1,g2).nodeLabels(l1,l2).mapping(iso).run())
1.316 + {
1.317 + checkSub(g1,g2,iso);
1.318 + checkLabel(g1,g2,l1,l2,iso);
1.319 + return true;
1.320 + }
1.321 + else return false;
1.322 +}
1.323 +
1.324 +int main() {
1.325 + make_graphs();
1.326 + check(checkSub(c5,petersen), "There should exist a C5->Petersen mapping.");
1.327 + check(!checkSub(c7,petersen),
1.328 + "There should not exist a C7->Petersen mapping.");
1.329 + check(checkSub(p10,petersen), "There should exist a P10->Petersen mapping.");
1.330 + check(!checkSub(c10,petersen),
1.331 + "There should not exist a C10->Petersen mapping.");
1.332 + check(checkSub(petersen,petersen),
1.333 + "There should exist a Petersen->Petersen mapping.");
1.334 +
1.335 + check(checkInd(c5,petersen),
1.336 + "There should exist a C5->Petersen spanned mapping.");
1.337 + check(!checkInd(c7,petersen),
1.338 + "There should exist a C7->Petersen spanned mapping.");
1.339 + check(!checkInd(p10,petersen),
1.340 + "There should not exist a P10->Petersen spanned mapping.");
1.341 + check(!checkInd(c10,petersen),
1.342 + "There should not exist a C10->Petersen spanned mapping.");
1.343 + check(checkInd(petersen,petersen),
1.344 + "There should exist a Petersen->Petersen spanned mapping.");
1.345 +
1.346 + check(!checkSub(petersen,c10),
1.347 + "There should not exist a Petersen->C10 mapping.");
1.348 + check(checkSub(p10,c10),
1.349 + "There should exist a P10->C10 mapping.");
1.350 + check(!checkInd(p10,c10),
1.351 + "There should not exist a P10->C10 spanned mapping.");
1.352 + check(!checkSub(c10,p10),
1.353 + "There should not exist a C10->P10 mapping.");
1.354 +
1.355 + check(!checkIso(p10,c10),
1.356 + "P10 and C10 are not isomorphic.");
1.357 + check(checkIso(c10,c10),
1.358 + "C10 and C10 are not isomorphic.");
1.359 +
1.360 + check(!checkSub(c5,petersen,c5_col,petersen_col1),
1.361 + "There should exist a C5->Petersen mapping.");
1.362 + check(checkSub(c5,petersen,c5_col,petersen_col2),
1.363 + "There should exist a C5->Petersen mapping.");
1.364 +}