#include <basic_impl.hpp>

#include <cassert>
#include <map>

#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;

//procedúra slúži na nahradenie vrcholu grafu 7 vrcholmi
void nahradVrchol7Vrcholmi(Graph &G, int i){
    deleteV(G, i);
    Graph Vrcholi(empty_graph(7));
    add_graph(G,Vrcholi,i);
}

//proceduúra slúži na vymenenie indexov vrcholol i a j v grafe G
void vymenVrchol (Graph &G, int i, int j ){

    if (j > i) {
        change_vertex_number(G, i, 100);
        change_vertex_number(G, j, i);
        change_vertex_number(G, 100, j);
    }
}

//prehladávanie do hĺbky
void DFSUtil(int v, bool visited[],Graph &G, std::map<int, int> &mapaSwitch, std::map<int, int> &mapaSwitchRev){
    visited[v] = true;
    int pozicia;
    for (auto &i : G[mapaSwitch[v]]) {
        pozicia= i.r2().n().to_int();
        if (!visited[mapaSwitchRev[pozicia]]){
            DFSUtil(mapaSwitchRev[pozicia], visited, G, mapaSwitch, mapaSwitchRev);
        }
    }
}

//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, std::map<int, int> &mapaSwitch, std::map<int, int> &mapaSwitchRev){

    bool* visited = new bool[G.order()];
    std::vector<int> Component;

    for (int i=0; i<G.order(); i++){
        visited[i]=false;
    }
    for (int v=0; v<G.order(); v++) {
        if (visited[v] == false) {
            DFSUtil(v, visited, G, mapaSwitch, mapaSwitchRev);
            Component.push_back(mapaSwitch[v]);
        }
    }
    delete[] visited;
    return Component;
}

// procedúra na vstupe dostane vstupný graf G, počet vrcholov, ktorý chceme nahradiť a hodnotu, kolkatý vrchol nahradzujeme
void generateGraphs(Graph G, int pocetVrcholov, int vrchol) {
    std::vector<int>::iterator it;
    //slúži na uchovavanie orbít vrcholov, ktoré možeme nahrádzať
    std::vector<int> sedmica;
    if (vrchol < pocetVrcholov) {

        int nahrad;
        int nahrad2;


        std::vector <Number> vertices;
        //indexy vrcholov grafu premapujeme *10 aby sa nám lahko dalo rozlišovať kružnice
        for (auto &i : G[(vrchol + 1) * 10]) {
            vertices.push_back(i.r2().n());
        }
            std::sort(vertices.begin(), vertices.end());
            Graph G3(copy_identical(G));
            nahradVrchol7Vrcholmi(G3, ((vrchol + 1) * 10));

            int noveVrcholy = 0;
            //spojíme naše novopridane vrcholy s pôvodným grafom
            for (auto v : vertices) {
                addE(G3, Location(((vrchol + 1) * 10 + noveVrcholy), v));
                noveVrcholy++;
            }

            std::vector<int> verticesPokus;
            std::vector<int> verticesPermuted;
            int vrcholKam, pom;
            Graph pomocnyGraf(copy_identical(finalnyPomocnyGraf));

            std::vector <std::vector<int>> generatory = automorfizmus(G3);
            for (const auto &permutacia : generatory) {
                for (auto &r : pomocnyGraf) {
                    verticesPokus = mapa[r.n().to_int()];
                    verticesPermuted.clear();

                    for (auto v : verticesPokus) {
                        verticesPermuted.push_back(permutacia[(v + (vrchol * 7))] - (vrchol * 7));
                    }
                    vrcholKam = mapaRev[verticesPermuted];
                    pom = 0;
                    for (auto &i : pomocnyGraf[r.n()]) {
                        if (i.r2().n().to_int() == vrcholKam) {
                            pom = 1;
                        }
                    }
                    if (pom == 0 && vrcholKam != r.n().to_int()) {
                        addE(pomocnyGraf, Location(r.n().to_int(), vrcholKam));
                    }
                }

            }
            std::vector<int> Komponenty = ConnectedComponents(grafPokus, mapaSwitch, mapaSwitchRev);

            for (auto Komponent : Komponenty) {
                Graph G1(copy_identical(G3));

                int predchadzajuciVrchol = 0;
                int prvyVrchol = (vrchol + 1) * 10;
                //7 nahradených vrcholov spájame do kružnice
                for (auto v : mapa[Komponent]) {
                    if (predchadzajuciVrchol > 0) {
                        addE(G1, Location(predchadzajuciVrchol, prvyVrchol + v));
                    }
                    predchadzajuciVrchol = prvyVrchol + v;
                }
                addE(G1, Location(predchadzajuciVrchol, prvyVrchol));


                std::string ret1 = canonical_sparse6(G1);

                if (newGraphs.find(ret1) == newGraphs.end()) {
                    sedmica.clear();
                    newGraphs.insert(ret1);
                    generateGraphs(copy_identical(G1), pocetVrcholov, vrchol + 1);
                    std::vector<int> cyklusOrbity;
                    if (vrchol + 1 < pocetVrcholov) {
                        //zistíme si orbity grafu G1
                        cyklusOrbity = Orbity(G1);
                        for (int i = (vrchol + 1) * 7; i < G1.order(); i++) {
                            int orbita = cyklusOrbity[i];
                            it = std::find(sedmica.begin(), sedmica.end(), orbita);
                            if (it == sedmica.end()) {
                                sedmica.push_back(orbita);
                                Graph G2(copy_identical(G1));
                                nahrad = (vrchol + 2) * 10;
                                nahrad2 = ((vrchol + 2) * 10) + (i - (vrchol + 1) * 7) * 10;
                                vymenVrchol(G2, nahrad, nahrad2);
                                generateGraphs(copy_identical(G2), pocetVrcholov, vrchol + 1);
                            }
                        }
                    }
                }

            }
        }
    }

int generateGraphs(Graph graphs) {
    generateGraphs(copy_identical(graphs),3,0);
    return newGraphs.size();
}



Graph Komplet8() {
    Graph G(complete_graph(8));
    for(int i=0; i<8; i++){
        change_vertex_number(G,i,(i+1)*10);
    }
    return G;
}


int main(){

    for (int i =0; i<=6; i++){
        verticesPokus.push_back(i);
    }
    int pokus, pom;
    Graph pomocnyGraf(empty_graph(0));

    //Vytvoríme si pomocny graf kde vrchl bude reprezentovať permutáciu vrcholo kružnice
    do
    {
        pokus = 0;
        for (auto v : verticesPokus) {
            pokus = pokus*10+v;
        }
        addV(pomocnyGraf, pokus);
        mapa[pokus] = verticesPokus;
        mapaRev[verticesPokus] = pokus;
    }
    while (std::next_permutation(verticesPokus.begin(), verticesPokus.end()));

    //Odstranujeme z grafu vrcholy, ktoré vzniknu kombinaciou posunti a reverzov
    for (auto &r : pomocnyGraf){
        verticesPokus = mapa[r.n().to_int()];
        for(int i=0; i<=6; i++){
            rotate(verticesPokus.begin(), verticesPokus.begin() + 1, verticesPokus.end());
            pokus = mapaRev[verticesPokus];
            if ( pokus != r.n().to_int()) {
                deleteV(pomocnyGraf, pokus);
                mapaRev[verticesPokus] = r.n().to_int();
            }
        }
        std::reverse(verticesPokus.begin()+1, verticesPokus.end());
        for(int i=0; i<=6; i++){
            rotate(verticesPokus.begin(), verticesPokus.begin() + 1, verticesPokus.end());
            pokus = mapaRev[verticesPokus];
            if ( pokus != r.n().to_int()) {
                deleteV(pomocnyGraf, pokus);
                mapaRev[verticesPokus] = r.n().to_int();
            }
        }
    }
    pom =0;
    //následne si naš pomocný graf prekopírujeme a naplníme si mapy
    for (auto &r : pomocnyGraf) {
        addV(finalnyPomocnyGraf, r.n().to_int());
        mapaSwitch[pom] = r.n().to_int();
        mapaSwitchRev[r.n().to_int()] = pom;
        pom++;
    }

    //TOTO je na generovanie
    std::cout << generateGraphs(Komplet8());

}
