path: root/algos.c

#include <assert.h>
#include <stdbool.h>
#include <stdlib.h>

#include "algos.h"


/* Heuristique de coloriage
 * Trouve un coloriage non-optimal (mais parfois proche) du sous-graphe engendré
 * par s dans le graphe g.
 * Ne donne pas le coloriage, mais juste le nombre de couleurs d'un coloriage possible (nombre que l'on cherche à minimiser)
 */

void color_subgraph_aux(const graph g, int *colors, int *v, int *nneigh, const int n) {
	int i, j, t;

	if (n == 0) return;

	if (n == 1) {
		colors[0] = 0;
		return;
	}

	// Find element with smallest neighbours count
	int x = 0;
	for (i = 1; i < n; i++) {
		if (nneigh[i] < nneigh[x]) x = i;
	}

	// Put that element at the beginning of vector v, so that the remaining subgraph is defined by v[1..]
	if (x != 0) {
		t = v[x];
		v[x] = v[0];
		v[0] = t;

		t = nneigh[x];
		nneigh[x] = nneigh[0];
		nneigh[0] = t;
	}

	// update nneigh
	for (i = 1; i < n; i++) {
		if (set_mem(v[i], graph_neighbours(g, v[0]))) nneigh[i]--;
	}

	// Color remaining subgraph (v[1..])
	color_subgraph_aux(g, colors + 1, v + 1, nneigh + 1, n - 1);

	// Find free color
	colors[0] = -1;
	bool used[n];
	for (i = 0; i < n; i++) used[i] = false;
	for (i = 1; i < n; i++) {
		if (set_mem(v[i], graph_neighbours(g, v[0])))
			used[colors[i]] = true;
	}
	for (i = 0; i < n; i++) {
		if (used[i] == false) {
			colors[0] = i;
			break;
		}
	}
	assert(colors[0] != -1);
}

int color_subgraph(const graph g, set s, int dump_colors) {
	int i, j, m;

	const int n = set_size(s);
	if (n == 0) return 0;

	int colors[n], vertices[n], nneigh[n];
	for (i = 0; i < n; i++)
		colors[i] = -1;
	
	// Put all vertices in vertice vector (order is not important)
	vertices[0] = elt_of_set(s);
	set_remove_ip(vertices[0], s);
	i = 1;
	while (!is_set_empty(s)) {
		vertices[i] = elt_of_set_heur(s, vertices[i-1]);
		set_remove_ip(vertices[i], s);
		i++;
	}

	// Calculate neighbour count for all nodes
	for (i = 0; i < n; i++) nneigh[i] = 0;
	for (i = 0; i < n; i++) {
		for (j = 0; j < n; j++) {
			if (set_mem(vertices[i], graph_neighbours(g, vertices[j])))
				nneigh[i]++;
		}
	}

	// Color graph
	color_subgraph_aux(g, colors, vertices, nneigh, n);

	// Count colors
	m = -1;
	for (i = 0; i < n; i++) {
		assert(colors[i] != -1);
		if (colors[i] > m) m = colors[i];
		if (dump_colors) printf("%d:%d ", vertices[i], colors[i]);
	}
	if (dump_colors) printf("\n");
	
	return m + 1;
}


/*Premier algorithme naïf.
 * g : graphe où on cherche les cliques
 * k : clique actuelle
 * c : noeuds candidats à l'ajout
 * mc : clique maximale actuelle
*/
void max_clique_a(const graph g, set k, set c, set *mc) {
	if (is_set_empty(c)) {
		if (set_size(k) > set_size(*mc)) {
			delete_set(*mc);
			*mc = copy_set(k);
			printf("Found new max clique: "); dump_set(*mc); fflush(stdout);
		}
	} else {
		set cc = copy_set(c);
		while (!(is_set_empty(cc))) {
			int x = elt_of_set(cc);
			set_remove_ip(x, cc);

			set k2 = set_add(x, k);
			set c2 = set_inter(c, graph_neighbours(g, x));
			max_clique_a(g,k2, c2, mc);
			delete_set(k2);
			delete_set(c2);
		}
		delete_set(cc);
	}
}

/** Algorithme avec l'optimisation : on évite d'énumérer plusieurs fois
 * la même clique.
 * g : graphe où on cherche les cliques
 * k : clique actuelle
 * c : noeuds candidats à l'ajout
 * a : noeuds que l'on s'autorise à ajouter
 * mc : clique maximale actuelle
 * */
// Voir notice de convention ci-dessous
void max_clique_b(const graph g, set k, set c, set a, set *mc) {
	if (is_set_empty(c)) {
		if (set_size(k) > set_size(*mc)) {
			delete_set(*mc);
			*mc = copy_set(k);
			printf("Found new max clique: "); dump_set(*mc); fflush(stdout);
		}
	} else {
		while (!(is_set_empty(a))) {
			int x = elt_of_set(a);
			set_remove_ip(x, a);

			set k2 = set_add(x, k);
			set c2 = set_inter(c, graph_neighbours(g, x));
			set a2 = set_inter(a,  graph_neighbours(g, x));
			
			max_clique_b(g,k2, c2, a2, mc);
			delete_set(k2);
			delete_set(c2);
			delete_set(a2);
		}
	}
}

/** Algorithme avec la méthode du pivot
 * la même clique.
 * g : graphe où on cherche les cliques
 * k : clique actuelle
 * c : noeuds candidats à l'ajout
 * a : noeuds que l'on s'autorise à ajouter
 * mc : clique maximale actuelle
 * */
// Convention : lors d'un appel de fonction, les set donnés en
// argument peuvent être modifiés à la guise de l'algorithme
// Il est donc de la responsabilité de l'appellant de vérifier qu'à
// chaque appel les sets sont utilisables et cohérents
void max_clique_c(const graph g, set k, set c, set a, set *mc) {
	// If we have no chance of improving our max clique, exit
	if (set_size(k) + set_size(c) <= set_size(*mc)) return;

	// If we have improved our clique, great
	if (set_size(k) > set_size(*mc)) {
		delete_set(*mc);
		*mc = copy_set(k);
		printf("Found new max clique: "); dump_set(*mc); fflush(stdout);
	}

	// If we have no possibility to explore, return
	if (is_set_empty(c)) return;

	// Find u that maximises |C inter Gamma(u)|
	set c_it = copy_set(c);
	int u = elt_of_set(c_it), n = 0;
	set_remove_ip(u, c_it);

	{	set temp = set_inter(c, graph_neighbours(g, u));
		n = set_size(temp);
		delete_set(temp);
	}

	// Explore possibilites
	int heur = u;
	while (!is_set_empty(c_it)) {
		int uprime = elt_of_set_heur(c_it, heur);
		set_remove_ip(uprime, c_it);
		heur = uprime;

		set temp = set_inter(c, graph_neighbours(g, uprime));
		if (set_size(temp) > n) {
			n = set_size(temp);
			u = uprime;
		}
		delete_set(temp);
	}
	delete_set(c_it);


	set t = set_diff(a, graph_neighbours(g, u));
	heur = u;
	while (!is_set_empty(t)) {
		int x = elt_of_set_heur(t, heur);
		heur = x;

		set k2 = set_add(x, k);
		set c2 = set_inter(c, graph_neighbours(g, x));
		set a2 = set_inter(a, graph_neighbours(g, x));
		max_clique_c(g, k2, c2, a2, mc);
		delete_set(a2);
		delete_set(c2);
		delete_set(k2);

		set_remove_ip(x, a);
		delete_set(t);
		t = set_diff(a, graph_neighbours(g, u));
	}
	delete_set(t);
}

void max_clique_c_color(const graph g, set k, set c, set a, set *mc, int prev_size) {
	// If we have no chance of improving our max clique, exit
	if (set_size(k) + set_size(c) <= set_size(*mc)) return;

	// If we have improved our clique, great
	if (set_size(k) > set_size(*mc)) {
		delete_set(*mc);
		*mc = copy_set(k);
		printf("Found new max clique: "); dump_set(*mc); fflush(stdout);
	}

	// If we have no possibility to explore, return
	if (is_set_empty(c)) return;

	if (set_size(c) <= prev_size / 2 && (set_size(c) >= 20 || set_size(c) >= g->N / 24)) {
		prev_size = set_size(c);
		// Color graph : we may have no possibility
		set c_copy = copy_set(c);
		int color_count = color_subgraph(g, c_copy, 0);
		delete_set(c_copy);
		if (set_size(k) + color_count <= set_size(*mc)) return;
	}


	// Find u that maximises |C inter Gamma(u)|
	set c_it = copy_set(c);
	int u = elt_of_set(c_it), n = 0;
	set_remove_ip(u, c_it);

	{	set temp = set_inter(c, graph_neighbours(g, u));
		n = set_size(temp);
		delete_set(temp);
	}

	// Explore possibilites
	int heur = u;
	while (!is_set_empty(c_it)) {
		int uprime = elt_of_set_heur(c_it, heur);
		set_remove_ip(uprime, c_it);
		heur = uprime;

		set temp = set_inter(c, graph_neighbours(g, uprime));
		if (set_size(temp) > n) {
			n = set_size(temp);
			u = uprime;
		}
		delete_set(temp);
	}
	delete_set(c_it);


	set t = set_diff(a, graph_neighbours(g, u));
	heur = u;
	while (!is_set_empty(t)) {
		int x = elt_of_set_heur(t, heur);
		heur = x;

		set k2 = set_add(x, k);
		set c2 = set_inter(c, graph_neighbours(g, x));
		set a2 = set_inter(a, graph_neighbours(g, x));
		max_clique_c_color(g, k2, c2, a2, mc, prev_size);
		delete_set(a2);
		delete_set(c2);
		delete_set(k2);

		set_remove_ip(x, a);
		delete_set(t);
		t = set_diff(a, graph_neighbours(g, u));
	}
	delete_set(t);
}