#include <basic_impl.hpp>

#include <cassert>
#include <map>
#include <vector>


#include <algorithms/isomorphism/isomorphism_nauty.hpp>
#include <io/graph6.hpp>
#include <random/renumber.hpp>

#include <invariants.hpp>
#include <iostream>
#include <operations.hpp>
#include "algorithms/isomorphism/isomorphism_nauty.hpp"

#include "algorithms/isomorphism/automorphism_group.hpp"
#include "io/print_nice.hpp"
#include <nausparse.h>
#include <ctime>
#include <cstdio>
#include <algorithm>



using namespace ba_graph;

std::vector <int> verticesPokus;
std::map<int,std::vector<int>> mapa;
std::map<std::vector<int>, int> mapaRev;
std::map<int, int> mapaSwitch;
std::map<int, int> mapaSwitchRev;
Graph finalnyPomocnyGraf(empty_graph(0));
std::set <std::string> newGraphs;
std::vector<int>::iterator it;
std::ofstream fout;


void DFSUtil(int v, bool visited[],Graph &G){
    visited[v] = true;
    int pozicia;
    // Recur for all the vertices
    // adjacent to this vertex
    for (auto &i : G[v]) {
        pozicia= i.r2().n().to_int();
        if (!visited[pozicia]){
            DFSUtil(pozicia, visited, G);
        }
    }
}

//funkcia, ktorá nám vyberie zakaždým jeden vrchol nezávislého komponentu grafu a vráti nám zoznam takých vrcholov
std::vector<int> ConnectedComponents(Graph &G, int velkost){
    bool* visited = new bool[velkost];
    std::vector<int> Component;

    for (int i=0; i<velkost; i++){
        visited[i]=true;
    }

    for (auto &v : G) {
        visited[v.n().to_int()] = false;
    }
    for (auto &v : G) {
        if (visited[v.n().to_int()] == false) {
            DFSUtil(v.n().to_int(), visited, G);
            Component.push_back(v.n().to_int());
        }
    }
    delete[] visited;
    return Component;
}



Graph Kruznica(){
    Graph G(circuit(7));
    return G;
}

void pridajKruznicu(Graph &G){
    Graph Kruh(circuit(7));
    add_graph(G,Kruh, G.order());
}

Graph Okuliare(){
    Graph G = Kruznica();
    pridajKruznicu(G);
    addE(G, Location(0, 7));
    return G;
}
int power(int zaklad, int exponent){
    int pomoc = 1;
    for (int i=0; i< exponent; i++){
        pomoc = pomoc * zaklad;
    }
    return pomoc;
}

//vráti zoznam vrcholov z výstupu funkcie ConnectedComponents aplikovnú na dany graf a velkosť
std::vector<int> genKomponentyKruznice (int stupen){
    Graph G2 = Kruznica();
    //vytvoríme si pomocny graf pre kružnicu velkosti 7 na počet zapojenych kružníc
    Graph pomocnyGrafKruznica(empty_graph(power(7, stupen)));

    int vrchol;
    int pomoc;
    std::vector<int> pole;
    std::vector<int> pomocnePole;
    pomocnePole.clear();
    for (auto &r : pomocnyGrafKruznica) {

        vrchol = r.n().to_int();
        pomoc = 0;
        pole.clear();
        while (pomoc < stupen){
            it = std::find (pole.begin(), pole.end(), (vrchol%7));
            if(it != pole.end()){
                pomocnePole.push_back(r.n().to_int());
                break;
            }
            pole.push_back((vrchol%7));
            vrchol = vrchol / 7;
            pomoc++;
        }
    }

    for(auto &v : pomocnePole){
        deleteV(pomocnyGrafKruznica, v);
    }

    generatory = automorfizmus(G2);
    for (const auto &permutaciaPokus : generatory) {
        for (auto &r : pomocnyGrafKruznica) {
            vrchol = r.n().to_int();
            pomoc = 0;
            pole.clear();
            while (pomoc < stupen){
                pole.push_back(permutaciaPokus[(vrchol%7)]);
                vrchol = vrchol / 7;
                pomoc++;
            }
            vrchol = 0;
            for (int i=pole.size(); i>0;i--){
                vrchol = (vrchol *7) + (pole[i-1]%7);
            }
            if(vrchol != r.n().to_int()) {
                addE(pomocnyGrafKruznica, Location(r.n().to_int(), vrchol));
            }
        }
    }
    return ConnectedComponents(pomocnyGrafKruznica, power(7, stupen));
}



//procedúra na generovanie grafov ktorá na vstupe dostane graf G, vektor vrcholov reprezentujúci nezávislé komponenty kružnice, hodnotu, kolkatu kružnicu pridávam a počet kolko kružnic mám pripojiť
void generateGraphs2(Graph G, std::vector<int> KomponentyKruznice, int stupen, int maxStupen){
    if (stupen > maxStupen) {
        return;
    }


    std::vector<int> newKomponentyKruznice = genKomponentyKruznice(stupen+1);

    //vytváram si pomocny graf velkosti 7 na počet už zapojených kružníc, dalej chceme z pomocného grafu odstrániť vrcholy, ktoré už sú použité pri zapojení kružníc
        Graph pomocnyGraf(empty_graph(power(7, stupen)));


        int vrchol;
        int pomoc;
        std::vector<int> pole;
        std::vector<int> pomocnePole;

        for (auto ii : G.list(RP::all(), IP::primary())) {
            if (ii->n1().to_int() / 7 != ii->n2().to_int() / 7) {
                pomocnePole.push_back(ii->n1().to_int());
                pomocnePole.push_back(ii->n2().to_int());
            }
        }


        for (auto &v : pomocnePole) {
            pomoc = 1;
            for (int i = 0; i < v / 7; i++) {
                pomoc = pomoc * 7;
            }

            for (auto &r : pomocnyGraf) {
                if ((r.n().to_int() / pomoc) % 7 == v % 7) {
                    pole.push_back(r.n().to_int());
                }
            }
            for (auto &i : pole) {
                deleteV(pomocnyGraf, i);
            }
            pole.clear();
        }
    // ak zapájame menej ako piatu kružnicu, tak si zistime generátory grupy automorfizmov pre daný graf G a vrcholy budeme spájať s ich automorfnými obrazmi
    if(stupen < 5) {
        std::vector <std::vector<int>> generatory = automorfizmus(G);
        for (const auto &permutaciaPokus : generatory) {
            for (auto &r : pomocnyGraf) {
                vrchol = r.n().to_int();
                pomoc = 0;
                pole.clear();
                while (pomoc < stupen) {
                    pole.push_back(permutaciaPokus[(vrchol % 7) + (pomoc * 7)]);
                    vrchol = vrchol / 7;
                    pomoc++;
                }

                vrchol = 0;
                std::sort(pole.begin(), pole.end());
                for (int i = pole.size(); i > 0; i--) {
                    vrchol = (vrchol * 7) + (pole[i - 1] % 7);

                }
                if (vrchol != r.n().to_int()) {
                    addE(pomocnyGraf, Location(r.n().to_int(), vrchol));
                }
            }
        }
    }


    std::vector<int> KomponentyGrafu = ConnectedComponents(pomocnyGraf, power(7, stupen));

    //pridáme kružnicu a postupne skúšame všetky možne spôsoby akými to možme zapojiť
    pridajKruznicu(G);
    int vrcholG;
    int vrcholK;

    for (auto KomponentGrafu : KomponentyGrafu) {
        for (auto Komponent : KomponentyKruznice) {
            Graph G1(copy_identical(G));
            pomoc =0;
            vrcholG = KomponentGrafu;
            vrcholK = Komponent;
            while (pomoc < stupen){
                addE(G1, Location((vrcholG%7)+(pomoc*7),(vrcholK%7)+(stupen*7)));
                vrcholG = vrcholG/7;
                vrcholK = vrcholK/7;
                pomoc++;
            }
            std::string ret1 = canonical_sparse6(G1);


            //ordered verzia s find
          /*  if (newGraphs.find(ret1) == newGraphs.end()) {
                newGraphs.insert(ret1);
                //std::cout << ret1 << "\n";
                if (stupen == maxStupen) {
                    fout << write_sparse6(G1, false);
                    fout << std::endl;
                }
                generateGraphs2(copy_identical(G1),newKomponentyKruznice, stupen+1, maxStupen);
            }*/

          //unordered verzia / ordered verzia bez find
            auto p = newGraphs.insert(ret1);
            if (p.second == true){
                if (stupen == maxStupen) {
                    fout << write_sparse6(G1, false);
                    fout << std::endl;
                }
                generateGraphs2(copy_identical(G1),newKomponentyKruznice, stupen+1, maxStupen);
            }
        }
    }
}

int generateGraphs2for3() {
    newGraphs.clear();
    fout.open("3kruznice.txt");
    if (!fout)
        throw std::runtime_error("cannot write into file ");
    Graph G = Okuliare();
    generateGraphs2(copy_identical(G),genKomponentyKruznice(2),2,2);
    fout.close();
    return newGraphs.size();
}

int generateGraphs2for4() {
    newGraphs.clear();
    fout.open("4kruznice.txt");
    if (!fout)
        throw std::runtime_error("cannot write into file ");
    Graph G = Okuliare();
    generateGraphs2(copy_identical(G),genKomponentyKruznice(2),2,3);
    fout.close();
    return newGraphs.size();
}

int generateGraphs2for5() {
    newGraphs.clear();
    fout.open("5kruznic.txt");
    if (!fout)
        throw std::runtime_error("cannot write into file ");
    Graph G = Okuliare();
    generateGraphs2(copy_identical(G),genKomponentyKruznice(2),2,4);
    fout.close();
    return newGraphs.size();
}




int main()
{
    //funkcia ktorá vygeneruje všetky neizomorfne grafy s tromi zapojenými kružnicami
     //std::cout << generateGraphs2for3();

    //funkcia ktorá vygeneruje všetky neizomorfne grafy so štyrmi zapojenými kružnicami
     std::cout << generateGraphs2for4();

    //funkcia ktorá vygeneruje všetky neizomorfne grafy s piatimi zapojenými kružnicami
    //std::cout << generateGraphs2for5();


}