graphe/cliques.c

//
// Created by Tiago Batista Cardoso on 2/26/2026.
//

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

static int degree(const graph_t *graph, int v)
{
	int d = 0;
	node_t *n = graph->adj_lists[v];
	while (n) {
		d++;
		n = n->next;
	}
	return d;
}

// Sort vertices by degree descending
static int *sort_by_degree_desc(const graph_t *graph)
{
	int n = graph->n;
	int *order = malloc(n * sizeof(int));
	for (int i = 0; i < n; i++)
		order[i] = i;

	// Simple insertion sort — fine for this use case
	for (int i = 1; i < n; i++) {
		int key = order[i];
		int key_deg = degree(graph, key);
		int j = i - 1;
		while (j >= 0 && degree(graph, order[j]) < key_deg) {
			order[j + 1] = order[j];
			j--;
		}
		order[j + 1] = key;
	}
	return order;
}

// Check if vertex v is adjacent to all vertices in clique
static int adjacent_to_all(const graph_t *graph, int *clique, int size, int v)
{
	for (int i = 0; i < size; i++)
		if (!has_edge(graph, v, clique[i]))
			return 0;
	return 1;
}

int find_max_clique_size(const graph_t *graph)
{
	int n = graph->n;

	int *order = sort_by_degree_desc(graph);
	int *max_clique = malloc(n * sizeof(int));
	int *curr_clique = malloc(n * sizeof(int));
	int max_size = 0;

	for (int i = 0; i < n; i++) {
		int v = order[i];

		curr_clique[0] = v;
		int curr_size = 1;

		node_t *nb = graph->adj_lists[v];
		while (nb) {
			if (adjacent_to_all(graph, curr_clique, curr_size,
					    nb->id))
				curr_clique[curr_size++] = nb->id;
			nb = nb->next;
		}

		if (curr_size > max_size) {
			max_size = curr_size;
			memcpy(max_clique, curr_clique,
			       curr_size * sizeof(int));

			printf("[max_clique] new max clique of size %d: {",
			       max_size);
			for (int j = 0; j < max_size; j++)
				printf("%d%s", max_clique[j],
				       j < max_size - 1 ? ", " : "");
			printf("}\n");
		}
	}

	printf("[max_clique] final max clique size: %d\n", max_size);

	free(order);
	free(max_clique);
	free(curr_clique);
	return max_size;
}

void store_clique(clique_store_t *store, int *current)
{
	if (store->count >= store->capacity) {
		store->capacity *= 2;
		store->list =
			realloc(store->list, store->capacity * sizeof(int *));
	}
	int *copy = malloc(store->k * sizeof(int));
	memcpy(copy, current, store->k * sizeof(int));
	store->list[store->count++] = copy;
}

void enumerate_cliques(const graph_t *graph, clique_store_t *store,
		       int *current, int depth, int start)
{
	if (depth == store->k) {
		store_clique(store, current);
		return;
	}
	for (int v = start; v < graph->n; v++) {
		if (depth > 0 && v <= current[depth - 1])
			continue;

		// v must be connected to all nodes already in current
		int ok = 1;
		for (int i = 0; i < depth; i++) {
			if (!has_edge(graph, current[i], v)) {
				ok = 0;
				break;
			}
		}
		if (!ok)
			continue;
		current[depth] = v;
		enumerate_cliques(graph, store, current, depth + 1, v + 1);
	}
}

static int uf_find(int *parent, int x)
{
	while (parent[x] != x) {
		parent[x] = parent[parent[x]];
		x = parent[x];
	}
	return x;
}

static void uf_union(int *parent, int *rank, int a, int b)
{
	a = uf_find(parent, a);
	b = uf_find(parent, b);
	if (a == b)
		return;
	if (rank[a] < rank[b]) {
		int t = a;
		a = b;
		b = t;
	}
	parent[b] = a;
	if (rank[a] == rank[b])
		rank[a]++;
}

void compute_kclique_distribution(const graph_t *graph)
{
	printf("\n=== Distribution des k-cliques ===\n");
	printf("%-5s %-15s %-20s\n", "k", "communautes", "noeuds_classes");

	int max_clique = find_max_clique_size(graph);

	for (int k = 2; k <= max_clique; k++) {
		community_result_t *result =
			find_k_clique_communities(graph, k);

		if (!result || result->count == 0) {
			printf("%-5d %-15d (aucune clique de taille %d)\n", k,
			       0, k);
			free_community_result(result);
			break; // inutile de continuer, k plus grand donnera aussi 0
		}

		// Compter les noeuds effectivement classés (non isolés)
		int classified = 0;
		for (int i = 0; i < graph->n; i++)
			if (result->node_community[i] != -1)
				classified++;

		printf("%-5d %-15d %-20d\n", k, result->count, classified);
		free_community_result(result);
	}
	printf("==================================\n");
}

community_result_t *find_k_clique_communities(const graph_t *graph, int k)
{
	clock_t start, end;
	double cpu_time_used;
	printf("[find_k_clique_communities()] starting...\n");
	start = clock();

	int n = graph->n;

	// find all k-cliques
	clique_store_t store = { .list = malloc(64 * sizeof(int *)),
				 .count = 0,
				 .capacity = 64,
				 .k = k };
	int *current = malloc(k * sizeof(int));
	enumerate_cliques(graph, &store, current, 0, 0);
	free(current);
	printf("[communities] found %d %d-cliques\n", store.count, k);

	// union-find : merge cliques sharing k-1 nodes
	int *parent = malloc(store.count * sizeof(int));
	int *rank = calloc(store.count, sizeof(int));
	for (int i = 0; i < store.count; i++)
		parent[i] = i;

	for (int i = 0; i < store.count; i++) {
		for (int j = i + 1; j < store.count; j++) {
			// Count shared nodes
			int shared = 0;
			for (int a = 0; a < k; a++)
				for (int b = 0; b < k; b++)
					if (store.list[i][a] ==
					    store.list[j][b])
						shared++;
			if (shared >= k - 1)
				uf_union(parent, rank, i, j);
		}
	}

	community_result_t *result = malloc(sizeof(community_result_t));
	result->node_community = malloc(n * sizeof(int));
	for (int i = 0; i < n; i++)
		result->node_community[i] = -1;

	for (int i = 0; i < store.count; i++) {
		int community_id = uf_find(parent, i);
		for (int j = 0; j < k; j++) {
			int node = store.list[i][j];
			result->node_community[node] = community_id;
		}
	}

	int *id_map = malloc(store.count * sizeof(int));
	memset(id_map, -1, store.count * sizeof(int));
	int next_id = 0;
	for (int i = 0; i < n; i++) {
		int c = result->node_community[i];
		if (c == -1)
			continue;
		if (id_map[c] == -1)
			id_map[c] = next_id++;
		result->node_community[i] = id_map[c];
	}
	result->count = next_id;
	printf("[communities] found %d communities\n", result->count);

	end = clock();
	cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;
	printf("[find_k_clique_communities()] done (%f s)\n", cpu_time_used);

	// cleanup
	for (int i = 0; i < store.count; i++)
		free(store.list[i]);
	free(store.list);
	free(parent);
	free(rank);
	free(id_map);

	return result;
}

void free_community_result(community_result_t *result)
{
	if (!result)
		return;
	free(result->node_community);
	free(result);
}