clasificación topológica

En informática , una clasificación topológica o un ordenamiento topológico de un gráfico dirigido es un ordenamiento lineal de sus vértices tal que para cada borde dirigido (u,v) desde el vértice u hasta el vértice v , u viene antes de v en el orden. Por ejemplo, los vértices del gráfico pueden representar tareas a realizar y los bordes pueden representar restricciones de que una tarea debe realizarse antes que otra; En esta aplicación, un ordenamiento topológico es simplemente una secuencia válida para las tareas. Precisamente, una clasificación topológica es un recorrido de gráfico en el que cada nodo v se visita solo después de que se visitan todas sus dependencias . Un ordenamiento topológico es posible si y sólo si el grafo no tiene ciclos dirigidos , es decir, si es un grafo acíclico dirigido (DAG). Cualquier DAG tiene al menos un ordenamiento topológico y se conocen algoritmos para construir un ordenamiento topológico de cualquier DAG en tiempo lineal . La clasificació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 clasificación topológica es la programación de una secuencia de trabajos o tareas en función de sus dependencias . Los trabajos están representados por vértices, y hay un borde de x a y si el trabajo x debe completarse antes de que se pueda iniciar el trabajo y (por ejemplo, al lavar ropa, la lavadora debe terminar antes de que pongamos la ropa en la secadora). . Luego, una clasificación topológica da un orden para realizar los trabajos. Una aplicación estrechamente relacionada de los algoritmos de clasificació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 los bordes representan las tareas que se deben realizar entre un hito y otro. La clasificació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 duración del cronograma general del proyecto.

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

Algoritmos

Los algoritmos habituales para la clasificació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|).$

algoritmo de kahn

Uno de estos algoritmos, descrito por primera vez por Kahn (1962), funciona eligiendo los vértices en el mismo orden que el orden topológico 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 gráfico acíclico no vacío. Entonces:

L ← Lista vacía que contendrá los elementos ordenados S ← Conjunto de todos los nodos sin borde 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, luego inserte m en Ssi  el gráfico tiene aristas , entonces  devuelve un error (el gráfico tiene al menos un ciclo); de lo contrario,  devuelve  L  (un orden ordenado topológicamente)

Si el gráfico es un DAG , habrá una solución en la lista L (aunque la solución no es necesariamente única). De lo contrario, el gráfico debe tener al menos un ciclo y, por tanto, una clasificación topológica es imposible.

Como reflejo de la no unicidad del tipo resultante, la estructura S puede ser simplemente un conjunto, una cola o una pila. Dependiendo del orden en que se eliminan los nodos n del conjunto S, se crea una solución diferente. Una variación del algoritmo de Kahn que rompe vínculos lexicográficamente forma 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 clasificación topológica se basa en la búsqueda en profundidad . El algoritmo recorre cada nodo del gráfico, en un orden arbitrario, iniciando una búsqueda en profundidad que termina cuando llega a cualquier nodo que ya ha sido visitado desde el comienzo de la clasificación topológica o el nodo no tiene bordes de salida (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 visite ( n )función visitar (nodo n ) si  n tiene una marca permanente , entonces  regresar  si  n tiene una marca temporal , luego  detenerse  (el gráfico tiene al menos un ciclo) marcar n con una marca temporal para cada nodo m con un borde de n a m  visite ( m ) eliminar la marca temporal de n marcar n con una marca permanente añadir n a la cabeza 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: fueron agregados a L mediante la llamada recursiva a visit() que finalizó antes de la llamada a visitar n , o mediante 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 paralela de acceso aleatorio , se puede construir un ordenamiento topológico en tiempo O ((log n ) ² utilizando un número polinómico de procesadores, colocando 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 gráfico dado, de manera logarítmica muchas veces, usando la multiplicación de matrices mínimo-más con maximización en lugar de minimización. La matriz resultante describe las distancias de camino más largas en el gráfico. Ordenar los vértices por la longitud de sus caminos entrantes más largos produce un ordenamiento topológico. ^[6]

Un algoritmo para clasificació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 0 y los agrega a la clasificación topológica en el orden en que fueron eliminados. Dado que los bordes salientes de los vértices eliminados también se eliminan, habrá un nuevo conjunto de vértices de grado 0, donde se repite el procedimiento 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)$ $D+1$

A continuación, se supone que la partición del gráfico se almacena en $p$ elementos de procesamiento (PE), que están etiquetados . Cada PE $i$ inicializa un conjunto de vértices locales con grado 0, donde el índice superior representa la iteración actual. Dado que todos los vértices en los conjuntos locales tienen grado 0, es decir, no son adyacentes, se pueden dar en un orden arbitrario para una clasificació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 clasificación topológica. $0,\puntos,p-1$ $Q_{i}^{1}$ $Q_{0}^{1},\dots,Q_{p-1}^{1}$ $Q_{0}^{1},\dots,Q_{p-1}^{1}$ ${\textstyle \sum _ {i=0}^{p-1}|Q_ {i}|}$

En el primer paso, PE $j$ asigna los índices a los vértices locales en . Estos vértices se eliminan, junto con sus correspondientes aristas salientes. Para cada borde saliente con punto final $v$ en otro PE , el mensaje se envía al PE $l$ . Una vez eliminados todos los vértices , los mensajes publicados se envían a su PE correspondiente. Cada mensaje recibido actualiza el grado del vértice local $v$ . Si el grado cae a cero, se suma $v$ a . Luego comienza la siguiente iteración. ${\textstyle \sum _{i=0}^{j-1}|Q_{i}^{1}|,\dots ,\left(\sum _{i=0}^{j}|Q_{i }^{1}|\derecha)-1}$ $Q_{j}^{1}$ $Q_{j}^{1}$ $(u,v)$ $l,j\neq l$ $(u,v)$ $Q_{j}^{1}$ $(u,v)$ $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 quedan vértices para procesar, por lo tanto . A continuación se muestra una descripción general del pseudocódigo de datos múltiples, de un solo programa y de alto nivel de este algoritmo. ${\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}$ $a_{k-1}$ $k-1$ ${\textstyle \sum _{i=0}^{p-1}|Q_{i}^{D+1}|=0}$

Tenga en cuenta que la suma del prefijo para las compensaciones locales se puede calcular de manera eficiente en paralelo. ${\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}$

p elementos de procesamiento con ID de 0 a p -1 Entrada: G = (V, E) DAG, distribuido a PE, índice PE j = 0, ..., p - 1 Salida: clasificación topológica de Gfunción atravesarDAGDistribuido δ grado entrante de los vértices locales V   $Q = {v \in V | δ[v] = 0}$  // Todos los vértices con grado 0 nrOfVerticesProcessed = 0 hacer la suma  global del prefijo de compilación sobre el tamaño de Q // obtener compensaciones y el número total de vértices en este paso offset = nrOfVerticesProcessed + sum(Q _i , i = 0 to j - 1) // j es el índice del procesador para cada u en Q  ordenlocal[u] = índice++; foreach (u,v) en E publica el mensaje ( u, v ) en PE que posee el vértice v nrOfVerticesProcessed += sum(|Q _i |, i = 0 to 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 agregue v a Q  mientras el tamaño global de Q > 0 devolver orden local

El costo de la 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 buscar y disminuir 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 a la búsqueda del camino más corto.

El orden topológico también se puede utilizar para calcular rápidamente los caminos más cortos a través de un gráfico acíclico dirigido ponderado . Sea $V$ la lista de vértices de dicho gráfico, en orden topológico. Luego, el siguiente algoritmo calcula la ruta más corta 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 mantendrá las distancias de camino más corto 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 a cero . Cada $p [u]$ contendrá al predecesor de $u$ en el camino más corto desde $sa$ $u$ .
Recorra 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 del borde de $u$ a $v$ .
  - Relaje el borde: si d [ v ] > d [ u ] + w , establezca
    - $re [v] \leftarrow re [u] + w$ ,
    - $pags [v] \leftarrow tu$ .

Equivalentemente:

Sea $d$ una matriz de la misma longitud que $V$ ; esto mantendrá las distancias de camino más corto 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 a cero . Cada $p$ $[$ $u$ $]$ contendrá al predecesor de $u$ en el camino más corto desde $sa$ $u$ .
Recorra 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$ .
  - Relaje el borde: si d [ u ] > d [ v ] + w , establezca
    - $re [u] \leftarrow re [v] + w$ ,
    - $pags [tu] \leftarrow v$ .

En una gráfica de $n$ vértices $ym$ aristas, este algoritmo toma tiempo $Θ(n + m)$ , es decir, lineal . ^[3]

Unicidad

Si una clasificació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 una ruta hamiltoniana dirigida en el DAG . Si existe un camino hamiltoniano, el orden de clasificación topológico es único; ningún otro orden respeta los bordes del camino. Por el contrario, si un ordenamiento topológico no forma una ruta hamiltoniana, el DAG tendrá dos o más ordenamientos topológicos válidos, ya que en este caso siempre es posible formar un segundo ordenamiento válido intercambiando dos vértices consecutivos que no están conectados por un borde. el uno al otro. Por lo tanto, es posible probar en tiempo lineal si existe un orden único y si existe una ruta hamiltoniana, a pesar de la dureza NP del problema de la ruta hamiltoniana para gráficos dirigidos más generales (es decir, gráficos dirigidos cíclicos). ^[8]

Relación con 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 y y ≤ x entonces x = y ) y transitividad. (si x ≤ y y y ≤ z , entonces x ≤ z ). Un orden total es un orden parcial en el que, por cada dos objetos xey en el conjunto, x ≤ y o y ≤ x . Los pedidos totales son familiares en informática como los operadores de comparación necesarios para realizar algoritmos de clasificación de comparación . Para conjuntos finitos, los pedidos 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 clasificación 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 en el orden total también.

Se puede definir un orden parcial de cualquier DAG dejando que el conjunto de objetos sean los vértices del DAG y definiendo x ≤ y como verdadero, para dos vértices cualesquiera x e y , siempre que exista una ruta dirigida de x a 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 orden parcial. Por el contrario, cualquier orden parcial puede definirse como la relación de accesibilidad 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 hacerlo es utilizar la reducción transitiva del ordenamiento parcial; en general, esto produce DAG con menos aristas, pero la relación de accesibilidad en estos DAG sigue siendo el mismo orden parcial. Al utilizar 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 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 utilizado 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 clasificación topológica, el algoritmo de Hu no es único y se puede resolver utilizando DFS (encontrando la longitud de ruta más grande y luego asignando los trabajos).

Ver también

tsort , un programa Unix para clasificación topológica
Conjunto de arco 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 la lista topológicamente ordenada de componentes fuertemente conectados en un gráfico.
Orden pretopológico

Referencias

^ Jarnagin, MP (1960), Métodos automáticos para probar la coherencia de las redes PERT , Memorando técnico n.º K-24/60, Dahlgren, Virginia: Laboratorio de armas navales de EE. UU.
^ Kahn, Arthur B. (1962), "Clasificación topológica de grandes redes", Comunicaciones del ACM , 5 (11): 558–562, doi : 10.1145/368996.369025 , S2CID 16728233
^ a b C Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2001), "Sección 22.4: Clasificació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 de bordes separados 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 gráficos y matrices paralelas", Revista SIAM de Computación , 10 (4): 657–675, doi :10.1137/0210049, SEÑOR 0635424
^ ab Sanders, Peter; Mehlhorn, Kurt; Dietzfelbinger, Martín; Dementiev, Roman (2019), Estructuras de datos y algoritmos 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 diagramas de flujo reducibles" (PDF) , Actas: XVII Conferencia Internacional de la Sociedad Chilena de Informática , págs. 264–267, doi :10.1109/SCCC.1997.637099, hdl : 11422/2585 , S2CID 206554481

Otras lecturas

DE Knuth , The Art of Computer Programming , Volumen 1, sección 2.2.3, que proporciona 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: clasificación topológica , utilizando un lenguaje de programación moderno, para una presentación pedagógica detallada de la clasificación topológica (usando una variante del algoritmo de Kahn) teniendo en cuenta el diseño de estructuras de datos, el diseño de API y las cuestiones de ingeniería de software.

enlaces externos

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