1.1 --- a/test/vf2pp_test.cc Tue Sep 19 14:08:20 2017 +0200
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,392 +0,0 @@
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-2017
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/vf2pp.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 -#include <lemon/maps.h>
1.27 -#include <lemon/list_graph.h>
1.28 -
1.29 -#include <test/test_tools.h>
1.30 -#include <sstream>
1.31 -
1.32 -using namespace lemon;
1.33 -
1.34 -char petersen_lgf[] =
1.35 - "@nodes\n"
1.36 - "label col1 col2\n"
1.37 - "0 1 1\n"
1.38 - "1 1 2\n"
1.39 - "2 1 3\n"
1.40 - "3 1 4\n"
1.41 - "4 2 5\n"
1.42 - "5 2 1\n"
1.43 - "6 2 2\n"
1.44 - "7 2 3\n"
1.45 - "8 2 4\n"
1.46 - "9 2 5\n"
1.47 - "@arcs\n"
1.48 - " -\n"
1.49 - "0 1\n"
1.50 - "1 2\n"
1.51 - "2 3\n"
1.52 - "3 4\n"
1.53 - "4 0\n"
1.54 - "0 5\n"
1.55 - "1 6\n"
1.56 - "2 7\n"
1.57 - "3 8\n"
1.58 - "4 9\n"
1.59 - "5 8\n"
1.60 - "5 7\n"
1.61 - "9 6\n"
1.62 - "9 7\n"
1.63 - "6 8\n";
1.64 -
1.65 -char c5_lgf[] =
1.66 - "@nodes\n"
1.67 - "label col\n"
1.68 - "0 1\n"
1.69 - "1 2\n"
1.70 - "2 3\n"
1.71 - "3 4\n"
1.72 - "4 5\n"
1.73 - "@arcs\n"
1.74 - " -\n"
1.75 - "0 1\n"
1.76 - "1 2\n"
1.77 - "2 3\n"
1.78 - "3 4\n"
1.79 - "4 0\n";
1.80 -
1.81 -char c7_lgf[] =
1.82 - "@nodes\n"
1.83 - "label\n"
1.84 - "0\n"
1.85 - "1\n"
1.86 - "2\n"
1.87 - "3\n"
1.88 - "4\n"
1.89 - "5\n"
1.90 - "6\n"
1.91 - "@arcs\n"
1.92 - " -\n"
1.93 - "0 1\n"
1.94 - "1 2\n"
1.95 - "2 3\n"
1.96 - "3 4\n"
1.97 - "4 5\n"
1.98 - "5 6\n"
1.99 - "6 0\n";
1.100 -
1.101 -char c10_lgf[] =
1.102 - "@nodes\n"
1.103 - "label\n"
1.104 - "0\n"
1.105 - "1\n"
1.106 - "2\n"
1.107 - "3\n"
1.108 - "4\n"
1.109 - "5\n"
1.110 - "6\n"
1.111 - "7\n"
1.112 - "8\n"
1.113 - "9\n"
1.114 - "@arcs\n"
1.115 - " -\n"
1.116 - "0 1\n"
1.117 - "1 2\n"
1.118 - "2 3\n"
1.119 - "3 4\n"
1.120 - "4 5\n"
1.121 - "5 6\n"
1.122 - "6 7\n"
1.123 - "7 8\n"
1.124 - "8 9\n"
1.125 - "9 0\n";
1.126 -
1.127 -char p10_lgf[] =
1.128 - "@nodes\n"
1.129 - "label\n"
1.130 - "0\n"
1.131 - "1\n"
1.132 - "2\n"
1.133 - "3\n"
1.134 - "4\n"
1.135 - "5\n"
1.136 - "6\n"
1.137 - "7\n"
1.138 - "8\n"
1.139 - "9\n"
1.140 - "@arcs\n"
1.141 - " -\n"
1.142 - "0 1\n"
1.143 - "1 2\n"
1.144 - "2 3\n"
1.145 - "3 4\n"
1.146 - "4 5\n"
1.147 - "5 6\n"
1.148 - "6 7\n"
1.149 - "7 8\n"
1.150 - "8 9\n";
1.151 -
1.152 -SmartGraph petersen, c5, c7, c10, p10;
1.153 -SmartGraph::NodeMap<int> petersen_col1(petersen);
1.154 -SmartGraph::NodeMap<int> petersen_col2(petersen);
1.155 -SmartGraph::NodeMap<int> c5_col(c5);
1.156 -
1.157 -void make_graphs(){
1.158 - std::stringstream ss(petersen_lgf);
1.159 - graphReader(petersen, ss)
1.160 - .nodeMap("col1",petersen_col1)
1.161 - .nodeMap("col2",petersen_col2)
1.162 - .run();
1.163 -
1.164 - ss.clear();
1.165 - ss.str("");
1.166 - ss<<c5_lgf;
1.167 -
1.168 - graphReader(c5, ss)
1.169 - .nodeMap("col",c5_col)
1.170 - .run();
1.171 -
1.172 - ss.clear();
1.173 - ss.str("");
1.174 - ss<<c7_lgf;
1.175 - graphReader(c7, ss).run();
1.176 -
1.177 - ss.clear();
1.178 - ss.str("");
1.179 - ss<<c10_lgf;
1.180 - graphReader(c10, ss).run();
1.181 -
1.182 - ss.clear();
1.183 - ss.str("");
1.184 - ss<<p10_lgf;
1.185 - graphReader(p10, ss).run();
1.186 -
1.187 -}
1.188 -
1.189 -class IntConvertible1{
1.190 -public:
1.191 - operator int(){
1.192 - return 0;
1.193 - }
1.194 -};
1.195 -
1.196 -class IntConvertible2{
1.197 -public:
1.198 - operator int(){
1.199 - return 0;
1.200 - }
1.201 -};
1.202 -
1.203 -template<class G1,class G2>
1.204 -void checkVf2Compile() {
1.205 - G1 g;
1.206 - G2 h;
1.207 - concepts::ReadWriteMap<typename G1::Node, typename G2::Node> r;
1.208 - bool succ;
1.209 - ::lemon::ignore_unused_variable_warning(succ);
1.210 -
1.211 - succ = vf2pp(g,h).run();
1.212 - succ = vf2pp(g,h).induced().run();
1.213 - succ = vf2pp(g,h).iso().run();
1.214 - succ = vf2pp(g,h).mapping(r).run();
1.215 - succ = vf2pp(g,h).induced().mapping(r).run();
1.216 - succ = vf2pp(g,h).iso().mapping(r).run();
1.217 -
1.218 -
1.219 - concepts::ReadMap<typename G1::Node, int> c1;
1.220 - concepts::ReadMap<typename G2::Node, int> c2;
1.221 - Vf2pp<G1,G2,concepts::ReadWriteMap<typename G1::Node, typename G2::Node>,
1.222 - concepts::ReadMap<typename G1::Node, int>,
1.223 - concepts::ReadMap<typename G2::Node, int> >
1.224 - myVf2pp(g,h,r,c1,c2);
1.225 - myVf2pp.find();
1.226 -
1.227 - succ = vf2pp(g,h).nodeLabels(c1,c2).mapping(r).run();
1.228 - succ = vf2pp(g,h).nodeLabels(c1,c2)
1.229 - .mapping(r).run();
1.230 -
1.231 -
1.232 - concepts::ReadMap<typename G1::Node, char> c1_c;
1.233 - concepts::ReadMap<typename G2::Node, char> c2_c;
1.234 - Vf2pp<G1,G2,concepts::ReadWriteMap<typename G1::Node, typename G2::Node>,
1.235 - concepts::ReadMap<typename G1::Node, char>,
1.236 - concepts::ReadMap<typename G2::Node, char> >
1.237 - myVf2pp_c(g,h,r,c1_c,c2_c);
1.238 - myVf2pp_c.find();
1.239 -
1.240 - succ = vf2pp(g,h).nodeLabels(c1_c,c2_c).mapping(r).run();
1.241 - succ = vf2pp(g,h).nodeLabels(c1_c,c2_c)
1.242 - .mapping(r).run();
1.243 -
1.244 -
1.245 - concepts::ReadMap<typename G1::Node, IntConvertible1> c1_IntConv;
1.246 - concepts::ReadMap<typename G2::Node, IntConvertible2> c2_IntConv;
1.247 - Vf2pp<G1,G2,concepts::ReadWriteMap<typename G1::Node, typename G2::Node>,
1.248 - concepts::ReadMap<typename G1::Node, IntConvertible1>,
1.249 - concepts::ReadMap<typename G2::Node, IntConvertible2> >
1.250 - myVf2pp_IntConv(g,h,r,c1_IntConv,c2_IntConv);
1.251 - myVf2pp_IntConv.find();
1.252 -
1.253 - succ = vf2pp(g,h).nodeLabels(c1_IntConv,c2_IntConv).mapping(r).run();
1.254 - succ = vf2pp(g,h).nodeLabels(c1_IntConv,c2_IntConv)
1.255 - .mapping(r).run();
1.256 -}
1.257 -
1.258 -void justCompile() {
1.259 - checkVf2Compile<concepts::Graph,concepts::Graph>();
1.260 - checkVf2Compile<concepts::Graph,SmartGraph>();
1.261 - checkVf2Compile<SmartGraph,concepts::Graph>();
1.262 -}
1.263 -
1.264 -template<class G1, class G2, class I>
1.265 -void checkSub(const G1 &g1, const G2 &g2, const I &i) {
1.266 - {
1.267 - std::set<typename G2::Node> image;
1.268 - for(typename G1::NodeIt n(g1);n!=INVALID;++n){
1.269 - check(i[n]!=INVALID, "Wrong isomorphism: incomplete mapping.");
1.270 - check(image.count(i[n])==0,"Wrong isomorphism: not injective.");
1.271 - image.insert(i[n]);
1.272 - }
1.273 - }
1.274 - for(typename G1::EdgeIt e(g1);e!=INVALID;++e)
1.275 - check(findEdge(g2,i[g1.u(e)],i[g1.v(e)])!=INVALID,
1.276 - "Wrong isomorphism: missing edge(checkSub).");
1.277 -}
1.278 -
1.279 -template<class G1, class G2, class I>
1.280 -void checkInd(const G1 &g1, const G2 &g2, const I &i) {
1.281 - std::set<typename G2::Node> image;
1.282 - for(typename G1::NodeIt n(g1);n!=INVALID;++n) {
1.283 - check(i[n]!=INVALID, "Wrong isomorphism: incomplete mapping.");
1.284 - check(image.count(i[n])==0,"Wrong isomorphism: not injective.");
1.285 - image.insert(i[n]);
1.286 - }
1.287 - for(typename G1::NodeIt n(g1); n!=INVALID; ++n)
1.288 - for(typename G1::NodeIt m(g1); m!=INVALID; ++m)
1.289 - if((findEdge(g1,n,m)==INVALID) != (findEdge(g2,i[n],i[m])==INVALID)) {
1.290 - std::cout << "Wrong isomorphism: edge mismatch";
1.291 - exit(1);
1.292 - }
1.293 -}
1.294 -
1.295 -template<class G1,class G2>
1.296 -int checkSub(const G1 &g1, const G2 &g2) {
1.297 - typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
1.298 - if(vf2pp(g1,g2).mapping(iso).run()){
1.299 - checkSub(g1,g2,iso);
1.300 - return true;
1.301 - }
1.302 - else
1.303 - return false;
1.304 -}
1.305 -
1.306 -template<class G1,class G2>
1.307 -int checkInd(const G1 &g1, const G2 &g2) {
1.308 - typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
1.309 - if(vf2pp(g1,g2).induced().mapping(iso).run()) {
1.310 - checkInd(g1,g2,iso);
1.311 - return true;
1.312 - }
1.313 - else
1.314 - return false;
1.315 -}
1.316 -
1.317 -template<class G1,class G2>
1.318 -int checkIso(const G1 &g1, const G2 &g2) {
1.319 - typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
1.320 - if(vf2pp(g1,g2).iso().mapping(iso).run()) {
1.321 - check(countNodes(g1)==countNodes(g2),
1.322 - "Wrong iso alg.: they are not isomophic.");
1.323 - checkInd(g1,g2,iso);
1.324 - return true;
1.325 - }
1.326 - else
1.327 - return false;
1.328 -}
1.329 -
1.330 -template<class G1, class G2, class L1, class L2, class I>
1.331 -void checkLabel(const G1 &g1, const G2 &,
1.332 - const L1 &l1, const L2 &l2,const I &i) {
1.333 - for(typename G1::NodeIt n(g1);n!=INVALID;++n)
1.334 - check(l1[n]==l2[i[n]],"Wrong isomorphism: label mismatch.");
1.335 -}
1.336 -
1.337 -template<class G1,class G2,class L1,class L2>
1.338 -int checkSub(const G1 &g1, const G2 &g2, const L1 &l1, const L2 &l2) {
1.339 - typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
1.340 - if(vf2pp(g1,g2).nodeLabels(l1,l2).mapping(iso).run()) {
1.341 - checkSub(g1,g2,iso);
1.342 - checkLabel(g1,g2,l1,l2,iso);
1.343 - return true;
1.344 - }
1.345 - else
1.346 - return false;
1.347 -}
1.348 -
1.349 -int main() {
1.350 - make_graphs();
1.351 -// justCompile();
1.352 - check(checkSub(c5,petersen), "There should exist a C5->Petersen mapping.");
1.353 - check(!checkSub(c7,petersen),
1.354 - "There should not exist a C7->Petersen mapping.");
1.355 - check(checkSub(p10,petersen), "There should exist a P10->Petersen mapping.");
1.356 - check(!checkSub(c10,petersen),
1.357 - "There should not exist a C10->Petersen mapping.");
1.358 - check(checkSub(petersen,petersen),
1.359 - "There should exist a Petersen->Petersen mapping.");
1.360 -
1.361 - check(checkInd(c5,petersen),
1.362 - "There should exist a C5->Petersen spanned mapping.");
1.363 - check(!checkInd(c7,petersen),
1.364 - "There should exist a C7->Petersen spanned mapping.");
1.365 - check(!checkInd(p10,petersen),
1.366 - "There should not exist a P10->Petersen spanned mapping.");
1.367 - check(!checkInd(c10,petersen),
1.368 - "There should not exist a C10->Petersen spanned mapping.");
1.369 - check(checkInd(petersen,petersen),
1.370 - "There should exist a Petersen->Petersen spanned mapping.");
1.371 -
1.372 - check(!checkSub(petersen,c10),
1.373 - "There should not exist a Petersen->C10 mapping.");
1.374 - check(checkSub(p10,c10),
1.375 - "There should exist a P10->C10 mapping.");
1.376 - check(!checkInd(p10,c10),
1.377 - "There should not exist a P10->C10 spanned mapping.");
1.378 - check(!checkSub(c10,p10),
1.379 - "There should not exist a C10->P10 mapping.");
1.380 -
1.381 - check(!checkIso(p10,c10),
1.382 - "P10 and C10 are not isomorphic.");
1.383 - check(checkIso(c10,c10),
1.384 - "C10 and C10 are isomorphic.");
1.385 -
1.386 - check(!vf2pp(p10,c10).iso().run(),
1.387 - "P10 and C10 are not isomorphic.");
1.388 - check(vf2pp(c10,c10).iso().run(),
1.389 - "C10 and C10 are isomorphic.");
1.390 -
1.391 - check(!checkSub(c5,petersen,c5_col,petersen_col1),
1.392 - "There should exist a C5->Petersen mapping.");
1.393 - check(checkSub(c5,petersen,c5_col,petersen_col2),
1.394 - "There should exist a C5->Petersen mapping.");
1.395 -}