/* -*- mode: C++; indent-tabs-mode: nil; -*-

  *

  * This file is a part of LEMON, a generic C++ optimization library.

  *

  * Copyright (C) 2015-2017

  * EMAXA Kutato-fejleszto Kft. (EMAXA Research Ltd.)

  *

  * Permission to use, modify and distribute this software is granted

  * provided that this copyright notice appears in all copies. For

  * precise terms see the accompanying LICENSE file.

  *

  * This software is provided "AS IS" with no warranty of any kind,

  * express or implied, and with no claim as to its suitability for any

  * purpose.

  *

  */

 #include <lemon/vf2pp.h>

 #include <lemon/concepts/digraph.h>

 #include <lemon/smart_graph.h>

 #include <lemon/lgf_reader.h>

 #include <lemon/concepts/maps.h>

 #include <lemon/maps.h>

 #include <lemon/list_graph.h>

 #include <test/test_tools.h>

 #include <sstream>

 using namespace lemon;

 char petersen_lgf[] =

   "@nodes\n"

   "label col1 col2\n"

   "0 1 1\n"

   "1 1 2\n"

   "2 1 3\n"

   "3 1 4\n"

   "4 2 5\n"

   "5 2 1\n"

   "6 2 2\n"

   "7 2 3\n"

   "8 2 4\n"

   "9 2 5\n"

   "@arcs\n"

   "     -\n"

   "0 1\n"

   "1 2\n"

   "2 3\n"

   "3 4\n"

   "4 0\n"

   "0 5\n"

   "1 6\n"

   "2 7\n"

   "3 8\n"

   "4 9\n"

   "5 8\n"

   "5 7\n"

   "9 6\n"

   "9 7\n"

   "6 8\n";

 char c5_lgf[] =

   "@nodes\n"

   "label col\n"

   "0 1\n"

   "1 2\n"

   "2 3\n"

   "3 4\n"

   "4 5\n"

   "@arcs\n"

   "     -\n"

   "0 1\n"

   "1 2\n"

   "2 3\n"

   "3 4\n"

   "4 0\n";

 char c7_lgf[] =

   "@nodes\n"

   "label\n"

   "0\n"

   "1\n"

   "2\n"

   "3\n"

   "4\n"

   "5\n"

   "6\n"

   "@arcs\n"

   "     -\n"

   "0 1\n"

   "1 2\n"

   "2 3\n"

   "3 4\n"

   "4 5\n"

   "5 6\n"

   "6 0\n";

 char c10_lgf[] =

   "@nodes\n"

   "label\n"

   "0\n"

   "1\n"

   "2\n"

   "3\n"

   "4\n"

   "5\n"

   "6\n"

   "7\n"

   "8\n"

   "9\n"

   "@arcs\n"

   "     -\n"

   "0 1\n"

   "1 2\n"

   "2 3\n"

   "3 4\n"

   "4 5\n"

   "5 6\n"

   "6 7\n"

   "7 8\n"

   "8 9\n"

   "9 0\n";

 char p10_lgf[] =

   "@nodes\n"

   "label\n"

   "0\n"

   "1\n"

   "2\n"

   "3\n"

   "4\n"

   "5\n"

   "6\n"

   "7\n"

   "8\n"

   "9\n"

   "@arcs\n"

   "     -\n"

   "0 1\n"

   "1 2\n"

   "2 3\n"

   "3 4\n"

   "4 5\n"

   "5 6\n"

   "6 7\n"

   "7 8\n"

   "8 9\n";

 SmartGraph petersen, c5, c7, c10, p10;

 SmartGraph::NodeMap<int> petersen_col1(petersen);

 SmartGraph::NodeMap<int> petersen_col2(petersen);

 SmartGraph::NodeMap<int> c5_col(c5);

 void make_graphs(){

   std::stringstream ss(petersen_lgf);

   graphReader(petersen, ss)

     .nodeMap("col1",petersen_col1)

     .nodeMap("col2",petersen_col2)

     .run();

   ss.clear();

   ss.str("");

   ss<<c5_lgf;

   graphReader(c5, ss)

     .nodeMap("col",c5_col)

     .run();

   ss.clear();

   ss.str("");

   ss<<c7_lgf;

   graphReader(c7, ss).run();

   ss.clear();

   ss.str("");

   ss<<c10_lgf;

   graphReader(c10, ss).run();

   ss.clear();

   ss.str("");

   ss<<p10_lgf;

   graphReader(p10, ss).run();

 }

 class IntConvertible1{

 public:

   operator int(){

     return 0;

   }

 };

 class IntConvertible2{

 public:

   operator int(){

     return 0;

   }

 };

 template<class G1,class G2>

 void checkVf2Compile() {

   G1 g;

   G2 h;

   concepts::ReadWriteMap<typename G1::Node, typename G2::Node> r;

   bool succ;

   ::lemon::ignore_unused_variable_warning(succ);

   succ = vf2pp(g,h).run();

   succ = vf2pp(g,h).induced().run();

   succ = vf2pp(g,h).iso().run();

   succ = vf2pp(g,h).mapping(r).run();

   succ = vf2pp(g,h).induced().mapping(r).run();

   succ = vf2pp(g,h).iso().mapping(r).run();

   concepts::ReadMap<typename G1::Node, int> c1;

   concepts::ReadMap<typename G2::Node, int> c2;

   Vf2pp<G1,G2,concepts::ReadWriteMap<typename G1::Node, typename G2::Node>,

         concepts::ReadMap<typename G1::Node, int>,

         concepts::ReadMap<typename G2::Node, int> >

     myVf2pp(g,h,r,c1,c2);

   myVf2pp.find();

   succ = vf2pp(g,h).nodeLabels(c1,c2).mapping(r).run();

   succ = vf2pp(g,h).nodeLabels(c1,c2)

     .mapping(r).run();

   concepts::ReadMap<typename G1::Node, char> c1_c;

   concepts::ReadMap<typename G2::Node, char> c2_c;

   Vf2pp<G1,G2,concepts::ReadWriteMap<typename G1::Node, typename G2::Node>,

         concepts::ReadMap<typename G1::Node, char>,

         concepts::ReadMap<typename G2::Node, char> >

     myVf2pp_c(g,h,r,c1_c,c2_c);

   myVf2pp_c.find();

   succ = vf2pp(g,h).nodeLabels(c1_c,c2_c).mapping(r).run();

   succ = vf2pp(g,h).nodeLabels(c1_c,c2_c)

     .mapping(r).run();

   concepts::ReadMap<typename G1::Node, IntConvertible1> c1_IntConv;

   concepts::ReadMap<typename G2::Node, IntConvertible2> c2_IntConv;

   Vf2pp<G1,G2,concepts::ReadWriteMap<typename G1::Node, typename G2::Node>,

         concepts::ReadMap<typename G1::Node, IntConvertible1>,

         concepts::ReadMap<typename G2::Node, IntConvertible2> >

     myVf2pp_IntConv(g,h,r,c1_IntConv,c2_IntConv);

   myVf2pp_IntConv.find();

   succ = vf2pp(g,h).nodeLabels(c1_IntConv,c2_IntConv).mapping(r).run();

   succ = vf2pp(g,h).nodeLabels(c1_IntConv,c2_IntConv)

     .mapping(r).run();

 }

 void justCompile() {

   checkVf2Compile<concepts::Graph,concepts::Graph>();

   checkVf2Compile<concepts::Graph,SmartGraph>();

   checkVf2Compile<SmartGraph,concepts::Graph>();

 }

 template<class G1, class G2, class I>

 void checkSub(const G1 &g1, const G2 &g2, const I &i) {

   {

     std::set<typename G2::Node> image;

     for(typename G1::NodeIt n(g1);n!=INVALID;++n){

       check(i[n]!=INVALID, "Wrong isomorphism: incomplete mapping.");

       check(image.count(i[n])==0,"Wrong isomorphism: not injective.");

       image.insert(i[n]);

     }

   }

   for(typename G1::EdgeIt e(g1);e!=INVALID;++e)

     check(findEdge(g2,i[g1.u(e)],i[g1.v(e)])!=INVALID,

           "Wrong isomorphism: missing edge(checkSub).");

 }

 template<class G1, class G2, class I>

 void checkInd(const G1 &g1, const G2 &g2, const I &i) {

   std::set<typename G2::Node> image;

   for(typename G1::NodeIt n(g1);n!=INVALID;++n) {

     check(i[n]!=INVALID, "Wrong isomorphism: incomplete mapping.");

     check(image.count(i[n])==0,"Wrong isomorphism: not injective.");

     image.insert(i[n]);

   }

   for(typename G1::NodeIt n(g1); n!=INVALID; ++n)

     for(typename G1::NodeIt m(g1); m!=INVALID; ++m)

       if((findEdge(g1,n,m)==INVALID) != (findEdge(g2,i[n],i[m])==INVALID)) {

         std::cout << "Wrong isomorphism: edge mismatch";

         exit(1);

       }

 }

 template<class G1,class G2>

 int checkSub(const G1 &g1, const G2 &g2) {

   typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);

   if(vf2pp(g1,g2).mapping(iso).run()){

     checkSub(g1,g2,iso);

     return true;

   }

   else

     return false;

 }

 template<class G1,class G2>

 int checkInd(const G1 &g1, const G2 &g2) {

   typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);

   if(vf2pp(g1,g2).induced().mapping(iso).run()) {

     checkInd(g1,g2,iso);

     return true;

   }

   else

     return false;

 }

 template<class G1,class G2>

 int checkIso(const G1 &g1, const G2 &g2) {

   typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);

   if(vf2pp(g1,g2).iso().mapping(iso).run()) {

     check(countNodes(g1)==countNodes(g2),

           "Wrong iso alg.: they are not isomophic.");

     checkInd(g1,g2,iso);

     return true;

   }

   else

     return false;

 }

 template<class G1, class G2, class L1, class L2, class I>

 void checkLabel(const G1 &g1, const G2 &,

                 const L1 &l1, const L2 &l2,const I &i) {

   for(typename G1::NodeIt n(g1);n!=INVALID;++n)

     check(l1[n]==l2[i[n]],"Wrong isomorphism: label mismatch.");

 }

 template<class G1,class G2,class L1,class L2>

 int checkSub(const G1 &g1, const G2 &g2, const L1 &l1, const L2 &l2) {

   typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);

   if(vf2pp(g1,g2).nodeLabels(l1,l2).mapping(iso).run()) {

     checkSub(g1,g2,iso);

     checkLabel(g1,g2,l1,l2,iso);

     return true;

   }

   else

     return false;

 }

 int main() {

   make_graphs();

 //   justCompile();

   check(checkSub(c5,petersen), "There should exist a C5->Petersen mapping.");

   check(!checkSub(c7,petersen),

         "There should not exist a C7->Petersen mapping.");

   check(checkSub(p10,petersen), "There should exist a P10->Petersen mapping.");

   check(!checkSub(c10,petersen),

         "There should not exist a C10->Petersen mapping.");

   check(checkSub(petersen,petersen),

         "There should exist a Petersen->Petersen mapping.");

   check(checkInd(c5,petersen),

         "There should exist a C5->Petersen spanned mapping.");

   check(!checkInd(c7,petersen),

         "There should exist a C7->Petersen spanned mapping.");

   check(!checkInd(p10,petersen),

         "There should not exist a P10->Petersen spanned mapping.");

   check(!checkInd(c10,petersen),

         "There should not exist a C10->Petersen spanned mapping.");

   check(checkInd(petersen,petersen),

         "There should exist a Petersen->Petersen spanned mapping.");

   check(!checkSub(petersen,c10),

         "There should not exist a Petersen->C10 mapping.");

   check(checkSub(p10,c10),

         "There should exist a P10->C10 mapping.");

   check(!checkInd(p10,c10),

         "There should not exist a P10->C10 spanned mapping.");

   check(!checkSub(c10,p10),

         "There should not exist a C10->P10 mapping.");

   check(!checkIso(p10,c10),

         "P10 and C10 are not isomorphic.");

   check(checkIso(c10,c10),

         "C10 and C10 are isomorphic.");

   check(!vf2pp(p10,c10).iso().run(),

         "P10 and C10 are not isomorphic.");

   check(vf2pp(c10,c10).iso().run(),

         "C10 and C10 are isomorphic.");

   check(!checkSub(c5,petersen,c5_col,petersen_col1),

         "There should exist a C5->Petersen mapping.");

   check(checkSub(c5,petersen,c5_col,petersen_col2),

         "There should exist a C5->Petersen mapping.");

 }