Universidad Sim´ on Bol´ıvar Departamento de Computaci´ on y Tecnolog´ıa de la Informaci´on CI-2693. Laboratorio de Algoritmos y Estructuras III Trimestre Abril-Julio 2015

Proyecto 2: recorridos sobre grafos y componentes conexas 1.

Introducci´ on

Se quiere que resuelva tres problemas en los que tiene que aplicar algoritmos de recorridos sobre grafos y algoritmos para determinar componentes conexas.

2.

Problema 1: Camino factible

Se desea contar con su ayuda para desarrollar un sistema que permita a un turista encontrar un camino desde una ciudad de partida hasta una ciudad destino bajo ciertas consideraciones. El mapa de las ciudades corresponder´ a a un grafo donde los v´ertices representan ciudades y los lados representan un viaje en un medio de transporte desde una ciudad a otra. El peso de los v´ertices indica el costo de visitar una ciudad, mientras que el peso de los lados es igual al costo del medio de transporte que lleva de una ciudad a otra. El costo de llegar a la ciudad destino debe ser menor al presupuesto del turista. El costo de visitar la ciudad destino incluye el costo del transporte hasta la ciudad m´as el costo de estad´ıa de las ciudades que se visitan hasta la ciudad destino, incluyendo el costo de visitar la ciudad destino. Tambi´en hay un valor m´ aximo que el turista esta dispuesto a pagar por el transporte en un viaje desde una ciudad a otra. Cuando se viaja de una ciudad a otra, el sistema primero verifica que el costo del viaje es menor que lo que el turista est´ a dispuesto a pagar. Si el valor es m´as bajo entonces acepta el viaje y descuenta el costo del mismo de su presupuesto. El sistema no puede recomendar una ruta de viaje que supere el presupuesto del turista. Para resolver este problema debe usar la t´ecnica de b´ usqueda en profundidad o la de b´ usqueda en amplitud.

2.1.

Entrada de los datos del Problema 1

Debe realizar un programa llamado RecorridoTurista.java que se debe poder ejecutar desde la consola con el siguiente comando: >java RecorridoTurista donde origen es el identificador de la ciudad desde donde comenzar´a el viaje, destino es el identificador de la ciudad destino, presupuesto es el presupuesto del turista, maxPorViaje es la cantidad m´axima est´ a dispuesto dispuesto a el turista pagar por el transporte entre ciudades y archivo es el nombre de un archivo que contendr´ a los datos de un grafo, con el formato del Proyecto 1.

2.2.

Salida de los datos del Problema 1

La primera l´ınea de la salida debe ser una secuencia de ciudades y medios de transporte, separadas por comas, que corresponden a la ruta que debe seguir el turista desde la ciudad origen hasta la ciudad de destino. La segunda l´ınea debe ser el presupuesto restante del turista. 1

2.3.

Ejemplo del Problema 1

Considere un grafo de entrada escrito en el formato de archivo del proyecto 1, almacenado en un archivo llamado “rutas.txt”, con el siguiente contenido: 9 13 SanRafael 9 SanFrancisco 10 PaloAlto 10 SanJose 20 SantaCruz 6 Fremont 12 Oakland 30 Berkeley 11 Sunnyvale 90 Tren1 SanRafael SanFrancisco 2 Bus1 SanFrancisco PaloAlto 3 Bus2 PaloAlto SanJose 5 Tren2 PaloAlto SanJose 8 Avion1 SanJose PaloAlto 7 Cola SanFrancisco Berkeley 1 Bus3 Berkeley SanRafael 5 Bus4 Berkeley Oakland 3 Bus5 Berkeley Sunnyvale 4 Tren3 Sunnyvale SantaCruz 3 Bus6 Oakland Fremont 1 Avion2 Fremont SantaCruz 9 Avion3 SanJose SantaCruz 10 Si se ejecuta el comando: java RecorridoTurista SanFrancisco SantaCruz 100 10 ruta.txt Un soluci´ on posible que se puede mostrar por la salida est´andar es: SanFrancisco, Cola, Berkeley, Bus4, Oakland, Bus6, Fremont, Avion2, SantaCruz 17

3.

Problema 2: Listar caminos

Dado un grafo dirigido, conexo y sin circuitos, debe encontrar el n´ umero de caminos desde un v´ertice inicial hasta cada uno de los v´ertices que componen un grafo, exceptuando al v´ertice inicial. Para resolver este problema debe usar la t´ecnica de b´ usqueda en profundidad o la de b´ usqueda en amplitud.

3.1.

Entrada de los datos del Problema 2

Debe realizar un programa llamado ListaCamino.java que se debe poder ejecutar desde la consola con el siguiente comando:

2

>java ListaCamino donde inicio es el identificador del v´ertice inicial, y archivo es el nombre de un archivo que contendr´ a los datos de un grafo, con el formato del Proyecto 1.

3.2.

Salida de los datos del Problema 2

Se debe mostrar por cada v´ertice del grafo una l´ınea en donde se imprima el siguiente par: identificador del v´ertice y el n´ umero de caminos.

3.3.

Ejemplo del Problema 2

Suponga como entrada el grafo de la figura 1. En la tabla 1 se los caminos posibles desde el v´ertice a hasta cada uno de los v´ertices del grafo de la figura 1.

Figura 1: Grafo 1 V´ertice b c d e f g h

caminos desde el v´ertice a hasta cada v´ertice < a, b > < a, c, b > < a, c > < a, c, d > < a, d > < a, e, d > < a, e > < a, b, f > < a, c, b, f > < a, c, f > < a, c, g > < a, c, d, g > < a, d, g > < a, e, d, g > < a, e, g > < a, b, f, h > < a, c, b, f, h > < a, c, f, h > < a, c, d, g, h > < a, d, g, h > < a, e, d, g, h > < a, c, g, h > < a, e, g, h > Cuadro 1: Caminos desde a hasta todos los v´ertices del grafo de la figura 1.

Suponiendo que el archivo que contiene al grafo de la figura 1, se llama g.txt si ejecuta: >java ListaCamino a g.txt se obtiene como salida b 2 c 1 d 3 3

e f g h

1 3 5 8

4.

Problema 3: Camino entre componentes conexas

Dado un grafo simple y no orientado se quiere determinar sus puntos de articulaci´on y dado un v´ertice inicial y un v´ertice final, se quiere saber si son alcanzables suponiendo que no es posible formar un camino que contenga un punto de articulaci´ on entre los v´ertices inicial y final. Se tiene que el v´ertice inicial y/o final pueden ser puntos de articulaci´ on. Suponiendo que el grafo de entrada corresponde a intersecciones de calles, el problema puede interpretarse de la siguiente manera. Queremos saber si dadas dos personas paradas en dos intersecciones, una puede alcanzar a la otra suponiendo que las intersecciones que son puntos de articulaci´ on est´ an bloqueadas. Si las personas parten desde una intersecci´on que es un punto de articulaci´ on, entonces suponemos que la misma no est´a bloqueada porque hay una persona all´ı.

4.1.

Entrada de los datos del Problema 3

Debe realizar un programa llamado Articulacion.java que se debe poder ejecutar desde la consola con el siguiente comando: >java Articulacion donde vertice1 vertice2 son los identificador de los v´ertices a estudiar, y archivo es el nombre de un archivo que contendr´ a los datos de un grafo, con el formato del Proyecto 1.

4.2.

Salida de los datos del Problema 3

Debe mostrar por la salida est´ andar dos l´ıneas. La primera l´ınea corresponde a los identificadores de los v´ertices que son los puntos de articulaci´on del grafo de entrada. La segunda l´ınea debe indicar si hay o no un camino entre los dos v´ertices imprimiendo las palabras “si” y “no”.

4.3.

Ejemplo del Problema 3

Considere que el grafo de entrada es el de la figura 2 el cual estar´ıa contenido en un archivo llamado g2.txt. Si se ejecuta el comando:

Figura 2: Grafo de ejemplo 2

4

>java Articulacion g h g2.txt se obtiene el siguiente resultado por la salida est´andar: a g f e h l si En otro ejemplo si se ejecuta: >java Articulacion m f g2.txt se debe obtener como salida: a g f e h l no

5.

Detalles de la implementaci´ on

Las t´ecnicas b´ usqueda en profundidad (Depth First Search) y b´ usqueda en amplitud (Breadth First Search), deben ser implementadas como algoritmos particulares del modelo general de etiquetamiento [1]. Sus implementaciones deben ser razonablemente eficientes. Todo el c´odigo debe estar debidamente documentado. Para cada m´etodo se debe indicar su descripci´on, la descripci´on de los par´ametros de entrada y salida, y las precondiciones y postcondiciones aplicando el est´andar para la documentaci´on de c´ odigo en JAVA. Puede usar las librer´ıas de JAVA que considere u ´tiles. Su c´odigo debe hacer uso de la gu´ıa de estilo publicada en el Aula Virtual. En la evaluaci´on del proyecto se tomar´a en cuenta aspectos como la documentaci´ on, el estilo de programaci´ on, la modularidad del c´odigo, la eficiencia en tiempo de ejecuci´ on y memoria, el buen uso de las librer´ıas y la robustez. Si todos los archivos fuentes del proyecto no compilan correctamente, el proyecto ser´ a calificado con cero.

6.

Condiciones de la entrega

La entrega del proyecto es hasta el d´ıa mi´ercoles de la semana 8 a las 1:30 pm y consiste de los siguientes elementos: Un sobre sellado y identificado con su nombre, carn´e y profesor de laboratorio, que debe contener dos documentos: • Un reporte de no m´ as de cuatro p´aginas en donde se explique y se justifique para cada problema, el dise˜ no de su soluci´ on y los detalles de implementaci´on m´as relevantes de los algoritmos y estructuras de datos utilizadas. • La “Declaraci´ on de Autenticidad para Entregas” firmada por los integrantes del equipo. Un archivo comprimido del tipo TGZ con el c´odigo fuente de su proyecto, que debe ser entrgado en la p´ agina del curso en el Aula Virtual. El nombre del archivo deber ser Proy2ci2693AbrJun15X-Y.tgz donde X y X son los n´ umeros de carn´e de los autores del proyecto. El no cumplimento de todos los requerimientos podr´ıa resultar en el rechazo de su entrega.

5

Referencias [1] Oscar Meza y Maruja Ortega, Grafos y Algoritmos. Equinoccio, Caracas. 2da edici´on. 2006.

Guillermo Palma / [email protected] / Mayo 2015

6