/** *************************************************************
 strong_edge_reducible.cpp -- Written by Derrick Stolee
 Last edited: 11/19/2014

 To compile, place this file in the nauty/ folder after unpacking the
 nauty source code, available at http://cs.anu.edu.au/~bdm/nauty/
 
 Compile using the following command:
 gcc -o strong_edge_reducible strong_edge_reducible.c nauty.o nausparse.o nautil.o gtools.o

 Then, run :
 strong_edge_reducible < inputfile.txt

 or (for 6 colors) :
 strong_edge_reducible -k 6 < inputfile.txt

 This 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 3 of the License, or
 (at your option) any later version.

 This 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 SearchLib.  If not, see <http://www.gnu.org/licenses/>.

 *************************************************************/


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

#include "nausparse.h"
#include "gtools.h"


/**
 * is_deletion_reducible : Given a graph g, the list of vertices to delete (deleting edges that have both endpoints in this set)
 * and a number of colors, determine if this is reducible for strong k-edge-colorings!
 */ 
int is_deletion_reducible(sparsegraph* g, int* del_vert_list, int num_del_verts, int k);

/**
 * Given a graph g and an ordering of (a subset of) its edges, return the graph on the edge list
 * where two edges are adjacent if and only if they have common endpoints or endpoints that are adjacent.
 */
sparsegraph* strong_edge_graph(sparsegraph* g, int* edge_list, int num_edges);


/**
 * the main executable
 *
 * optional parameter "-k #" allows you to change the number of colors.
 *
 * Reads from standard input until end-of-file or an empty line:
 *    - A label for the graph
 *    - A sparse 6 representation of a graph
 *    - A space-separated list of vertices in the deletion set
 *
 * Will check if each is reducible or not.
 */
int main(int argc, char** argv)
{
	int k = 5;

	int i,j;

	for ( i = 0; i < argc; i++ )
	{
		if (strcmp(argv[i], "-k") == 0 && i < argc - 1 )
		{
			k = atoi(argv[i+1]);
		}
	}

	size_t buflen = 500;
	char* buffer = (char*)malloc(buflen);


	while ( getline(&buffer, &buflen, stdin) > 0 )
	{
		if ( strlen(buffer) <= 1 )
		{
			break;
		}

		buffer[strlen(buffer) - 1] = 0;
		char* name = (char*)malloc(strlen(buffer)+1);
		strcpy(name, buffer);

		getline(&buffer, &buflen, stdin);
		sparsegraph* g = (sparsegraph*)malloc(sizeof(sparsegraph));

		SG_INIT((*g));

		int num_loops = 0;
		stringtosparsegraph(buffer, g, &num_loops);

		getline(&buffer, &buflen, stdin);

		// read the line to receive the deletion set.
		int num_del = 0;
		int* del_set = (int*)malloc(g->nv * sizeof(int));
		bzero(del_set, g->nv * sizeof(int));

		char* next = buffer;
		next = strtok(next, " ");

		while ( next != 0  )
		{
			int contains_number_character = 0;

			int j = 0; 
			for ( j = 0; j < strlen(next); j++ )
			{
				if ( next[j] >= '0' && next[j] <= '9')
				{
					contains_number_character++;
				}
			}

			if ( contains_number_character == 0 )
			{
				break;
			}

			int i = atoi(next);
			del_set[i] = 1;
			num_del++;
			
			printf("%d ", i);

			next = strtok(NULL, " ");
		}
		 printf("\n");

		int* edge_list = (int*)malloc(g->nde * sizeof(int));
		int* del_edge_list = (int*)malloc(g->nde * sizeof(int));
		int num_edges = 0; 
		int num_del_edges = 0;
		for ( i = 0; i < g->nv; i++ )
		{
			for ( j = 0; j < g->d[i]; j++ )
			{
				int v = g->e[ g->v[i] + j ];

				if ( v > i )
				{
					edge_list[2 * num_edges] = i;
					edge_list[2 * num_edges + 1] = v;

					if ( del_set[i] == 1 || del_set[v] == 1 )
					{
						// printf("delete edge (%2d) : %d %d\n", num_edges, i, v);
						del_edge_list[num_del_edges++] = num_edges;
					}
					else
					{
						// printf("keep edge (%2d) : %d %d\n", num_edges, i, v);
					}

					num_edges++;
				}
			}
		}

		sparsegraph* seg = strong_edge_graph(g, edge_list, num_edges);

		int result = is_deletion_reducible(seg, del_edge_list, num_del_edges, k);

		printf("Configuration %s ", name);
		if ( result )
		{
			printf("is");
		}
		else
		{
			printf("IS NOT");
		}
		printf(" %d-reducible.\n\n", k);


		SG_FREE((*g));
		free(g);
		g = 0;

		free(del_set);
		del_set = 0;

		free(del_edge_list);
		free(edge_list);

		free(name);
	}

	free(buffer);

	return 0;
}




/**
 * g - the graph
 * coloring_order - a permutation of the vertices
 * num_colored - How many already have a color
 * colors - the colors assigned to each vertex. -1 for uncolored
 * color_domains - a bitmask of the available colors at each vertex. Should have n*n entries, for deepening!
 * k - how many colors to use
 */
int can_extend_coloring(sparsegraph* g, int* coloring_order, int num_colored, int* colors, int* color_domains, int k, int cur_max_color)
{
	if ( num_colored >= g->nv )
	{
		return 1;
	}

	// extend color domains using previous color
	if ( num_colored > 0 )
	{	
		int* new_color_domains = &(color_domains[g->nv]);

		int i = 0;
		for ( i = 0; i < g->nv; i++ )
		{
			new_color_domains[i] = color_domains[i];
		}
		color_domains = new_color_domains;

		int v = coloring_order[num_colored-1];
		int c = colors[v];

		for ( i = 0; i < g->d[v]; i++ )
		{
			int u = g->e[ g->v[v] + i ];

			if ( colors[u] < 0 )
			{
				// Uncolored!
				// remove c from the domain.
				color_domains[u] &= ~(1 << c);

				if ( color_domains[u] == 0 )
				{
					// no way to extend!
					return 0;
				}
			}
		}
	}
	else
	{
		// initialize color domains!
		int i = 0;
		for ( i = 0; i < g->nv; i++ )
		{
			color_domains[i] = (1 << k) - 1;
		}
	}

	int v = coloring_order[num_colored];

	int c = 0;
	for ( c = 0; c < k && c <= cur_max_color; c++ )
	{
		if ( (color_domains[v] & (1 << c)) != 0 )
		{
			colors[v] = c;

			int cmc_append = 0;

			if ( c == cur_max_color )
			{
				cmc_append  = 1;
			}

			int result = can_extend_coloring(g, coloring_order, num_colored+1, colors, color_domains, k, cur_max_color + cmc_append);

			colors[v] = -1;

			if ( result == 1 ) 
			{
				return 1;
			}
		}
	}

	return 0;
}


int is_deletion_reducible_recurse(sparsegraph* g, int num_del_verts, int* coloring_order, int num_colored,  int* colors, int* color_domains, int k, int cur_max_color)
{
	if ( num_colored >= g->nv - num_del_verts )
	{
		int result = can_extend_coloring(g, coloring_order, num_colored, colors, color_domains, k, cur_max_color);

		if ( result == 0 )
		{
			// print the coloring!
			printf("Fails on Coloring: ");
			int i = 0;
			for ( i = 0;i < num_colored; i++ )
			{
				printf("%d : %d, ", coloring_order[i], colors[coloring_order[i]]);
			}
			printf("\n");
		}

		return result;
	}

	// extend color domains using previous color
	if ( num_colored > 0 )
	{	
		int* new_color_domains = &(color_domains[g->nv]);

		int i = 0;
		for ( i = 0; i < g->nv; i++ )
		{
			new_color_domains[i] = color_domains[i];
		}
		color_domains = new_color_domains;

		int v = coloring_order[num_colored-1];
		int c = colors[v];

		for ( i = 0; i < g->d[v]; i++ )
		{
			int u = g->e[ g->v[v] + i ];

			if ( colors[u] < 0 )
			{
				// Uncolored!
				// remove c from the domain.
				color_domains[u] &= ~(1 << c);

				if ( color_domains[u] == 0 )
				{
					// no way to extend!
					return 0;
				}
			}
		}
	}
	else
	{
		// initialize color domains!
		int i = 0;
		for ( i = 0; i < g->nv; i++ )
		{
			color_domains[i] = (1 << k) - 1;
		}
	}

	int v = coloring_order[num_colored];

	// Want: for all colorings, the coloring extends
	int big_result = 1;
	int c = 0;
	for ( c = 0; c <= cur_max_color; c++ )
	{
		if ( (color_domains[v] & (1 << c)) != 0 )
		{
			colors[v] = c;

			int cmc_append = 0;
			if ( c == cur_max_color )
			{
				cmc_append = 1;
			}

			int result = is_deletion_reducible_recurse(g, num_del_verts, coloring_order, num_colored+1, colors, color_domains, k, cur_max_color + cmc_append);

			colors[v] = -1;

			if ( result == 0 ) 
			{
				return 0;
			}
		}
	}

	return big_result;
}

int is_deletion_reducible(sparsegraph* g, int* del_vert_list, int num_del_verts, int k)
{
	int* coloring_order = (int*)malloc(g->nv * sizeof(int));

	int* colors = (int*)malloc(g->nv*sizeof(int));
	int* color_domains = (int*)malloc(g->nv * g->nv * sizeof(int));

	int nco = 0;

	// printf("Color Order: ");
	int i = 0;
	for ( i = 0; i < g->nv; i++ )
	{
		colors[i] = -1;

		int is_del = 0;
		int j = 0;
		for ( j = 0; j < num_del_verts; j++ )
		{
			if ( i == del_vert_list[j] )
			{
				is_del = 1;
				break;
			}
		}		

		if ( is_del == 0 )
		{
			coloring_order[nco++] = i;
			// printf("%d ", i);
		}
	}

	// printf("| ");
	for ( i = 0; i < num_del_verts; i++ )
	{
		// printf("%d ", del_vert_list[i]);
		coloring_order[nco++] = del_vert_list[i];
	}

	// printf("\n");

	int result = is_deletion_reducible_recurse(g, num_del_verts, coloring_order, 0, colors, color_domains, k, 0);

	free(colors);
	free(color_domains);
	free(coloring_order);

	return result;
}



sparsegraph* strong_edge_graph(sparsegraph* g, int* edge_list, int num_edges)
{
	sparsegraph* seg = (sparsegraph*)malloc(sizeof(sparsegraph));

	SG_INIT((*seg));

	seg->nv = num_edges;
	seg->nde = 0;
	seg->vlen = seg->nv;
	seg->dlen = seg->nv;

	seg->v = (int*)malloc(seg->nv * sizeof(int));
	seg->d = (int*)malloc(seg->nv * sizeof(int));

	int num_strong_dedges = 0;

	int i = 0;
	for ( i = 0; i < num_edges; i++ )
	{
		seg->v[i] = num_strong_dedges;

		int u = edge_list[2*i];
		int v = edge_list[2*i+1];

		int di = 0;

		int j = 0;
		for ( j = 0; j < g->d[u]; j++ )
		{
			int x = g->e[g->v[u]+j];

			di += g->d[x];
		}

		for ( j = 0; j < g->d[v]; j++ )
		{
			int x = g->e[g->v[v]+j];

			int adj_to_u = 0;
			int jj = 0;
			for ( jj = 0; jj < g->d[u]; jj++ )
			{
				int xx = g->e[g->v[u] + jj];

				if ( x == xx )
				{
					adj_to_u = 1;
				}
			}

			if ( adj_to_u == 0 )
			{
				di += g->d[x];
			}
		}

		seg->d[i] = di;
		num_strong_dedges += di;
	}

	seg->elen = num_strong_dedges;
	seg->e = (int*)malloc(num_strong_dedges*sizeof(int));

	for ( i = 0; i < num_edges; i++ )
	{
		int u = edge_list[2*i];
		int v = edge_list[2*i+1];

		int di = 0;

		int j = 0;
		for ( j = 0; j < g->d[u]; j++ )
		{
			int x = g->e[g->v[u]+j];

			int t = 0;
			for ( t = 0; t < g->d[x]; t++ )
			{
				int y = g->e[g->v[x] + t];

				int ii = 0;
				for ( ii = 0; ii < num_edges; ii++ )
				{
					if ( (edge_list[2*ii] == x && edge_list[2*ii+1] == y )||(edge_list[2*ii] == y && edge_list[2*ii+1] == x ) )
					{
						// add adjacency!
						seg->e[seg->v[i] + di] = ii;
						di++;
					}
				}
			}
		}

		for ( j = 0; j < g->d[v]; j++ )
		{
			int x = g->e[g->v[v]+j];

			int adj_to_u = 0;
			int jj = 0;
			for ( jj = 0; jj < g->d[u]; jj++ )
			{
				int xx = g->e[g->v[u] + jj];

				if ( x == xx )
				{
					adj_to_u = 1;
				}
			}

			if ( adj_to_u == 0 )
			{
				int t = 0;
				for ( t = 0; t < g->d[x]; t++ )
				{
					int y = g->e[g->v[x] + t];

					int ii = 0;
					for ( ii = 0; ii < num_edges; ii++ )
					{
						if ( (edge_list[2*ii] == x && edge_list[2*ii+1] == y )||(edge_list[2*ii] == y && edge_list[2*ii+1] == x ))
						{
							// add adjacency!
							seg->e[seg->v[i] + di] = ii;
							di++;
						}
					}
				}
			}
		}

		seg->d[i] = di;
	}

	return seg;	
}



