019365 ADA ProyectoFinal

5/14/2018 019365 ADA ProyectoFinal - slidepdf.com

http://slidepdf.com/reader/full/019365-ada-proyectofinal 1/26

Ingeniería en Ciencias Computacionales

Análisis y Diseño de Algoritmos

Prof. Wendy Trujillo Lugo

Proyecto final:

Aplicación para manipulary visualizar grafos dirigidos

Luis Pulido DíazMatrícula: 19365

Tijuana, B.C. México, a 24 de mayo de 2011



Cetys Universidad – ICC – Análisis y Diseño de AlgoritmosAplicación para Manipular y Visualizar Grafos Dirigidos (2011-1)

Luis Pulido Díaz (19365)Página 2 de 26

Tabla de contenidos

Introducción y Marco Teórico ............................................................... 4

Teoría de Grafos ............................................................................... 4

Historia ......................................................................................... 4

Aplicaciones .................................................................................. 4

Grafo ................................................................................................ 5

Algoritmos .................................................................................... 6

Operaciones .................................................................................. 6

Representaciones .......................................................................... 6

Borradores y Bosquejos Previos ........................................................... 7

Lenguajes ......................................................................................... 7

Esbozos ........................................................................................... 7

Aplicación ........................................................................................... 8

Estructura ........................................................................................ 8

Librerías .......................................................................................... 9

Screenshots ................................................................................... 10

Cargando la aplicación ................................................................ 10

Presentación ............................................................................... 10

Agregando nodos ........................................................................ 11

Agregando nodos por voz ............................................................ 11

Menú de opciones (click derecho) ................................................ 12

Agregando aristas ....................................................................... 12

Grafo completo con aristas no valuados ....................................... 14

Grafo completo con aristas valuados ........................................... 14

Eliminando una arista ................................................................. 15

Eliminando un nodo .................................................................... 16

Guardando un grafo .................................................................... 18

Recuperando un grafo ................................................................. 18





Encontrando la ruta más corta .................................................... 20

Matriz de pesos........................................................................... 21

Matriz de adyacencia .................................................................. 22

Lista de adyacencia ..................................................................... 22

Profundidad ................................................................................ 23

Debugging con Chrome Developer Tools ...................................... 23

Desarrollo ................................................................................... 24

Conclusión ........................................................................................ 25

Referencias ....................................................................................... 26





Introducción y Marco Teórico

Este proyecto es para demostrar lo aprendido en el curso de Análisis yDiseño de Algoritmos (CC405).

El proyecto consta de una aplicación para crear, manipular y visualizargrafos dirigidos; y ejecutar sus operaciones básicas y algunas avanzadas.

Antes de mostrar la aplicación y describir su funcionamiento, esnecesario definir ciertos conceptos que ayudarán al usuario que no tieneconocimiento del tema a familiarizarse con ellos. Si usted ya conocesobre este tema, puede omitir su lectura.

Teoría de GrafosEn los campos de matemáticas y ciencias computacionales, la teoría degrafos es aquella que estudia las propiedades de los grafos.

Historia

El estudio de los grafos (la teoría de grafos), se remonta a 1736, cuandoLeonhard Euler plantea un problema de lógica llamado “problema de lossiete puentes de Königsberg”. El problema consta en pasar por todoslos puentes sólo una vez y regresar al mismo lugar del que se partió.

En 1845, Gustav Kirchhoff publicó leyes de los circuitos para calcular elvoltaje y la corriente en los circuitos eléctricos mediante el análisis denodos y las aristas adyacentes.

En 1852 Francis Guthrie planteó el problema de los cuatro colores queplantea si es posible, utilizando solamente cuatro colores, colorearcualquier mapa de países de tal forma que dos países vecinos nuncatengan el mismo color. Este problema, que no fue resuelto hasta unsiglo después por Kenneth Appel y Wolfgang Haken, puede serconsiderado como el nacimiento de la teoría de grafos. Al tratar deresolverlo, los matemáticos definieron términos y conceptos teóricosfundamentales de los grafos.

Aplicaciones

Los grafos dirigidos se encuentran en los modelos más ubicuos, tantoen las estructuras naturales como en las creadas por el hombre. Pueden





ser usados para modelar muchos tipos de relaciones y procesardinámicas en sistemas físicos, biológicos y sociales. Varios problemasde interés práctico pueden ser representados por grafos.

En ciencias de la computación, los grafos son usados para representar

redes de comunicación, organización de datos, dispositivoscomputacionales, flujo computacional, etc. Un ejemplo práctico: laestructura de vínculos de un sitio Web puede representarse mediante ungrafo dirigido. Los nodos (o vértices) representan páginas disponibles enel sitio Web, y el arista entre una página A a una página B existe sí ysolo si A tiene un vínculo a B. Una aproximación parecida se puedetomar de los problemas de viajes, biología, diseño de chips decomputadoras, y muchos otros campos de estudio. El desarrollo dealgoritmos para manipular grafos es de gran interés en las cienciascomputacionales.

La teoría de grafos también es usada para estudiar moléculas en lasciencias química y física. En física de materiales condensados, laestructura tridimensional de modelos atómicos complejos simuladospuede ser estudiada cuantitativamente generando estadísticas depropiedades de la teoría de grafos relacionadas a la topología de losátomos.

Esta teoría también es usada ampliamente en la sociología, por ejemplo,para medir el prestigio de un actor, o explorar mecanismos de difusión,notablemente mediante el uso de software de análisis de redes sociales.

Grafo

Un grafo es una estructura de datosabstracta con la que se pretendeimplementar los conceptos de grafoe hipergrafo de matemáticas.

Esta estructura de datos consisteen un conjunto finito (y si es posible

mutable) de pares ordenados,llamados aristas o arcos, de lasentidades llamadas nodos o vértices. Como en matemáticas, un arista(x,y) se dice que va de x a y. Los nodos pueden ser parte de laestructura de datos, o pueden ser entidades externas representadas poríndices enteros o referencias.

Una estructura de datos tipo grafo también puede asociar cada aristacon un valor, ya sea una etiqueta simbólica o un atributo numérico(costo, capacidad, peso, longitud, etc.).





AlgoritmosLos algoritmos de los grafos son un campo muy interesante en lasciencias computacionales. Las operaciones típicas de alto nivelasociadas con los grafos son:

• Encontrar el camino entre dos nodoso Algoritmo depth-first search (profundidad)o Algoritmo depth-first search (amplitud)

• Encontrar la ruta más corta entre un nodo y otroo Algoritmo Dijkstrao Algoritmo Floyd-Warshall

Un grafo dirigido también se puede ver como una red de flujo, dondecada arista tiene una capacidad y recibe un flujo. El algoritmo Ford-Fulkerson se usa para encontrar el flujo máximo desde la raíz hasta elfondo de un grafo.

OperacionesLas operaciones básicas provistas por una estructura de datos de grafoG usualmente incluyen:

• adjacent(G,x,y): Verifica si existe un arista del nodo x al nodo y .• neighbors(G,x): Enlista todos los nodos y a los que apunta el

nodo x.• add(G,x,y): Agrega a G un arista de x a y , si no existe alguno.

• add(G,x,value): Agrega a G un arista de x a y con el valor value,

si no existe alguno.• delete(G,x,t): Elimina el arista de x a y en G, si existe.

RepresentacionesHay diferentes estructuras de datos que se usan en la práctica pararepresentar grafos:

• Lista de adyacencia: La lista de adyacencia se implementa comoun arreglo de listas, con una lista de nodos de destino para cadanodo fuente.

• Lista de incidencia: Una variante de la lista de adyacencia que

incluye el peso (valor) de cada arista.• Matriz de adyacencia: Una matriz bidimensional booleana en la

que las filas y columnas representan los vértices fuente y destino,y el contenido de la matriz indica si existe o no un arista asociadocon esa fila y columna.

• Matriz de incidencia: Una matriz bidimensional booleana en laque las filas representan los nodos y las columnas los aristas. Elcontenido de la matriz indica si ambos están relacionados.

• Matriz de pesos: Es la matriz de adyacencia en donde en vez decontener valores booleanos, el contenido del arreglo

bidimensional es el valor de cada arista, si existe.





Borradores y Bosquejos Previos

El diseño de la estructura de datos tipo grafo tuvo dos etapas en esteproyecto. El primero de ellos fue de dos listas dinámicas: una paraguardar los nodos y otra para guardar las aristas.

LenguajesEl lenguaje de programación utilizado en este proyecto fue JavaScript,un lenguaje dinámico, de alto nivel, utilizado hoy en día en todos losnavegadores y más recientemente en aplicaciones de escritorio ymóviles.

Gracias al poder de este lenguaje, se aprovecharon sus arreglosdinámicos que funcionan como listas enlazadas y su contenido puede

variar en cuanto al tipo de dato.

EsbozosEl primer esbozo de la estructura (sin sus operaciones) fue como semuestra a continuación:

/* * nodes: ['example','node','in','each','element']* edges: [ ['example','in'] , ['example','each'] , ['node','element'] ]*/ function DirectedGraph(){

this.nodes = new Array(); this.edges = new Array();

} DirectedGraph.prototype = {

constructor:DirectedGraph, }

La estructura de las aristas era una lista de pares, que contenían cadauno el nodo raíz y el nodo destino de cada arista.

Para optimizar el funcionamiento de los algoritmos de la estructura, sedecidió cambiar la manera en que se guardan las aristas:

/* * edge: { * node: "rootNode",* targets: ["target1","target2","target3"]* }*/ function Edge(node,target,value){

this.node=undefined; this.targets=new Array(); node ? this.node=node : null; if(target&&value)

this.addTarget(target,value) else if(target){

if(typeof target == "object") this.addTargets(target);

else this.addTarget(target);

} } Edge.prototype = {





constructor:Edge}

En la optimización se creó una nueva estructura que representa a cadaarista. El objeto creado guarda el nodo raíz y una lista de nodos a losque este nodo raíz conecta. En este caso la estructura de nodos

representa directamente la lista de adyacencia.

Para guardar aristas valuados, en la primera versión en vez de pares, seguardaban tripletas, siendo el índice 2 del arreglo la posición del valorde la arista, y si éste no existía, quería decir que esa arista no conteníavalor.

Primera versión:

[ [“a”,”b”,12], [“a”,”c”,6], [“b”,”e”,2.55], [“c”,”a], [“c”,”b”,7] ]

Segunda version:

[ {

node: "a", targets: [ ["b",12], ["c",6] ]

}, {

node: "b", targets: [ ["e",2.55] ]

}, {

node: "c", targets: [ "a", ["b",7] ]

}

]

Aplicación

La aplicación llamada “jQuery Directed Graph” se encuentra en línea enla dirección http://directedgraph.co.cc, y se incluyen en ella lasinstrucciones para su uso.

Estructura

Su estructura final consta de tres capas:

• Elementos de la UI:o Lenguaje: HTML5

o Archivo: index.html

• Diseño de la UI:

o Lenguaje: CSS3o Archivos:

_js/_main.css _js/jq-alerts.css

o Adicionales: Imágenes PNG





• Motor de ejecución:

o Lenguaje: JavaScripto Plataformas: jQuery (para interacción entre la UI y el

motor)

o Archivos: _js/Cookies.js _js/_directedGraphCustom-stable.js _js/__main.js

LibreríasLas librerías utilizadas fueron:

• jQuery

o URL: http://jquery.com o Archivo: _js/jq.js

• jQuery User Interface

o URL: http://jqueryui.com o Archivo: _js/jq-ui.js

• jQuery Alert Dialogso URL: http://abeautifulsite.net/blog/2008/12/jquery-alert-

dialogs/ o Archivo: _js/jq-alerts.js

• jQuery Notify Baro URL: http://www.dmitri.me/misc/notify/

o Archivo: _js/jq-notify.js• Curry-1.0.1

o URL: http://goo.gl/lKyxX o Archivo: _js/Curry-1.0.1.js

• Raphaëlo URL: http://raphaeljs.com/

o Archivo: _js/raphael-min.js

• SeedRandom

o URL: http://goo.gl/QhR3N o Archivo: _js/seedrandom.js

• Dracula Graph Libraryo URL: http://www.graphdracula.net/

o Archivos: _js/dracula_algorithms.js

_js/dracula_graffle.js _js/dracula_graph.js





Screenshots

Cargando la aplicación

Presentación





Agregando nodos

Agregando nodos por voz





Menú de opciones (click derecho)

Agregando aristas









Grafo completo con aristas no valuados

Grafo completo con aristas valuados





Eliminando una arista





Eliminando un nodo









Guardando un grafo

Recuperando un grafo









Encontrando la ruta más corta





Matriz de pesos





Matriz de adyacencia

Lista de adyacencia





Profundidad

Debugging con Chrome Developer Tools





Desarrollo





Conclusión

La estructura de datos de grafo dirigido es una de las más útiles en lasciencias computacionales. Gracias a ella y a la ayuda de dispositivos dealta capacidad, la conectividad entre ellos y el Internet, hoy se puedesacar provecho de las estructuras y algoritmos que se han ido refinandocon el paso del tiempo.

Un ejemplo muy claro del poder que tienen los grafos dirigidos y losalgoritmos para trabajar con esa estructura es Google Maps. Esaaplicación tiene la capacidad de encontrar las mejores rutas entre variospuntos mediante miles de nodos y aristas que los conectan, tomando encuenta varios factores, no solo distancia entre los nodos.

La aplicación que aquí se presenta es un medio educativo para conocerde manera interactiva esta estructura de datos y puede ser utilizadocomo herramienta de aprendizaje.





Referencias

Directed Graphs Robert Sedgewick and Kevin Wayne.Algorithms and Data Structures Fall 2007.Department of Computer Science, Princeton University. United States.

http://www.cs.princeton.edu/~rs/AlgsDS07/13DirectedGraphs.pdf

Path Problems in Directed GraphsLloyd Allison. Algorithms and Data Structures Research & Reference MaterialDepartament of Computer Science, Monash University. Australia.

http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Graph/Directed/

Graph Theory Tutorials

Chris K. Caldwell. Math Departament, The University of Tennessee Martin. United States.

http://www.utm.edu/departments/math/graph/

Documents

019365 ADA ProyectoFinal