ANÁLISIS Y DISEÑOS DE ALGORITMOS

TRABAJO: TALLER SCC

MATERIA: ANÁLISIS Y DISEÑOS DE ALGORITMOS

PROFESORA: LUZ ENITH GUERRERO MENDIETAI

PRESENTADO POR:

JUAN JOSÉ PALACIO GARCÍA

LEONARDO GARCÍA OROZCO

JUEVES 14 DE MARZO DE 2019

UNIVERSIDAD NACIONAL DE COLOMBIA

SEDE MANIZALES

TALLER SCC

“Bitácora de desarrollo”

Desarrollador utilizado: Inicialmente se le da uso a NetBeans 8.2, pero tuvo ciertas fallas mediante una actualización entonces emigramos a Eclipse en su versión más nueva.

Algoritmos Usados: Al inicio del taller, se empezó implementando un algoritmo de Kosaraju, pero a ese algoritmo le hacían falta ciertas referencias importantes que hacían que no se cumpliera a cabalidad lo que se estaba pidiendo. Luego de ello, por recomendaciones de compañeros se decidió revisar el algoritmo de matriz de adyacencia, pero no satisfizo nuestras necesidades este y volvimos al de Kosaraju, el cual sabíamos que en internet podríamos encontrar uno más completo. Terminamos encontrando un Kosaraju que cumplía todas las funciones y decidimos trabajar sobre ese algoritmo. (github.com)

Estas fueron las funciones que utilizamos en el algoritmo de Kosaraju para cumplir con las condiciones del taller:

• Public Class Graph: Es en esta clase en donde se inicializa todo lo correspondiente al grafo que será recibido mediante el archivo.txt. Además de ello esta clase también trabaja con:

• Revisiones de ordenamiento del grafo (Cómo se encuentra ordenado el grafo y de qué manera se ve)
• Da un repaso al grafo y dice cuáles son sus nodos principales.
• Inicializa una variable que toma el tiempo que tarda en hacer todas estas funciones.
• Tiene un acumulador de DFS, es donde se guarda los nodos ya revisados y se van acumulando.
• Es dentro de esta función, que es la función de dónde se saca el nombre principal. Es aquí en este pedazo de la función en donde se instaura el archivo y garantiza que cada uno de los vértices y aristas de este grafo sean recorridas (mediante una función While ) en donde se garantiza que vértices lleguen hasta el “máximo” o hasta “máximo – 1” garantizando que todos los vértices sean recorridos.

• Public Int[] Computer SCC

• Es dentro de esta función en donde se hace respuesta a las solicitudes del ejercicio. Esta función está encargada de tomar los datos que darán dos funciones que más adelante explicaremos (DFS1, DFS2), que devolverán los grafos de mayor tamaño y ya esta función se encargará de compararlos y así poder llegar a los primeros 5; los cuales se organizarán de mayor a menor.

• Public Void DFSLoop1

• Esta función es la encargada de revisar de atrás hacia delante el grafo que está en el archivo (grafo.txt). Se hace con el fin de recorrer todos los puntos de un grafo, pudiendo conocer cada uno de sus caminos.

• Public Void DFSLoop2

• Este a diferencia de la función anterior, este se encarga de recorrer cada uno de los vértices, garantizándole al programa que todos los vértices sean recorridos.

• Public Void DFS1

• Comprueba lo que se hizo en DFSLoop1, garantizando que cada uno de los nodos revisados, hayan quedado listos para sacar la respuesta

• Public Void DFS2

• Comprueba de manera distinta que el DFS1, mientras que el se encarga de revisar por nodos, este se encarga de revisar el grafo mediante los vértices y así luego de tener todos los vértices

• Public Void PrintGraph

• Función en donde estará pintado o dibujado el grafo, con todos sus nodos y sus vértices.

• Public Static Void Main

• Es el main, es donde todas las funciones anteriores se conectan para poder ejecutar el ejercicio completo. A diferencia de esto, es que si el archivo no se encuentra o el archivo de ninguna manera existe, el archivo arrojará un error, ya que en el Main se hace ejecución a una excepción que ayuda a eso. La función de excepción es: FileNotFoundException

Bibliografía

• https://github.com/lisalisadong/algorithms-design-and-analysis/blob/master/graph/kosaraju-dfs-scc/Graph.java (tomado de aquí el Algoritmo de trabajo)

• https://www.sanfoundry.com/java-program-kosaraju-algorithm/ (Primer algoritmo revisado)

• https://es.wikipedia.org/wiki/Componente_fuertemente_conexo

• http://www.jc-mouse.net/java/matriz-de-adyacencia-representacion-de-grafos-en-java

• https://yoandroide.xyz/grafos-implementacion-matriz-de-adyacencia-en-java/

...