En un intento desesperado para ganar las elecciones nacionales de un desconocido país, uno de los candidatos decide embarcarse en un proyecto multimillonario: la creación de rutas ferroviarias que conecten toda la nación para poder ganar los votos de los ciudadanos más indecisos.
Sus asesores especializados en transporte (y marketing) recomendaron un listado de ciudades estratégicas con múltiples rutas para incluir en la planificación. Se conoce el largo de cada ruta, así como también la cantidad de gente favorecida con la creación de cada una. Sin embargo, como se cuenta con un presupuesto ajustado por encontrarse en los meses finales del año, no se pueden construir todas; sino que se deben construir las suficientes como para poder ganar el voto popular, interconectando todas las ciudades y maximizando la cantidad de gente beneficiada.
Para llevar a cabo este ambicioso proyecto se requiere de la previa renovación del tendido eléctrico de todas las ciudades. Se sabe que el costo de cada tramo es proporcional a la distancia entre las ciudades, y el único requerimiento es que exista una conexión entre todas para poder alimentar todo el circuito con un sólo generador dedicado.
Finalmente, como su contrincante político ya ha realizado un sistema que permite conocer la mejor ruta para trasladarse entre dos puntos de la ciudad capital del país, se requiere un sistema que además nos provea la posibilidad de conocer el recorrido mínimo (sobre las rutas construidas previamente) para ir de una determinada ciudad a otra, y exportarlo en un cómodo mapa.
Dado un listado de ciudades y un listado de rutas que las conectan, implementar un programa que modele la situación descripta usando un grafo y que permita resolver el siguiente problema:
Se proveen dos archivos con información que deberá ser interpretada para realizar el ejercicio.
Se trata de un archivo llamado ciudades.csv (delimitador '\t') que cuenta con los registros de las ciudades, con la siguiente información:
id: identificador unívoco de la ciudad, de tipo entero.nombre: nombre completo de la ciudad.longitud: coordenada de longitud de la ubicación geográfica de la ciudad, de tipo decimal.latitud: coordenada de latitud de la ubicación geográfica de la ciudad, de tipo decimal.provincia: número que indica la provincia en la que se encuentra la ciudad.habitantes: número que indica la cantidad de habitantes de la ciudad.Se trata de un archivo llamado rutas.csv que cuenta con las posibles rutas a incluir para resolver el problema. Tiene la siguiente información:
id: identificador unívoco de la ruta, de tipo entero.id_ciudad_1, id_ciudad_2: identificadores de las ciudades que son conectadas por la ruta, de tipo entero.distancia: un número decimal que indica el largo de la ruta, es decir, la distancia entre las dos ciudades que conecta.Al ser ejecutado, el programa deberá procesar los archivos de entradas de rutas y ciudades, y:
La aplicación funcionará para encontrar una ruta eficiente entre dos ciudades usando los algoritmos que ya se encuentran implementados.
Para realizar esto le debe solicitar al usuario los nombres de las ciudades por las que se desea trasladar.
El programa deberá generar un archivo KML llamado: ruta_ciudad1_ciudad2.kml que contenga el mapa que muestre la ruta entre las ciudades.
Los archivos KML son archivos de texto plano utilizados por aplicaciones como Google Earth o Google Maps para mostrar información geográfica. Estos archivos deben cumplir un estándar con el que se pueden representar puntos, líneas y polígonos, entre otras cosas.
Para visualizar estos archivos generados se puede usar Google Maps o alguna aplicación externa que no requiere haber iniciado sesión con una cuenta de Google.
La primera línea de cada archivo KML debe ser el encabezado del estándar XML:
<?xml version="1.0" encoding="UTF-8"?>
Las siguientes líneas del archivo indica que se trata de un archivo KML y se anuncia su inicio:
<kml xmlns="http://earth.google.com/kml/2.1">
<Document>
A continuación se puede agregar el nombre del archivo y una descripción.
<name>KML de ejemplo</name>
<description>Un ejemplo introductorio.</description>El lenguaje incluye muchos componentes para visualizar en mapas, especificando su estilo y muchos atributos. Para el alcance de este trabajo sólo serán necesarios dos que serán explicados en esta sección. Se pueden incluir muchos de estos componentes en un mismo archivo sin necesidad de ordenarlos ni especificar su cantidad previamente.
Se usan para indicar un lugar de interés en las coordenadas especificadas:
<Placemark>
<name>Facultad de Ingeniería, UBA</name>
<Point>
<coordinates>-58.3679593, -34.6176355</coordinates>
</Point>
</Placemark>Este ejemplo ubica un punto con el nombre “Facultad de Ingeniería, UBA” en la coordenada indicada (especificando primero la longitud y luego la latitud, separadas por comas).
Se usan para indicar un recorrido entre las coordenadas especificadas:
<Placemark>
<LineString>
<coordinates>-58.36795, -34.61763 -58.39644, -34.58850</coordinates>
</LineString>
</Placemark>Este ejemplo dibuja una ruta entre los dos puntos indicados.
Se indica el fin del archivo.
</Document>
</kml>