/* reduce.c */

/* This program is part of the paper "On The Three Coloring Problem" 
 * by Mohammad R. Salavatirpour.
 * Copyright 2002 by Mohammad R. Salavatipour
 * Permission to use for the purpose of scholarly research is hereby granted */

/* Version 1,  May 2002 */

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

#define Max_No_of_vertices 50
#define Error_filename "UnColorable_Config.txt"

int Nvertices, Nedges,  /* No. of vertices and edges of the configuration */
  Nbound,               /* No. of boundary vertices */
  NConstrained_groups,  /* No. of Constrained groups */
  Ncolored,             /* No. of colored vertices so far */
  Nof_colorings,    /* No. of differenet colorings found for a configuration */
  is_in_bound [Max_No_of_vertices],   
         /* is_in_bound [v] = 1 if v is a boundary vertex, 0 otherwise */
  adj_list[Max_No_of_vertices][Max_No_of_vertices], 
     /* The adjacancy list; for vertex v adj_list[v][0] specifies the 
        degree of v */

  bound[Max_No_of_vertices],       /* The list of boundary vertices */
  non_bound[Max_No_of_vertices],   /* The list of non-boundary vertices */

  constrained_groups[3][Max_No_of_vertices],  
      /* The list of constrained groups; the vertices in a group are those
         boundary vertices which must not all have the same color, 
         enforced by a gadget. For group i constrained_groups[i][0] 
         specifies the number of vertices in that group */

  color[Max_No_of_vertices],   /* Color of vertex v is color[v], 0 if it
                                  is not colored */
  Nof_configurations,          /* No. of configuration in the file */
  current_conf;    /* index of the current configuration being tested */
       
FILE *fErrors;     /* The file to write in any non-reducible configuration */

/***********************************************************************************************************/
/* Function Prototypes */
int Check_Boundary_Colorings (int NColored_bound);
void Read_Data (char *filename);
void UnColorable (void);
int Check_Extendable (int vertex);
int Valid_Boundary_Coloring (void);
int Check_Boundary_Colorings (int NColored_bound);

/***********************************************************************************************************/
/* Read the configurations from a file whose name is "filename", one by one, and check reducibility of each  */
void Read_Data (char *filename){

  FILE *fin;
  int i, j, v1, v2;
  char tmpStr[100];

  /* Openning the input file */
  if ((fin = fopen (filename, "r")) == NULL) {
    printf ("Cannot open the input file! \n");
    exit (1);
  }

  /* Openning the output (i.e. error) file */
  if ((fErrors = fopen (Error_filename, "w")) == NULL) {
    printf ("Cannot open the output file! \n");
    fclose(fin);
    exit (1);
  }

  fscanf (fin, "%d \n", &Nof_configurations);

  /* Reading the information of configurations one by one and checking the reducibility of them */
  for (current_conf = 1; current_conf <= Nof_configurations; current_conf++){
    fgets (tmpStr, sizeof (tmpStr), fin); 
    fscanf (fin, "%d %d \n", &Nvertices, &Nedges);
    Ncolored = 0;
    Nbound = 0;
    Nof_colorings = 0;
    for (i = 1; i <= Nvertices; i++){
      adj_list[i][0] = 0;
      color[i] = 0;
      is_in_bound[i] = 0;
    }

    /* Reading the adjacancy lists of the current configuration    */
    for (i = 1; i <= Nedges; i++){
      fscanf (fin, "%d %d \n", &v1, &v2);
      adj_list[v1][++adj_list[v1][0]] = v2;
      adj_list[v2][++adj_list[v2][0]] = v1;
    }

    /* Setting up the boundary vertices */
    j = 0;
    for (i = 1; i <= Nvertices; i++){
      if (adj_list[i][0] <= 2){
	bound[++Nbound] = i;
	is_in_bound[i] = 1;
      }
      else non_bound[++j] = i; 
    }

    /* Reading (just passing on) the information about the coordinates of vertices */
    for (i = 1; i <= Nvertices; i++)
      fscanf (fin, "%d %d \n", &v1, &v2);

    /* Reading the number of groups of the constrained vertices and then the vertices of each group */
    fscanf (fin, "%d\n", &NConstrained_groups);
    for (i = 1; i <= NConstrained_groups; i++){
      constrained_groups[i][0] = 0;
      while (fscanf (fin, "%d\n", &v1) == 1) {
	constrained_groups[i][++constrained_groups[i][0]] = v1;
      }
      fscanf (fin, "%s\n", tmpStr);
    }
    
    /* Check to see if the current configuration is reducible */
    if (!Check_Boundary_Colorings (0)) {   
      printf ("Configuration No. %d is reducible! No of Colorings Checked = %d\n", current_conf, Nof_colorings);
    }
  }

  fclose (fin);
  fclose (fErrors);
}

/********************************************************************************************************/
/* If the current configuration is not reducible this procedure writes the index of the configuration  */
/* as well as the coloring of the boundary vertices into a file. */
void UnColorable (void){
  int i;

  printf ("Configuration No. %d is *NOT* reducible \n", current_conf);
  fprintf (fErrors, "Configurtion No %d\n", current_conf);
  fprintf (fErrors, "The coloring of the boundary vertices that cannot be extended is :\n");

  for (i = 1; i <= Nbound; i++)
    fprintf (fErrors, "Color of vertex %d = %d\n", bound[i], color[bound[i]]);
  fprintf(fErrors, "\n");
}


/********************************************************************************************************/
/* Checks whether the current 3-coloring of the boundary vertices can be extended to a 3-coloring of the whole */
/* configuration. Returns 1 when it can NOT be extended, 0 otherwise */
int Check_Extendable (int vertex){    

  int i, j, Next_vertex, Equal;
  Next_vertex = 0;
  /* Find the "Next vertex" to be colored after coloring the current "vertex", by finding an uncolored 
     neighbor of it, if exists any */
  for (i = 1; i <= adj_list[vertex][0]; i++)
    if (!color[adj_list[vertex][i]]) {
      Next_vertex = adj_list[vertex][i];
      i = adj_list[vertex][0];
    }

  /* If all the neighbors of the current "vertex" are colored,  find the next (available) uncolored vertex */
  if (Next_vertex == 0){
    for (i = 1; i <= Nvertices-Nbound; i++)
      if (non_bound[i] != vertex && !color[non_bound[i]]){
	Next_vertex = non_bound[i];
	i = Nvertices-Nbound;
      }	  
  }
  /* Check all possible colorings of the current "vertex" and continue by coloring the "Next_vertex" */
  for (i = 1; i <= 3; i++){
    Equal = 0;
    for (j = 1; j <= adj_list[vertex][0]; j++)
      if (color[adj_list[vertex][j]] == i) Equal = 1;
    if (!Equal){
      color[vertex] = i;
      Ncolored++;
      if (Ncolored == Nvertices || !Check_Extendable (Next_vertex)){
        Ncolored--;
        color[vertex] = 0;
        return 0;
      }
      Ncolored--;
      color[vertex] = 0;
    }
  }
  return 1;
}


/********************************************************************************************************/
/* Checks whether the current boundary coloring satisfies the requirments by the constrained groups. That is, not all */
/* the vertices in the same group have the same color. Returns 1 if it does NOT satisfy this condition, 0 otherwise. */
int Valid_Boundary_Coloring (void){
  
  int i, j;
  for (i = 1; i <= NConstrained_groups; i++){
    int All_Equal=1;
    for (j = 2; j <= constrained_groups[i][0]; j++){
      if (color[constrained_groups[i][1]] != color[constrained_groups[i][j]]) {
	All_Equal = 0;
	j = constrained_groups[i][0];
      }
    }
    if (All_Equal) return 1;
  }
  return 0;
}

/********************************************************************************************************/
/* For all possible (valid) colorings of the boundary vertices checks if it is extendable to a coloring of the whole */
/* configuration. Returns 1 if it is NOT, 0 otherwise */
int Check_Boundary_Colorings (int NColored_bound){

  /* If all boundary vertices are colored  */
  if (NColored_bound == Nbound) {
    /* check if this coloring of the boundary vertices satisfies the requirements by the constrained groups */
    if (NConstrained_groups > 0 && Valid_Boundary_Coloring ()) return 0;   
    /* check if this coloring can be extended to a coloring of the non-boundary vertices of the configuration. */
    if (!Check_Extendable (non_bound[1])) {
      Nof_colorings++;
      return 0;
    }
    else {
      UnColorable ();
      return 1;
    }
  }

  else {      
    int i, MaxColor;
    /* if this is the first boundary vertex we want to color try only color 1 */
    if (NColored_bound == 0) {
      Nof_colorings = 0;
      MaxColor = 1;
    }
    /* if this is the second boundary vertex we want to color try only colors 1 and 2 */
    else if (NColored_bound == 1) MaxColor = 2;
    /* Otherwise, try all possbile 3 colors */
    else MaxColor = 3;
    NColored_bound++;
    for (i = 1; i <= MaxColor; i++){
      color[bound[NColored_bound]] = i;
      Ncolored++;
      if (Check_Boundary_Colorings (NColored_bound)) {
	color[bound[NColored_bound]] = 0;
	Ncolored--;	
	return 1;
      }
      color[bound[NColored_bound]] = 0;
      Ncolored--;
    }
    return 0;
  }
}


/********************************************************************************************************/
int main (int argc, char *argv[]){  
  
  time_t start_time = time(NULL);

  if (argc >= 2)
    Read_Data (argv[1]);
  else Read_Data ("conf.dat");

  printf ("All done in %g seconds!\n", difftime(time(NULL), start_time));
  return 0;

}