TP4_q4.c

#include "./implems.c"
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void aff_tab(unsigned long *t, int size)
{
	for (int i = 0; i < size; i++)
	{
		printf("%li ", t[i]);
	}
	printf("\n");
}

// génère un nombre aléatoire sur 4 octets
unsigned long randlu()
{
	unsigned long res = 0;
	unsigned long tmp1 = rand() & 0x0F;
	unsigned long tmp2 = rand() & 0x0F;
	unsigned long tmp3 = rand() & 0x0F;
	unsigned long tmp4 = rand() & 0x0F;

	tmp2 = tmp2 << 8;
	tmp3 = tmp3 << 16;
	tmp4 = tmp4 << 24;

	res = res | tmp1;
	res = res | tmp2;
	res = res | tmp3;
	res = res | tmp4;

	return res;
}

// génère un nombre aléatoire sur 4 octets entre min et max inclue
unsigned long randlu_from(unsigned long min, unsigned long max)
{
	unsigned long range = (max - min);
	return min + (randlu() % (range + 1));
}

void Fisher_Yates(unsigned long *tab, unsigned long size)
{
	unsigned long tmp;
	unsigned long rdm;
	for (unsigned long i = size - 1; i > 0; i--)
	{
		rdm = randlu_from(0, i);
		tmp = tab[i];
		tab[i] = tab[rdm];
		tab[rdm] = tmp;
	}
}

void ajuste_label_1(adjlist *g, unsigned long *label, unsigned long *label_count, unsigned long node, unsigned long commu)
{
	label[node] = commu;
	unsigned long size_commu = 1;
	unsigned long nb = 1;
	unsigned long best = 0;

	for (unsigned long i = 0; i < g->n; i++)
	{
		label_count[i] = 0;
	}

	for (unsigned long i = g->cd[node]; i < g->cd[node + 1]; i++)
	{
		if (label[g->adj[i]] == 0)
		{
			label_count[g->adj[i]]++;
		}
	}

	int in_progress = 1;

	while (in_progress)
	{
		in_progress = 0;
		nb = 1;
		best = label_count[0];

		for (unsigned long i = 1; i < g->n; i++)
		{
			if (label_count[i] > best)
			{
				best = label_count[i];
				nb = 1;
			}
			else if (label_count[i] == best)
			{
				nb++;
			}
		}

		if (best >= size_commu / 2)
		{
			in_progress = 1;
			unsigned long chosen = randlu_from(1, nb);
			unsigned long i = 0;

			while (i < g->n && chosen > 0)
			{
				if (label_count[i] == best)
				{
					chosen--;
					if (chosen == 0)
					{
						label[i] = commu;
						size_commu++;
						for (unsigned long j = g->cd[i]; j < g->cd[i + 1]; j++)
						{
							if (label[g->adj[j]] == 0)
							{
								label_count[g->adj[j]]++;
							}
						}
					}
				}
				i++;
			}
			if (chosen != 0)
			{
				printf("AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA\n");
			}
		}
	}
}

int ajuste_label_2(adjlist *g, unsigned long *label, unsigned long *label_count, unsigned long node)
{

	for (unsigned long i = 0; i < g->n; i++)
	{
		label_count[i] = 0;
	}

	for (unsigned long i = g->cd[node]; i < g->cd[node + 1]; i++)
	{
		label_count[label[g->adj[i]]]++;
	}

	unsigned long best = 0;

	for (unsigned long i = 1; i < g->n; i++)
	{
		if (label_count[i] > label_count[best])
		{
			best = i;
		}
	}

	if (label[node] == best)
	{
		return 0;
	}
	

	if (label_count[best] > (g->cd[node + 1] - g->cd[node]) / 2)
	{
		label[node] = best;
		return 1;
	}

	return 0;
}

unsigned long *label_propagation(adjlist *g)
{
	unsigned long *ordre = (unsigned long *)malloc(sizeof(unsigned long) * g->n);
	unsigned long *label = (unsigned long *)malloc(sizeof(unsigned long) * g->n);
	unsigned long *label_count = (unsigned long *)malloc(sizeof(unsigned long) * g->n);

	unsigned long nb_commu = 0;

	for (unsigned long i = 0; i < g->n; i++)
	{
		ordre[i] = i;
		label[i] = 0;
	}

	Fisher_Yates(ordre, g->n);
	for (unsigned long i = 0; i < g->n; i++)
	{
		if (label[i] == 0)
		{
			nb_commu++;
			ajuste_label_1(g, label, label_count, ordre[i], nb_commu);
		}
	}

	int in_progress = 1;

	while (in_progress)
	{
		in_progress = 0;
		Fisher_Yates(ordre, g->n);
		for (unsigned long i = 0; i < g->n; i++)
		{
			in_progress = in_progress | ajuste_label_2(g, label, label_count, ordre[i]);
		}
	}

	free(ordre);
	free(label_count);
	return label;
}

// -----------------------------------------------------------------------------------------------------------------------------------------

// renvoie le nombre de label et les renommes
unsigned long simplifie_label(unsigned long *label, unsigned long size)
{
	unsigned long c = 0;
	unsigned long smallest = size;
	unsigned long in_progress = 1;
	while (in_progress)
	{
		in_progress = 0;
		smallest = size;
		for (unsigned long i = 0; i < size; i++)
		{
			if (label[i] >= c && label[i] < smallest)
			{
				smallest = label[i];
				in_progress = 1;
			}
		}
		for (unsigned long i = 0; i < size; i++)
		{
			if (label[i] == smallest)
			{
				label[i] = c;
			}
		}
		c++;
	}
	return c - 1;
}

void output_graphe(adjlist *g, unsigned long *label, char *filename)
{
	FILE *ptr;
	unsigned long tmp_nb_node;

	tmp_nb_node = g->n;

	ptr = fopen(filename, "w");

	//définition des noeuds
	fprintf(ptr, "graph D {\n");
	//noeuds
	for (unsigned long k = 0; k < tmp_nb_node; k++)
	{
		fprintf(ptr, "%li [", k);
		switch (label[k])
		{
		case 0:
			fprintf(ptr, "color=red");
			break;
		case 1:
			fprintf(ptr, "color=blue");
			break;
		case 2:
			fprintf(ptr, "color=green");
			break;
		case 3:
			fprintf(ptr, "color=yellow");
			break;
		case 4:
			fprintf(ptr, "color=black");
			break;
		case 5:
			fprintf(ptr, "color=brown");
			break;
		case 6:
			fprintf(ptr, "color=orange");
			break;
		case 7:
			fprintf(ptr, "color=grey");
			break;
		case 8:
			fprintf(ptr, "color=magenta");
			break;
		case 9:
			fprintf(ptr, "color=aqua");
			break;
		case 10:
			fprintf(ptr, "color=lime");
			break;

		default:
			fprintf(ptr, "color=white");
			break;
		}

		fprintf(ptr, "]\n");
	}

	for (unsigned long k = 0; k < tmp_nb_node; k++)
	{
		for (unsigned long i = g->cd[k]; i < g->cd[k + 1]; i++)
		{
			if (g->adj[i] > k)
			{
				fprintf(ptr, "%li -- %li\n", k, g->adj[i]);
			}
		}
	}
	fprintf(ptr, "}");
	fclose(ptr);
	return;
}

// -----------------------------------------------------------------------------------------------------------------------------------------

int main(int argc, char **argv)
{
	if (argc < 2)
	{
		printf("un argument est attendu\n");
		return 1;
	}

	adjlist *g;
	time_t t1, t2, t3, t4;

	// PARSING
	t1 = time(NULL);

	printf("Reading edgelist from file %s\n", argv[1]);
	g = al_readedgelist(argv[1]);
	t3 = time(NULL);
#if defined(WIN32) || defined(_WIN32) || defined(__WIN32) && !defined(__CYGWIN__)
	printf("- edge list time = %I64dh%I64dm%I64ds\n", (t3 - t1) / 3600, ((t3 - t1) % 3600) / 60, ((t3 - t1) % 60));
#else
	printf("- edge list time = %ldh%ldm%lds\n", (t3 - t1) / 3600, ((t3 - t1) % 3600) / 60, ((t3 - t1) % 60));
#endif

	printf("Number of nodes: %lu\n", g->n);
	printf("Number of edges: %lu\n", g->e);

	printf("Building the adjacency list\n");
	mkadjlist(g);

	t2 = time(NULL);

#if defined(WIN32) || defined(_WIN32) || defined(__WIN32) && !defined(__CYGWIN__)
	printf("- Overall time = %I64dh%I64dm%I64ds\n", (t2 - t1) / 3600, ((t2 - t1) % 3600) / 60, ((t2 - t1) % 60));
#else
	printf("- Overall time = %ldh%ldm%lds\n", (t2 - t1) / 3600, ((t2 - t1) % 3600) / 60, ((t2 - t1) % 60));
#endif

	// srand(time(NULL));

	unsigned long *res = label_propagation(g);

	t4 = time(NULL);

#if defined(WIN32) || defined(_WIN32) || defined(__WIN32) && !defined(__CYGWIN__)
	printf("- label_propagation time = %I64dh%I64dm%I64ds\n", (t4 - t2) / 3600, ((t4 - t2) % 3600) / 60, ((t4 - t2) % 60));
#else
	printf("- label_propagation time = %ldh%ldm%lds\n", (t4 - t2) / 3600, ((t4 - t2) % 3600) / 60, ((t4 - t2) % 60));
#endif

	unsigned long nb = simplifie_label(res, g->n);
	printf("%li label different\n", nb);
	output_graphe(g, res, "toto.dot");

	printf("run {dot -Tpng -o out.png toto.dot} pour avoir une visualisation de la solution\n");

	free(res);
	free_adjlist(g);
	return 0;
}