Ordenamiento topológico
Cada vez que instalas software, compilas un programa o planificas un proyecto, algo tiene que decidir qué hacer primero. Si la tarea B necesita la tarea A, A debe ir antes. Un ordenamiento topológico convierte una red de reglas así en una sola línea recta.
La idea
Dibuja cada tarea como un nodo y cada regla «A antes que B» como una flecha de A a B. Un orden topológico es una fila con todos los nodos en la que cada flecha apunta a la derecha. Se llama ordenamiento porque pone las cosas en orden, pero a diferencia de ordenar números, solo tiene que respetar las flechas: los nodos que ninguna cadena de flechas une pueden ir en cualquier orden.
Cuándo es imposible
Si las flechas forman un ciclo, por ejemplo A antes que B, B antes que C y C antes que A, entonces A tendría que ir antes que sí mismo. Así que un orden topológico existe exactamente cuando el grafo no tiene ciclos dirigidos. Un grafo así se llama grafo acíclico dirigido, o DAG. Los dos métodos de abajo encuentran un ciclo si lo hay, lo que los convierte también en una prueba de ciclos muy práctica.
Un ejemplo
Toma las flechas A → C, B → C, B → D, C → E y D → E. El algoritmo de Kahn cuenta las flechas entrantes: A y B no tienen ninguna, así que A va primero, luego B. Quitar las flechas de B deja libres a C y D, que van a continuación, y luego E: el orden A, B, C, D, E. El método DFS visita A, luego C, luego E; E termina primero, luego C, luego A, y cada uno pasa al principio. Después visita B y D, que terminan y se ponen delante de ellos: el orden B, D, A, C, E. Los dos órdenes son correctos.
¿Kahn o DFS?
El algoritmo de Kahn, publicado por Arthur Kahn en 1962, trabaja hacia delante: siempre sabe qué tareas pueden empezar ya, lo que va bien para planificar, y puede elegir entre las tareas libres con cualquier regla, como el orden alfabético. El método DFS, popularizado por Robert Tarjan en 1976, trabaja hacia atrás desde los extremos y solo necesita una búsqueda en profundidad. Ambos tardan un tiempo que crece con el número de nodos más aristas.
Usos
Las herramientas de compilación como make compilan los archivos después de los archivos de los que dependen. Los gestores de paquetes instalan las bibliotecas en orden de dependencias. Las hojas de cálculo recalculan una celda después de las celdas que usa su fórmula. Las universidades comprueban que se pueden cumplir los requisitos previos de las asignaturas, los compiladores ordenan instrucciones y las canalizaciones de datos ejecutan cada paso cuando sus entradas están listas. El comando de Unix tsort hace por sí solo un ordenamiento topológico.
Explóralo
Abre la aplicación y pulsa Paso. Las flechas dicen qué nodo debe ir antes de cuál. Con el algoritmo de Kahn, el número de cada nodo cuenta sus flechas entrantes restantes, y los nodos libres son azules. Con el método DFS, los nodos azules están en visita y los verdes están colocados. El orden crece en la fila bajo el grafo. Marca Añadir un ciclo y mira cómo los dos métodos descubren que no existe ningún orden.
Preguntas frecuentes
¿Qué significa topológico aquí?
El nombre viene de la topología, el estudio de cómo están conectadas las cosas más que de su forma exacta. El orden solo depende de qué nodos están unidos por flechas, no de dónde están dibujados.
¿Cómo encuentro el ciclo cuando no hay orden?
El método DFS lo muestra directamente: la arista hacia un nodo que aún está en visita, junto con el camino de los nodos en visita, es el ciclo. El algoritmo de Kahn solo dice qué nodos están atascados; una búsqueda entre ellos encuentra el ciclo.
¿Puedo elegir un orden concreto entre los válidos?
Sí. En el algoritmo de Kahn, cuando hay varios nodos libres, elige el que prefieras, por ejemplo la letra más baja o la tarea más urgente. Con una cola de prioridad se obtiene el orden que va primero alfabéticamente.
¿Cómo se usa el ordenamiento topológico con caminos más cortos?
En un grafo acíclico dirigido, relajar las aristas de cada nodo en orden topológico encuentra todos los caminos más cortos desde un origen en una sola pasada, incluso con aristas negativas, más rápido que Dijkstra o Bellman–Ford.
¿Listo para probarlo?
Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.
Prueba el ordenamiento topológico