Ordenamiento topológico

En informática , una ordenación topológica de un grafo dirigido es una ordenación lineal de sus vértices de modo que para cada arista dirigida (u,v) desde el vértice u hasta el vértice v , u viene antes que v en la ordenación. Por ejemplo, los vértices del grafo pueden representar tareas a realizar, y las aristas pueden representar restricciones de que una tarea debe realizarse antes que otra; en esta aplicación, una ordenación topológica es simplemente una secuencia válida para las tareas. Precisamente, una ordenación topológica es un recorrido del grafo en el que cada nodo v se visita solo después de que se visitan 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). Cualquier DAG tiene al menos una ordenación topológica, y se conocen algoritmos para construir una ordenación topológica de cualquier DAG en tiempo lineal . La ordenación topológica tiene muchas aplicaciones, especialmente en problemas de clasificación como el conjunto de arcos de retroalimentación . La clasificación topológica es posible incluso cuando el DAG tiene componentes desconectados .

Ejemplos

La aplicación canónica de la ordenación topológica es la programación de una secuencia de trabajos o tareas en función de sus dependencias . Los trabajos se representan mediante vértices y hay una arista de x a y si el trabajo x debe completarse antes de que pueda iniciarse el trabajo y (por ejemplo, al lavar la ropa, la lavadora debe terminar antes de que pongamos la ropa en la secadora). Luego, una ordenación topológica da 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 programación en la gestión de proyectos . ^[1] En esta aplicación, los vértices de un gráfico 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 forma 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 longitud del cronograma general del proyecto.

En informática, este tipo de aplicaciones se dan en la programación de instrucciones , la ordenación de la 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 que se deben realizar en los archivos make , la serialización de datos y la resolución de dependencias de símbolos en los enlazadores . También se utiliza para decidir en qué orden cargar tablas con claves externas en bases de datos.

Algoritmos

Los algoritmos habituales de ordenamiento topológico tienen un tiempo de ejecución lineal en el número de nodos más el número de aristas, asintóticamente, $O(\izquierda|{V}\derecha|+\izquierda|{E}\derecha|).$

Algoritmo de Kahn

Uno de estos algoritmos, descrito por primera vez por Kahn (1962), funciona eligiendo vértices en el mismo orden que la clasificación topológica final. ^[2] Primero, busque una lista de "nodos iniciales" que no tengan aristas entrantes e insértelos en un conjunto S; al menos uno de esos 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 entrantemientras  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 gráfico si  m no tiene otras aristas entrantes , inserte m en SSi  el gráfico tiene aristas ,  devuelve un error (el gráfico tiene al menos un ciclo); de lo contrario,  devuelve  L  (un orden topológico ordenado).

Si el grafo es un DAG , la lista L contendrá una solución (aunque la solución 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 falta de unicidad de la clasificación resultante, la estructura S puede ser simplemente un conjunto, una cola o una pila. Según el orden en que se eliminen los nodos n del conjunto S, se crea una solución diferente. Una variación del algoritmo de Kahn que rompe los vínculos lexicográficamente constituye un componente clave del algoritmo de Coffman-Graham para la programación paralela y el dibujo de gráficos 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 llega a cualquier nodo que ya haya sido visitado desde el comienzo de la ordenación topológica o el nodo no tiene bordes 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 no marcado n visit( n )función visita(nodo n ) si  n tiene una marca permanente entonces  retorna  si  n tiene una marca temporal entonces  detiene  (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  haga visit( m ) marcar n con una marca permanente añadir 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 gráfico). 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 finalizó 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 borde 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 forma impresa por Tarjan en 1976. ^[4]

Algoritmos paralelos

En una máquina de acceso aleatorio en paralelo , se puede construir un ordenamiento topológico en tiempo O ((log n ) ² ) utilizando un número polinomial de procesadores, lo que coloca el problema en la clase de complejidad NC ² . ^[5] Un método para hacer esto es elevar al cuadrado repetidamente la matriz de adyacencia del grafo dado, logarítmicamente muchas veces, utilizando la multiplicación de matrices min-plus con maximización en lugar de minimización. La matriz resultante describe las distancias de ruta más largas en el grafo. Ordenar los vértices por las longitudes de sus rutas de entrada más largas 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 . ^[7] En un nivel alto, 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 también se eliminan los bordes salientes de los vértices eliminados, 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 iteraciones, donde $D$ es el camino más largo en $G.$ Cada iteración se puede paralelizar, que es la idea del siguiente algoritmo. $G=(V,E)$ ${\estilo de visualización D+1}$

En lo que sigue, se supone que la partición del grafo se almacena en $p$ elementos de procesamiento (PE), que están etiquetados como . Cada PE $i$ inicializa un conjunto de vértices locales con grado de entrada 0, donde el índice superior representa la iteración actual. Dado que todos los vértices en los conjuntos locales 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 prefijo sobre los tamaños de . Entonces, en cada paso, se agregan vértices a la ordenación topológica. $0,\puntos ,p-1$ $Estilo de visualización Q_{i}^{1}}$ $Q_{0}^{1},\puntos ,Q_{p-1}^{1}$ $Q_{0}^{1},\puntos ,Q_{p-1}^{1}$ ${\textstyle \suma _{i=0}^{p-1}|Q_{i}|}$

En el primer paso, el PE $j$ asigna los índices a los vértices locales en . Estos vértices en se eliminan, junto con sus aristas salientes correspondientes. Para cada arista saliente con punto final $v$ en otro PE , el mensaje se envía al PE $l$ . Después de que se eliminan todos los vértices en , los mensajes enviados se envían a su PE correspondiente. Cada mensaje recibido actualiza el grado de entrada del vértice local $v$ . Si el grado de entrada cae a cero, $v$ se agrega a . Luego comienza la siguiente iteración. ${\textstyle \suma _{i=0}^{j-1}|Q_{i}^{1}|,\puntos ,\izquierda(\suma _{i=0}^{j}|Q_{i}^{1}|\derecha)-1}$ $Estilo de visualización Q_{j}^{1}}$ $Estilo de visualización Q_{j}^{1}}$ ${\estilo de visualización (u,v)}$ $l,j\neq l$ ${\estilo de visualización (u,v)}$ $Estilo de visualización Q_{j}^{1}}$ ${\estilo de visualización (u,v)}$ $Estilo de visualización Q_ {j}^{2}}$

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

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

p elementos de procesamiento con identificadores de 0 a p -1 Entrada: G = (V, E) DAG, distribuido a los PE, índice PE j = 0, ..., p - 1 Salida: ordenamiento topológico de GFunción traverseDAGDistributed δ grado de entrada de los vértices locales V   $Q = {v \in V | δ[v] = 0}$  // Todos los vértices con grado de entrada 0 nrOfVerticesProcesados = 0 Realice la suma del prefijo de construcción  global sobre el tamaño de Q // Obtenga los desplazamientos y el número total de vértices en este paso offset = nrOfVerticesProcessed + sum(Q _i , i = 0 a j - 1) // j es el índice del procesador para cada u en Q localOrder[u] = índice++; foreach (u,v) en E envía un mensaje ( u,v ) a PE que posee el 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 añadir 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 gráfico dada. En cuanto al tiempo de ejecución, en un modelo CRCW-PRAM que permite la búsqueda y decremento en tiempo constante, este algoritmo se ejecuta en , donde $D$ es nuevamente la ruta más larga en $G$ y $Δ$ el grado máximo. ^[7] ${\textstyle {\mathcal {O}}\left({\frac {m+n}{p}}+D(\Delta +\log n)\right)}$

Aplicación para la búsqueda del camino más corto

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

Sea $d$ una matriz de la misma longitud que $V$ ; esto contendrá las distancias de ruta más corta desde $s$ . Establezca $d [s] = 0$ , todos los demás $d [u] = \infty$ .
Sea $p$ una matriz de la misma longitud que $V$ , con todos los elementos inicializados en nil . Cada $p [u]$ contendrá el predecesor de $u$ en la ruta más corta de $s$ a $u$ .
Recorre los vértices u según lo ordenado 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 del borde 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$ una matriz de la misma longitud que $V$ ; esto contendrá las distancias de ruta más corta desde $s$ . Establezca $d [s] = 0$ , todos los demás $d [u] = \infty$ .
Sea $p$ una matriz de la misma longitud que $V$ , con todos los elementos inicializados en nil . Cada $p$ $[$ $u$ $]$ contendrá el predecesor de $u$ en la ruta más corta de $s$ a $u$ .
Recorre los vértices u según lo ordenado 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 del borde desde $v$ hasta $u$ .
  - Relaja el borde: si d [ u ] > d [ v ] + w , establece
    - $d [u] \leftarrow d [v] + w$ ,
    - $y [y] \leftarrow v$ .

En un gráfico de $n$ vértices y $m$ aristas, este algoritmo toma un tiempo $Θ(n + m)$ , es decir, 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, el orden de ordenación topológica es único; 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 probar en tiempo lineal si existe un ordenamiento único y si existe un camino hamiltoniano, a pesar de la NP-dureza del problema del camino hamiltoniano para grafos dirigidos más generales (es decir, grafos dirigidos cíclicos). ^[8]

Relación con pedidos parciales

Los ordenamientos topológicos también están estrechamente relacionados con el concepto de una 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, por cada dos objetos x e y en el conjunto, o bien x ≤ y o bien y ≤ x . Los órdenes totales son conocidos en informática como los operadores de comparación necesarios para realizar algoritmos de ordenamiento 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 precede al segundo objeto en el orden; se puede utilizar un algoritmo de ordenamiento por comparación 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 ordenamiento parcial a partir de cualquier DAG dejando que el conjunto de objetos sean los vértices del DAG y definiendo que x ≤ y es verdadero, para cualesquiera dos vértices x e y , siempre que exista un camino dirigido desde x hasta y ; es decir, siempre que y sea alcanzable desde x . Con estas definiciones, un ordenamiento topológico del DAG es lo mismo que una extensión lineal de este ordenamiento parcial. A la inversa, cualquier ordenamiento parcial puede definirse como la relación de alcanzabilidad en un DAG. Una forma de hacer esto es definir un DAG que tenga un vértice para cada objeto en el conjunto parcialmente ordenado y una arista xy para cada par de objetos para los cuales x ≤ y . Una forma alternativa de hacer esto es usar la reducción transitiva del ordenamiento parcial; en general, esto produce DAG con menos aristas, pero la relación de alcanzabilidad en estos DAG sigue siendo el mismo orden parcial. Al usar estas construcciones, se pueden usar algoritmos de ordenamiento topológico para encontrar extensiones lineales de órdenes parciales.

Relación con la optimización de la programación

Por definición, la solución de un problema de programación que incluye un gráfico 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 en sí misma no es suficiente para resolver de manera óptima un problema de optimización de la programación. El algoritmo de Hu es un método popular que se utiliza para resolver problemas de programación que requieren un gráfico de precedencia e involucran tiempos de procesamiento (donde el objetivo es minimizar el mayor tiempo de finalización entre todos los trabajos). Al igual que la ordenación topológica, el algoritmo de Hu no es único y se puede resolver utilizando DFS (al encontrar la longitud de ruta más grande y luego asignar los trabajos).

Véase también

tsort , un programa Unix para ordenamiento topológico
Conjunto de arcos de retroalimentación , un conjunto de aristas cuya eliminación permite ordenar topológicamente el subgrafo restante
Algoritmo de componentes fuertemente conectados de Tarjan , un algoritmo que proporciona una lista ordenada topológicamente de componentes fuertemente conectados en un gráfico.
Orden pretopológico

Referencias

^ Jarnagin, MP (1960), Métodos automáticos de máquina para probar la consistencia de las redes PERT , Memorándum técnico n.º K-24/60, Dahlgren, Virginia: Laboratorio de Armas Navales de EE. UU.
^ Kahn, Arthur B. (1962), "Ordenación topológica de redes grandes", Communications of the ACM , 5 (11): 558–562, doi : 10.1145/368996.369025 , S2CID 16728233
^ abc 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 con disyunción de 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", Información y control , 64 (1–3): 2–22, doi : 10.1016/S0019-9958(85)80041-3
^ Dekel, Eliezer; Nassimi, David; Sahni, Sartaj (1981), "Algoritmos de matrices y gráficos paralelos", SIAM Journal on Computing , 10 (4): 657–675, doi :10.1137/0210049, MR 0635424
^ ab Sanders, Peter; Mehlhorn, Kurt; Dietzfelbinger, Martin; Dementiev, Roman (2019), Algoritmos secuenciales y paralelos y estructuras de datos: la caja de herramientas básica, Springer International Publishing, ISBN 978-3-030-25208-3
^ Vernet, Oswaldo; Markenzon, Lilian (1997), "Problemas hamiltonianos para diagramas 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, Número de identificación del sujeto 206554481

Lectura adicional

DE Knuth , El arte de la programación informática , Volumen 1, sección 2.2.3, que ofrece un algoritmo para la clasificación topológica de un ordenamiento parcial y una breve historia.
Bertrand Meyer , Touch of Class: Learning to Program Well with Objects and Contracts , Springer , 2099, capítulo 15, Diseño e ingeniería de un algoritmo: ordenamiento topológico , utilizando un lenguaje de programación moderno, para una presentación pedagógica detallada del ordenamiento topológico (utilizando una variante del algoritmo de Kahn) con consideración del diseño de la estructura de datos, el diseño de API y las preocupaciones de ingeniería de software.

Enlaces externos

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