Grafos y planes de dependencias
Representa trabajo que depende de otro trabajo y descubre cuándo el plan es imposible.
AL TERMINAR, PODRÁS
- Representar vértices y aristas dirigidas
- Explicar el recorrido en anchura y el orden topológico
- Detectar ciclos en flujos de trabajo con dependencias
Descripción del diagrama: fetch → build; fetch → test; build → deploy; test → deploy; a → b (ciclo: falla pronto); b → a
Las relaciones también son datos
Un grafo está formado por vértices y aristas.
En un flujo de trabajos, cada vértice es un trabajo y una arista significa que un trabajo debe terminar antes de que otro empiece. Elige y documenta la dirección de las aristas: «A apunta a B» puede significar que A desbloquea a B o que A depende de B, y esas convenciones son opuestas. Una lista de adyacencia guarda los vecinos de cada vértice.
Los grafos también modelan dependencias de paquetes, llamadas entre servicios, sistemas de compilación y responsabilidades en una organización. Su utilidad viene de hacer las relaciones lo bastante explícitas como para analizarlas.
Cada recorrido responde una pregunta distinta
La búsqueda en anchura (breadth-first search, BFS) explora los vértices en orden creciente de cantidad de aristas desde un punto de partida y encuentra caminos más cortos en un grafo sin pesos.
Un conjunto de visitados evita exploraciones repetidas y bucles infinitos en grafos con ciclos. El recorrido en profundidad (depth-first) explora una rama completa antes de regresar. Ningún recorrido por sí solo da todos los calendarios posibles.
Para trabajo con prerrequisitos, un orden topológico pone los prerrequisitos antes de lo que depende de ellos. Ese orden solo existe en un grafo dirigido acíclico, y puede haber varios órdenes válidos cuando hay trabajos independientes.
Un plan imposible debe fallar pronto
TopologicalSorter de Python recibe un diccionario que asocia cada nodo con sus predecesores.
El ejemplo dice que publish depende de render y render depende de fetch. Un ciclo, como que fetch dependa de publish, no tiene un punto de partida válido. Detéctalo al aceptar el flujo, en lugar de dejar trabajos esperando para siempre.
Distingue también un grafo de dependencias válido de una ejecución exitosa: un prerrequisito puede fallar al ejecutarse. Relay necesita una política para los trabajos dependientes cuando falla uno anterior, como cancelarlos o mostrar un estado bloqueado visible.
from graphlib import TopologicalSorter
plan = {"fetch": [], "render": ["fetch"], "publish": ["render"]}
print(list(TopologicalSorter(plan).static_order()))ERROR FRECUENTE
Confundir «el grafo tiene un orden válido» con «todos los trabajos van a funcionar». Las fallas de dependencias siguen necesitando una política en ejecución.
INTÉNTALO TÚ
Dibuja las dependencias fetch → render → publish y fetch → archive. Enumera dos calendarios válidos; luego introduce un ciclo y explica por qué la ejecución no puede empezar de forma segura.
Decide en el laboratorio.
El checkpoint de dos preguntas, tus notas y tu progreso guardado están en el laboratorio. Gratis y sin cuenta.
Abrir en el laboratorio ↗CONÉCTALO CON RELAY
Haz que Relay valide un flujo pequeño con dependencias. Rechaza los ciclos y define qué significa «bloqueado por un prerrequisito fallido».