/* 1factorGComplet.c
 * 
 *  1-factors of a complete graph
 *  
 Application 1factorGComplet (1FACTORGCOMPLET), Copyright (C) 2005 Jean-Paul Davalan.

 29900 Concarneau (France) le : ven déc 23 01:20:10 UTC 2005

 1factorGComplet (1FACTORGCOMPLET) is free software; you can redistribute it and/or modify
 it under the terms of the GNU General Public License as published by
 the Free Software Foundation; either version 2, or (at your option)
 any later version.

 1factorGComplet (1FACTORGCOMPLET) is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 GNU General Public License for more details.
 You should have received a copy of the GNU General Public License
 along with ./1factorGComplet (1FACTORGCOMPLET); see the file COPYING.  If not, write to
 the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.

 Jean-Paul Davalan <jpdvl@wanadoo.fr>
  
 *                  
 *    Si nb solutions trop grand pour un long long
 *    gcc -O2 -D GMP -o 1factorGComplet 1factorGComplet.c -lgmp 
 *    
 *    mais pour nsommets=8 ceci suffit
 *    gcc -O2 -o 1factorGComplet 1factorGComplet.c
 *
 *    usage :   1factorGComplet options
 *           -n #  nombre (pair) de sommets
 *           -s    pour un affichage des solutions sous la forme d'un tableau
 *           -l    pour un affichage sur une seule ligne des solutions
 *           de tous les couples (i, j) avec i != 0 (sa plus petite valeur)
 *                                      et i< j < n
 *                                      affichage de la couleur k (k-ième jour)
 *    la solution n° 1 pour 6 sommets :
 *    1 : 1 2 3 4 5 3 4 5 2 5 1 4 2 1 3
 *    correspondent dans l'ordre aux couples (0,1) (0,2) (0.3) ... (4,5)
 *    comme dans la table ci-dessous gauche -> droite et haut -> bas  
 *    
 *        0 1 2 3 4 5
 *      ---------------
 *      0 - 1 2 3 4 5
 *      1 - - 3 4 5 2
 *      2 - - - 5 1 4
 *      3 - - - - 2 1
 *      4 - - - - - 3
 *    le premier jour (cases 1 à l'intérieur de la table) correspond aux couples
 *    (0, 1) (2, 4) et (3, 5)    
 *
 *    l'option -s permet d'obtenir plus simplement
 *    # 1
 *    [ 0 --  1] [ 2 --  4] [ 3 --  5]
 *    [ 0 --  2] [ 1 --  5] [ 3 --  4]
 *    [ 0 --  3] [ 1 --  2] [ 4 --  5]
 *    [ 0 --  4] [ 1 --  3] [ 2 --  5]
 *    [ 0 --  5] [ 1 --  4] [ 2 --  3]
 *    # ----------------
 *        
 *    quelques exemples :
 *    -------------------
 *    1factorGComplet -n 8  -s -t
 *    1factorGComplet -n 8  -l -t
 *    1factorGComplet -n 8  -t
 *
 * */

#include <stdio.h>
#include <stdlib.h>
#include <getopt.h>
#ifdef GMP
#include <gmp.h>
#endif

/*
 * Le graphe g est non orienté et complet (sans boucles)
 * les n sommets sont numérotés de 0 à n-1
 * les arêtes a --- b (a<b) sont de l'une des n-1 couleurs numérotées de 1 à n-1
 * les arêtes sont ordonnées   ab << a'b' si a<a' ou (a=a' et b<b')
 * les arêtes 0-1 ... 0-b ... 0-(n-1) sont précoloriées 1, 2, ..., n-1
 *
 * Pour obtenir tous les coloriages possibles les arêtes sont parcourues de 
 * la manière suivante
 * on commence par 1-2 (de couleur 0)
 * on essaie les couleurs suivantes (dans l'ordre croissant) jusqu'à obtenir
 *    une couleur compatible
 *    la couleur de a-b doit être différente des couleurs 
 *        de a a+1, a a+2 ... a b-1
 *        et aussi de 0 a, 1 a, ... 
 * si on trouve une couleur 
 *    on va à l'arête suivante que l'on colorie en 0, si elle existe
 *       et on recommence
 *    sinon on a un coloriage, on l'affiche
 *       on cherche la couleur suivante
 * s'il n'y a pas de couleur, on revient à l'arête précédente
 * 
 */
int     opt_solutions=0, opt_lignes=0, opt_total=0, nsommets=6;

static char *helparr[] =
{
   "Options :",
   "  --help         -h",
   "  --copyright    -c",
   "  --sommets      -n #",
   "  --solutions    -s",
   "  --lignes       -l",
   "  --total        -t",
   0
};
static const struct option long_options[] =
{
   {"help", no_argument, 0, 'h'},
   {"copyright", no_argument, 0, 'c'},
   {"sommets", required_argument, 0, 'n'},
   {"solutions", no_argument, 0, 's'},
   {"lignes", no_argument, 0, 'l'},
   {"total", no_argument, 0, 't'},

   {0, 0, 0}
};

void    options();
void    help();
void    copyright();

void options(int argc, char *argv[])
{
  int     c, longoptindex = 0, errflag = 0;
  //printf("options ");
  if (argc == 1) {
    help(argc, argv);
    exit(2);
  }
  while ((c = getopt_long_only(argc, argv,
           "hcn:slt",
           long_options, &longoptindex)) != EOF) {
    switch (c) {
      case 0:
        switch (longoptindex) {
          case 1:
            break;
          default:
            break;
        }
        break;
      case 'h':
        help(argc, argv);
        exit(1);
        break;
      case 'c':
        copyright(argc, argv);
        exit(1);
        break;
      case 'n':
        if(optarg){
          nsommets = atoi(optarg);
        }
        //printf("n %d ",nsommets);
        break;

      case 's':
        opt_solutions=1;
        //printf("s ");
        break;
      case 'l':
        opt_lignes=1;
        //printf("l ");
        break;
      case 't':
        opt_total=1;
        //printf("t ");
        break;
      default:
        errflag++;
        break;
    }
  }
  if (errflag) {
    help(argc, argv);
    exit(2);
  }
  //printf("\n");
}
void help(int argc, char *argv[])
{
  char  **pt;
  fprintf(stderr, "usage: %s options\n", argv[0]);
  for (pt = helparr; *pt; pt++)
    fprintf(stderr, "%s\n", *pt);
}

void copyright(int argc, char *argv[])
{
 fprintf(stdout,
    " Application %s (1FACTORGCOMPLET), Copyright (C) 2005 Jean-Paul Davalan.\n\n"
    " 29900 Concarneau (France) le : ven déc 23 01:20:10 UTC 2005\n\n"
    " %s (1FACTORGCOMPLET) is free software; you can redistribute it and/or modify\n"
    " it under the terms of the GNU General Public License as published by\n"
    " the Free Software Foundation; either version 2, or (at your option)\n"
    " any later version.\n\n"
    " %s (1FACTORGCOMPLET) is distributed in the hope that it will be useful,\n"
    " but WITHOUT ANY WARRANTY; without even the implied warranty of\n"
    " MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the\n"
    " GNU General Public License for more details.\n"
    " You should have received a copy of the GNU General Public License\n"
    " along with %s (1FACTORGCOMPLET); see the file COPYING.  If not, write to\n"
    " the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.\n\n"
    " Jean-Paul Davalan <jpdvl@wanadoo.fr>\n"
    ,argv[0],argv[0],argv[0],argv[0]);
}



int f(int **g, int n) {
    int a = 1, b=2;
#ifdef GMP
    mpz_t nsols;
    mpz_init_set_ui (nsols,0);
#else
    long long nsols=0;
#endif
    void affiche() {
      int i, j;
      if(opt_lignes) {
#ifdef GMP
	mpz_out_str (stdout, 10, nsols);
	printf(" : ");
#else
        printf("%ld : ",nsols);
#endif
					      
      for(i=0; i<n-1; i++) {
        for(j=i+1; j<n;j++) {
           printf("%d ",g[i][j]);
        }
      }
      printf("\n");
      } else {
        int k;
#ifdef GMP
        printf("# ");
	mpz_out_str (stdout, 10, nsols);
	printf("\n");
		     
#else
        printf("# %ld\n",nsols);
#endif
        for(k=1; k<n; k++) { // couleurs
           for(i=0;i<n;i++) {
             for(j=i+1;j<n;j++) {
                if(g[i][j]==k) {
                   printf("[%2d -- %2d] ",i,j);
                }
              }
            }
            printf("\n");
         }
         printf("# ----------------\n");
      }
    }  /* affiche */

    int teste() {
       int i, u=g[a][b];
       for(i=0;i< a;i++) {
          if(g[i][a]==u) {
             return 0;
          }
       }
       for(i=0;i< a;i++) {
         if( g[i][b] == u) {
            return 0;
         }
       }
       for(i=a+1;i<b;i++) {
          if(g[a][i] == u) {
             return 0;
          }
       }
       return 1;
    } /* teste */

    void suivte() {
       int u=a, v=b+1;
       if(v >= n) {
         u++;
         v=u+1;
         if(u>=n-1) {
#ifdef GMP
           mpz_add_ui(nsols,nsols,1);
#else
           nsols++;
#endif
         
           if(opt_lignes || opt_solutions) affiche();
           // on reste à la même place
           return;
         }
       }
       a=u;
       b=v;
       g[a][b] = 0;
    } /* suivte */

    void prec() {
      g[a][b] = 0;
      int u=a, 
          v=b-1;
      if(v<=a) {
         u = a-1;
         v=n-1;
         if(u==0) {
	   if(opt_total) {
#ifdef GMP
             printf("Nb solutions ");
             mpz_out_str (stdout, 10, nsols);
             printf("\n");
#else
             printf("Nb solutions %ld\n",nsols);
#endif
           }
           exit(0);
         }
      }
      a=u;
      b=v;
    } /* prec */
    
    while(1) { 
        do {
          g[a][b] += 1;
    	} while(g[a][b] <= n-1 && teste()==0);
	if(g[a][b] <= n-1) {
            suivte();
	} else {
            prec();
        }
    } /* while 1 */
    if(opt_total) {
#ifdef GMP
           printf("Nb solutions ");
           mpz_out_str (stdout, 10, nsols);
           printf("\n");
#else
           printf("Nb solutions %d\n",nsols);
#endif
    } /* opt_total */
    return 0;
} /* f */
	
int main(int argc, char *argv[]) {
   int i, j, **graphe;
   options(argc, argv);
   nsommets += nsommets%2;  // pair
   
   if(nsommets<4) return 0;
   
   graphe = (int **)malloc(nsommets*sizeof(int *));
   for(i=0; i<nsommets; i++) {
	    graphe[i] = (int *)malloc(nsommets*sizeof(int));
   }
   for(i=0; i<nsommets; i++) {
	   for(j=0;j<nsommets;j++) {
		   graphe[i][j]=0;
	   }
   }
   // précoloriage des arêtes 0-j de la couleur j
   for(j=1;j<nsommets;j++) {
	   graphe[0][j]=j;
   }
   f(graphe, nsommets);
   return 0;
}