Ordenación topológica

En informática , una ordenación topológica de un grafo dirigido es una ordenación lineal de sus vértices tal que, para cada arista dirigida ( u,v) desde el vértice u al vértice v , u precede a v en la ordenación. Por ejemplo, los vértices del grafo pueden representar tareas a realizar, y las aristas pueden representar restricciones que indican que una tarea debe realizarse antes que otra; en este caso, una ordenación topológica es simplemente una secuencia válida para las tareas.

Precisamente, una ordenación topológica es un recorrido de grafos en el que cada nodo v se visita solo después de que se hayan visitado todas sus dependencias . Una ordenación topológica es posible si y solo si el grafo no tiene ciclos dirigidos , es decir, si es un grafo acíclico dirigido (DAG). Todo DAG tiene al menos una ordenación topológica, y existen algoritmos de tiempo lineal para construirla. La ordenación topológica tiene muchas aplicaciones, especialmente en problemas de clasificación como el conjunto de arcos de retroalimentación . La ordenación topológica también es posible cuando el DAG tiene componentes desconectadas .

Ejemplos

La aplicación canónica de la ordenación topológica es la planificación de una secuencia de trabajos o tareas en función de sus dependencias . Los trabajos se representan mediante vértices, y existe una arista de x a y si el trabajo x debe completarse antes de que pueda comenzar el trabajo y (por ejemplo, al lavar la ropa, la lavadora debe terminar antes de que pongamos la ropa en la secadora). Entonces, una ordenación topológica proporciona un orden en el que realizar los trabajos. Una aplicación estrechamente relacionada de los algoritmos de ordenación topológica se estudió por primera vez a principios de la década de 1960 en el contexto de la técnica PERT para la planificación en la gestión de proyectos . ^{[ 1 ]} En esta aplicación, los vértices de un grafo representan los hitos de un proyecto, y las aristas representan las tareas que deben realizarse entre un hito y otro. La ordenación topológica constituye la base de los algoritmos de tiempo lineal para encontrar la ruta crítica del proyecto, una secuencia de hitos y tareas que controla la duración del cronograma general del proyecto.

En informática, este tipo de aplicaciones se dan en la planificación de instrucciones , el orden de evaluación de celdas de fórmulas al recalcular valores de fórmulas en hojas de cálculo , la síntesis lógica , la determinación del orden de las tareas de compilación en los makefiles , la serialización de datos y la resolución de dependencias de símbolos en los enlazadores . También se utiliza para decidir el orden de carga de tablas con claves foráneas en bases de datos.

Algoritmos

Los algoritmos habituales para la ordenación topológica tienen un tiempo de ejecución lineal en el número de nodos más el número de aristas, asintóticamente, $O(\left|{V}\right|+\left|{E}\right|).$

El algoritmo de Kahn

Uno de estos algoritmos, descrito por primera vez por Kahn (1962) , funciona eligiendo vértices en el mismo orden que la ordenación topológica final. ^{[ 2 ]} Primero, se encuentra una lista de "nodos iniciales" que no tienen aristas entrantes y se insertan en un conjunto S; al menos uno de estos nodos debe existir en un grafo acíclico no vacío (finito). Luego:

L ← Lista vacía que contendrá los elementos ordenados S ← Conjunto de todos los nodos sin arista entrante Mientras S no esté vacío , elimine un nodo n de S, agregue n a L. Para cada nodo m con una arista e de n a m , elimine la arista e del grafo. Si m no tiene otras aristas entrantes , inserte m en S.Si el grafo tiene aristas , devuelve un error (el grafo tiene al menos un ciclo); de lo contrario, devuelve L (un orden topológicamente ordenado).

Si el grafo es un DAG , la lista L contendrá una solución (aunque esta no sea necesariamente única). De lo contrario, el grafo debe tener al menos un ciclo y, por lo tanto, es imposible realizar una ordenación topológica.

Como reflejo de la no unicidad del ordenamiento resultante, la estructura S puede ser simplemente un conjunto, una cola o una pila. Dependiendo del orden en que se eliminen los nodos n del conjunto S, se genera una solución diferente. Una variación del algoritmo de Kahn que resuelve los empates lexicográficamente constituye un componente clave del algoritmo de Coffman-Graham para la planificación paralela y el dibujo de grafos en capas .

Búsqueda en profundidad

Un algoritmo alternativo para la ordenación topológica se basa en la búsqueda en profundidad . El algoritmo recorre cada nodo del grafo, en un orden arbitrario, iniciando una búsqueda en profundidad que finaliza cuando encuentra un nodo que ya ha sido visitado desde el inicio de la ordenación topológica o cuando el nodo no tiene aristas salientes (es decir, un nodo hoja):

L ← Lista vacía que contendrá los nodos ordenados mientras existan nodos sin una marca permanente, seleccione un nodo sin marcar n visitar( n ) función visitar(nodo n ) si n tiene una marca permanente entonces regresar si n tiene una marca temporal entonces detener (el gráfico tiene al menos un ciclo) marca n con una marca temporal para cada nodo m con una arista de n a m hacer visita( m ) marcar n con una marca permanente agregar n al encabezado de L

Cada nodo n se antepone a la lista de salida L solo después de considerar todos los demás nodos que dependen de n (todos los descendientes de n en el grafo). Específicamente, cuando el algoritmo agrega el nodo n , tenemos la garantía de que todos los nodos que dependen de n ya están en la lista de salida L: se agregaron a L ya sea por la llamada recursiva a visit() que terminó antes de la llamada a visit n , o por una llamada a visit() que comenzó incluso antes de la llamada a visit n . Dado que cada arista y nodo se visita una vez, el algoritmo se ejecuta en tiempo lineal. Este algoritmo basado en búsqueda en profundidad es el descrito por Cormen et al. (2001) ; ^{[ 3 ]} parece haber sido descrito por primera vez en una publicación por Tarjan en 1976. ^{[ 4 ]}

Algoritmos paralelos

En una máquina de acceso aleatorio paralelo , se puede construir un ordenamiento topológico en tiempo O ((log n ) ^² ) utilizando un número polinomial de procesadores, lo que sitúa el problema en la clase de complejidad NC₂ ^.^{[ 5 ]} Un método para lograrlo consiste en elevar repetidamente al cuadrado la matriz de adyacencia del grafo dado, logarítmicamente muchas veces, utilizando la multiplicación de matrices min+ con maximización en lugar de minimización. La matriz resultante describe las distancias de los caminos más largos en el grafo. Ordenar los vértices según la longitud de sus caminos entrantes más largos produce un ordenamiento topológico. ^{[ 6 ]}

Un algoritmo para la ordenación topológica paralela en máquinas de memoria distribuida paraleliza el algoritmo de Kahn para un DAG. $G=(V,E)$ [ ⁷^{] A grandes rasgos, el algoritmo de}^Kahn elimina repetidamente los vértices de grado de entrada 0 y los agrega a la ordenación topológica en el orden en que fueron eliminados. Dado que las aristas salientes de los vértices eliminados también se eliminan, habrá un nuevo conjunto de vértices de grado de entrada 0, donde el procedimiento se repite hasta que no queden vértices. Este algoritmo realiza $D+1$ iteraciones, donde $D$ es el camino más largo en $G.$ Cada iteración se puede paralelizar, que es la idea del siguiente algoritmo.

A continuación, se supone que la partición del grafo se almacena en $p$ elementos de procesamiento (PE), que están etiquetados $0,\dots ,p-1$ Cada PE $i$ inicializa un conjunto de vértices locales . $Q_{i}^{1}$ con grado de entrada 0, donde el índice superior representa la iteración actual. Dado que todos los vértices en los conjuntos locales $Q_{0}^{1},\dots ,Q_{p-1}^{1}$ tienen grado de entrada 0, es decir, no son adyacentes, se pueden dar en un orden arbitrario para una ordenación topológica válida. Para asignar un índice global a cada vértice, se calcula una suma de prefijos sobre los tamaños de $Q_{0}^{1},\dots ,Q_{p-1}^{1}$ . Entonces, en cada paso, hay ${\textstyle \sum _{i=0}^{p-1}|Q_{i}|}$ vértices añadidos a la ordenación topológica.

En el primer paso, PE $j$ asigna los índices ${\textstyle \sum _{i=0}^{j-1}|Q_{i}^{1}|,\dots ,\left(\sum _{i=0}^{j}|Q_{i}^{1}|\right)-1}$ a los vértices locales en $Q_{j}^{1}$ . Estos vértices en $Q_{j}^{1}$ se eliminan, junto con sus correspondientes aristas salientes. Para cada arista saliente $(u,v)$ con punto final $v$ en otro PE $l,j\neq l$ , el mensaje $(u,v)$ se publica en PE $l$ . Después de todos los vértices en $Q_{j}^{1}$ Se eliminan los mensajes publicados y se envían a su PE correspondiente. Cada mensaje $(u,v)$ Se reciben actualizaciones del grado de entrada del vértice local $v$ . Si el grado de entrada cae a cero, $v$ se agrega a $Q_{j}^{2}$ . Entonces comienza la siguiente iteración.

En el paso $k$ , PE $j$ asigna los índices ${\textstyle a_{k-1}+\sum _{i=0}^{j-1}|Q_{i}^{k}|,\dots ,a_{k-1}+\left(\sum _{i=0}^{j}|Q_{i}^{k}|\right)-1}$ , dónde $a_{k-1}$ es el número total de vértices procesados después del paso ⁠ $k-1$ Este procedimiento se repite hasta que no queden vértices por procesar, por lo tanto ${\textstyle \sum _{i=0}^{p-1}|Q_{i}^{D+1}|=0}$ A continuación se presenta una descripción general de alto nivel, con un solo programa y múltiples datos, en pseudocódigo, de este algoritmo.

Tenga en cuenta que la suma del prefijo para los desplazamientos locales ${\textstyle a_{k-1}+\sum _{i=0}^{j-1}|Q_{i}^{k}|,\dots ,a_{k-1}+\left(\sum _{i=0}^{j}|Q_{i}^{k}|\right)-1}$ se puede calcular de forma eficiente en paralelo.

p elementos de procesamiento con ID de 0 a p -1 Entrada: G = DAG (V, E), distribuido a PE, índice de PE j = 0, ..., p - 1 Salida: ordenación topológica de G función recorrer DAG distribuido δ grado de entrada de los vértices locales V  $Q = {v \in V | δ[v] = 0}$  // Todos los vértices con grado de entrada 0 nrDeVérticesProcesados = 0 realizar la suma global del prefijo de construcción sobre el tamaño de Q // obtener desplazamientos y el número total de vértices en este paso desplazamiento = nrDeVérticesProcesados + suma(Q _i , i = 0 a j - 1) // j es el índice del procesador para cada u en Q localOrder[u] = index++; para cada (u,v) en E hacer enviar mensaje ( u, v ) a PE propietario del vértice v nrOfVerticesProcessed += suma(|Q _i |, i = 0 a p - 1) entregar todos los mensajes a los vecinos de los vértices en Q recibir mensajes para vértices locales V eliminar todos los vértices en Q para cada mensaje ( u, v ) recibido: si --δ[v] = 0 agregar v a Q mientras el tamaño global de Q > 0 devolver orden local

El costo de comunicación depende en gran medida de la partición del grafo dada. En cuanto al tiempo de ejecución, en un modelo CRCW-PRAM que permite la obtención y el decremento en tiempo constante, este algoritmo se ejecuta en ${\textstyle {\mathcal {O}}\left({\frac {m+n}{p}}+D(\Delta +\log n)\right)}$ , donde $D$ es nuevamente el camino más largo en $G$ y $Δ$ el grado máximo. ^{[ 7 ]}

Aplicación a la búsqueda de la ruta más corta

El ordenamiento topológico también puede utilizarse para calcular rápidamente los caminos más cortos a través de un grafo dirigido acíclico ponderado . Sea $V$ la lista de vértices en dicho grafo, en orden topológico. Entonces, el siguiente algoritmo calcula el camino más corto desde un vértice de origen $s$ a todos los demás vértices: ^{[ 3 ]}

Sea $d$ un arreglo de la misma longitud que $V$ ; este almacenará las distancias de camino más corto desde $s$ . Establezca $d [s] = 0$ , todos los demás $d [u] = \infty$ .
Sea $p$ un arreglo de la misma longitud que $V$ , con todos los elementos inicializados a nil . Cada $p [u]$ contendrá el predecesor de $u$ en el camino más corto de $s$ a $u$ .
Recorre los vértices u ordenados en V , comenzando desde s :
- Para cada vértice v que sigue directamente a u (es decir, existe una arista de u a v ):
  - Sea $w$ el peso de la arista desde $u$ hasta $v$ .
  - Relaja el borde: si d [ v ] > d [ u ] + w , establece
    - $d [v] \leftarrow d [u] + w$ ,
    - $p [v] \leftarrow u$ .

Equivalentemente:

Sea $d$ un arreglo de la misma longitud que $V$ ; este almacenará las distancias de camino más corto desde $s$ . Establezca $d [s] = 0$ , todos los demás $d [u] = \infty$ .
Sea $p$ un arreglo de la misma longitud que $V$ , con todos los elementos inicializados a nil . Cada $p$ $[$ $u$ $]$ contendrá el predecesor de $u$ en el camino más corto de $s$ a $u$ .
Recorre los vértices u ordenados en V , comenzando desde s :
- Para cada vértice v en u (es decir, existe una arista de v a u ):
  - Sea $w$ el peso de la arista desde $v$ hasta $u$ .
  - Relaja el borde: si d [ u ] > d [ v ] + w , establece
    - $d [u] \leftarrow d [v] + w$ ,
    - $p [u] \leftarrow v$ .

En un grafo de $n$ vértices y $m$ aristas, este algoritmo toma $Θ(n + m)$ , es decir, tiempo lineal . ^{[ 3 ]}

Unicidad

Si una ordenación topológica tiene la propiedad de que todos los pares de vértices consecutivos en el orden ordenado están conectados por aristas, entonces estas aristas forman un camino hamiltoniano dirigido en el DAG . Si existe un camino hamiltoniano, la ordenación topológica es única; ningún otro orden respeta las aristas del camino. Por el contrario, si una ordenación topológica no forma un camino hamiltoniano, el DAG tendrá dos o más ordenaciones topológicas válidas, ya que en este caso siempre es posible formar una segunda ordenación válida intercambiando dos vértices consecutivos que no estén conectados entre sí por una arista. Por lo tanto, es posible comprobar en tiempo lineal si existe una ordenación única y si existe un camino hamiltoniano, a pesar de la NP-dificultad del problema del camino hamiltoniano para grafos dirigidos más generales (es decir, grafos dirigidos cíclicos). ^{[ 8 ]}

Relación con los pedidos parciales

Los ordenamientos topológicos también están estrechamente relacionados con el concepto de extensión lineal de un orden parcial en matemáticas. Un conjunto parcialmente ordenado es simplemente un conjunto de objetos junto con una definición de la relación de desigualdad "≤", que satisface los axiomas de reflexividad ( x ≤ x ), antisimetría (si x ≤ y e y ≤ x, entonces x = y ) y transitividad (si x ≤ y e y ≤ z , entonces x ≤ z ). Un orden total es un orden parcial en el que, para cada par de objetos x e y del conjunto, se cumple que x ≤ y o y ≤ x . Los órdenes totales son conocidos en informática como los operadores de comparación necesarios para realizar algoritmos de ordenación por comparación . Para conjuntos finitos, los órdenes totales pueden identificarse con secuencias lineales de objetos, donde la relación "≤" es verdadera siempre que el primer objeto preceda al segundo en el orden; un algoritmo de ordenación por comparación puede utilizarse para convertir un orden total en una secuencia de esta manera. Una extensión lineal de un orden parcial es un orden total que es compatible con él, en el sentido de que, si x ≤ y en el orden parcial, entonces x ≤ y también en el orden total.

Se puede definir un orden parcial a partir de cualquier DAG considerando el conjunto de objetos como los vértices del DAG y definiendo x ≤ y como verdadero para cualesquiera dos vértices x e y , siempre que exista un camino dirigido de x a y ; es decir, siempre que y sea alcanzable desde x . Con estas definiciones, un orden topológico del DAG es equivalente a una extensión lineal de este orden parcial. A la inversa, cualquier orden parcial puede definirse como la relación de alcanzabilidad en un DAG. Una forma de hacerlo es definir un DAG que tenga un vértice por cada objeto en el conjunto parcialmente ordenado y una arista xy por cada par de objetos para los cuales x ≤ y . Una forma alternativa de hacerlo es utilizar la reducción transitiva del orden parcial; en general, esto produce DAGs con menos aristas, pero la relación de alcanzabilidad en estos DAGs sigue siendo el mismo orden parcial. Mediante estas construcciones, se pueden utilizar algoritmos de ordenamiento topológico para encontrar extensiones lineales de órdenes parciales.

Relación con la optimización de la planificación

Por definición, la solución de un problema de planificación que incluye un grafo de precedencia es una solución válida para la ordenación topológica (independientemente del número de máquinas); sin embargo, la ordenación topológica por sí sola no es suficiente para resolver de forma óptima un problema de optimización de la planificación. El algoritmo de Hu es un método popular utilizado para resolver problemas de planificación que requieren un grafo de precedencia e involucran tiempos de procesamiento (donde el objetivo es minimizar el mayor tiempo de finalización entre todas las tareas). Al igual que la ordenación topológica, el algoritmo de Hu no es único y puede resolverse utilizando DFS (encontrando la ruta de mayor longitud y luego asignando las tareas).

Véase también

tsort , un programa de Unix para la ordenación topológica.
Conjunto de arcos de retroalimentación , un conjunto de aristas cuya eliminación permite ordenar topológicamente el subgrafo restante.
El algoritmo de componentes fuertemente conexas de Tarjan es un algoritmo que proporciona la lista topológicamente ordenada de componentes fuertemente conexas en un grafo.
Orden pretopológico

Referencias

↑ Jarnagin, MP (1960), Métodos automáticos de máquinas para probar la consistencia de redes PERT , Memorando técnico n.° K-24/60, Dahlgren, Virginia: Laboratorio de Armamento Naval de EE. UU.
↑ Kahn, Arthur B. (1962), "Clasificación topológica de grandes redes", Communications of the ACM , 5 (11): 558– 562, doi : 10.1145/368996.369025 , S2CID 16728233
1 2 3 Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001), "Sección 22.4: Ordenación topológica", Introducción a los algoritmos (2.ª ed.), MIT Press y McGraw-Hill, págs. 549–552 , ISBN 0-262-03293-7
↑ Tarjan, Robert E. (1976), "Árboles de expansión disjuntos por aristas y búsqueda en profundidad", Acta Informatica , 6 (2): 171–185 , doi : 10.1007/BF00268499 , S2CID 12044793
↑ Cook, Stephen A. (1985), "Una taxonomía de problemas con algoritmos paralelos rápidos", Information and Control , 64 ( 1–3 ): 2–22 , doi : 10.1016/S0019-9958(85)80041-3
↑ Dekel, Eliezer; Nassimi, David; Sahni, Sartaj (1981), "Algoritmos paralelos de matrices y grafos", SIAM Journal on Computing , 10 (4): 657–675 , doi : 10.1137/0210049 , MR 0635424
1 2 Sanders, Peter; Mehlhorn, Kurt; Dietzfelbinger, Martin; Dementiev, Roman (2019), Algoritmos y estructuras de datos secuenciales y paralelos: La caja de herramientas básica , Springer International Publishing, ISBN 978-3-030-25208-3
↑ Vernet, Oswaldo; Markenzon, Lilian (1997), "Problemas hamiltonianos para grafos de flujo reducibles" (PDF) , Actas: 17.ª Conferencia Internacional de la Sociedad Chilena de Ciencias de la Computación , pp. 264–267 , doi : 10.1109/SCCC.1997.637099 , hdl : 11422/2585 , ISBN 0-8186-8052-0, S2CID 206554481

Lecturas adicionales

DE Knuth , El arte de la programación informática , Volumen 1, sección 2.2.3, que ofrece un algoritmo para la ordenación topológica de un orden parcial y una breve historia.
Bertrand Meyer , Touch of Class: Learning to Program Well with Objects and Contracts , Springer , 2009, capítulo 15, Devising and engineering an algorithm: topological sort , using a modern programming language, para una presentación pedagógica detallada de la ordenación topológica (utilizando una variante del algoritmo de Kahn) con consideración del diseño de la estructura de datos, el diseño de la API y las cuestiones de ingeniería de software.

Enlaces externos

Diccionario de algoritmos y estructuras de datos del NIST: ordenación topológica
Weisstein, Eric W. , "Ordenación topológica" , MathWorld

[Jarnagin-1] Jarnagin, MP (1960), Métodos automáticos de máquinas para probar la consistencia de redes PERT , Memorando técnico n.° K-24/60, Dahlgren, Virginia: Laboratorio de Armamento Naval de EE. UU.

[Kahn-2] Kahn, Arthur B. (1962), "Clasificación topológica de grandes redes", Communications of the ACM , 5 (11): 558– 562, doi : 10.1145/368996.369025 , S2CID 16728233

[CLRS-3] 1 2 3 Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001), "Sección 22.4: Ordenación topológica", Introducción a los algoritmos (2.ª ed.), MIT Press y McGraw-Hill, págs. 549–552 , ISBN 0-262-03293-7

[Tarjan-4] Tarjan, Robert E. (1976), "Árboles de expansión disjuntos por aristas y búsqueda en profundidad", Acta Informatica , 6 (2): 171–185 , doi : 10.1007/BF00268499 , S2CID 12044793

[Cook-5] Cook, Stephen A. (1985), "Una taxonomía de problemas con algoritmos paralelos rápidos", Information and Control , 64 ( 1–3 ): 2–22 , doi : 10.1016/S0019-9958(85)80041-3

[DNS-6] Dekel, Eliezer; Nassimi, David; Sahni, Sartaj (1981), "Algoritmos paralelos de matrices y grafos", SIAM Journal on Computing , 10 (4): 657–675 , doi : 10.1137/0210049 , MR 0635424

[SMDD-7] 1 2 Sanders, Peter; Mehlhorn, Kurt; Dietzfelbinger, Martin; Dementiev, Roman (2019), Algoritmos y estructuras de datos secuenciales y paralelos: La caja de herramientas básica , Springer International Publishing, ISBN 978-3-030-25208-3

[VM-8] Vernet, Oswaldo; Markenzon, Lilian (1997), "Problemas hamiltonianos para grafos de flujo reducibles" (PDF) , Actas: 17.ª Conferencia Internacional de la Sociedad Chilena de Ciencias de la Computación , pp. 264–267 , doi : 10.1109/SCCC.1997.637099 , hdl : 11422/2585 , ISBN 0-8186-8052-0, S2CID 206554481

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

7

[ 8 ]