/* tomj2dimacs.c
 *
 * writes the graph for Tom Johnson's perfect rythmic tilings
 * in DIMACS Challenge II binary format:
 * 
 * DIMACS Format for Storing Undirected Graphs in Binary Files
 * The binary format for storing a graph is an alternative to the ascii
 * (human readable) format described in the File Formats section of the
 * document /pub/challenge/graph/doc/ccformat.tex at dimacs.rutgers.edu
 * (anonymous ftp).
 *
 * parts from asc2bin.c and genbin.h
 *   Written by Tamas Badics (badics@rutcor.rutgers.edu)
 *   using the technique of Marcus Peinado, Boston University.
 *
 * adaptation to Tom Johnson's graph by
 *   2005 Jean-Paul Davalan <jpdvl@wanadoo.fr>
 * 
 * compilation:
 * gcc -O2 -o tomj2dimacs tomj2dimacs.c
 * usage:
 * tomj2dimacs 5 3
 * (two files TomJ5_3.b and Nodes5_3)
 *
 * Tom Johnson's perfect rythmic tilings
 * -------------------------------------
 * a perfect rythmic tiling is a maximum clique of the graph
 *
 * each node S = 1...Nr_nodes correspond to an arithmetic progression
 *                 a, a+r, a+2*r, ... , a+(k-1)*r
 * with origine a
 *      reason  r
 *      length k
 * the file Nodesn_k have a line
 * c S a r
 * (example: c 23 9 2)
 *
 * the file TomJ5_3.b for n=5 and k=3 have two parts:  Preamble and Bitmap
 * Preamble:
 * p edge 49 414
 * c
 * c Johnson's Perfect Rythmic Tilings
 * etc.
 * c
 * Bitmap:
 * 
 * bin2asc converts from bin format to ascii format
 * asc2bin               ascii      to bin
 *
 * bin2asc TomJ5_3.b
 * asc2bin TomJ5_3
 * */

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

#define MAX_TETE 10000
#define MAX_NAME 100

#define NODES_NAME	"nodes"	// "Nodes"

//#define OUT_NAME      "clig"
#define OUT_NAME	"tomj.clg"

#define BOOL char

int n,				/* n progressions */
 k,				/* of length k (k terms) */
 kn,				/* length k*n of the segment */
 rmax,				/* floor((k*n-1)/(k-1)) raison maximum */
 Nr_vert,			/* nombre de sommets du graphe */
 Nr_vert_div8, Nr_edges, *anodes,	/* valeur de l'origine a */
*rnodes;			/*           la raison r */

char masks[8] = { 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80 };
static char Preamble[MAX_TETE], outfile[MAX_NAME], outnodes[MAX_NAME];

BOOL **Bitmap;


void alloc_set_nodes()
{
    register int nv, v, i, j;
    /* allocation de deux tableaux pour origines et raisons */
    if ((anodes = (int *) malloc((Nr_vert + 1) * sizeof(int))) == NULL) {
	fprintf(stderr, "allocation error\n");
	exit(1);
    }
    if ((rnodes = (int *) malloc((Nr_vert + 1) * sizeof(int))) == NULL) {
	fprintf(stderr, "allocation error\n");
	exit(1);
    }

    /* valeurs des origines et raisons */
    for (nv = 0, i = 1; i <= rmax; i++) {
	v = kn - (k - 1) * i;
	for (j = 0; j < v; j++) {
	    rnodes[nv] = i;
	    anodes[nv] = j;
	    nv++;
	}
    }
}

/* writes the nodes file */

void write_nodes()
{
    register int i;
    FILE *fp;
    sprintf(outnodes, NODES_NAME "%d_%d", n, k);

    if ((fp = fopen(outnodes, "w")) == NULL) {
	printf("ERROR: Cannot open outfile for nodes\n");
	exit(10);
    }
    for (i = 0; i < Nr_vert; i++)
	fprintf(fp, "c %d %d %d\n", i + 1, anodes[i], rnodes[i]);
    fclose(fp);
}


void alloc_matrix()
{
    register int i;
    /* allocation de la matrice du graphe */
    if ((Bitmap = (char **) malloc(Nr_vert * sizeof(char *))) == NULL) {
	fprintf(stderr, "allocation error\n");
	exit(1);
    }
    for (i = 0; i < Nr_vert; i++) {
	if ((Bitmap[i] =
	     (char *) malloc(Nr_vert_div8 * sizeof(char))) == NULL) {
	    fprintf(stderr, "allocation error\n");
	    exit(1);
	}
	memset(Bitmap[i], 0x0, Nr_vert_div8);
    }
}

void set_preamble()
{
    sprintf(Preamble, "p edge %d %d\n"
	    "c \n"
	    "c Johnson's Perfect Rythmic Tilings\n"
	    "c \n"
	    "c nr arithm. progr. in a segment: n = %d\n"
	    "c progression lengths:            k = %d\n"
	    "c segment length                k*n = %d\n"
	    "c \n"
	    "c graph nodes are progressions\n"
	    "c nr of graph vertices                %d\n"
	    "c             edges                   %d\n"
	    "c nodes in maximum clique          <= %d\n"
	    "c \n", Nr_vert, Nr_edges, n, k, kn, Nr_vert, Nr_edges, n);
}

void set_edge(register int i, register int j, BOOL x)
{
    register int byte, bit, mask;

    bit = 7 - (j & 0x00000007);
    byte = j >> 3;

    mask = masks[bit];
    if (x == 1)
	Bitmap[i][byte] |= mask;
}

void set_matrix()
{
    register int i, j, mi, mj, u;
    register BOOL test;

    Nr_edges = 0;

    for (i = 0; i < Nr_vert - 1; i++) {
	for (j = i + 1; j < Nr_vert; j++) {
	    test = (BOOL) 0;
	    // raisons différentes
	    if (rnodes[i] != rnodes[j]) {
		test = (BOOL) 1;
		for (mi = 0; test && mi < k; mi++) {
		    // position du terme de rang mi du premier
		    u = anodes[i] + mi * rnodes[i];
		    for (mj = 0; test && mj < k; mj++) {
			// égale position du terme de rang mj de l'autre
			if (u == anodes[j] + mj * rnodes[j])
			    test = (BOOL) 0;
		    }
		}
	    }
	    if (test)
		Nr_edges++;
	    set_edge(j, i, test);	/* j > i */

	}
    }
}

void write_graph_DIMACS_bin()
{
    int i;
    FILE *fp;

    sprintf(outfile, OUT_NAME "%d_%d.b", n, k);

    if ((fp = fopen(outfile, "w")) == NULL) {
	printf("ERROR: Cannot open outfile\n");
	exit(10);
    }

    fprintf(fp, "%d\n", strlen(Preamble));
    fprintf(fp, Preamble);

    for (i = 0;
	 i < Nr_vert && fwrite(Bitmap[i], 1, (int) ((i + 8) / 8), fp);
	 i++);

    fclose(fp);
}

int main(int argc, char *argv[])
{
    if (argc < 3) {
	fprintf(stderr, "usage: %s n k\n", argv[0]);
	exit(10);
    }

    /* Johnson's perfect tiling of the segment
     * parameters n and k :
     * n progressions of length k
     * */
    n = atoi(argv[1]);
    k = atoi(argv[2]);
    /* tests */
    if (n < 1) {
	fprintf(stderr, "incorrect value: n = %d < 1\n", n);
	exit(10);
    }
    if (k < 2) {
	fprintf(stderr, "incorrect value: k = %d < 2\n", k);
	exit(10);
    }

    /* constantes utiles */
    kn = k * n;
    rmax = (kn - 1) / (k - 1);

    /* calcul du nombre de sommets  */

    /*
       for(Nr_vert=0, i=1; i<= rmax; i++)
       Nr_vert += kn-(k-1)*i;

       fprintf(stderr,"%d %d\n",Nr_vert,
       ( rmax * ( 2*kn -(k-1)*(rmax+1) ) )/2);
     */
    Nr_vert = (rmax * (2 * kn - (k - 1) * (rmax + 1))) / 2;

    Nr_vert_div8 = (Nr_vert + 7) >> 3;

    alloc_set_nodes();
    write_nodes();

    alloc_matrix();
    set_matrix();

    set_preamble();

    write_graph_DIMACS_bin();

    return 0;
}