Calculadora de Ordenación Topológica

Calculadora de Ordenación Topológica

La Calculadora de Ordenación Topológica calcula un ordenamiento lineal de los vértices de un grafo acíclico dirigido (DAG) tal que cada arista dirigida de u a v coloca a u antes que v. Ingrese su grafo como una lista de aristas o lista de adyacencia y la herramienta devolverá el orden topológico utilizando el algoritmo de Kahn o DFS post-orden, detectará ciclos (con la ruta exacta del ciclo), agrupará tareas en capas de ejecución paralela, contará el número de ordenamientos válidos y animará cada paso en un grafo interactivo.

¿Qué es una ordenación topológica?

Dado un grafo dirigido G = (V, E), una ordenación topológica (o ordenamiento topológico) es una disposición lineal v₁, v₂, …, vₙ de sus vértices tal que para cada arista dirigida (u → v), u aparece antes que v en la disposición. Un ordenamiento topológico existe si y solo si el grafo no tiene ciclos dirigidos, es decir, si el grafo es un DAG. El ordenamiento rara vez es único: un grafo puede tener muchos ordenamientos topológicos válidos cuando varios vértices tienen grado de entrada cero al mismo tiempo.

Algoritmos utilizados por esta calculadora

Algoritmo de Kahn (basado en BFS, 1962)

El algoritmo de Kahn es la ordenación topológica más intuitiva. En cada paso, elige un vértice con grado de entrada cero (sin aristas entrantes), lo añade a la salida y lo "elimina" del grafo disminuyendo el grado de entrada de cada uno de sus sucesores. Cuando varios vértices tienen grado de entrada cero, el desempate puede utilizar un min-heap (dando el ordenamiento lexicográficamente más pequeño) o una cola FIFO (dando el orden de inserción). El algoritmo de Kahn se ejecuta en tiempo O(|V| + |E|) y funciona también como detector de ciclos: si algún vértice todavía tiene grado de entrada > 0 después de que la cola se vacíe, el grafo tiene un ciclo.

DFS post-orden (Tarjan, 1976)

El algoritmo DFS ejecuta una búsqueda en profundidad y, cada vez que un vértice termina (es decir, todos sus sucesores han sido explorados por completo), se coloca en una pila. Invertir la pila al final produce un orden topológico válido. La detección de ciclos es natural: encontrar un vértice que todavía está en progreso (marcado como GRIS) significa que se ha encontrado una arista hacia atrás, por lo que el grafo no es un DAG. El DFS post-orden también se ejecuta en tiempo O(|V| + |E|).

Capas de ejecución paralela

Una vista estratificada de un DAG divide sus vértices en niveles de modo que cada arista vaya de un nivel con número menor a uno con número mayor. Los vértices de la misma capa son independientes entre sí, por lo que pueden ejecutarse en paralelo. El número de capas es igual a la longitud de la ruta más larga más uno; esta es la ruta crítica del DAG, el número mínimo de rondas secuenciales necesarias para terminar todas las tareas incluso con paralelismo ilimitado. Esta calculadora produce la vista de capas automáticamente siempre que la entrada sea un DAG.

Detección de ciclos

Si el grafo contiene un ciclo dirigido, no es posible realizar una ordenación topológica. Nuestra calculadora informa la ruta exacta del ciclo (por ejemplo, A → B → C → A) y resalta las aristas del ciclo en rojo en la visualización. Eliminar cualquier arista del ciclo es suficiente para restaurar la aciclicidad.

Formatos de entrada

Lista de aristas

Escriba cada arista dirigida como origen -> destino, separada por comas o saltos de línea. Variantes de flecha aceptadas: ->, →, =>, -->, :. También puede encadenar aristas: A -> B -> C es una forma abreviada de A->B y B->C. Las etiquetas de los vértices pueden ser letras, dígitos, guiones bajos, guiones y puntos.

Lista de adyacencia

Escriba cada vértice, dos puntos y sus sucesores directos (vértices a los que apunta). Un vértice sin sucesores sigue necesitando su línea, como D:.

Cómo usar esta calculadora

1. Elija un formato: Alterne entre lista de aristas y lista de adyacencia con los botones de opción.
2. Ingrese el grafo: Pegue sus datos o haga clic en uno de los ejemplos rápidos (orden de vestimenta, prerrequisitos de cursos, objetivos de compilación, un grafo con un ciclo y más).
3. Elija un algoritmo: Kahn lexicográfico para un orden único y reproducible; orden de inserción para preservar el orden de entrada; DFS post-orden para el método clásico de búsqueda en profundidad; o Mostrar todo para ver cada ordenamiento uno al lado del otro.
4. Haga clic en "Ordenar Topológicamente": El ordenamiento, la detección de ciclos, la vista de capas, la longitud de la ruta crítica, el número total de ordenamientos válidos y un grafo interactivo aparecerán debajo.
5. Explore: Presione Reproducir para ver cómo se emite cada vértice paso a paso. Las insignias de grado de entrada se actualizan en vivo. Arrastre cualquier nodo para reorganizar el diseño.

Aplicaciones en el mundo real

Sistemas de compilación y compiladores

Herramientas como make, Bazel, Gradle y npm ordenan topológicamente sus objetivos de compilación para que cada objetivo se compile solo después de todas sus dependencias. Un ciclo en el grafo de dependencias generalmente se informa como un error fatal: el sistema de compilación no puede decidir por dónde empezar.

Programación de tareas

Los gestores de proyectos utilizan DAGs para capturar las dependencias de las tareas. La ordenación topológica proporciona un orden de ejecución válido y la vista de capas indica el número mínimo de rondas bajo paralelismo ilimitado. La cadena más larga es la ruta crítica que determina la duración del proyecto.

Planificación de prerrequisitos de cursos

Un catálogo de cursos universitarios es un DAG: las aristas son relaciones de prerrequisitos. Un orden topológico es un plan de estudios válido y las capas indican a los estudiantes qué conjuntos de cursos pueden tomar en paralelo durante cada semestre.

Recálculo de hojas de cálculo

Cuando una celda cambia, una hoja de cálculo debe volver a calcular cada celda dependiente en el orden de dependencia, lo que supone una ordenación topológica del DAG de dependencia de celdas. La aplicación rechaza las referencias circulares (ciclos).

Gestores de paquetes y cargadores de complementos

Apt, pip, Homebrew, Maven y un sinfín de marcos de complementos (plugins) resuelven el orden de instalación o carga mediante la ordenación topológica de sus DAGs de dependencia.

Resolución de símbolos y programación de instrucciones

Los compiladores utilizan la ordenación topológica para ordenar las declaraciones y las CPUs utilizan DAGs de dependencia de datos para programar las instrucciones en el búfer de reordenamiento sin violar los riesgos de datos.

Contar ordenamientos topológicos

Para un DAG con n vértices, el número de ordenamientos topológicos válidos distintos puede variar desde 1 (para una cadena totalmente ordenada) hasta n! (para el grafo sin aristas). El cálculo del recuento exacto es #P-completo en general, pero para grafos de hasta 16 vértices, esta calculadora los enumera utilizando una formulación de programación dinámica con máscara de bits: f(S) = Σ f(S ∪ {v}) sobre todos los v ∉ S cuyos predecesores están todos en S.

Complejidad y rendimiento

• Tiempo: Tanto el algoritmo de Kahn como el DFS post-orden se ejecutan en O(|V| + |E|), lineal respecto al tamaño del grafo.
• Espacio: O(|V|) para el seguimiento del grado de entrada y el orden de salida, más O(|V| + |E|) para la estructura de adyacencia.
• Detección de ciclos: Integrada en ambos algoritmos. Kahn detecta ciclos cuando |salida| < |V|; DFS los detecta cuando se encuentra una arista hacia atrás (vecino GRIS).
• Límites en esta herramienta: hasta 80 vértices y 800 aristas para la visualización interactiva. El conteo de ordenamientos se limita a 16 vértices.

Preguntas frecuentes

¿Qué es una ordenación topológica?

Una ordenación topológica de un grafo acíclico dirigido es un ordenamiento lineal de sus vértices tal que cada arista dirigida de u a v coloca a u antes que v. Representa un orden válido en el que procesar tareas respetando sus dependencias.

¿Qué algoritmo utiliza esta calculadora?

La calculadora ejecuta tanto el algoritmo de Kahn como el DFS post-orden. El algoritmo de Kahn elimina repetidamente un vértice con grado de entrada cero y disminuye los grados de entrada de sus sucesores. El DFS post-orden ejecuta una búsqueda en profundidad e invierte el orden de finalización. Ambos se ejecutan en tiempo O(|V| + |E|).

¿Qué pasa si mi grafo tiene un ciclo?

Un grafo con un ciclo dirigido no tiene ordenación topológica. La calculadora detecta el ciclo, lo resalta en rojo en la visualización e informa la ruta exacta del ciclo para que pueda ver qué aristas eliminar para convertir el grafo en un DAG.

¿Cuál es el orden topológico lexicográficamente más pequeño?

Cuando hay muchos ordenamientos topológicos válidos, el lexicográficamente más pequeño se obtiene eligiendo siempre el vértice alfabéticamente menor cuyo grado de entrada es cero en cada paso. El modo predeterminado de Kahn de esta calculadora devuelve este ordenamiento único, que es estable y fácil de reproducir.

¿Qué es la vista de capa o nivel?

La vista de capas agrupa los vértices según la longitud de la ruta más larga desde cualquier origen. Los vértices en la misma capa no tienen dependencia entre sí, por lo que pueden ejecutarse en paralelo. El número de capas es igual a la cadena de dependencia más larga más uno y representa el número mínimo de rondas paralelas necesarias para terminar todas las tareas.

¿Puede un grafo tener muchos ordenamientos topológicos válidos?

Sí. Si en cualquier paso el algoritmo de Kahn tiene múltiples vértices con grado de entrada cero, cualquiera de ellos puede ser elegido a continuación. Esta calculadora cuenta el número exacto de ordenamientos topológicos distintos para grafos de hasta 16 vértices.

¿Cuál es la diferencia entre el algoritmo de Kahn y el DFS post-orden?

Kahn funciona de arriba hacia abajo: elige repetidamente fuentes (grado de entrada 0) y las emite primero. El DFS post-orden funciona de abajo hacia arriba: termina primero los sumideros y los antepone al orden. Ambos son O(|V| + |E|) y producen ordenamientos topológicos válidos, pero normalmente diferentes. Kahn es más fácil de paralelizar y de adaptar para el ordenamiento lexicográfico; DFS es más fácil de combinar con otros análisis basados en DFS, como los componentes fuertemente conectados.

¿Cuál es el tamaño máximo de grafo que admite esta herramienta?

La calculadora admite hasta 80 vértices y 800 aristas. El conteo del número total de ordenamientos topológicos válidos está limitado a 16 vértices porque el problema es #P-completo y el espacio de estados crece como 2ⁿ. La visualización interactiva y la animación del algoritmo escalan sin problemas hasta el tamaño máximo.

Lecturas adicionales

• Ordenamiento topológico — Wikipedia
• Grafo acíclico dirigido — Wikipedia
• Búsqueda en profundidad — Wikipedia
• Método de la ruta crítica — Wikipedia
• Componente fuertemente conectado — Wikipedia