#ifndef BA_GRAPH_ALGORITHMS_ISOMORPHISM_ISOMORPHISM_NAUTY_HPP
#define BA_GRAPH_ALGORITHMS_ISOMORPHISM_ISOMORPHISM_NAUTY_HPP

#include <map>
#include <stdlib.h>
#include <gtools.h>
#include <nausparse.h>
#include "../../basic_impl.hpp"
#include "../../operations.hpp"
#include "../../invariants/girth.hpp"
#include "../../io/graph6.hpp"
#include "../../io/print_nice.hpp"

using namespace ba_graph;

/**
 * Returns a sparse6 string of G in canonical form computed by nauty.
 *
 * DOES NOT WORK FOR GRAPHS WITH PARALLEL EDGES AND LOOPS
 */


void setColoredPartition(int n, int k, int* c, int* lab, int* ptn)
{
    /* loop over all colors to fill it */
    int cur_index = 0;
    int i,j;
    for ( i = 0; i < k; i++ )
    {
        for ( j = 0; j < n; j++ )
        {
            //std::cout << j <<"::"<< c[j]<<"/" << i<<"\n";
            if ( c[j] == i )
            {
                lab[cur_index] = j;
                ptn[cur_index] = 1;
                cur_index++;
            }
        }

        if (cur_index > 0)
        {
            ptn[cur_index - 1] = 0;
        }
    }

}

std::string canonical_sparse6(const Graph &G)
{
#ifdef BA_GRAPH_DEBUG
    //assert(!has_loop(G));
    //assert(!has_parallel_edge(G));
#endif

    //JZ/////////
    int n = G.order();
    int ne = G.size();
    bool l_has_loop = has_loop(G);
    bool l_has_parallel_edge = has_parallel_edge(G);
    static DEFAULTOPTIONS_SPARSEGRAPH( options);
    options.defaultptn = TRUE;
    options.getcanon = TRUE;
    options.digraph = FALSE;
    int k = 1;
    std::vector<int> velkost(n+ne);
    int *c = velkost.data();
    //int *c = new int[n+ne];
    int maxId=0;
    for (int i=0 ; i < n+ne; i++) {
        c[i]=0;
    }
    Graph G1(createG());
    if(l_has_loop||l_has_parallel_edge){
        Factory f;
        Graph G2= std::move(copy_other_factory(G, f));
        options.defaultptn = FALSE;
        k = 2;
        std::map<std::pair<Vertex,Vertex>,int> existEdges;

        for (auto &r : G) {
            if (r.n().to_int()> maxId){
                maxId = r.n().to_int();
            }
            addV(G1,r.n());
        }

        for (auto ii : G.list(RP::all(), IP::primary())) {
            int ui = ii->n1().to_int();
            int vi = ii->n2().to_int();
            Vertex uu = ii->v1();
            Vertex vv = ii->v2();
            std::pair<Vertex,Vertex> testedEdge;
            if (ui <= vi) {
                testedEdge = std::pair(uu,vv);
            } else {
                testedEdge = std::pair(vv,uu);
            }
            if (existEdges.find(testedEdge) == existEdges.end()){
                existEdges[testedEdge] = 0;
                if(ui==vi){
                    c[ii->n1().to_int()] = 1;
                } else {
                    if (ui <= vi) {
                        addE(G1, Location(ui,vi));
                    } else {
                        addE(G1, Location(vi,ui));
                    }
                }
            } else {
                existEdges[testedEdge]++;
                maxId++;
                Vertex addedVertex = createV();
                c[G1.order()] = 1+existEdges[testedEdge];
                if (k <= (1+existEdges[testedEdge])) {
                    k= 2+existEdges[testedEdge];
                }
                addV(G1,addedVertex,maxId);
                addMultipleE(G1, Locs({{ui,maxId},{maxId,vi}}));
            }
        }
        std::cout << G1.order()<<"\n";
      for ( int j = 0; j < G1.order(); j++ )
        {
            std::cout << j <<":c:"<< c[j]<<"\n";
        }
    }

    std::string s;
    if (l_has_loop||l_has_parallel_edge) {  n= G1.order(); s = write_sparse6(G1, false); //deleteGraph(G1);
    }
    else { s = write_sparse6(G, false);
    }

    char *Gs6 = new char[s.length() + 1];
    std::copy(s.begin(), s.end(), Gs6);
    Gs6[s.length()] = '\0';

    sparsegraph* g = (sparsegraph*)malloc(sizeof(sparsegraph));
    SG_INIT((*g));
    int num_loops;

    stringtosparsegraph(Gs6, g, &num_loops);
    delete[] Gs6;



    int m = (n + WORDSIZE - 1) / WORDSIZE;
    nauty_check(WORDSIZE, m, n, NAUTYVERSIONID);

    DYNALLSTAT(int, lab, lab_n);
    DYNALLSTAT(int, ptn, ptn_n);
    DYNALLSTAT(int, orbits, orbits_n);
    DYNALLOC1(int, lab, lab_n, n, "malloc");
    DYNALLOC1(int, ptn, ptn_n, n, "malloc");
    DYNALLOC1(int, orbits, orbits_n, n, "malloc");



    DYNALLSTAT(setword, workspace, worksize);
    DYNALLOC1(setword, workspace, worksize, 50 * m, "malloc");

    sparsegraph canonical_g;


    if (k > 0) {
        setColoredPartition(n,k, c, lab, ptn);
    }

    SG_INIT(canonical_g);
//    for ( int j = 0; j < n; j++ )
//    {
//        std::cout << j <<":"<< lab[j]<<"/" << ptn[j]<<"\n";
//    }

    statsblk stats;
    //sparsenauty( g,lab,ptn,orbits,&options,&stats,&canonical_g);
    nauty((graph*) g, lab, ptn, NULL, orbits, &options, &stats, workspace, 50 * m, m, n, (graph*) &canonical_g);



    sortlists_sg(&canonical_g);


    std::string result(sgtos6(&canonical_g));


   /* for ( int j = 0; j < n; j++ )
    {
        std::cout << j <<":::"<< lab[j]<<"/" << orbits[j]<<"\n";
    }*/


    DYNFREE(workspace, worksize);
    DYNFREE(lab,lab_n);
    DYNFREE(ptn,ptn_n);
    DYNFREE(orbits,orbits_n);
    SG_FREE(canonical_g);
    SG_FREE((*g));
    free(g);


    result.pop_back();
    return result;
}


//------------------------------------------------------------------------------------------

int* canonicalOrbits(const Graph &G)
{
#ifdef BA_GRAPH_DEBUG
    //assert(!has_loop(G));
    //assert(!has_parallel_edge(G));
#endif

    //JZ/////////
    int n = G.order();
    int ne = G.size();
    bool l_has_loop = has_loop(G);
    bool l_has_parallel_edge = has_parallel_edge(G);
    static DEFAULTOPTIONS_SPARSEGRAPH( options);
    options.defaultptn = TRUE;
    options.getcanon = TRUE;
    options.digraph = FALSE;
    int k = 1;
    int *c = new int[n+ne];
    int maxId=0;
    for (int i=0 ; i < n+ne; i++) {
        c[i]=0;
    }
    Graph G1(createG());
    if(l_has_loop||l_has_parallel_edge){
        Factory f;
        Graph G2= std::move(copy_other_factory(G, f));
        options.defaultptn = FALSE;
        k = 2;
        std::map<std::pair<Vertex,Vertex>,int> existEdges;

        for (auto &r : G) {
            if (r.n().to_int()> maxId){
                maxId = r.n().to_int();
            }
            addV(G1,r.n());
        }

        for (auto ii : G.list(RP::all(), IP::primary())) {
            int ui = ii->n1().to_int();
            int vi = ii->n2().to_int();
            Vertex uu = ii->v1();
            Vertex vv = ii->v2();
            std::pair<Vertex,Vertex> testedEdge;
            if (ui <= vi) {
                testedEdge = std::pair(uu,vv);
            } else {
                testedEdge = std::pair(vv,uu);
            }
            if (existEdges.find(testedEdge) == existEdges.end()){
                existEdges[testedEdge] = 0;
                if(ui==vi){
                    c[ii->n1().to_int()] = 1;
                } else {
                    if (ui <= vi) {
                        addE(G1, Location(ui,vi));
                    } else {
                        addE(G1, Location(vi,ui));
                    }
                }
            } else {
                existEdges[testedEdge]++;
                maxId++;
                Vertex addedVertex = createV();
                c[G1.order()] = 1+existEdges[testedEdge];
                if (k <= (1+existEdges[testedEdge])) {
                    k= 2+existEdges[testedEdge];
                }
                addV(G1,addedVertex,maxId);
                addMultipleE(G1, Locs({{ui,maxId},{maxId,vi}}));
            }
        }
        std::cout << G1.order()<<"\n";
        for ( int j = 0; j < G1.order(); j++ )
        {
            std::cout << j <<":c:"<< c[j]<<"\n";
        }
    }

    std::string s;
    if (l_has_loop||l_has_parallel_edge) {  n= G1.order(); s = write_sparse6(G1, false); //deleteGraph(G1);
    }
    else { s = write_sparse6(G, false);
    }

    char *Gs6 = new char[s.length() + 1];
    std::copy(s.begin(), s.end(), Gs6);
    Gs6[s.length()] = '\0';

    sparsegraph* g = (sparsegraph*)malloc(sizeof(sparsegraph));
    SG_INIT((*g));
    int num_loops;

    stringtosparsegraph(Gs6, g, &num_loops);
    delete[] Gs6;



    int m = (n + WORDSIZE - 1) / WORDSIZE;
    nauty_check(WORDSIZE, m, n, NAUTYVERSIONID);

    DYNALLSTAT(int, lab, lab_n);
    DYNALLSTAT(int, ptn, ptn_n);
    DYNALLSTAT(int, orbits, orbits_n);
    DYNALLOC1(int, lab, lab_n, n, "malloc");
    DYNALLOC1(int, ptn, ptn_n, n, "malloc");
    DYNALLOC1(int, orbits, orbits_n, n, "malloc");



    DYNALLSTAT(setword, workspace, worksize);
    DYNALLOC1(setword, workspace, worksize, 50 * m, "malloc");

    sparsegraph canonical_g;


    if (k > 0) {
        setColoredPartition(n,k, c, lab, ptn);
    }

    SG_INIT(canonical_g);
//    for ( int j = 0; j < n; j++ )
//    {
//        std::cout << j <<":"<< lab[j]<<"/" << ptn[j]<<"\n";
//    }

    statsblk stats;
    //sparsenauty( g,lab,ptn,orbits,&options,&stats,&canonical_g);
    nauty((graph*) g, lab, ptn, NULL, orbits, &options, &stats, workspace, 50 * m, m, n, (graph*) &canonical_g);




   /*  for ( int j = 0; j < n; j++ )
     {
         std::cout << j <<":::"<< lab[j]<<"/" << orbits[j]<<"\n";
     }*/
    int* pomoc = new int[n];
    for ( int j = 0; j < n; j++ ){
        pomoc[lab[j]] = j;
    };
   /* for ( int j = 0; j < n; j++ )
    {
        std::cout <<pomoc[j] << " ";
    }/
    int x = std::distance(pomoc, std::find(pomoc, pomoc + n, 0));
    std::cout <<"\n" << x;*/
    int* result = new int[n];
    for ( int j = 0; j < n; j++ ){
        result[j] = pomoc[orbits[j]];
    };



    DYNFREE(workspace, worksize);
    DYNFREE(lab,lab_n);
    DYNFREE(ptn,ptn_n);
    DYNFREE(orbits,orbits_n);
    SG_FREE(canonical_g);
    SG_FREE((*g));
    free(g);

    return result;
}


std::vector<int> Orbity(const Graph &G)
{
#ifdef BA_GRAPH_DEBUG
    //assert(!has_loop(G));
    //assert(!has_parallel_edge(G));
#endif

    //JZ/////////
    int n = G.order();
    static DEFAULTOPTIONS_SPARSEGRAPH( options);
    options.defaultptn = TRUE;
    options.getcanon = TRUE;
    options.digraph = FALSE;

    std::string s;
    s = write_sparse6(G, false);

    char *Gs6 = new char[s.length() + 1];
    std::copy(s.begin(), s.end(), Gs6);
    Gs6[s.length()] = '\0';

    sparsegraph* g = (sparsegraph*)malloc(sizeof(sparsegraph));
    SG_INIT((*g));
    int num_loops;

    stringtosparsegraph(Gs6, g, &num_loops);
    delete[] Gs6;



    int m = (n + WORDSIZE - 1) / WORDSIZE;
    nauty_check(WORDSIZE, m, n, NAUTYVERSIONID);

    DYNALLSTAT(int, lab, lab_n);
    DYNALLSTAT(int, ptn, ptn_n);
    DYNALLSTAT(int, orbits, orbits_n);
    DYNALLOC1(int, lab, lab_n, n, "malloc");
    DYNALLOC1(int, ptn, ptn_n, n, "malloc");
    DYNALLOC1(int, orbits, orbits_n, n, "malloc");



    DYNALLSTAT(setword, workspace, worksize);
    DYNALLOC1(setword, workspace, worksize, 50 * m, "malloc");

    sparsegraph canonical_g;

    SG_INIT(canonical_g);

    statsblk stats;
    nauty((graph*) g, lab, ptn, NULL, orbits, &options, &stats, workspace, 50 * m, m, n, (graph*) &canonical_g);

   // std::vector<int> velkostN(n);
    //int *result = velkostN.data();

    //int* result = new int[n];

    std::vector<int> result;
    for ( int j = 0; j < n; j++ ){
        result.push_back( orbits[j]);
    };

    DYNFREE(workspace, worksize);
    DYNFREE(lab,lab_n);
    DYNFREE(ptn,ptn_n);
    DYNFREE(orbits,orbits_n);
    SG_FREE(canonical_g);
    SG_FREE((*g));
    free(g);

    return result;
}

// TODO edge orbits?

/**
 * Returns a list of orbits computed by nauty. Assumes that the graph G has vertices numbered contiguously from 0.
 *
 * DOES NOT WORK FOR GRAPHS WITH PARALLEL EDGES AND LOOPS
 */
std::map<Number, Number> orbits_nauty(const Graph &G)
{
#ifdef BA_GRAPH_DEBUG
    assert(!has_loop(G));
    assert(!has_parallel_edge(G));
#endif
    std::string s = write_sparse6(G, false);
    char *Gs6 = new char[s.length() + 1];
    std::copy(s.begin(), s.end(), Gs6);
    Gs6[s.length()] = '\0';

    sparsegraph* g = (sparsegraph*)malloc(sizeof(sparsegraph));
    SG_INIT((*g));
    int num_loops;
    stringtosparsegraph(Gs6, g, &num_loops);
    delete[] Gs6;

    int n = g->nv; // G.order()

    int m = (n + WORDSIZE - 1) / WORDSIZE;
    nauty_check(WORDSIZE, m, n, NAUTYVERSIONID);

    DYNALLSTAT(int, lab, lab_n);
    DYNALLSTAT(int, ptn, ptn_n);
    DYNALLSTAT(int, orbits, orbits_n);
    DYNALLOC1(int, lab, lab_n, n, "malloc");
    DYNALLOC1(int, ptn, ptn_n, n, "malloc");
    DYNALLOC1(int, orbits, orbits_n, n, "malloc");

    static DEFAULTOPTIONS_SPARSEGRAPH( options);
    options.defaultptn = TRUE;
    options.getcanon = TRUE;
    options.digraph = FALSE;

    DYNALLSTAT(setword, workspace, worksize);
    DYNALLOC1(setword, workspace, worksize, 50 * m, "malloc");

    sparsegraph canonical_g;
    SG_INIT(canonical_g);

    statsblk stats;
    nauty((graph*) g, lab, ptn, NULL, orbits, &options, &stats, workspace, 50 * m, m, n, (graph*) &canonical_g);

    std::map<Number, Number> result;
    for (int i = 0; i < n; ++i)
        result[i] = orbits[i];

    DYNFREE(workspace, worksize);
    DYNFREE(lab,lab_n);
    DYNFREE(ptn,ptn_n);
    DYNFREE(orbits,orbits_n);
    SG_FREE(canonical_g);
    SG_FREE((*g));
    free(g);

    return result;
}

bool are_isomorphic_nauty(const Graph &G, const Graph &H)
{
    std::string Gs6 = canonical_sparse6(G);
    std::string Hs6 = canonical_sparse6(H);
    std::cout  <<"Gs6:::  "<< Gs6 <<"\n";
    std::cout  <<"Hs6:::  "<< Hs6 <<"\n";
    if(Gs6 == Hs6){
        if(G.size()==H.size()){
            return true;
        } else {
            return false;
        }
    } else {
        return false;
    }
}

#endif