ESTRUCTURAS Y ALGORITMOS DE PROCESAMIENTO DE DATOS: ORDENACION TOPOLOGICA

1 Introducción:

La ordenación topológica mediante algoritmos de grafos es una utilidad que facilita la toma de decisiones.
Es uno de los algoritmos más conocidos de grafos, el cual se emplea para hallar un orden en una lista de todos
los nodos del grafo (dirigido acíclico) de tal forma que sea visitado antes que sus predecesores (padres)
Hoy en día la toma de decisiones es muy importante ya sea en la vida empresarial o en la doméstica.

2 Conceptos Previos:

• 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.

3 Ordenación Topológica:

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 / Finalización.
• El algoritmo nos devuelve una lista enlazada, con los nodos del grafo, en orden decreciente en tiempo de finalización.
• 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.

Un Orden Topológico ordena los nodos de un grafo dirigido acíclico de forma que si hay una camino del nodo A al nodo B entonces A aparece antes que B en la ordenación. El sentido de las flechas indica las dependencias. A depende de B y C, B depende de C, etc, etc. La librería standard de Ruby tiene un módulo (TSort) que implementa el orden topológico usando el algoritmo de Tarjan y nos ofrece una interfaz para utilizarlo. El módulo TSort está diseñado para ser utilizado con cualquier objeto que pueda ser modelado como un grafo dirígido. 

4 Ejemplo Clarificador:

4.1 Caso práctico Ordenamiento topológico de un grafo

Problema:

Existen varios problemas en las cuales no es posible iniciar una actividad sin antes haber terminado otra. Un problema que ya seguramente h podido apreciar es el de determinar el orden en el cual usted podrá tomar cursos. Algunos tienen prerrequisitos. Otros más de un prerrequisito. Y adicionalmente los prerrequisitos pueden tener a su vez prerrequisitos del plan de estudios de la carrera de Ingeniería de Software de la universidad tecnológica del Perú.
Los grafos que se muestran en la figura se conocen como grafos acíclicos dirigidos (DAG). Se trata de grafos dirigidos que no contienen ciclos, de, modo que una vez que se pasa por un vértice, no hay trayectoria de regreso a ese vértice

• Ejemplo de grafo acíclico dirigido

• Prerrequisitos del Plan de estudios

5 Algoritmos de Ordenación Topológica:

Una forma de encontrar un ordenamiento topológico es examinando todos los nodos del grafo y aquellos nodos que no tengan aristas incidentes sobre ellos son eliminados del grafo e introducidos en una cola (o lista), se repite este proceso hasta que no queden nodos en el grafo.


Se escoge un vértice que no tenga lados incidentes y se coloca en una lista. Escogemos el vértice 1, lo eliminamos del grafo. (al eliminar este vértice, se eliminan todos los lados que salen de él)

Del grafo resultante, se escoge un vértice que no tenga lados incidentes en él, se quita del grafo y se coloca en la cola. Escogemos el vértice 3, La cola es 1 3


Del grafo resultante, se escoge un vértice que no tenga lados incidentes en él, se quita del grafo y se coloca en la cola. Escogemos el vértice 2, La cola es 1 3 2




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óntopológico.

Análisis Asintótico:
En el análisis asintótico del algoritmo de ordenacióntopológica es costoso buscar vértice sin predecesores, varias veces.La solución seria calcular previamente cuantos predecesores tiene cada vértice, almacenar el datoen 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.

Algoritmo para la búsqueda en profundidad:
Este algoritmo realiza la búsqueda en profundidad el grafo G comenzando en un nodo A.
1. Inicializar todos los nodos al estado de preparado (ESTADO=1)
2. Meter el nodo inicial A en la pila y cambiar su estado a estado de espera (ESTADO=2).
3. Repetir los pasos 4 y 5 hasta que la pila este vacia.
4. Sacar el nodo N en la cima de la pila. Procesar el nodo N y cambiar su
estado al de procesado (ESTADO=3).
5. Meter en la pila todos los vecinos de N que estén en estado de
preparados (ESTADO=1) y cambiar su estado a estado de espera
(ESTADO=2).
[ fin de bucle del paso 3 ]
6. Salir.

Algoritmo de ordenación topológica:
El siguiente algoritmo encuentra una ordenación topológica T de un grafo S sin ciclos.
1. Encontrar el grado de entrada GraEnt(N) de cada nodo N de S (se puede hacer recorriendo cada lista de adyacencia)
2. Poner en una cola todos los nodos con grado de entrada nulo.
3. Repetir los pasos 4 y 5 hasta que la cola esté vacía.
4. Quitar el nodo N al frente de la cola (haciendo Frente:=Frente + 1)
Hacer GraRnt(M):= GraEnt(M) – 1 (esto elimina la arista de N a M)
si GraEnt(M)=0, entonces: Añadir M al final de la cola.
[ fin de bucle paso 5 ]
[ fin de bucle paso 3 ]
5. Repetir lo siguiente para cada vecino M de N:
6. Salir.

6 Código:

Codigo C++:
Grafo.h

#ifndefGRAFO_H_ #defineGRAFO_H_ #include<list> #include<iostream> template<typename C> class Grafo{ public: class Arco { public: Arco(); Arco(const Arco & otroArco); Arco(int adyacente, const C & costo); int devolverAdyacente() const; const C & devolverCosto() const; int vertice; C costo; }; public: Grafo(); Grafo(const Grafo & otroGrafo); ~Grafo(); Grafo & operator = (const Grafo & otroGrafo); bool estaVacio() const; int devolverLongitud() const; bool existeVertice(int vertice) const; bool existeArco(int origen, int destino) const; const C & costoArco(int origen, int destino) const; void devolverVertices(list<int> & vertices) const; void devolverAdyacentes(int origen, list<Arco> & adyacentes) const; void agregarVertice(int vertice); void eliminarVertice(int vertice); void agregarArco(int origen, int destino, const C & costo); void eliminarArco(int origen, int destino); void vaciar(); private: struct NGrafo{ int vertice; list<Arco> adyacentes; }; list<NGrafo> grafo; };

Código Completo C++:

http://ordenacion-topologica-grafos.wikispaces.com/file/view/ordenamiento_topologico.rar/226222620/ordenamiento_topologico.rar

PPT:

http://ordenacion-topologica-grafos.wikispaces.com/file/view/Orden%20Topol%C3%B3gico.ppt/225960166/Orden%20Topol%C3%B3gico.ppt