El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
HOME Mis cursos Finalizados
◄ Anterior
◄

Aplicaciones de los Grafos

Siguiente ►
►

Ya tenemos toda la teoría del módulo: recorridos (07-03), caminos mínimos (07-04) y árboles de expansión (07-05). Esta lección no introduce ni un algoritmo nuevo: los pone a trabajar en aplicaciones completas y reconocibles. Primero, el plato fuerte: el planificador de TaskFlow, que combina orden topológico, detección de ciclos, paralelización por niveles y el cálculo de la ruta crítica del proyecto. Después saldremos de TaskFlow para ver dos clásicos: la sugerencia de colaboradores de una red social (amigos-de-amigos con BFS) y un PageRank en miniatura, el algoritmo que hizo despegar a Google. Cerramos con un panorama de los grafos en producción. Todo el código corre sobre la clase Grafo de 07-02.

Contenido

  1. El planificador de TaskFlow completo
    • Validar: detección de ciclos
    • Ordenar: orden topológico
    • Paralelizar: tareas por niveles
    • Estimar: la ruta crítica del proyecto
  2. Sugerencia de colaboradores: amigos-de-amigos
  3. PageRank simplificado
  4. Grafos en producción: panorama breve

El planificador de TaskFlow completo

Partimos del grafo dependencias y del índice tareas de 07-02 (recuerda: cada tarea es un dict con id, titulo, prioridad, estado y horas; la arista A → B significa "B depende de A"). El planificador debe responder, en este orden, cuatro preguntas: ¿es ejecutable el proyecto?, ¿en qué orden?, ¿qué puede hacerse en paralelo?, ¿cuántas horas durará como mínimo?

Validar: detección de ciclos

Nada tiene sentido si hay un ciclo, así que el planificador empieza reutilizando hay_ciclo (blanco/gris/negro, 07-03) como guardia de entrada:

def planificar(grafo, tareas):
    if hay_ciclo(grafo):
        raise ValueError("Dependencias circulares: revisa el proyecto")
    return {
        "orden": orden_topologico(grafo),        # 07-03, Kahn
        "niveles": niveles_paralelos(grafo),     # nuevo, abajo
        "duracion": ruta_critica(grafo, tareas), # nuevo, abajo
    }

En una aplicación real esta validación correría también antes de aceptar cada nueva dependencia, que es más barato que dejar que el error se acumule.

Ordenar: orden topológico

orden_topologico (Kahn, 07-03) ya nos da una secuencia válida de ejecución para un solo trabajador. Nada nuevo que añadir — salvo notar que un orden en serie desaprovecha al equipo: si disenar_esquema y disenar_ui no dependen entre sí, ¿por qué esperarse?

Paralelizar: tareas por niveles

La versión por capas de Kahn agrupa las tareas en niveles: el nivel 0 son las tareas sin dependencias; el nivel k, las que quedan listas cuando terminan los niveles anteriores. Todas las tareas de un mismo nivel pueden ejecutarse en paralelo:

from collections import deque

def niveles_paralelos(grafo):
    grados = grafo.grados_entrada()
    nivel_actual = [v for v, g in grados.items() if g == 0]
    niveles = []
    while nivel_actual:
        niveles.append(nivel_actual)
        siguiente = []
        for v in nivel_actual:                 # "terminamos" todo el nivel a la vez
            for vecino in grafo.vecinos(v):
                grados[vecino] -= 1
                if grados[vecino] == 0:
                    siguiente.append(vecino)
        nivel_actual = siguiente
    return niveles

for i, nivel in enumerate(niveles_paralelos(dependencias)):
    print(f"Nivel {i}: {nivel}")
# Nivel 0: ['disenar_esquema', 'configurar_servidor', 'disenar_ui']
# Nivel 1: ['migrar_bd', 'implementar_ui']
# Nivel 2: ['desplegar_api']
# Nivel 3: ['pruebas_integracion']
# Nivel 4: ['lanzamiento']

Es el mismo Kahn de 07-03, pero procesando la cola por tandas en lugar de elemento a elemento — compárese con el recorrido por niveles del módulo 6, que hacía exactamente esta maniobra sobre árboles. Lectura de gestión: con gente suficiente, el proyecto necesita 5 tandas; tres personas pueden arrancar el lunes a la vez.

Estimar: la ruta crítica del proyecto

Pregunta final: con paralelismo ilimitado, ¿cuántas horas como mínimo dura el proyecto? No es la suma de todas las horas (hay paralelo), ni el camino mínimo de 07-04. Es el camino más largo del DAG contando las horas de cada tarea: la ruta crítica. Cualquier retraso en ella retrasa el proyecto entero; las demás tareas tienen holgura.

¿Camino más largo? Suena a invertir Dijkstra (negar pesos... solo válido sin ciclos), pero en un DAG hay una vía más limpia y sin trampas: orden topológico + programación dinámica. Recorriendo las tareas en orden topológico, cuando llegamos a una tarea ya conocemos el momento de fin de todas sus dependencias, así que:

fin(v) = horas(v) + max(fin(u) para cada dependencia u de v; 0 si no tiene)
def ruta_critica(grafo, tareas):
    fin = {}          # id -> hora de finalizacion mas temprana posible
    padre_critico = {}
    for v in orden_topologico(grafo):          # garantiza fin(u) ya calculado
        mejor, culpable = 0, None
        for u in grafo.vertices():             # dependencias de v: aristas u -> v
            if grafo.existe_arista(u, v) and fin[u] > mejor:
                mejor, culpable = fin[u], u
        fin[v] = mejor + tareas[v]["horas"]
        padre_critico[v] = culpable            # la dependencia que marca el ritmo

    ultimo = max(fin, key=fin.get)             # la tarea que acaba mas tarde
    camino, actual = [], ultimo                # reconstruir hacia atras (07-04)
    while actual is not None:
        camino.append(actual)
        actual = padre_critico[actual]
    return {"horas": fin[ultimo], "ruta": camino[::-1]}

print(ruta_critica(dependencias, tareas))
# {'horas': 17,
#  'ruta': ['disenar_ui', 'implementar_ui', 'pruebas_integracion', 'lanzamiento']}

Comprobación a mano de los momentos de fin: disenar_ui 5 → implementar_ui 5+8=13; por la otra rama, migrar_bd acaba en 5 y desplegar_api en 7. pruebas_integracion espera a la más lenta: max(13, 7) + 3 = 16, y lanzamiento cierra en 17 horas. La ruta crítica pasa por la interfaz: acelerar migrar_bd no adelantaría el proyecto ni un minuto (tiene 6 horas de holgura), pero cada hora ganada en implementar_ui es una hora de proyecto.

graph LR
    A[disenar_esquema 3h] --> B[migrar_bd 2h]
    S[configurar_servidor 1h] --> C
    B --> C[desplegar_api 2h]
    C --> D
    U[disenar_ui 5h] ==> I[implementar_ui 8h]
    I ==> D[pruebas_integracion 3h]
    D ==> L[lanzamiento 1h]
    style U stroke:#c00,stroke-width:3px
    style I stroke:#c00,stroke-width:3px
    style D stroke:#c00,stroke-width:3px
    style L stroke:#c00,stroke-width:3px

Nota de eficiencia: el doble bucle con existe_arista es O(n · a) por claridad didáctica; con el grafo invertido de 07-03 (ejercicio 2) quedaría en O(n + a). Con esto, el planificador está completo: validación, orden, paralelismo y estimación en unas 60 líneas sobre estructuras que ya teníamos.

Sugerencia de colaboradores: amigos-de-amigos

Cambiamos de dominio. TaskFlow añade un toque social: sugerir colaboradores a cada usuario. La heurística clásica de las redes sociales: sugerir a los que están a distancia exactamente 2 — colaboradores de mis colaboradores que aún no son míos — ordenados por cuántos contactos comunes tenemos. Es un BFS limitado a dos capas sobre un grafo no dirigido:

def sugerir_colaboradores(grafo, usuario, maximo=3):
    directos = set(grafo.vecinos(usuario))            # distancia 1
    candidatos = {}                                   # candidato -> contactos comunes
    for amigo in directos:
        for segundo in grafo.vecinos(amigo):          # distancia 2
            if segundo != usuario and segundo not in directos:
                candidatos[segundo] = candidatos.get(segundo, 0) + 1
    return sorted(candidatos, key=candidatos.get, reverse=True)[:maximo]

social = Grafo(dirigido=False)
for a, b in [("ana", "bea"), ("ana", "carlos"), ("bea", "diego"),
             ("carlos", "diego"), ("carlos", "eva"), ("diego", "fran")]:
    social.anadir_arista(a, b)

print(sugerir_colaboradores(social, "ana"))   # ['diego', 'eva']

A ana se le sugiere diego antes que eva porque comparte con él dos contactos (bea y carlos) y con eva solo uno. Aquí no hizo falta ni la cola: al ser exactamente dos capas, dos bucles anidados son el BFS truncado — pero conceptualmente es bfs_distancias (ejercicio 1 de 07-03) filtrando distancia 2. Así funcionan, con muchos refinamientos encima, los "quizá conozcas a" de LinkedIn o Facebook.

PageRank simplificado

La web es un grafo dirigido (páginas → enlaces, lección 07-01). La pregunta de Google en 1998: ¿qué páginas son importantes? La idea de PageRank: una página es importante si la enlazan páginas importantes — definición circular que se resuelve por iteración. Modelo del "navegante aleatorio": con probabilidad d (≈ 0,85) sigue un enlace al azar de la página actual; con 1 − d salta a una página cualquiera. El rango de una página es la fracción de tiempo que el navegante pasa en ella:

def pagerank(grafo, d=0.85, iteraciones=30):
    vertices = grafo.vertices()
    n = len(vertices)
    rango = {v: 1 / n for v in vertices}          # arranque: todos iguales
    for _ in range(iteraciones):
        nuevo = {v: (1 - d) / n for v in vertices}    # el salto aleatorio
        for v in vertices:
            salidas = grafo.grado_salida(v)
            if salidas == 0:                      # pagina sin enlaces:
                for destino in vertices:          # reparte entre todas
                    nuevo[destino] += d * rango[v] / n
            else:
                for destino in grafo.vecinos(v):  # reparte su rango
                    nuevo[destino] += d * rango[v] / salidas
        rango = nuevo
    return rango

web = Grafo(dirigido=True)
for origen, destino in [("blog", "docs"), ("blog", "home"), ("docs", "home"),
                        ("foro", "home"), ("home", "docs")]:
    web.anadir_arista(origen, destino)

for pagina, r in sorted(pagerank(web).items(), key=lambda x: -x[1]):
    print(f"{pagina}: {r:.3f}")
# home: 0.470
# docs: 0.455
# blog: 0.038
# foro: 0.038

Lectura del código: en cada iteración, cada página reparte su rango entre sus enlaces salientes (d * rango / salidas), y todas reciben además la migaja del salto aleatorio ((1 - d) / n). Tras unas decenas de iteraciones los valores se estabilizan (converge a un punto fijo). home gana porque la enlazan las otras tres; docs la sigue muy de cerca con un único enlace entrante, porque quien la enlaza es la importantísima home — ahí está la circularidad resuelta: no cuenta solo cuántos enlaces recibes, sino de quién. blog y foro, sin enlaces entrantes, se quedan con la migaja del salto aleatorio. En TaskFlow, la misma idea aplicada al grafo de dependencias invertido señalaría las tareas "estructuralmente centrales" del proyecto.

Grafos en producción: panorama breve

Para terminar, dónde viven los grafos en sistemas reales (sin código, solo mapa):

Ámbito Qué modela el grafo Qué se ejecuta encima
Bases de datos de grafos (Neo4j, Neptune) Entidades y relaciones como ciudadanos de primera Consultas de patrones y caminos (Cypher, Gremlin)
Recomendación (Amazon, Netflix, Spotify) Usuarios ↔ productos, bipartito Vecindad, paseos aleatorios, filtrado colaborativo
CI/CD y build (Make, Gradle, Airflow) Pasos y sus dependencias: un DAG Orden topológico y paralelización — nuestro planificador, a escala
Mapas y logística Cruces y tramos ponderados Dijkstra y variantes con heurísticas (A*)
Detección de fraude Cuentas, tarjetas, dispositivos compartidos Componentes conexas y patrones sospechosos

La moraleja: lo que hemos construido este módulo no es un ejercicio académico; es la versión pequeña y comprensible de la maquinaria que orquesta pipelines, rutas y recomendaciones a diario. Cuando la escala crece, cambian los motores (bases de datos de grafos, procesamiento distribuido), pero los conceptos —adyacencia, BFS, orden topológico, caminos— son exactamente estos.

Errores Comunes y Consejos

  • Confundir ruta crítica con camino mínimo. La ruta crítica es el camino más LARGO del DAG: marca la duración inevitable del proyecto. Minimizar (07-04) y maximizar (aquí) responden preguntas opuestas; la programación dinámica sobre orden topológico solo es válida para maximizar porque el DAG no tiene ciclos.
  • Calcular la ruta crítica sin validar antes el DAG. Con un ciclo, orden_topologico lanza excepción (bien); si usaras otra implementación silenciosa, la programación dinámica leería valores no calculados. Valida siempre primero.
  • Olvidar el caso "sin enlaces salientes" en PageRank. Sin ese reparto, el rango de los callejones sin salida se evapora en cada iteración y la suma total deja de ser 1 — un bug clásico difícil de notar porque el ranking relativo puede seguir pareciendo razonable.
  • Sugerir amigos con grafo dirigido sin querer. Si construyes la red social con dirigido=True (el valor por defecto de nuestra clase), "amigos de mis amigos" solo mirará en un sentido. Para amistades, Grafo(dirigido=False) explícito.
  • Consejo: fíjate en el patrón de esta lección: ninguna aplicación necesitó estructuras nuevas, solo componer las existentes. Esa composición es la habilidad que distingue a quien "sabe algoritmos" de quien resuelve problemas.

Ejercicios

Ejercicio 1: holgura de una tarea

Amplía ruta_critica para calcular la holgura de cada tarea: cuántas horas puede retrasarse sin afectar a la duración total. Pista: calcula también el instante más tardío de fin permitido, recorriendo el orden topológico al revés desde la duración total; holgura = tardío − temprano.

Ejercicio 2: colaboradores a distancia 3

Generaliza sugerir_colaboradores a colaboradores_a_distancia(grafo, usuario, k) usando bfs_distancias (ejercicio 1 de 07-03) para devolver los usuarios a distancia exactamente k.

Ejercicio 3: la tarea más central

Aplica pagerank al grafo dependencias invertido (con invertir de 07-03) y razona por qué la tarea con mayor rango es la que es.

Soluciones

Solución 1:

def holguras(grafo, tareas):
    datos = ruta_critica(grafo, tareas)
    total = datos["horas"]
    fin = {}
    for v in orden_topologico(grafo):
        previo = max((fin[u] for u in grafo.vertices()
                      if grafo.existe_arista(u, v)), default=0)
        fin[v] = previo + tareas[v]["horas"]

    tardio = {}
    for v in reversed(orden_topologico(grafo)):   # del final hacia el principio
        sucesores = [tardio[s] - tareas[s]["horas"] for s in grafo.vecinos(v)]
        tardio[v] = min(sucesores, default=total) # sin sucesores: el fin del proyecto
    return {v: tardio[v] - fin[v] for v in fin}

print(holguras(dependencias, tareas))
# {'disenar_esquema': 6, 'configurar_servidor': 10, 'migrar_bd': 6,
#  'desplegar_api': 6, 'disenar_ui': 0, 'implementar_ui': 0,
#  'pruebas_integracion': 0, 'lanzamiento': 0}

Las tareas con holgura 0 son exactamente la ruta crítica; configurar_servidor puede retrasarse hasta 10 horas sin mover el lanzamiento. Este es el análisis PERT/CPM de los manuales de gestión de proyectos, construido con nuestras piezas.

Solución 2:

def colaboradores_a_distancia(grafo, usuario, k):
    distancias = bfs_distancias(grafo, usuario)   # 07-03, ejercicio 1
    return [v for v, d in distancias.items() if d == k]

print(colaboradores_a_distancia(social, "ana", 2))  # ['diego', 'eva']
print(colaboradores_a_distancia(social, "ana", 3))  # ['fran']

Toda la lógica estaba ya en bfs_distancias: la aplicación es un filtro de una línea. (Se pierde el desempate por contactos comunes; combinarlo con el conteo de la versión original queda como mejora opcional.)

Solución 3: Al invertir, las flechas apuntan de cada tarea hacia sus dependencias, así que el rango fluye desde el final del proyecto hacia sus cimientos. Gana disenar_esquema o configurar_servidor... no: recorriendo el flujo, el rango se acumula en las tareas de las que más se depende transitivamente — con este grafo, disenar_esquema y disenar_ui reciben el rango que baja por sus cadenas, y la más beneficiada es disenar_ui, de la que cuelga la rama más pesada (toda la UI y, a través de las pruebas, el lanzamiento). Ejecutarlo confirma la intuición: las tareas "raíz" de las cadenas largas son las estructuralmente críticas, coherente con la ruta crítica de la sección 1.

Conclusión

Hemos visto los grafos ganarse el sueldo: el planificador de TaskFlow (validar con ciclos, ordenar con Kahn, paralelizar por niveles, estimar con la ruta crítica — el camino más largo del DAG por programación dinámica), las sugerencias sociales por distancia 2 y un PageRank de juguete que destila la idea que ordenó la web. Nada de esto requirió algoritmos nuevos: solo componer BFS, DFS, Kahn y Dijkstra con las estructuras de los módulos anteriores. Queda el último paso del módulo, y es todo tuyo: una lección íntegra de ejercicios para consolidar grafos de principio a fin, del modelado a los algoritmos, otra vez con TaskFlow como campo de pruebas.

◄ Anterior
◄
Siguiente ►
►
El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
© Copyright 2026. Todos los derechos reservados