madarasip@1141: /* -*- mode: C++; indent-tabs-mode: nil; -*-
madarasip@1141:  *
madarasip@1141:  * This file is a part of LEMON, a generic C++ optimization library.
madarasip@1141:  *
madarasip@1186:  * Copyright (C) 2015-2017
madarasip@1141:  * EMAXA Kutato-fejleszto Kft. (EMAXA Research Ltd.)
madarasip@1141:  *
madarasip@1141:  * Permission to use, modify and distribute this software is granted
madarasip@1141:  * provided that this copyright notice appears in all copies. For
madarasip@1141:  * precise terms see the accompanying LICENSE file.
madarasip@1141:  *
madarasip@1141:  * This software is provided "AS IS" with no warranty of any kind,
madarasip@1141:  * express or implied, and with no claim as to its suitability for any
madarasip@1141:  * purpose.
madarasip@1141:  *
madarasip@1141:  */
madarasip@1141: 
madarasip@1141: #include <lemon/vf2.h>
kpeter@1187: #include <lemon/vf2pp.h>
madarasip@1141: #include <lemon/concepts/digraph.h>
madarasip@1141: #include <lemon/smart_graph.h>
madarasip@1141: #include <lemon/lgf_reader.h>
madarasip@1141: #include <lemon/concepts/maps.h>
madarasip@1141: 
madarasip@1141: #include <test/test_tools.h>
madarasip@1141: #include <sstream>
madarasip@1141: 
madarasip@1141: using namespace lemon;
madarasip@1141: 
madarasip@1141: char petersen_lgf[] =
madarasip@1141:   "@nodes\n"
madarasip@1141:   "label col1 col2\n"
madarasip@1141:   "0 1 1\n"
madarasip@1141:   "1 1 2\n"
madarasip@1141:   "2 1 3\n"
madarasip@1141:   "3 1 4\n"
madarasip@1141:   "4 2 5\n"
madarasip@1141:   "5 2 1\n"
madarasip@1141:   "6 2 2\n"
madarasip@1141:   "7 2 3\n"
madarasip@1141:   "8 2 4\n"
madarasip@1141:   "9 2 5\n"
madarasip@1141:   "@arcs\n"
madarasip@1141:   "     -\n"
madarasip@1141:   "0 1\n"
madarasip@1141:   "1 2\n"
madarasip@1141:   "2 3\n"
madarasip@1141:   "3 4\n"
madarasip@1141:   "4 0\n"
madarasip@1141:   "0 5\n"
madarasip@1141:   "1 6\n"
madarasip@1141:   "2 7\n"
madarasip@1141:   "3 8\n"
madarasip@1141:   "4 9\n"
madarasip@1141:   "5 8\n"
madarasip@1141:   "5 7\n"
madarasip@1141:   "9 6\n"
madarasip@1141:   "9 7\n"
madarasip@1141:   "6 8\n";
madarasip@1141: 
madarasip@1141: char c5_lgf[] =
madarasip@1141:   "@nodes\n"
madarasip@1141:   "label col\n"
madarasip@1141:   "0 1\n"
madarasip@1141:   "1 2\n"
madarasip@1141:   "2 3\n"
madarasip@1141:   "3 4\n"
madarasip@1141:   "4 5\n"
madarasip@1141:   "@arcs\n"
madarasip@1141:   "     -\n"
madarasip@1141:   "0 1\n"
madarasip@1141:   "1 2\n"
madarasip@1141:   "2 3\n"
madarasip@1141:   "3 4\n"
madarasip@1141:   "4 0\n";
madarasip@1141: 
madarasip@1141: char c7_lgf[] =
madarasip@1141:   "@nodes\n"
madarasip@1141:   "label\n"
madarasip@1141:   "0\n"
madarasip@1141:   "1\n"
madarasip@1141:   "2\n"
madarasip@1141:   "3\n"
madarasip@1141:   "4\n"
madarasip@1141:   "5\n"
madarasip@1141:   "6\n"
madarasip@1141:   "@arcs\n"
madarasip@1141:   "     -\n"
madarasip@1141:   "0 1\n"
madarasip@1141:   "1 2\n"
madarasip@1141:   "2 3\n"
madarasip@1141:   "3 4\n"
madarasip@1141:   "4 5\n"
madarasip@1141:   "5 6\n"
madarasip@1141:   "6 0\n";
madarasip@1141: 
madarasip@1141: char c10_lgf[] =
madarasip@1141:   "@nodes\n"
madarasip@1141:   "label\n"
madarasip@1141:   "0\n"
madarasip@1141:   "1\n"
madarasip@1141:   "2\n"
madarasip@1141:   "3\n"
madarasip@1141:   "4\n"
madarasip@1141:   "5\n"
madarasip@1141:   "6\n"
madarasip@1141:   "7\n"
madarasip@1141:   "8\n"
madarasip@1141:   "9\n"
madarasip@1141:   "@arcs\n"
madarasip@1141:   "     -\n"
madarasip@1141:   "0 1\n"
madarasip@1141:   "1 2\n"
madarasip@1141:   "2 3\n"
madarasip@1141:   "3 4\n"
madarasip@1141:   "4 5\n"
madarasip@1141:   "5 6\n"
madarasip@1141:   "6 7\n"
madarasip@1141:   "7 8\n"
madarasip@1141:   "8 9\n"
madarasip@1141:   "9 0\n";
madarasip@1141: 
madarasip@1141: char p10_lgf[] =
madarasip@1141:   "@nodes\n"
madarasip@1141:   "label\n"
madarasip@1141:   "0\n"
madarasip@1141:   "1\n"
madarasip@1141:   "2\n"
madarasip@1141:   "3\n"
madarasip@1141:   "4\n"
madarasip@1141:   "5\n"
madarasip@1141:   "6\n"
madarasip@1141:   "7\n"
madarasip@1141:   "8\n"
madarasip@1141:   "9\n"
madarasip@1141:   "@arcs\n"
madarasip@1141:   "     -\n"
madarasip@1141:   "0 1\n"
madarasip@1141:   "1 2\n"
madarasip@1141:   "2 3\n"
madarasip@1141:   "3 4\n"
madarasip@1141:   "4 5\n"
madarasip@1141:   "5 6\n"
madarasip@1141:   "6 7\n"
madarasip@1141:   "7 8\n"
madarasip@1141:   "8 9\n";
madarasip@1141: 
madarasip@1141: SmartGraph petersen, c5, c7, c10, p10;
madarasip@1141: SmartGraph::NodeMap<int> petersen_col1(petersen);
madarasip@1141: SmartGraph::NodeMap<int> petersen_col2(petersen);
madarasip@1141: SmartGraph::NodeMap<int> c5_col(c5);
madarasip@1141: 
madarasip@1141: void make_graphs() {
madarasip@1141:   std::stringstream ss(petersen_lgf);
madarasip@1141:   graphReader(petersen, ss)
kpeter@1187:     .nodeMap("col1", petersen_col1)
kpeter@1187:     .nodeMap("col2", petersen_col2)
madarasip@1141:     .run();
madarasip@1141: 
madarasip@1141:   ss.clear();
madarasip@1141:   ss.str("");
kpeter@1187:   ss << c5_lgf;
madarasip@1141:   //std::stringstream ss2(c5_lgf);
madarasip@1141:   graphReader(c5, ss)
kpeter@1187:     .nodeMap("col", c5_col)
madarasip@1141:     .run();
madarasip@1141: 
madarasip@1141:   ss.clear();
madarasip@1141:   ss.str("");
kpeter@1187:   ss << c7_lgf;
madarasip@1141:   graphReader(c7, ss).run();
madarasip@1141: 
madarasip@1141:   ss.clear();
madarasip@1141:   ss.str("");
kpeter@1187:   ss << c10_lgf;
madarasip@1141:   graphReader(c10, ss).run();
madarasip@1141: 
madarasip@1141:   ss.clear();
madarasip@1141:   ss.str("");
kpeter@1187:   ss << p10_lgf;
madarasip@1141:   graphReader(p10, ss).run();
madarasip@1141: 
madarasip@1141: }
madarasip@1141: 
madarasip@1141: class EqComparable {
madarasip@1141: public:
madarasip@1186:   bool operator==(const EqComparable&) {
madarasip@1186:     return false;
madarasip@1186:   }
madarasip@1141: };
madarasip@1141: 
madarasip@1141: template<class A, class B>
madarasip@1141: class EqClass {
madarasip@1141: public:
madarasip@1186:   bool operator()(A, B){
madarasip@1186:     return false;
madarasip@1186:   }
madarasip@1141: };
madarasip@1141: 
kpeter@1187: class IntConvertible1 {
kpeter@1187: public:
kpeter@1187:   operator int() {
kpeter@1187:     return 0;
kpeter@1187:   }
kpeter@1187: };
kpeter@1187: 
kpeter@1187: class IntConvertible2 {
kpeter@1187: public:
kpeter@1187:   operator int() {
kpeter@1187:     return 0;
kpeter@1187:   }
kpeter@1187: };
kpeter@1187: 
madarasip@1141: template<class G1,class G2>
madarasip@1186: void checkVf2Compile() {
madarasip@1141:   G1 g;
madarasip@1141:   G2 h;
madarasip@1141:   concepts::ReadWriteMap<typename G1::Node, typename G2::Node> r;
madarasip@1141:   bool succ;
madarasip@1141:   ::lemon::ignore_unused_variable_warning(succ);
madarasip@1141: 
madarasip@1141:   succ = vf2(g,h).run();
madarasip@1141:   succ = vf2(g,h).induced().run();
madarasip@1141:   succ = vf2(g,h).iso().run();
madarasip@1141:   succ = vf2(g,h).mapping(r).run();
madarasip@1186: 
madarasip@1186:   Vf2<G1,G2,concepts::ReadWriteMap<typename G1::Node, typename G2::Node>,
madarasip@1186:       EqClass<typename G1::Node,typename G2::Node> >
madarasip@1186:     myVf2(g,h,r,EqClass<typename G1::Node,typename G2::Node>());
madarasip@1186:   myVf2.find();
madarasip@1186: 
madarasip@1141:   succ = vf2(g,h).induced().mapping(r).run();
madarasip@1141:   succ = vf2(g,h).iso().mapping(r).run();
madarasip@1186: 
madarasip@1141:   concepts::ReadMap<typename G1::Node, EqComparable> l1;
madarasip@1141:   concepts::ReadMap<typename G2::Node, EqComparable> l2;
madarasip@1141:   succ = vf2(g,h).nodeLabels(l1,l2).mapping(r).run();
madarasip@1141:   succ = vf2(g,h).nodeEq(EqClass<typename G1::Node,typename G2::Node>())
madarasip@1141:     .mapping(r).run();
madarasip@1141: }
madarasip@1141: 
kpeter@1187: void vf2Compile() {
madarasip@1141:   checkVf2Compile<concepts::Graph,concepts::Graph>();
madarasip@1141:   checkVf2Compile<concepts::Graph,SmartGraph>();
madarasip@1141:   checkVf2Compile<SmartGraph,concepts::Graph>();
madarasip@1141: }
madarasip@1141: 
kpeter@1187: template<class G1,class G2>
kpeter@1187: void checkVf2ppCompile() {
kpeter@1187:   G1 g;
kpeter@1187:   G2 h;
kpeter@1187:   concepts::ReadWriteMap<typename G1::Node, typename G2::Node> r;
kpeter@1187:   bool succ;
kpeter@1187:   ::lemon::ignore_unused_variable_warning(succ);
kpeter@1187: 
kpeter@1187:   succ = vf2pp(g,h).run();
kpeter@1187:   succ = vf2pp(g,h).induced().run();
kpeter@1187:   succ = vf2pp(g,h).iso().run();
kpeter@1187:   succ = vf2pp(g,h).mapping(r).run();
kpeter@1187:   succ = vf2pp(g,h).induced().mapping(r).run();
kpeter@1187:   succ = vf2pp(g,h).iso().mapping(r).run();
kpeter@1187: 
kpeter@1187:   concepts::ReadMap<typename G1::Node, int> c1;
kpeter@1187:   concepts::ReadMap<typename G2::Node, int> c2;
kpeter@1187:   Vf2pp<G1,G2,concepts::ReadWriteMap<typename G1::Node, typename G2::Node>,
kpeter@1187:         concepts::ReadMap<typename G1::Node, int>,
kpeter@1187:         concepts::ReadMap<typename G2::Node, int> >
kpeter@1187:     myVf2pp(g,h,r,c1,c2);
kpeter@1187:   myVf2pp.find();
kpeter@1187: 
kpeter@1187:   succ = vf2pp(g,h).nodeLabels(c1,c2).mapping(r).run();
kpeter@1187:   succ = vf2pp(g,h).nodeLabels(c1,c2).mapping(r).run();
kpeter@1187: 
kpeter@1187:   concepts::ReadMap<typename G1::Node, char> c1_c;
kpeter@1187:   concepts::ReadMap<typename G2::Node, char> c2_c;
kpeter@1187:   Vf2pp<G1,G2,concepts::ReadWriteMap<typename G1::Node, typename G2::Node>,
kpeter@1187:         concepts::ReadMap<typename G1::Node, char>,
kpeter@1187:         concepts::ReadMap<typename G2::Node, char> >
kpeter@1187:     myVf2pp_c(g,h,r,c1_c,c2_c);
kpeter@1187:   myVf2pp_c.find();
kpeter@1187: 
kpeter@1187:   succ = vf2pp(g,h).nodeLabels(c1_c,c2_c).mapping(r).run();
kpeter@1187:   succ = vf2pp(g,h).nodeLabels(c1_c,c2_c).mapping(r).run();
kpeter@1187: 
kpeter@1187:   concepts::ReadMap<typename G1::Node, IntConvertible1> c1_IntConv;
kpeter@1187:   concepts::ReadMap<typename G2::Node, IntConvertible2> c2_IntConv;
kpeter@1187:   Vf2pp<G1,G2,concepts::ReadWriteMap<typename G1::Node, typename G2::Node>,
kpeter@1187:         concepts::ReadMap<typename G1::Node, IntConvertible1>,
kpeter@1187:         concepts::ReadMap<typename G2::Node, IntConvertible2> >
kpeter@1187:     myVf2pp_IntConv(g,h,r,c1_IntConv,c2_IntConv);
kpeter@1187:   myVf2pp_IntConv.find();
kpeter@1187: 
kpeter@1187:   succ = vf2pp(g,h).nodeLabels(c1_IntConv,c2_IntConv).mapping(r).run();
kpeter@1187:   succ = vf2pp(g,h).nodeLabels(c1_IntConv,c2_IntConv).mapping(r).run();
kpeter@1187: }
kpeter@1187: 
kpeter@1187: void vf2ppCompile() {
kpeter@1187:   checkVf2ppCompile<concepts::Graph,concepts::Graph>();
kpeter@1187:   checkVf2ppCompile<concepts::Graph,SmartGraph>();
kpeter@1187:   checkVf2ppCompile<SmartGraph,concepts::Graph>();
madarasip@1141: }
madarasip@1141: 
madarasip@1141: template<class G1, class G2, class I>
kpeter@1187: void checkSubIso(const G1 &g1, const G2 &g2, const I &i) {
madarasip@1141:   std::set<typename G2::Node> image;
kpeter@1187:   for (typename G1::NodeIt n(g1);n!=INVALID;++n){
madarasip@1141:     check(i[n]!=INVALID, "Wrong isomorphism: incomplete mapping.");
madarasip@1141:     check(image.count(i[n])==0,"Wrong isomorphism: not injective.");
madarasip@1141:     image.insert(i[n]);
madarasip@1186:   }
kpeter@1187:   for (typename G1::EdgeIt e(g1);e!=INVALID;++e) {
kpeter@1187:     check(findEdge(g2,i[g1.u(e)],i[g1.v(e)])!=INVALID,
kpeter@1187:           "Wrong isomorphism: missing edge(checkSub).");
kpeter@1187:   }
kpeter@1187: }
kpeter@1187: 
kpeter@1187: template<class G1, class G2, class I>
kpeter@1187: void checkIndIso(const G1 &g1, const G2 &g2, const I &i) {
kpeter@1187:   std::set<typename G2::Node> image;
kpeter@1187:   for (typename G1::NodeIt n(g1);n!=INVALID;++n) {
kpeter@1187:     check(i[n]!=INVALID, "Wrong isomorphism: incomplete mapping.");
kpeter@1187:     check(image.count(i[n])==0,"Wrong isomorphism: not injective.");
kpeter@1187:     image.insert(i[n]);
kpeter@1187:   }
kpeter@1187:   for (typename G1::NodeIt n(g1); n!=INVALID; ++n) {
kpeter@1187:     for (typename G1::NodeIt m(g1); m!=INVALID; ++m) {
madarasip@1186:       if((findEdge(g1,n,m)==INVALID) != (findEdge(g2,i[n],i[m])==INVALID)) {
madarasip@1141:         std::cout << "Wrong isomorphism: edge mismatch";
madarasip@1141:         exit(1);
madarasip@1186:       }
kpeter@1187:     }
kpeter@1187:   }
madarasip@1141: }
madarasip@1141: 
kpeter@1187: template<class G1,class G2,class T>
kpeter@1187: bool checkSub(const G1 &g1, const G2 &g2, const T &vf2) {
madarasip@1141:   typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
kpeter@1187:   if (const_cast<T&>(vf2).mapping(iso).run()) {
kpeter@1187:     checkSubIso(g1,g2,iso);
madarasip@1186:     return true;
madarasip@1186:   }
kpeter@1187:   return false;
madarasip@1141: }
madarasip@1141: 
kpeter@1187: template<class G1,class G2,class T>
kpeter@1187: bool checkInd(const G1 &g1, const G2 &g2, const T &vf2) {
madarasip@1141:   typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
kpeter@1187:   if (const_cast<T&>(vf2).induced().mapping(iso).run()) {
kpeter@1187:     checkIndIso(g1,g2,iso);
madarasip@1186:     return true;
madarasip@1186:   }
kpeter@1187:   return false;
madarasip@1186: }
madarasip@1186: 
kpeter@1187: template<class G1,class G2,class T>
kpeter@1187: bool checkIso(const G1 &g1, const G2 &g2, const T &vf2) {
madarasip@1186:   typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
kpeter@1187:   if (const_cast<T&>(vf2).iso().mapping(iso).run()) {
madarasip@1186:     check(countNodes(g1)==countNodes(g2),
madarasip@1186:           "Wrong iso alg.: they are not isomophic.");
kpeter@1187:     checkIndIso(g1,g2,iso);
madarasip@1186:     return true;
madarasip@1186:   }
kpeter@1187:   return false;
madarasip@1141: }
madarasip@1141: 
madarasip@1141: template<class G1, class G2, class L1, class L2, class I>
madarasip@1141: void checkLabel(const G1 &g1, const G2 &,
kpeter@1187:                 const L1 &l1, const L2 &l2, const I &i) {
kpeter@1187:   for (typename G1::NodeIt n(g1);n!=INVALID;++n) {
madarasip@1186:     check(l1[n]==l2[i[n]],"Wrong isomorphism: label mismatch.");
kpeter@1187:   }
kpeter@1187: }
kpeter@1187: 
kpeter@1187: template<class G1,class G2,class L1,class L2,class T>
kpeter@1187: bool checkSub(const G1 &g1, const G2 &g2, const L1 &l1, const L2 &l2, const T &vf2) {
kpeter@1187:   typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
kpeter@1187:   if (const_cast<T&>(vf2).nodeLabels(l1,l2).mapping(iso).run()){
kpeter@1187:     checkSubIso(g1,g2,iso);
kpeter@1187:     checkLabel(g1,g2,l1,l2,iso);
kpeter@1187:     return true;
kpeter@1187:   }
kpeter@1187:   return false;
kpeter@1187: }
kpeter@1187: 
kpeter@1187: template<class G1,class G2>
kpeter@1187: void checkSub(const G1 &g1, const G2 &g2, bool expected, const char* msg) {
kpeter@1187:   check(checkSub(g1,g2,vf2(g1,g2)) == expected, msg);
kpeter@1187:   check(checkSub(g1,g2,vf2pp(g1,g2)) == expected, msg);
kpeter@1187: }
kpeter@1187: 
kpeter@1187: template<class G1,class G2>
kpeter@1187: void checkInd(const G1 &g1, const G2 &g2, bool expected, const char* msg) {
kpeter@1187:   check(checkInd(g1,g2,vf2(g1,g2)) == expected, msg);
kpeter@1187:   check(checkInd(g1,g2,vf2pp(g1,g2)) == expected, msg);
kpeter@1187: }
kpeter@1187: 
kpeter@1187: template<class G1,class G2>
kpeter@1187: void checkIso(const G1 &g1, const G2 &g2, bool expected, const char* msg) {
kpeter@1187:   check(checkIso(g1,g2,vf2(g1,g2)) == expected, msg);
kpeter@1187:   check(checkIso(g1,g2,vf2pp(g1,g2)) == expected, msg);
madarasip@1141: }
madarasip@1141: 
madarasip@1141: template<class G1,class G2,class L1,class L2>
kpeter@1187: void checkSub(const G1 &g1, const G2 &g2, const L1 &l1, const L2 &l2, bool expected, const char* msg) {
kpeter@1187:   check(checkSub(g1,g2,l1,l2,vf2(g1,g2)) == expected, msg);
kpeter@1187:   check(checkSub(g1,g2,l1,l2,vf2pp(g1,g2)) == expected, msg);
madarasip@1141: }
madarasip@1141: 
madarasip@1141: int main() {
madarasip@1141:   make_graphs();
madarasip@1141: 
kpeter@1187:   checkSub(c5,petersen,true,
kpeter@1187:       "There should exist a C5->Petersen mapping.");
kpeter@1187:   checkSub(c7,petersen,false,
kpeter@1187:       "There should not exist a C7->Petersen mapping.");
kpeter@1187:   checkSub(p10,petersen,true,
kpeter@1187:       "There should exist a P10->Petersen mapping.");
kpeter@1187:   checkSub(c10,petersen,false,
kpeter@1187:       "There should not exist a C10->Petersen mapping.");
kpeter@1187:   checkSub(petersen,petersen,true,
kpeter@1187:       "There should exist a Petersen->Petersen mapping.");
kpeter@1187: 
kpeter@1187:   checkInd(c5,petersen,true,
kpeter@1187:       "There should exist a C5->Petersen spanned mapping.");
kpeter@1187:   checkInd(c7,petersen,false,
kpeter@1187:       "There should exist a C7->Petersen spanned mapping.");
kpeter@1187:   checkInd(p10,petersen,false,
kpeter@1187:       "There should not exist a P10->Petersen spanned mapping.");
kpeter@1187:   checkInd(c10,petersen,false,
kpeter@1187:       "There should not exist a C10->Petersen spanned mapping.");
kpeter@1187:   checkInd(petersen,petersen,true,
madarasip@1141:         "There should exist a Petersen->Petersen spanned mapping.");
madarasip@1141: 
kpeter@1187:   checkSub(petersen,c10,false,
kpeter@1187:       "There should not exist a Petersen->C10 mapping.");
kpeter@1187:   checkSub(p10,c10,true,
kpeter@1187:       "There should exist a P10->C10 mapping.");
kpeter@1187:   checkInd(p10,c10,false,
kpeter@1187:       "There should not exist a P10->C10 spanned mapping.");
kpeter@1187:   checkSub(c10,p10,false,
kpeter@1187:       "There should not exist a C10->P10 mapping.");
madarasip@1141: 
kpeter@1187:   checkIso(p10,c10,false,
kpeter@1187:       "P10 and C10 are not isomorphic.");
kpeter@1187:   checkIso(c10,c10,true,
kpeter@1187:       "C10 and C10 are isomorphic.");
alpar@1143: 
kpeter@1187:   checkSub(c5,petersen,c5_col,petersen_col1,false,
kpeter@1187:       "There should exist a C5->Petersen mapping.");
kpeter@1187:   checkSub(c5,petersen,c5_col,petersen_col2,true,
kpeter@1187:       "There should exist a C5->Petersen mapping.");
madarasip@1141: 
kpeter@1187:   check(!vf2(p10,c10).iso().run(), "P10 and C10 are not isomorphic.");
kpeter@1187:   check(!vf2pp(p10,c10).iso().run(), "P10 and C10 are not isomorphic.");
kpeter@1187: 
kpeter@1187:   check(vf2(c10,c10).iso().run(), "C10 and C10 are isomorphic.");
kpeter@1187:   check(vf2pp(c10,c10).iso().run(), "C10 and C10 are isomorphic.");
madarasip@1141: }