Taller 8: Metro de Nueva York

Objetivos

  • Aprender a construir un grafo en dos de sus posibles representaciones.
  • Familiarizarse con el concepto de grafo.
  • Aprender a navegar un grafo según su representación.

Para este taller, construirá dos grafos con las representaciones de matriz y de listas de adyacencias y aprenderá a navegar la estructura de datos. Los grafos deberán construirse con la información del metro de Nueva York. Descargue de Bitbucket el taller 8, donde encontrará un archivo de texto con todas las rutas, titulado "routes.txt", otro archivo de texto, titulado "stations.txt" donde está la información de todas las estaciones, y una carpeta titulada "route_info". En esta carpeta encontrará la sucesión de estaciones que cada ruta visita en archivos de texto separados, bajo el nombre "id ruta.txt". Para la construcción, recuerde que si la ruta va de la estación 101 a la estación 102, ésto significa que hay un arco entre la estación 101 y la estación 102. Tenga en cuenta que ésto significa que una ruta no equivale a un arco.

  1. Explore la interfaz. Conozca que hace cada una de las opciones.
  2. En la clase metro, encontrará los métodos que tiene que implementar.
  3. Comience implementando los dos métodos que crean el grafo con las dos representaciones. Cree las clases que considere necesarias. Estos métodos deberían borrar cualqueir grafo antiguo y rehacerlo, no hacer múltiples grafos.
  4. Implemente los métodos restantes. Sea conciente que la implementación puede cambiar dependiendo de qué representación de grafo haya utilizado. El método tiene espacio para que cree las dos implementaciones.
  5. Utilice las diferentes opciones del menú y vea los diferentes resultados temporales.

Ayudas:

  • Los id's de las estaciones del metro no son id's numéricos. Como podrá ver en el esqueleto, existe un diccionario llamado estacionesPorId. Utilícelo para, al cargar las estaciones, agregar cada estación con el id como su llave. De esta manera, podrá recuperarlo fácilmente después.
  • Notará que la clase estación tiene un atributo posicion. Este atributo describe la posición de la estación en su arreglo de estaciones. Utilícelo para manejar los índices de la matriz y de las listas de adyacencias y facilitará su trabajo.

Entrega para bonificación

Fecha límite de entrega: Ver

  1. Siga las instrucciones de estructura de talleres presentes en Envío talleres
  2. Realice pruebas unitarias para la aplicación del metro, que como mínimo, validen los siguientes casos:
    • Búsqueda de nombres para representación de listas de adyacencia.
    • Búsqueda de nombres para representación de matriz de adyacencia.
    • Verificación de conección para representación de listas de adyacencia.
    • Verificación de conección para representación de matriz de adyacencia.
  3. Añada a la aplicación otro método que usted quiera. En lo posible, escoja un método que tenga una implementación diferente para las dos representaciones.
  4. En el archivo README.txt describa claramente los pasos para poder ejecutar su aplicación y pruebas.
  5. Cargue el taller a su repositorio en Bitbucket.

=======

Reto

En la carpeta de data encontrará archivos de excel con la información completa del metro de nueva york. Cambie su aplicación de manera que tenga en cuenta las horas de llegada de cada ruta a la estación y pueda responder si una ruta dada estará a una hora dada en alguna estación dada.