Resolución del problema de K-Clustering sobre grafos no dirigidos y no pesados para Teoría de Algoritmos (FIUBA).

Integrantes

• Franco Guardia
• Mateo Requejo
• Santino Regidor

Descripción

El problema de K-Clustering se puede definir como: dado un grafo y un valor K, particionar los vértices en K clusters minimizando la máxima distancia (diámetro) dentro de cada cluster.

Se implementan tres enfoques algorítmicos distintos para resolver el problema:

• Programación Lineal (PL): formulación como problema de optimización entera binaria, resuelto con PuLP (CBC solver). Garantiza la solución óptima.
• Backtracking: exploración exhaustiva con podas por cota superior y ordenamiento por grado. Garantiza la solución óptima.
• Louvain (Aproximación): algoritmo de detección de comunidades basado en optimización de modularidad, adaptado para producir exactamente K clusters. No garantiza optimalidad pero es significativamente más rápido.

Requisitos

• Python 3
• Dependencias: networkx, pulp, matplotlib, numpy

Las cuales pueden instalarse con:

pip install networkx pulp matplotlib numpy

Estructura del proyecto

.
├── tp3.py                   # Punto de entrada principal
├── backtracking.py          # Solución exacta por backtracking con podas
├── programacion_lineal.py   # Solución exacta por programación lineal entera
├── louvain.py               # Solución aproximada (Louvain adaptado a K clusters)
├── validador.py             # Validador de soluciones
├── comparar_algoritmos.py   # Comparación de calidad y tiempos entre algoritmos
├── util.py                  # Funciones auxiliares (ejecución paralela, generación de grafos)
├── cuadrados_minimos.py     # Análisis de complejidad por cuadrados mínimos
├── grafos/                  # Grafos de entrada
├── tests/                   # Tests unitarios
└── tests_catedra/           # Tests de la cátedra con resultados esperados

Ejecución

python3 tp3.py grafos/<nombre_grafo>.txt <K>

Donde:

• <nombre_grafo>.txt es un archivo donde cada línea representa una arista con el formato nodo1,nodo2
• es la cantidad de clusters deseada (entero positivo)

El programa presenta un menú interactivo para elegir el algoritmo:

Ingrese el algoritmo a utilizar:
1. Programación Lineal
2. Backtracking
3. Louvain

Ejemplo

python3 tp3.py grafos/10_3.txt 3

Salida esperada (puede variar en asignación, no en distancia óptima):

Cluster 1 = ['0', '1', '3', '4', '5', '8', '9']
Cluster 2 = ['2', '6', '7']
Distancia maxima = 2

Formato de entrada

Archivo de texto plano donde cada línea define una arista:

0,1
0,8
1,4
1,3

Los nodos se identifican por strings y el grafo se interpreta como no dirigido y no pesado.

Comparación de algoritmos

Se incluye un script para comparar la calidad y el tiempo de ejecución de Backtracking vs Louvain:

python3 comparar_algoritmos.py

Genera un gráfico comparando el diámetro máximo obtenido por cada algoritmo en los distintos grafos de prueba.

Créditos

Proyecto realizado como trabajo práctico académico en la materia Teoría de Algoritmos (FIUBA).