Ordenación Topológica

Algoritmo:

La ordenación topológica es un sistema de ordenamiento de un grafo acíclico, es decir, que no tiene ciclos; el cual consiste, en organizar de forma lineal ó en lista ascendente ó descendente, una serie de vértices en desorden, para lo cual primero debe de empezar de un "vértice padre" osea, un vértice sin predecesores, y después visitar a sus vecinos, después de que haya visitado a tos sus vecinos, pasa a analizar otro vértice, y de igual forma identifica todos sus vecinos, y así recursivamente, hasta que haya visitado a todos los vértices. En pocas palabras no se visitara un vértice, hasta que todos sus predecesores hayan sido visitados.

Después de que ya han sido visitados todos los vértices del grafo dirigido, se acomodan en lista ya sea d forma ascendente o descendente, según se requiera, y se acomodan en base a el coste de tiempo de los vértices.

Ejemplo: Este es un ejemplo común aplicado a la vida diaria, tan simple de como vestirse.

• Arriba de cada vértice se muestra el coste de tiempo.
• Distancia / Finalizacion

• El algoritmo nos devuelve una lista enlazada, con los nodos del grafo, en orden decreciente en tiempo de finalizacion.

• Una vez ya ordenado topologicamente se pueden ver las precedencias de las tareas:

1. Ponerse la camisa antes que el cinturón y el jersey.
2. Ponerse el pantalón antes que los zapatos y el cinturón.
3. Ponerse los calcetines antes que los zapatos.

Pseudocódigo:

1. Para cada vértice "u" que pertenezca al grafo hacer:
2. El estado "u" No visitado, por que se comienza el algoritmo.
3. El padre debe ser nulo, por que no tiene predecesores.
4. El tiempo inicia de 0, obviamente por que se inicia el algoritmo.
5. Después, si el estado = No visitado entonces: Se pone en marcha la ordenación topológica.
6. El estado cambiara a Visitado por que ya fue visitado y analizados su s predecesores.
7. Por lo tanto se le suma un 1 al tiempo por que es lo que tardo en ese vértice.
8. Después para cada vértice adyacente hacer:
9. Si el estado= No visitado entonces:
10. El padre ahora sera ese vértice, ya que es el siguiente en orden.
11. Cuando el estado del vértice = Terminado:
12. Se suman los tiempos y este seria el coste total por el ordenamiento.
13. Se inserta el resultado de la lista del algoritmo de ordenación topológico.

Análisis Asintótico:

En el análisis asintótico del algoritmo de ordenación topológica es costoso buscar vértice sin predecesores, varias veces.

La solución seria calcular previamente cuantos predecesores tiene cada vértice, almacenar el dato en un vector y actualizarlo siempre que se incorpore un nuevo vértice a la solución.

Coste de Tiempo:

• Inicializacion:

Primer bucle: O(n) --- Quiere decir que va a depender del numero de vértices que tenga el grafo.

Segundo bucle: Examinacion de todas las aristas.

O(a+n) --- Para listas de adyacencia.

O(n^2) --- Para matriz de adyacencia.

• Bucle Principal:

O(a+n) --- Para listas de adyacencia.

O(n^2) --- Para matriz de adyacencia.

Estructuras de datos:

• Listas Enlazadas: Para este algoritmo de ordenación topológica, se usan las listas enlazadas, ya que la ordenación ya finalizada es una lista lineal simple con aristas que conectan de igual forma como se tenia antes.
• Isomorfismo: Algo tiene que ver con ismorfismo, aunque no son grafos conexos y es acíclico el algoritmo permite alinear los vértices, pero conservando los enlaces entre cada uno de los vértices, es decir, solo se acomoda por prioridad, pero conserva su estructura.
• Arboles: También se puede decir que esta relacionado con árboles ya que estos contienen nodos también llamados vértices, y los arboles pueden adoptar distintas formas de ordenamiento.
• Búsqueda de profundidad (DFS): La ordenación topológica necesita del algoritmo de búsqueda DFS ya que necesita aplicarlo para ir explorando nodos, y al final llegar a un ordenamiento lineal.
  

Aplicaciones:

• Puede ser aplicable a la reprecentacion de las fases de un proyecto , donde los vértices representen tareas, y las aristas relaciones temporales a ellas.
• Evaluacion en la fase semántica de un compilador.
• En la vida diaria lo podríamos aplicar en cosas simples por ejemplo, organizar los recibos de los servicios a pagar, ya que estos llegan en diferentes días, y difieren en precio y vencimiento, y al aplicarle este algoritmo, podríamos ordenarlos en orden de prioridad de vencimiento, para irlos pagando ordenadamente, sin que se nos pasen y sin que gastemos el dinero necesario para pagarlos.
• También nos serviria para encontrar algun ciclo en un grafo e identificarlo.
• También para encontrar algun problema o defecto de cierto algoritmo que se ordene topologicamente.
  

Autoevaluación

En lo personal este proyecto y los otros cuatro me han sido de gran ayuda ya que la mayoría de los temas vistos eran nuevos para mi, y me di cuenta que son de gran utilidad aplicarlos a la vida cotidiana; en lo que respecta a este de la ordenación topológica, pues me deja como enseñanza a los casos en los que puedo aplicar este algoritmo. Aprendí que para alguna tarea en particular hay una(s) antes de precedencia y otra(s) como consecuencia de esa tarea, y que al fin y al cabo están vinculadas unas con otras. En conclusión de ahora en adelante las cosas que tenga que hacer a las que se le pueda aplicar este algoritmo, me facilitara la tarea, y por lo tanto tiempo y esfuerzo.

Para cualquier duda ó pregunta que tengan dejen su comentario y yo les responderé los mas pronto posible.