#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#include "jmgraph.h"


#define CYCLE_LENGTH 7
#define N 70
#define NGRAPHS 1000000
#define MAXGRAPHS 10000000


jmgraph *g;


int getPair(int v, int existingConnections[][N/CYCLE_LENGTH]) {
    const int STEP = 1299827; // some large enough prime    
    int u = random() % N;
    int count = 0;
    while (1) {
        if (count++ > N)
            return -1;
        int cu = u / CYCLE_LENGTH;
        int cv = v / CYCLE_LENGTH;
        if ((cu == cv) || existingConnections[cu][cv] > 0) {
            u = (u+STEP) % N;
            continue;
        }
        if (g->e[u][2] != -1) {
            u = (u+STEP) % N;
            continue;
        }
        return u;
    }
}


int generateGraph() {
    int existingConnections[N/CYCLE_LENGTH][N/CYCLE_LENGTH];
    for (int i = 0; i < N/CYCLE_LENGTH; i++)
        for (int j = 0; j < N/CYCLE_LENGTH; j++)
            existingConnections[i][j] = 0;

    int **e = g->e;
    for (int i = 0; i < N/CYCLE_LENGTH; i++) {
        for (int j = 0; j < CYCLE_LENGTH; j++) {
            int v = CYCLE_LENGTH*i + j;
            int vNext = CYCLE_LENGTH*i + ((j+1) % CYCLE_LENGTH);
            int vPrev = (j == 0) ?
                    CYCLE_LENGTH*i + CYCLE_LENGTH - 1 :
                    CYCLE_LENGTH*i + ((j-1) % CYCLE_LENGTH);                
            e[v][0] = vNext;
            e[v][1] = vPrev;
            if (e[v][2] == -1) {
                int u = getPair(v, existingConnections);
                if (u == -1)
                    return -1;
                e[v][2] = u;
                e[u][2] = v;
                existingConnections[u/CYCLE_LENGTH][v/CYCLE_LENGTH]++;
                existingConnections[v/CYCLE_LENGTH][u/CYCLE_LENGTH]++;
            }
        }
    }
    return 0;
}




int main() {
    if (N % CYCLE_LENGTH != 0) {
        fprintf(stderr, "N not divisible by CYCLE_LENGTH\n");
        exit(1);
    }
    srand(time(NULL));
    
    int graphCount = 0;
    for (int k = 0; k < MAXGRAPHS; k++) {        
        g = newCubicGraph(N);
        if (generateGraph() != -1) {
            graphCount++;
            if (graphCount % 100 == 0)
                printf("%d\n", graphCount);
        } else {
            destroyGraph(g);
            continue;
        }
        
        if (!isColourable(g)) {
            FILE *output = fopen("generatedUncolourable.g6", "a");
            char *s = writeGraph6(g);
            fprintf(output, "%s\n", s);
            free(s);
            fclose(output);
        }

        destroyGraph(g);
        if (graphCount >= NGRAPHS)
            break;
    }
    return 0;
}
