
#include "vertex_star_dfs.h"

static DEFAULTOPTIONS(options);

extern int timeval_subtract(struct timeval *result, struct timeval *t2, struct timeval *t1);

VERTEX_STAR_DFS::VERTEX_STAR_DFS(int a,int b, int c, int d, int e, int f, int g, int h) {

    int i, j;
    struct timeval tvBegin, tvEnd, tvDiff;

    perm_pole_2_fak = 2;
    perm_pole_3_fak = 6;
    perm_pole_4_fak = 24;
    perm_pole_5_fak = 120;
    perm_pole_6_fak = 720;
    perm_pole_tmp = 0;

    faktorizacia_pocet = 0;

    option.SEMI_CHECK = a; 
    option.SEMI_POLOHA_POCAS = b; 
    option.SEMI_POLOHA_KONIEC = c; 
    option.VYPIS = d; 
    option.NAUTY = e; 
    option.NAUTY_POLOHA_KONIEC = g; 
    option.NAUTY_POLOHA_POCAS = f;
    option.NAUTY_D_TABULKA = h;

    zapis_iba_do_labu = 0;

    NaplnDefault();

    for (i = 0; i < POCET_FARIEB; i++) {
        su_ofarbene_global[nove_hrany[0][perm_susedia[0][i]]] = i + 1;
        ofarbenie_perm_vrcholov_global[perm_susedia[0][i]][0] = i + 1;
        ofarbenie_perm_vrcholov_global[0][i] = i + 1;
    }

    gettimeofday(&tvBegin, NULL);
    najdi_faktorizaciu(1, ofarbenie_perm_vrcholov_global, su_ofarbene_global);
    gettimeofday(&tvEnd, NULL);
    timeval_subtract(&tvDiff, &tvEnd, &tvBegin);

    

    if (option.VYPIS == 1) {
        for (j = 0; j < faktorizacia_pocet; j++) {
            for (i = 0; i < POCET_VRCHOLOV; i++) {
                printf("%d ", faktorizacia[j]->ofarbenie[i]);
            }
            printf("\n");
        }
    }

    printf("Pocet vysledkov: %d\n", faktorizacia_pocet);
    printf("Doba trvania: %ld.%06ld (sekund)\n", tvDiff.tv_sec, tvDiff.tv_usec);
}

VERTEX_STAR_DFS::~VERTEX_STAR_DFS() {
}

void VERTEX_STAR_DFS::najdi_faktorizaciu(int vrchol_lokal, int ofarbenie_perm_vrcholov[POCET_PERM_VRCHOLOV][POCET_FARIEB], int su_ofarbene_lokal[POCET_VRCHOLOV]) {

    int indexi_lokal[FAKTORIAL_FARIEB];
    int farba[POCET_FARIEB];
    int pocet_vacsich_susedov = 0;
    int ofarbenie_perm_vrcholov_lokal[POCET_PERM_VRCHOLOV][POCET_FARIEB];
    int su_ofarbene_lokal_funk[POCET_VRCHOLOV];

    unsigned int i, j, k, l;

    for (i = 0; i < POCET_PERM_VRCHOLOV; i++) {
        for (j = 0; j < POCET_FARIEB; j++) {
            ofarbenie_perm_vrcholov_lokal[i][j] = ofarbenie_perm_vrcholov[i][j];
        }
    }
    for (i = 0; i < FAKTORIAL_FARIEB; i++) {
        indexi_lokal[i] = 0;
    }
    for (i = 0; i < POCET_VRCHOLOV; i++) {
        su_ofarbene_lokal_funk[i] = su_ofarbene_lokal[i];
    }
    if (vrchol_lokal == POCET_PERM_VRCHOLOV - 2) {
        for (i = 0; i < POCET_FARIEB; i++)
            farba[i] = 0;
       for (i = 1; i <= POCET_FARIEB; i++) {
            for (j = 0; j < POCET_FARIEB; j++) {
                if (ofarbenie_perm_vrcholov_lokal[vrchol_lokal][j] == i) {
                    break;
                }
            }
            if (j == POCET_FARIEB) {
                su_ofarbene_lokal_funk[nove_hrany[vrchol_lokal][vrchol_lokal + 1]] = i;
                ofarbenie_perm_vrcholov_lokal[vrchol_lokal][POCET_FARIEB - 1] = i;
                ofarbenie_perm_vrcholov_lokal[vrchol_lokal + 1][POCET_FARIEB - 1] = i;
                break;
            }
        }
        if ((option.SEMI_CHECK > 0) && (option.SEMI_POLOHA_KONIEC == 1) && (check_P1F(su_ofarbene_lokal_funk, vrchol_lokal) == -1)) {
            return;
        }
        faktorizacia[faktorizacia_pocet] = (item_faktorizacia *) malloc(sizeof (item_faktorizacia));
        l = 0;
        for (i = 1; i <= POCET_FARIEB; i++) {
            for (j = 0; j < POCET_VRCHOLOV; j++) {
                if (su_ofarbene_lokal_funk[j] == i) {
                    faktorizacia[faktorizacia_pocet]->ofarbenie[l] = j;
                    l++;
                }
            }
        }
        if (option.NAUTY_D_TABULKA == 1) {
            vyrataj_D_tabulku(faktorizacia_pocet);
            if (faktorizacia_pocet == 0) {
                zapis_iba_do_labu = 1;
                RunNautyKoniec(su_ofarbene_lokal_funk);
                zapis_iba_do_labu = 0;
            }
            k = 0;
            for (j = 0; j < faktorizacia_pocet; j++) {
                k = 0;
                i = 0;
                while (faktorizacia[faktorizacia_pocet]->D_tabulka[i] != 0) {
                    if (faktorizacia[j]->D_tabulka[i] != faktorizacia[faktorizacia_pocet]->D_tabulka[i]) {
                        k = 1;
                        break;
                    }
                    i++;
                }
                if (k == 0) {
                    if ((option.NAUTY == 1) && (option.NAUTY_POLOHA_KONIEC == 1)) {
                        if (RunNautyKoniec(su_ofarbene_lokal_funk) == -1) {
                            faktorizacia[faktorizacia_pocet] = NULL;
                            return;
                        }
                    }
                    break;
                }
            }
            if (k == 1) {
                zapis_iba_do_labu = 1;
                RunNautyKoniec(su_ofarbene_lokal_funk);
                zapis_iba_do_labu = 0;
            }
        } else {
            if ((option.NAUTY == 1) && (option.NAUTY_POLOHA_KONIEC == 1)) {
                if (RunNautyKoniec(su_ofarbene_lokal_funk) == -1) {
                    faktorizacia[faktorizacia_pocet] = NULL;
                    return;
                }
            }
        }
        faktorizacia_pocet++;
     return;
    } else {
        for (k = 0; k < FAKTORIAL_FARIEB; k++) {
            pocet_vacsich_susedov = 0;
            for (i = 0; i < POCET_FARIEB; i++) {
                if (perm_susedia[vrchol_lokal][i] < vrchol_lokal) {
                    if (indexi_lokal[k] == 0) {
                        if (su_ofarbene_lokal_funk[nove_hrany[vrchol_lokal][perm_susedia[vrchol_lokal][i]]] != perm_pole_3[k][i]) {
                            indexi_lokal[k] = 1;
                            goto endindex;
                        }
                    }
                } else if (perm_susedia[vrchol_lokal][i] > vrchol_lokal) {
                    pocet_vacsich_susedov++;
                    if (indexi_lokal[k] == 0) {
                        for (l = 0; l < POCET_FARIEB; l++) {
                            if ((ofarbenie_perm_vrcholov_lokal[perm_susedia[vrchol_lokal][i]][l] != 0) && (ofarbenie_perm_vrcholov_lokal[perm_susedia[vrchol_lokal][i]][l] == perm_pole_3[k][i])) {
                                indexi_lokal[k] = 1;
                                goto endindex;
                            }
                        }
                    }
                }
            }
            for (i = 0; i < pocet_vacsich_susedov; i++) {
                su_ofarbene_lokal_funk[nove_hrany[vrchol_lokal][perm_susedia[vrchol_lokal][POCET_FARIEB - pocet_vacsich_susedov + i]]] = perm_pole_3[k][POCET_FARIEB - pocet_vacsich_susedov + i];
            }

            i--;
            if ((option.SEMI_CHECK > 0) && (option.SEMI_POLOHA_POCAS == 1) && (check_P1F(su_ofarbene_lokal_funk, vrchol_lokal) == -1)) {
                indexi_lokal[k] = 1;
                goto endindex;
            }
            if ((option.NAUTY == 1) && (option.NAUTY_POLOHA_POCAS == 1) && (indexi_lokal[k] == 0) && (RunNautyPocas(su_ofarbene_lokal_funk, vrchol_lokal) == -1)) {
                indexi_lokal[k] = 1;
            }
            for (i = 0; i < pocet_vacsich_susedov; i++) {
                su_ofarbene_lokal_funk[nove_hrany[vrchol_lokal][perm_susedia[vrchol_lokal][POCET_FARIEB - pocet_vacsich_susedov + i]]] = 0;
            }
            if (indexi_lokal[k] == 0) {
                for (i = 0; i < POCET_FARIEB; i++) {
                    ofarbenie_perm_vrcholov_lokal[vrchol_lokal][i] = perm_pole_3[k][i];
                }
                for (i = POCET_FARIEB - pocet_vacsich_susedov; i < POCET_FARIEB; i++) {
                    for (j = 0; j < POCET_FARIEB; j++) {
                        if (perm_susedia[perm_susedia[vrchol_lokal][i]][j] == vrchol_lokal) {
                            ofarbenie_perm_vrcholov_lokal[perm_susedia[vrchol_lokal][i]][j] = perm_pole_3[k][i];
                            break;
                        }
                    }
                }
                for (i = 0; i < pocet_vacsich_susedov; i++) {
                    su_ofarbene_lokal_funk[nove_hrany[vrchol_lokal][perm_susedia[vrchol_lokal][POCET_FARIEB - pocet_vacsich_susedov + i]]] = perm_pole_3[k][POCET_FARIEB - pocet_vacsich_susedov + i];
                }
                najdi_faktorizaciu(vrchol_lokal + 1, ofarbenie_perm_vrcholov_lokal, su_ofarbene_lokal_funk);

                for (i = 0; i < POCET_FARIEB; i++) {
                    ofarbenie_perm_vrcholov_lokal[vrchol_lokal][i] = 0;
                }
                for (i = POCET_FARIEB - pocet_vacsich_susedov; i < POCET_FARIEB; i++) {
                    for (j = 0; j < POCET_FARIEB; j++) {
                        if (perm_susedia[perm_susedia[vrchol_lokal][i]][j] == vrchol_lokal) {
                            ofarbenie_perm_vrcholov_lokal[perm_susedia[vrchol_lokal][i]][j] = 0;
                            break;
                        }
                    }
                }
                for (i = 0; i < pocet_vacsich_susedov; i++) {
                    su_ofarbene_lokal_funk[nove_hrany[vrchol_lokal][perm_susedia[vrchol_lokal][POCET_FARIEB - pocet_vacsich_susedov + i]]] = 0;
                }
            }
endindex:
            ;
        }
    }
}

int VERTEX_STAR_DFS::RunNautyKoniec(int su_ofarbene_lokal[POCET_VRCHOLOV]) {
    int i, j, k, l, o, pom, level;
    nvector ptn_lokal[POCET_VRCHOLOV];
    nvector lab_lokal[POCET_VRCHOLOV];
    permutation lab_lokal_upd[POCET_VRCHOLOV];

    unsigned int perm_nauty[POCET_VRCHOLOV][POCET_VRCHOLOV_FARBA];
    unsigned int ofarbenie_lokal[POCET_VRCHOLOV];

    for (i = 0; i < POCET_VRCHOLOV; i++) {
        ofarbenie_lokal[i] = 0;
    }

    l = 0;
    for (i = 1; i <= POCET_FARIEB; i++) {
        for (j = 0; j < POCET_VRCHOLOV; j++) {
            if (su_ofarbene_lokal[j] == i) {
                ofarbenie_lokal[l] = j;
                l++;
            }
        }
        if (i == 1) {
            level = l;
        }
    }

    for (i = 0; i < POCET_VRCHOLOV; i++) {
        if (su_ofarbene_lokal[i] == 0) {
            ofarbenie_lokal[l] = i;
            l++;
        }
    }

    k = 0;
    l = 0;
    for (i = 0; i < POCET_VRCHOLOV; i++) {

        ptn_lokal[i] = 1;
        lab_lokal[i] = ofarbenie_lokal[i];
        perm_nauty[l][k] = lab_lokal[i];
        k++;
        if (k == POCET_VRCHOLOV_FARBA) {
            l++;
            k = 0;
        }
    }

    for (i = 1; i <= POCET_FARIEB; i++) {
        ptn_lokal[(level * i) - 1] = 0;
    }
    nauty(g, lab_lokal, ptn_lokal, NILSET, orbits, &options, &stats, workspace, 50 * MAXM, M, POCET_VRCHOLOV, cg);

    pom = lab_farby_level_pocet;

    if (zapis_iba_do_labu == 1) {
        pom = 0;
    }

    for (i = 0; i < pom; i++) {
        for (j = 0; j < POCET_VRCHOLOV; j++) {
            lab_lokal_upd[j] = lab_farby_level[i][j];
        }
        updatecan(g, cgi, lab_lokal_upd, 0, M, POCET_VRCHOLOV);
        for (j = POCET_VRCHOLOV * POCET_SUSEDOV; j >= 0; j--) {
            if (cgi[j] != cg[j]) {
                break;
            }
        }
        if (j < 0) {
            return -1;
        }
    }
    switch (POCET_FARIEB) {
        case 3:
            for (j = 0; j < perm_pole_3_fak; j++) {
                if (j != 0) {
                    o = 0;
                    for (k = 0; k < POCET_FARIEB; k++) {
                        for (l = 0; l < POCET_VRCHOLOV_FARBA; l++) {
                            lab_lokal[o] = perm_nauty[perm_pole_3[j][k] - 1][l];
                            o++;
                        }
                    }
                    nauty(g, lab_lokal, ptn_lokal, NILSET, orbits, &options, &stats, workspace, 50 * MAXM, M, POCET_VRCHOLOV, cg);
                }
                for (i = 0; i < POCET_VRCHOLOV; i++) {
                    lab_farby_level[lab_farby_level_pocet][i] = lab_lokal[i];
                }
                lab_farby_level_pocet++;
            }
            break;
        case 4:
            for (j = 0; j < perm_pole_4_fak; j++) {
                if (j != 0) {
                    o = 0;
                    for (k = 0; k < POCET_FARIEB; k++) {
                        for (l = 0; l < POCET_VRCHOLOV_FARBA; l++) {
                            lab_lokal[o] = perm_nauty[perm_pole_4[j][k] - 1][l];
                            o++;
                        }
                    }
                    nauty(g, lab_lokal, ptn_lokal, NILSET, orbits, &options, &stats, workspace, 50 * MAXM, M, POCET_VRCHOLOV, cg);
                }
                for (i = 0; i < POCET_VRCHOLOV; i++) {
                    lab_farby_level[lab_farby_level_pocet][i] = lab_lokal[i];
                }
                lab_farby_level_pocet++;
            }
            break;
    }
    return 1;
}

int VERTEX_STAR_DFS::RunNautyPocas(int su_ofarbene_lokal[POCET_VRCHOLOV], int vrchol) {
    int i, j, k, l, o, n, pom, level, tmp, tmp1, tmp2;
    nvector ptn_lokal[POCET_VRCHOLOV];
    nvector ptn_tmp[POCET_VRCHOLOV];
    nvector lab_lokal[POCET_VRCHOLOV];
    unsigned int lab_tmp[POCET_VRCHOLOV];
    permutation lab_lokal_upd[POCET_VRCHOLOV];

    int perm_nauty[POCET_FARIEB][POCET_VRCHOLOV_FARBA];
    unsigned int ofarbenie_lokal[POCET_VRCHOLOV];

    for (i = 0; i < POCET_VRCHOLOV; i++) {
        ofarbenie_lokal[i] = 0;
    }
    for (i = 0; i < POCET_FARIEB; i++) {
        for (j = 0; j < POCET_VRCHOLOV_FARBA; j++) {
            perm_nauty[i][j] = -1;
        }
    }
    l = 0;
    for (i = 1; i <= POCET_FARIEB; i++) {
        k = 0;
        for (j = 0; j < POCET_VRCHOLOV; j++) {
            if (su_ofarbene_lokal[j] == i) {
                ofarbenie_lokal[l] = j;
                perm_nauty[i - 1][k] = j;
                l++;
                k++;
            }
        }

        if (i == 1) {
            level = l;
        }
    }
    for (i = 0; i < POCET_VRCHOLOV; i++) {
        if (su_ofarbene_lokal[i] == 0) {
            ofarbenie_lokal[l] = i;
            l++;
        }
    }

    k = 0;
    l = 0;
    for (i = 0; i < POCET_VRCHOLOV; i++) {

        ptn_lokal[i] = 1;
        lab_lokal[i] = ofarbenie_lokal[i];
        if (k == POCET_VRCHOLOV_FARBA) {
        }
    }
    k = 0;
    tmp2 = 1000;
    tmp = 0;
    n = 0;
    for (i = 0; i < POCET_FARIEB; i++) {
        for (j = 0; j < POCET_VRCHOLOV_FARBA; j++) {
            if (perm_nauty[i][j] == -1) {
                k += j - 1;
                ptn_lokal[k] = 0;
                k++;
                tmp += j;
                break;
            }
        }
    }

    ptn_lokal[POCET_VRCHOLOV - 1] = 0;

    nauty(g, lab_lokal, ptn_lokal, NILSET, orbits, &options, &stats, workspace, 50 * MAXM, M, POCET_VRCHOLOV, cg);

    pom = lab_farby_level_pocet_pocas[vrchol][tmp];

    for (i = 0; i < pom; i++) {
        for (j = 0; j < POCET_VRCHOLOV; j++) {
            lab_lokal_upd[j] = lab_farby_level_pocas[vrchol][tmp][i][j];
        }
        updatecan(g, cgi, lab_lokal_upd, 0, M, POCET_VRCHOLOV);
        for (j = POCET_VRCHOLOV * POCET_SUSEDOV; j >= 0; j--) {
            if (cgi[j] != cg[j]) {
                break;
            }
        }
        if (j < 0) {
            return -1;
        }
    }
    switch (POCET_FARIEB) {
        case 3:
            for (j = 0; j < perm_pole_3_fak; j++) {

                if (j != 0) {
                    for (i = 0; i < POCET_VRCHOLOV; i++) {
                        ptn_tmp[i] = 1;
                    }
                    o = 0;
                    n = 0;
                    tmp2 = 1000;
                    tmp = 0;
                    for (k = 0; k < POCET_FARIEB; k++) {
                        for (l = 0; l < POCET_VRCHOLOV_FARBA; l++) {
                            if (perm_nauty[perm_pole_3[j][k] - 1][l] == -1) {
                                n += l - 1;
                                ptn_tmp[n] = 0;
                                n++;
                                tmp += l;
                                break;
                            } else {
                                lab_lokal[o] = perm_nauty[perm_pole_3[j][k] - 1][l];
                                o++;
                            }

                        }
                    }
                    while (o < POCET_VRCHOLOV) {
                        lab_lokal[o] = ofarbenie_lokal[o];
                        o++;
                    }
                    nauty(g, lab_lokal, ptn_tmp, NILSET, orbits, &options, &stats, workspace, 50 * MAXM, M, POCET_VRCHOLOV, cg);
                }
                for (i = 0; i < POCET_VRCHOLOV; i++) {
                    lab_farby_level_pocas[vrchol][tmp][lab_farby_level_pocet_pocas[vrchol][tmp]][i] = lab_lokal[i];
                }
                lab_farby_level_pocet_pocas[vrchol][tmp]++;
            }
            break;
        case 4:
            for (j = 0; j < perm_pole_4_fak; j++) {

                if (j != 0) {
                    for (i = 0; i < POCET_VRCHOLOV; i++) {
                        ptn_tmp[i] = 1;
                    }
                    o = 0;
                    n = 0;
                    tmp2 = 1000;
                    tmp = 0;
                    for (k = 0; k < POCET_FARIEB; k++) {
                        for (l = 0; l < POCET_VRCHOLOV_FARBA; l++) {
                            if (perm_nauty[perm_pole_4[j][k] - 1][l] == -1) {
                                n += l - 1;
                                ptn_tmp[n] = 0;
                                n++;
                                tmp += l*tmp2;
                                tmp2 = tmp2 / 10;
                                break;
                            } else {
                                lab_lokal[o] = perm_nauty[perm_pole_4[j][k] - 1][l];
                                o++;
                            }
                        }
                    }
                    while (o < POCET_VRCHOLOV) {
                        lab_lokal[o] = ofarbenie_lokal[o];
                        o++;
                    }
                    nauty(g, lab_lokal, ptn_tmp, NILSET, orbits, &options, &stats, workspace, 50 * MAXM, M, POCET_VRCHOLOV, cg);
                }
                for (i = 0; i < POCET_VRCHOLOV; i++) {
                    lab_farby_level_pocas[vrchol][tmp][lab_farby_level_pocet_pocas[vrchol][tmp]][i] = lab_lokal[i];
                }
                lab_farby_level_pocet_pocas[vrchol][tmp]++;
            }
            break;
    }
    return 1;
}

extern int compare(const void * a, const void * b);

void VERTEX_STAR_DFS::vyrataj_D_tabulku(int akt_faktorizacia) {
    unsigned int i, j, k, index, prva_farba[POCET_VRCHOLOV_FARBA], akt_farba[POCET_VRCHOLOV_FARBA], dlzka_cyklu, dlzka_all_cyklov, pocet_cyklov;
    unsigned int A, S, l;
    int uplna_D_tabulka[VELKOST_D * POCET_VRCHOLOV / 4];

    for (i = 0; i < VELKOST_D * POCET_VRCHOLOV / 4; i++) {
        uplna_D_tabulka[i] = 0;
    }

    index = 0;
    for (i = 0; i < POCET_FARIEB; i++) {
        for (j = i + 1; j < POCET_FARIEB; j++) {
            index++;
            for (k = 0; k < POCET_VRCHOLOV_FARBA; k++) {
                akt_farba[k] = faktorizacia[akt_faktorizacia]->ofarbenie[j * POCET_VRCHOLOV_FARBA + k];
                prva_farba[k] = faktorizacia[akt_faktorizacia]->ofarbenie[i * POCET_VRCHOLOV_FARBA + k];
            }
            pocet_cyklov = 0;
            dlzka_all_cyklov = 0;

            do {
                dlzka_cyklu = 0;
                for (k = 0; k < POCET_VRCHOLOV_FARBA; k++) {
                    if (akt_farba[k] != -1) {
                        A = akt_farba[k];
                        akt_farba[k] = -1;
                        dlzka_cyklu = 1;
                        break;
                    }
                }
                do {
                    for (k = 0; k < POCET_SUSEDOV; k++) {
                        for (l = 0; l < POCET_VRCHOLOV_FARBA; l++) {
                            if (prva_farba[l] == default_susedia[A][k]) {
                                S = default_susedia[A][k];
                                prva_farba[l] = -1;
                                dlzka_cyklu++;
                                goto endk;
                            }
                        }
                    }
endk:
                    ;
                    A = -1;
                    for (k = 0; k < POCET_SUSEDOV; k++) {
                        for (l = 0; l < POCET_VRCHOLOV_FARBA; l++) {
                            if (akt_farba[l] == default_susedia[S][k]) {
                                A = default_susedia[S][k];
                                akt_farba[l] = -1;
                                dlzka_cyklu++;
                                goto endk1;
                            }
                        }
                    }
endk1:
                    ;

                } while (A != -1);
                uplna_D_tabulka[((index - 1) * POCET_VRCHOLOV / 4) + pocet_cyklov] = dlzka_cyklu;
                dlzka_all_cyklov += dlzka_cyklu;
                pocet_cyklov++;
            } while (dlzka_all_cyklov < POCET_PERM_VRCHOLOV);
        }
    }
    qsort(uplna_D_tabulka, VELKOST_D * POCET_VRCHOLOV / 4, sizeof (int), compare);
    for (i = 0; i < VELKOST_D * POCET_VRCHOLOV / 4; i++) {
        faktorizacia[akt_faktorizacia]->D_tabulka[i] = uplna_D_tabulka[i];
    }

}

inline int VERTEX_STAR_DFS::check_P1F(int su_ofarbene_lokal[POCET_VRCHOLOV], int vrchol) {

    int i, j;

    if (option.SEMI_CHECK == 1) {
        for (i = 2; i <= POCET_FARIEB; i++) {
            if (check_level_P1F(vrchol, 1, i, su_ofarbene_lokal) == -1) {
                return -1;
            }
        }
        return 1;
    } else {
        for (i = 1; i <= POCET_FARIEB; i++) {
            for (j = i + 1; j <= POCET_FARIEB; j++) {
                if (check_level_P1F(vrchol, i, j, su_ofarbene_lokal) == -1) {
                    return -1;
                }
            }
        }
        return 1;
    }
}

int VERTEX_STAR_DFS::check_level_P1F(unsigned int vrchol, unsigned int p_farba, unsigned int d_farba, int su_ofarbene_lokal[POCET_VRCHOLOV]) {

    int prva_farba[POCET_VRCHOLOV_FARBA], druha_farba[POCET_VRCHOLOV_FARBA];
    int A, S, dlzka_cyklu;
    unsigned int i, j, k, l, zaciatok;

    k = 0;
    l = 0;
    for (i = 0; i < POCET_VRCHOLOV; i++) {
        if (su_ofarbene_lokal[i] == p_farba) {
            prva_farba[k] = i;
            k++;
        } else if (su_ofarbene_lokal[i] == d_farba) {
            druha_farba[l] = i;
            l++;
        }
    }
    for (; l < POCET_VRCHOLOV_FARBA; l++) {
        druha_farba[l] = -1;
    }
    for (; k < POCET_VRCHOLOV_FARBA; k++) {
        prva_farba[k] = -1;
    }

    for (i = 0; i < POCET_FARIEB; i++) {
        if (su_ofarbene_lokal[nove_hrany[perm_susedia[vrchol][i]][vrchol]] == d_farba) {
            A = nove_hrany[perm_susedia[vrchol][i]][vrchol];
            zaciatok = A;
            break;
        }
    }

    dlzka_cyklu = 2;
    for (i = POCET_SUSEDOV; i != 0;) {
        --i;
        for (j = POCET_VRCHOLOV_FARBA; j != 0;) {
            --j;
            if (default_susedia[A][i] == prva_farba[j]) {
                S = default_susedia[A][i];
                prva_farba[j] = -1;
                goto end11;
            }
        }
    }
end11:
    ;

    for (i = POCET_SUSEDOV; i != 0;) {
        --i;
        for (j = POCET_VRCHOLOV_FARBA; j != 0;) {
            --j;
            if ((default_susedia[S][i] == druha_farba[j]) && (default_susedia[S][i] != A)) {
                A = default_susedia[S][i];
                druha_farba[j] = -1;
                goto end12;
            }
        }
    }
    if (A == zaciatok) {
        return A;
    }

end12:
    ;

    do {
        for (i = 0; i < POCET_SUSEDOV; i++) {
            for (j = 0; j < POCET_VRCHOLOV_FARBA; j++) {
                if (default_susedia[A][i] == prva_farba[j]) {
                    S = default_susedia[A][i];
                    prva_farba[j] = -1;
                    goto end13;
                }
            }
        }
        if (i == POCET_SUSEDOV) {
            return 1;
        }
end13:
        ;

        for (i = 0; i < POCET_SUSEDOV; i++) {
            for (j = 0; j < POCET_VRCHOLOV_FARBA; j++) {
                if (default_susedia[S][i] == druha_farba[j]) {
                    A = default_susedia[S][i];
                    druha_farba[j] = -1;
                    goto end14;
                }
            }
        }
        dlzka_cyklu = POCET_PERM_VRCHOLOV;
        break;
end14:
        ;
        dlzka_cyklu++;
        dlzka_cyklu++;
    } while (A != zaciatok);
    if (dlzka_cyklu < POCET_PERM_VRCHOLOV) {
        return -1;
    } else {
        return vrchol;
    }
}

void VERTEX_STAR_DFS::NaplnDefault() {
    int i, j, k, l, tmp, hrana, sused, zhoda;
    int N = DIMENSION;
    int Value[DIMENSION];
    int perm_sused[DIMENSION];
    int vrchol[DIMENSION];

    options.writemarkers = FALSE;
    options.getcanon = TRUE;
    options.defaultptn = FALSE;
    options.writeautoms = FALSE;
    options.linelength = 100;
    options.cartesian = FALSE;

    m = M = (POCET_VRCHOLOV + WORDSIZE - 1) / WORDSIZE;

    int ofarbeni_bin_susedia[POCET_BIN_VRCHOLOV];


    /*
        for (i = 0; i < POCET_BIN_VRCHOLOV; i++) {
            for (j = 0; j < POCET_BIN_VRCHOLOV; j++) {
                nove_vrcholy[i][j] = -1;
            }
        }

        for (i = 0; i < POCET_BIN_VRCHOLOV; i++) {
            najdiSusedovDec(i);
            for (j = 0; j < DIMENSION; j++) {
                bin_susedia[i][j] = susedia_napln_def[j];
            }

        }
     */ //koor[0] = 0;
    /*    for (i = 0; i < POCET_FARIEB; i++) {
            ofarbeni_bin_susedia[bin_susedia[0][i]] = 1;
            ofarbenia_bin_vrcholov_global[bin_susedia[0][i]][i] = 0;
            ofarbenia_bin_vrcholov_global[0][i] = 0;
        }
     */ for (i = 0; i < POCET_VRCHOLOV; i++) {
        su_ofarbene_global[i] = 0;
    }
    /*
    pocet_koor = 1;
    for (i = 1; i < POCET_BIN_VRCHOLOV; i++) {

        if (ofarbeni_bin_susedia[i] != 1) {
            koor[pocet_koor] = i;
            pocet_koor++;
            for (j = 0; j < POCET_FARIEB; j++) {
                ofarbeni_bin_susedia[bin_susedia[i][j]] = 1;
            }
        }
    }
     */
    /*
        for (i=0; i<POCET_BIN_VRCHOLOV; i++) {
            for (j=0; j<POCET_BIN_VRCHOLOV; j++) {
                    printf(" %d ", nove_vrcholy[i][j]);

            }
            printf("\n");
        }
     */
    for (i = 0; i < POCET_PERM_VRCHOLOV; i++) {
        for (j = 0; j < POCET_FARIEB; j++) {
            ofarbenie_perm_vrcholov_global[i][j] = 0;
        }
    }
    hrana = 0;
    for (i = 0; i < POCET_BIN_VRCHOLOV; i++) {
        for (j = 0; j < DIMENSION; j++) {
            sused = bin_susedia[i][j];
            if ((nove_vrcholy[i][sused] == -1) && (nove_vrcholy[sused][i] == -1)) {
                nove_vrcholy[i][sused] = hrana;
                hrana++;
            }
        }
    }
    for (i = 0; i < POCET_BIN_VRCHOLOV; i++) {
        for (j = 0; j < DIMENSION; j++) {
            sused = bin_susedia[i][j];
            if ((nove_vrcholy[i][sused] != -1)) {
                nove_vrcholy[sused][i] = nove_vrcholy[i][sused];

            }
        }
    }


    for (i = 0; i < POCET_BIN_VRCHOLOV; i++) {
        for (j = i; j < POCET_BIN_VRCHOLOV; j++) {
            if (nove_vrcholy[i][j] != -1) {
                tmp = 0;
                for (k = 0; k < DIMENSION; k++) {
                    if (bin_susedia[i][k] != j) {
                        if (i < bin_susedia[i][k]) {
                            default_susedia[nove_vrcholy[i][j]][tmp] = nove_vrcholy[i][bin_susedia[i][k]];
                        } else {
                            default_susedia[nove_vrcholy[i][j]][tmp] = nove_vrcholy[bin_susedia[i][k]][i];
                        }
                        tmp++;
                    }


                }
                for (k = 0; k < DIMENSION; k++) {
                    if (bin_susedia[j][k] != i) {
                        if (j < bin_susedia[j][k]) {
                            default_susedia[nove_vrcholy[i][j]][tmp] = nove_vrcholy[j][bin_susedia[j][k]];
                        } else {
                            default_susedia[nove_vrcholy[i][j]][tmp] = nove_vrcholy[bin_susedia[j][k]][j];
                        }
                        tmp++;
                    }


                }

            }
        }
    }


    for (i = 0; i < POCET_VRCHOLOV; i++) {
        default_ofarbenie[i] = -1;
        ofarbenie[i] = -1;
        su_ofarbene[i] = -1;
    }



    default_ofarbenie[0] = 0;
    ofarbenie[0] = 0;
    su_ofarbene[ofarbenie[0]] = 0;
    for (i = 1; i < DIMENSION; i++) {
        default_ofarbenie[i * POCET_VRCHOLOV_FARBA] = default_susedia[0][i - 1];
        ofarbenie[i * POCET_VRCHOLOV_FARBA] = default_susedia[0][i - 1];
        su_ofarbene[ofarbenie[i * POCET_VRCHOLOV_FARBA]] = i;
    }


    for (i = 0; i < 2 * POCET_VRCHOLOV_FARBA - 1; i++) {
        cesta_global[i] = -1;
    }

    cesta_global[0] = 0;
    cesta_global[1] = bin_susedia[0][0];


    for (i = 0; i < POCET_VRCHOLOV; i++) {
        for (j = 0; j < POCET_SUSEDOV; j++) {
            for (k = j; k < POCET_SUSEDOV; k++) {
                if (default_susedia[i][j] < default_susedia[i][k]) {
                    tmp = default_susedia[i][j];
                    default_susedia[i][j] = default_susedia[i][k];
                    default_susedia[i][k] = tmp;
                }
            }

        }
    }


    /*for (i = 0; i < N; i++) {
      Value[i] = 0;
    }
    visit(Value, N, 0);
     */

    switch (N) {
        case 6:

            for (i = 0; i < N; i++) {
                Value[i] = 0;
            }
            perm_pole_tmp = 0;
            visit(Value, N, 0);
            N--;
        case 5:

            for (i = 0; i < N; i++) {
                Value[i] = 0;
            }
            perm_pole_tmp = 0;
            visit(Value, N, 0);
            N--;
        case 4:

            for (i = 0; i < N; i++) {
                Value[i] = 0;
            }
            perm_pole_tmp = 0;
            visit(Value, N, 0);
            N--;
        case 3:

            for (i = 0; i < N; i++) {
                Value[i] = 0;
            }
            perm_pole_tmp = 0;
            visit(Value, N, 0);
            N--;
        case 2:
            for (i = 0; i < N; i++) {
                Value[i] = 0;
            }
            perm_pole_tmp = 0;
            visit(Value, N, 0);
    }

    for (i = 0; i < POCET_PERM_VRCHOLOV; i++) {
        for (j = 0; j < DIMENSION; j++) {
            perm_vrcholy[i][j] = perm_pole_4[i][j];
        }
    }

    hrana = 0;
    for (i = 0; i < POCET_PERM_VRCHOLOV; i++) {
        for (j = 0; j < DIMENSION; j++) {
            perm_sused[j] = perm_vrcholy[i][j];
        }
        for (j = 1; j < DIMENSION; j++) { //vymeni 0ty a j-ty prvok v permutacii
            tmp = perm_sused[j];
            perm_sused[j] = perm_sused[0];
            perm_sused[0] = tmp;

            for (k = 0; k < POCET_PERM_VRCHOLOV; k++) {
                zhoda = 0;
                for (l = 0; l < DIMENSION; l++) {
                    if (perm_vrcholy[k][l] == perm_sused[l]) {
                        zhoda++;
                    }
                }
                if (zhoda == DIMENSION) { //k je index perm_suseda v perm_vrcholy
                    goto end31;
                }
            }
end31:
            ;
            perm_susedia[i][j - 1] = k;

            if ((vyskyt_perm_vrcholov[k] < DIMENSION - 1) && (vyskyt_perm_vrcholov[i] < DIMENSION - 1)) { //ak este moze, spravi novu hranu pre i,k
                vyskyt_perm_vrcholov[k]++;
                vyskyt_perm_vrcholov[i]++;
                for (l = 0; l < DIMENSION; l++) {
                    perm_hrany[hrana][l] = perm_vrcholy[i][l];
                    perm_hrany[hrana][l + DIMENSION] = perm_sused[l];
                    hrany[hrana][0] = i;
                    hrany[hrana][1] = k;
                    nove_hrany[i][k] = hrana;
                    nove_hrany[k][i] = hrana;
                }
                hrana++;
            }
            tmp = perm_sused[0]; //vrati perm_suseda do povodnej formy
            perm_sused[0] = perm_sused[j];
            perm_sused[j] = tmp;
        }

    }

    for (i = 0; i < POCET_PERM_VRCHOLOV; i++) {
        for (j = 0; j < POCET_FARIEB; j++) {
            for (k = j + 1; k < POCET_FARIEB; k++) {
                if (perm_susedia[i][j] > perm_susedia[i][k]) {
                    tmp = perm_susedia[i][j];
                    perm_susedia[i][j] = perm_susedia[i][k];
                    perm_susedia[i][k] = tmp;
                }
            }
        }
    }

    for (i = 0; i < POCET_VRCHOLOV; i++) { //naplnenenie default_susedia
        zhoda = 0;
        for (k = 0; k < DIMENSION - 1; k++) {
            if ((perm_susedia[hrany[i][0]][k] != hrany[i][1])) {
                for (l = 0; l < POCET_VRCHOLOV; l++) {
                    if (((hrany[l][0] == perm_susedia[hrany[i][0]][k]) && (hrany[l][1] == hrany[i][0])) || ((hrany[l][1] == perm_susedia[hrany[i][0]][k]) && (hrany[l][0] == hrany[i][0]))) {
                        default_susedia[i][zhoda] = l;
                        zhoda++;
                        break;
                    }
                }
            }

        }

        for (k = 0; k < DIMENSION - 1; k++) {
            if ((perm_susedia[hrany[i][1]][k] != hrany[i][0])) {
                for (l = 0; l < POCET_VRCHOLOV; l++) {
                    if (((hrany[l][0] == perm_susedia[hrany[i][1]][k]) && (hrany[l][1] == hrany[i][1])) || ((hrany[l][1] == perm_susedia[hrany[i][1]][k]) && (hrany[l][0] == hrany[i][1]))) {
                        default_susedia[i][zhoda] = l;
                        zhoda++;
                        break;
                    }
                }
            }

        }
    }

    for (i = 0; i < POCET_VRCHOLOV; i++) {
        for (j = 0; j < POCET_SUSEDOV; j++) {
            for (k = j; k < POCET_SUSEDOV; k++) {
                if (default_susedia[i][j] < default_susedia[i][k]) {
                    tmp = default_susedia[i][j];
                    default_susedia[i][j] = default_susedia[i][k];
                    default_susedia[i][k] = tmp;
                }
            }

        }
    }


    for (novy_vrchol = 0; novy_vrchol < POCET_VRCHOLOV; novy_vrchol++) {
        gv = GRAPHROW(g, novy_vrchol, M);
        EMPTYSET(gv, m);
        for (i = 0; i < POCET_SUSEDOV; i++) {
            // if (default_susedia[novy_vrchol][i] != -1){
            sused = default_susedia[novy_vrchol][i];
            //if (vrchol!=Neigh(v,i))
            ADDELEMENT(gv, sused);
            // }
            // else {
            //     break;
            // }
        }
    }

    /*
        for (novy_vrchol = 0; novy_vrchol < POCET_VRCHOLOV; novy_vrchol++) {
            gv = GRAPHROW(g, novy_vrchol, M);
            EMPTYSET(gv, m);
            for (i = 0; i < (DIMENSION - 1)*2; i++) {
                if (default_susedia[novy_vrchol][i] != -1) {
                    sused = default_susedia[novy_vrchol][i];
                    //if (vrchol!=Neigh(v,i))
                    ADDELEMENT(gv, sused);
                } else {
                    break;
                }
            }
        }
     */ /*
        for (i = 0; i < POCET_VRCHOLOV; i++) {
            printf("%d. hrana:  ", i);
            for (j = 0; j < POCET_SUSEDOV; j++) {
                printf("%d ", default_susedia[i][j]);
            }
            printf("\n");
        }

        for (i = 0; i < POCET_BIN_VRCHOLOV; i++) {
            for (j = 0; j < POCET_BIN_VRCHOLOV; j++) {



                if (nove_vrcholy[i][j] != -1) {
                    printf("hrana : %d  ", nove_vrcholy[i][j]);
                    printf("nove vrcholy : %d %d \n", i, j);
                }
            }
        }
     */
}

void VERTEX_STAR_DFS::print(const int *v, const int size) {
    int i, j;

    switch (size) {
        case 6:
            if (v != 0) {

                for (i = 0; i < size; i++) {
                    //printf("%4d", v[i] );
                    perm_pole_6[perm_pole_tmp][i] = v[i];
                }
                perm_pole_tmp++;
                //printf("\n");
            }
            break;
        case 5:
            if (v != 0) {

                for (i = 0; i < size; i++) {
                    //printf("%4d", v[i] );
                    perm_pole_5[perm_pole_tmp][i] = v[i];
                }
                perm_pole_tmp++;
                //printf("\n");
            }
            break;
        case 4:
            if (v != 0) {

                for (i = 0; i < size; i++) {
                    //printf("%4d", v[i] );
                    perm_pole_4[perm_pole_tmp][i] = v[i];
                }
                perm_pole_tmp++;
                //printf("\n");
            }
            break;
        case 3:
            if (v != 0) {

                for (i = 0; i < size; i++) {
                    //printf("%4d", v[i] );
                    perm_pole_3[perm_pole_tmp][i] = v[i];
                }
                perm_pole_tmp++;
                //printf("\n");
            }
            break;
        case 2:
            if (v != 0) {

                for (i = 0; i < size; i++) {
                    //printf("%4d", v[i] );
                    perm_pole_2[perm_pole_tmp][i] = v[i];
                }
                perm_pole_tmp++;
                //printf("\n");
            }
            break;
    }

    /*
    if (v != 0) {
      for (i = 0; i < size; i++) {
        printf("%4d", v[i] );

      }
      printf("\n");
    }
     */
} // print

void VERTEX_STAR_DFS::visit(int *Value, int N, int k) {
    static int level = -1;
    level = level + 1;
    Value[k] = level;
    int i;


    if (level == N)
        print(Value, N);
    else
        for (i = 0; i < N; i++)
            if (Value[i] == 0)
                visit(Value, N, i);

    level = level - 1;
    Value[k] = 0;
}

