Ordenamiento topológico

Ordenamiento topológico

Christian von Lücken

clucken@pol.una.py

Original by Douglas Wilhelm Harder

Translated by Christian von Lücken

Ordenamiento topológicoTopological Sort

• En este tópico, discutiremos:– la idea de ordenar elementos en un DAG– un ejemplo de ordenamiento topológico– la implementación utilizando una tabal de grados

de entrada

Directed acyclic graph (DAG)

• Un grafo directo sin ciclos• Bueno para modelar procesos y estructuras que

tienen un orden parcial:a > b y b > c a > c.⇒Pero puede suceder que existan a y b tales que ni a > b ni b > c.

• Puede construirse un orden total (ya sea a > b o b > a para todo a = b) desde un orden parcial. Esto es lo que hace el ordenamiento topológico.

Teorema

• En el DFS de un grafo no dirigido, tenemos solo arcos tree y back. No existen arcos forward o cross edges.

Lemma• Un grafo dirigido G es aciclico si y solo si un

DFS de G no produce back edges.• Prueba : Si existe un back edge hay un ⇒ ⇒

ciclo.• Suponga que existe un back edge

(u, v). Entonces v es ancestro de u en un depht-first forest.

• Entonces existe un camino v ~> u, y entonces v ~> u → v es un ciclo.

LemmaUn grafo dirigido G es aciclico si y solo si un DFS de

G no produce back edges.⇒: Si existe un back edge hay un ciclo.⇒⇐: Si existe un ciclo back edge.⇒• Si G contiene un ciclo c. Sea v el primer vértice

descubierto en c, y sea (u, v) un arco predecesor en c. En el tiempo d[v], los vertices de c forman un camino blanco de v a u. Por el teorema del camino blanco u es un descendiente de v en el bosque depth-first. Por tanto, (u, v) es un back edge.

Topological sort• Un ordenamiento topológico de un DAG G = (V,

E) es un ordenamiento lineal de todos sus vértices tal que si G contiene un arco (u, v), entonces u aparece antes de v en el ordenamiento (Si el grafo no es acíclico, entonces no es posible un ordenamiento lineal)

• Un ordenamiento topológico de un grafo puede verse como un ordenamiento de sus vértices a lo largo de una linea horizontal tal que todos los arcos directos van desde la izquierda a la derecha.

Algoritmo

Ordenamiento topológico

• Dados dos vértices vi y vj en un DAG, como mucho puede existir solo:– un camino de vi a vj, o

– un camino de vj a vi

• Entonces, debe ser posible listar todos los vértices tal que en esa lista, vi precede a vj si existe un camino entre vi a vj

• Si esto no es posible, esto podría implicar la existencia de un ciclo

Ordenamiento topológico

• Este ordenamiento se llama ordenamiento topológico

• Por ejemplo, en este DAG, un ordenamiento topológico es 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13

Ordenamiento topológico

• Un ordenamiento topológico puede no ser único

• Por ejemplo, los siguientes ordenamientos– 1, 3, 2, 7, 6, 5, 4, 10, 9, 8, 12, 11, 13– 1, 2, 4, 8, 5, 9, 11, 3, 6, 10, 7, 12, 13

Aplicación

• Dado un número de tareas, usualmente existen un número de restricciones entre las tareas:– la tarea A debe completarse antes de que la

tarea B pueda empezar• Estas tareas y restricciones se pueden

representar usando un DAG• Un ordenamiento topológico del grafo

proporciona un orden en el cual se pueden ejecutar las tareas satisfaciendo las restricciones

Aplicaciones

• Secuenciade cursos en un DAG

Aplicaciones

• Un DAG representandouna serie de tares

• La numeración indicael orden topológicode la tarea

• Las flechas verdesrepresentan restricciones de

precedenciaRef: The Standard Task Graph http://www.kasahara.elec.waseda.ac.jp/schedule/

Application

• Otro orden topológicode un DAG

• El camino critico en rojo es la secuenciade tareas que toman mástiempo

Ref: The Standard Task Graph http://www.kasahara.elec.waseda.ac.jp/schedule/

Aplicaciones

• Este último DAG puede ser utilizado para realizar estas tareas en m procesadores

• En este caso, el ordenamiento topológico toma otras consideraciones, específicamente, minimizar el tiempo total de ejecutar un conjunto de tareas

• Veremos un planificador simple cuando se vean algoritmos greedy

Ordenamiento topológico

• Para generar un ordenamiento topológico debemos empezar con un vértice que tenga un grado de entrada 0: 1

Ordenamiento topológico

• En este punto, podemos ignorar estos arcos que conectan 1 con otros vértices y podemos elegir el vértice 2:

1, 2

Ordenamiento topológico

• Elegimos entre 4, 5, o 3:

1, 2, 4

Ordenamiento topológico

• Agregamos los vértices que llegan a 4 a los que ignoramos, podemos agreagar el 8

1, 2, 4, 8

Ordenamiento topológico

• En este punto no se puede agregar 11, pues sigue a 9 en el ordenamiento topológico. Debemos elegir entre 5 o 3:

1, 2, 4, 8, 5

Ordenamiento topológico

• Eliminando el 5 de consideración podemos ahora elegir los vértices 3 o 9Pero 3 debe preceder a 10:

1, 2, 4, 8, 5, 9

Ordenamiento topológico

• Podemos agregar 11 a nuestro ordenamiento topológico

1, 2, 4, 8, 5, 9, 11

Ordenamiento topológico

• El único vértice que tiene un grado de entrada con 0 es 3

1, 2, 4, 8, 5, 9, 11, 3

Ordenamiento topológico

• Agregando 3,se puede elegir entre 6 o 7

1, 2, 4, 8, 5, 9, 11, 3, 6

Ordenamiento topológico

• Agregando 6 podemos elegir entre los vértices 7 o 10

1, 2, 4, 8, 5, 9, 11, 3, 6, 10

Ordenamiento topológico

• Como 7 debe preceder 12 en el ordenamiento topológico, debemos agregar 7 al ordenamiento

1, 2, 4, 8, 5, 9, 11, 3, 6, 10, 7

Ordenamiento topológico

• En este punto se agrega 12

1, 2, 4, 8, 5, 9, 11, 3, 6, 10, 7, 12

Ordenamiento topológico

• Finalmente el vértice 13

1, 2, 4, 8, 5, 9, 11, 3, 6, 10, 7, 12, 13

Ordenamiento topológico

• En este punto no quedan vértices, y se ha completado el ordenamiento topológico en este grafo

1, 2, 4, 8, 5, 9, 11, 3, 6, 10, 7, 12, 13

Ordenamiento topológico

• Es obvio que el ordenamiento topológico no es único

• En cualquier punto donde existe una elección sobre cual vértice seguir tenemos posibilidades de formar un orden topológico diferente

Ordenamiento topológico

• Por ejemplo, en esta etapa, podríamos elegir 7 en vez de 6:

1, 2, 4, 8, 5, 9, 11, 3, 7

Ordenamiento topológico

• El orden topológico resultante podría ser entonces

1, 2, 4, 8, 5, 9, 11, 3, 7, 6, 10, 12, 13

Ordenamiento topológico

• Dos ordenamientos distintos son:1, 2, 4, 8, 5, 9, 11, 3, 6, 10, 7, 12, 13

1, 2, 4, 8, 5, 9, 11, 3, 7, 6, 10, 12, 13

• Pero no son los únicos posibles:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13

es igualmente aceptable

Implementación

• Qué se necesita para construir un ordenamiento topológico?

• Suponga que tenemos un array con los grados de entrada de cada vértice

1 0

2 1

3 1

4 1

5 1

6 1

7 1

8 1

9 1

10 2

11 2

12 2

13 2

Implementación

• Recorrido en amplitud

• Creamos un contenedor (stack o cola) que contiene todos los vértices con grado de entrada 0

1 0

2 1

3 1

4 1

5 1

6 1

7 1

8 1

9 1

10 2

11 2

12 2

13 2

Implementación

• Usamos una cola

• La cola inicialmente contiene solo el vértice 1

• Podemos sacar 1 de la cola y agregar a nuestro ordenamiento topológico:

1

1 0

2 1

3 1

4 1

5 1

6 1

7 1

8 1

9 1

10 2

11 2

12 2

13 2

Implementación

• Ahora con el recorrido en amplitud encolamos todos los vértices hijo

• En este caso, decrementamos el grado de entrada de todos los vértices adyacentes al vértice desencolado

1 0

2 0

3 0

4 1

5 1

6 1

7 1

8 1

9 1

10 2

11 2

12 2

13 2

Implementación

• Cada vez que decrementamos el grado de entrada de un vertice verificamos si es cero

• Si es cero encolamos el nodo

• Ahora nuestra cola contiene 2 y 3

1 0

2 0

3 0

4 1

5 1

6 1

7 1

8 1

9 1

10 2

11 2

12 2

13 2

Implementación

• Desencolamos 2, lo agregamos al ordenamiento topológico

1, 2y decrementamos los grados de entrada de los vértices 4 y 5

• Tanto 4 y 5 se reducen a cero, nuestra cola es: 3, 4, 5

1 0

2 0

3 0

4 0

5 0

6 1

7 1

8 1

9 1

10 2

11 2

12 2

13 2

Ejemplo

• Considere el DAG con seis vértices

Ejemplo

• Creamos la tabla con los grados de entrada

1 0

2 1

3 3

4 3

5 2

6 0

Ejemplo

• Cremos una cola donde agregamos 1 y 6

1 0

2 1

3 3

4 3

5 2

6 01 6Queue

Ejemplo

• Desencolamos (1), decrementamos el grado de entrada de toos los vértices y desencolamos 2

1 0

2 0

3 3

4 2

5 2

6 06 2Queue

Sort1

Ejemplo

• Desencolamos 6 y decrementamos los grados de entrada de los adyacentes

1 0

2 0

3 2

4 2

5 1

6 02Queue

Sort1, 6

Ejemplo

• Desencolamos 2, decrementamos, y encolamos 5

1 0

2 0

3 1

4 1

5 0

6 05Queue

Sort1, 6, 2

Ejemplo

• Desencolamos 5, decrementamos, y encolamos el vértice 3

1 0

2 0

3 0

4 1

5 0

6 03Queue

Sort1, 6, 2, 5

Ejemplo

• Desencolamos 3, decrementamos 4, y agreagamos 4 al la cola

1 0

2 0

3 0

4 0

5 0

6 04Queue

Sort1, 6, 2, 5, 3

Ejemplo

• Desencolamos 4, no existen vértices adyacentes para decrementar

1 0

2 0

3 0

4 0

5 0

6 0Queue

Sort1, 6, 2, 5, 3, 4

Ejemplo

• La cola esta vacía, el ordenamiento tpológico es1, 6, 2, 5, 3, 4

Referencias

[1] Cormen, Leiserson, and Rivest, Introduction to Algorithms, McGraw Hill, 1990, §11.1, p.200.

[1] Cormen, Leiserson, and Rivest, Stein Introduction to Algorithms, McGraw Hill, 2001, §22.

[2] Weiss, Data Structures and Algorithm Analysis in C++, 3rd Ed., Addison Wesley, §9.2, p.342-5.