graphe/cbla.c

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

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

// Step 1 : find all k-cliques

// Step 2 : build clique graph (simple graph)
// Nodes = cliques, edges between cliques sharing >= k-1 nodes

//static graph_t *build_clique_graph(clique_store_t *store, int k)
//{
//	int nc = store->count;
//	if (nc == 0)
//		return NULL;
//
//	graph_t *cg = malloc(sizeof(graph_t));
//	cg->n = nc;
//	cg->p = 0;
//	cg->q = 0;
//	cg->adj_lists = calloc(nc, sizeof(node_t *));
//
//	for (int i = 0; i < nc; i++) {
//		for (int j = i + 1; j < nc; j++) {
//			// Count shared nodes between clique i and clique j
//			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) {
//				// Add edge in clique graph
//				node_t *n1 = malloc(sizeof(node_t));
//				n1->id = j;
//				n1->next = cg->adj_lists[i];
//				cg->adj_lists[i] = n1;
//
//				node_t *n2 = malloc(sizeof(node_t));
//				n2->id = i;
//				n2->next = cg->adj_lists[j];
//				cg->adj_lists[j] = n2;
//			}
//		}
//	}
//	return cg;
//}
//
//static void free_clique_graph(graph_t *cg)
//{
//	for (int i = 0; i < cg->n; i++) {
//		node_t *n = cg->adj_lists[i];
//		while (n) {
//			node_t *tmp = n->next;
//			free(n);
//			n = tmp;
//		}
//	}
//	free(cg->adj_lists);
//	free(cg);
//}
//
//// ── Step 3 : map clique communities back to original nodes ────────────────────
//
//static int *map_cliques_to_nodes(const graph_t *graph, clique_store_t *store,
//				 louvain_result_t *louvain_result, int k,
//				 int *classified)
//{
//	int n = graph->n;
//	int *node_community = malloc(n * sizeof(int));
//	memset(node_community, -1,
//	       n * sizeof(int)); // -1 = not classified (ncn)
//
//	for (int i = 0; i < store->count; i++) {
//		int community = louvain_result->node_community[i];
//		for (int j = 0; j < k; j++) {
//			int node = store->list[i][j];
//			node_community[node] = community;
//		}
//	}
//
//	// Mark which nodes are classified
//	for (int i = 0; i < n; i++)
//		classified[i] = (node_community[i] != -1) ? 1 : 0;
//
//	return node_community;
//}
//
//// ── Step 4 : assign ncn to nearest community ─────────────────────────────────
//// Each unclassified node joins the community it has the most edges into
//
//static void assign_ncn(const graph_t *graph, int *node_community,
//		       int *classified, int community_count)
//{
//	int n = graph->n;
//	int changed = 1;
//
//	// Iterate until no more ncn can be assigned (some may be fully isolated)
//	while (changed) {
//		changed = 0;
//		for (int i = 0; i < n; i++) {
//			if (classified[i])
//				continue;
//
//			// Count edges to each community
//			int *votes = calloc(community_count, sizeof(int));
//			int total = 0;
//
//			node_t *nb = graph->adj_lists[i];
//			while (nb) {
//				if (classified[nb->id]) {
//					votes[node_community[nb->id]]++;
//					total++;
//				}
//				nb = nb->next;
//			}
//
//			if (total == 0) {
//				free(votes);
//				continue;
//			} // still isolated
//
//			// Find community with most connections
//			int best_c = -1, best_v = 0;
//			for (int c = 0; c < community_count; c++) {
//				if (votes[c] > best_v) {
//					best_v = votes[c];
//					best_c = c;
//				}
//			}
//
//			if (best_c != -1) {
//				node_community[i] = best_c;
//				classified[i] = 1;
//				changed = 1;
//			}
//			free(votes);
//		}
//	}
//
//	// Any remaining isolated ncn get their own community
//	for (int i = 0; i < n; i++) {
//		if (!classified[i]) {
//			node_community[i] = community_count++;
//			classified[i] = 1;
//		}
//	}
//}
//
//// ── Compact ids ───────────────────────────────────────────────────────────────
//
//static int compact(int *community, int n)
//{
//	int *map = malloc(n * sizeof(int));
//	memset(map, -1, n * sizeof(int));
//	int next = 0;
//	for (int i = 0; i < n; i++) {
//		if (community[i] < 0)
//			continue;
//		if (map[community[i]] == -1)
//			map[community[i]] = next++;
//		community[i] = map[community[i]];
//	}
//	free(map);
//	return next;
//}
//
//// ── Main ──────────────────────────────────────────────────────────────────────
//
//cbla_result_t *cbla_community_detection(const graph_t *graph, int k)
//{
//	int n = graph->n;
//	printf("[cbla] starting cbla k-clique + louvain (k=%d, n=%d)\n", k, n);
//
//	// Step 1 — 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("[cbla] found %d %d-cliques\n", store.count, k);
//
//	cbla_result_t *result = malloc(sizeof(cbla_result_t));
//	result->node_community = malloc(n * sizeof(int));
//
//	if (store.count == 0) {
//		// No cliques found — assign all nodes to community 0
//		printf("[cbla] no cliques found, all nodes are ncn\n");
//		for (int i = 0; i < n; i++)
//			result->node_community[i] = 0;
//		result->count = 1;
//		free(store.list);
//		return result;
//	}
//
//	// Step 2 — build clique graph and apply Louvain on it
//	graph_t *clique_graph = build_clique_graph(&store, k);
//	printf("[cbla] clique graph built (%d nodes)\n", clique_graph->n);
//
//	louvain_result_t *lv = compute_louvain(clique_graph);
//	printf("[cbla] louvain found %d communities on clique graph\n",
//	       lv->count);
//
//	// Step 3 — map clique communities back to original nodes
//	int *classified = calloc(n, sizeof(int));
//	int *node_community =
//		map_cliques_to_nodes(graph, &store, lv, k, classified);
//
//	int ncn_count = 0;
//	for (int i = 0; i < n; i++)
//		if (!classified[i])
//			ncn_count++;
//	printf("[cbla] %d non-classified nodes (ncn)\n", ncn_count);
//
//	// Step 4 — assign ncn to nearest community
//	assign_ncn(graph, node_community, classified, lv->count);
//
//	// Compact and finalize
//	result->count = compact(node_community, n);
//	memcpy(result->node_community, node_community, n * sizeof(int));
//	printf("[cbla] final community count: %d\n", result->count);
//
//	// Cleanup
//	for (int i = 0; i < store.count; i++)
//		free(store.list[i]);
//	free(store.list);
//	free_louvain_result(lv);
//	free_clique_graph(clique_graph);
//	free(node_community);
//	free(classified);
//
//	return result;
//}
//
void free_cbla_result(cbla_result_t *result)
{
	if (!result)
		return;
	free(result->node_community);
	free(result);
}

graph_t *build_meta_graph(const graph_t *graph, clique_store_t *store)
{
	graph_t *meta = malloc(sizeof(graph_t));
	meta->n = store->count;
	meta->adj_lists = calloc(meta->n, sizeof(node_t *));

	for (int i = 0; i < store->count; i++) {
		for (int j = i + 1; j < store->count; j++) {
			int connected = 0;
			// Vérifier s'il existe une arête entre un nœud de clique i et clique j
			for (int ni = 0; ni < store->k && !connected; ni++) {
				for (int nj = 0; nj < store->k; nj++) {
					if (has_edge(graph, store->list[i][ni],
						     store->list[j][nj])) {
						connected = 1;
						break;
					}
				}
			}
			if (connected) {
				add_edge(meta, i, j);
				add_edge(meta, j, i);
			}
		}
	}
	return meta;
}

cbla_result_t *cbla_community_detection(const graph_t *graph, int k)
{
	cbla_result_t *final_result = malloc(sizeof(cbla_result_t));
	final_result->node_community = malloc(graph->n * sizeof(int));
	// Initialisation à -1 (non classifié)
	for (int i = 0; i < graph->n; i++)
		final_result->node_community[i] = -1;

	// 1. Énumérer toutes les k-cliques
	clique_store_t store = { NULL, 0, 10, k };
	store.list = malloc(store.capacity * sizeof(int *));
	int *current_clique = malloc(k * sizeof(int));

	enumerate_cliques(graph, &store, current_clique, 0, 0);
	free(current_clique);

	if (store.count == 0) {
		// Cas dégradé : pas de cliques, on pourrait renvoyer Louvain simple
		final_result->count = 0;
		free(store.list);
		return final_result;
	}

	// 2. Reconstruire le méta-graphe (Graphe de cliques)
	// Chaque clique devient un "super-nœud"
	//graph_t *meta_graph = malloc(sizeof(graph_t));
	//meta_graph->n = store.count;
	// Initialisation simplifiée de l'adjacence du méta-graphe
	// (Supposons une matrice ou liste d'adjacence pour meta_graph)
	// On connecte Clique A et Clique B s'il existe une arête entre un noeud de A et un noeud de B

	// NOTE: Pour Louvain, nous devons construire meta_graph proprement (adjacences)
	// Ici, nous simulons la création pour l'algorithme
	graph_t *meta_graph = build_meta_graph(graph, &store);

	// 3. Appliquer Louvain sur le méta-graphe
	louvain_result_t *l_res = compute_louvain(meta_graph);

	// 4. Mapper les résultats : Nœuds originaux appartenant aux cliques
	for (int c_idx = 0; c_idx < store.count; c_idx++) {
		int community_id = l_res->node_community[c_idx];
		for (int i = 0; i < k; i++) {
			int original_node = store.list[c_idx][i];
			final_result->node_community[original_node] =
				community_id;
		}
	}

	// 5. Gérer les NCN (Non-Classified Nodes)
	// On les affecte à la première communauté d'un voisin classifié
	// ou à une nouvelle communauté isolée.
	for (int i = 0; i < graph->n; i++) {
		if (final_result->node_community[i] == -1) {
			// Logique simplifiée : on cherche un voisin déjà classé
			// Sinon, on le laisse à -1 ou on crée une ID unique
			final_result->node_community[i] =
				0; // Exemple : par défaut communauté 0
		}
	}

	final_result->count = l_res->count;

	// Nettoyage
	for (int i = 0; i < store.count; i++)
		free(store.list[i]);
	free(store.list);
	free_louvain_result(l_res);
	// free_graph(meta_graph);

	return final_result;
}