TABLA DE CONTENIDOS:
*Descripción del problema
*Diseño del problema
-Decisiones de diseño
-Algoritmos usados
*Análisis del resultados
-Objetivos alcanzados
-Objetivos no alcanzados
-Razones
*Manual de usuario
*Lecciones aprendidas
Descripción del problema:
El siguiente proyecto programado trata de cubrir las necesidades de una pequeña empresa de mensajería, que ostenta algunos problemas, para medir la distancia entre distintos puntos, para realizar los viaje mas corto entre el origen y el destino, de forma eficiente de a cuerdo a lo que establece las necesidades de dicha empresa, ademas de crear un mapeado (grafo) con la información de cada bodega, como, nombre, latitud, longitud, ID, tipo, etc.
Entonces, en base a esto, se creo un programa en el Lenguaje C, que mediante grafos, se pudo enlazar todas las bodegas, ademas de medir la distancia entre cada bodega, de forma que se puede señalar las medidas de menor tamaño para realizar los viajes de mensajería. De esta forma se cumplió con lo requerido ademas de añadir algunas funciones mas para la practicidad del programa.
Diseño del problema:
Se trata de cubrir las necesidades del cliente, para enlazar las bodegas y ademas, determinar el camino mas corto entre dichas bodegas.
Decisiones de diseño:
Para esto se implemento un grafo no dirigido, para que cada bodega al ser conectada se interconecten ambas, y no solo una en una dirección, ademas de hacer uso de una lista de adyacencia para poder establecer el grafo.
La lista de adyacencia que se uso, es una representación del grafo, en forma de listas.
Nuestra lista de adyacencia se puede adaptar a N bodegas, ademas de tener la capacidad de reconocer cuando una bodega es de tipo central, para asi conectarse con todo el resto de bodegas.
Dentro del código nos referimos a la lista vertical como Vectores, y a las listas horizontales como Aristas.
Los vectores guardan la posicion de memoria de cada bodega, mientras que en las Aristas solo se guardar una copia del ID de la bodega, mas no la posición de memoria, esto con el fin de operar libremente.
Nótese que cada lista de adyacencia esta ordenada de menor a mayor, esto para hacer mas eficiente el programa.
Nuestro proyecto, constituye, de 5 archivos esenciales:
– Main.c:
En este archivo podemos encontrar el menú de nuestro programa
-Funciones.c
Aquí se aloja todo el código fuente, las distintas funciones que nuestro programa necesita para realizar los distintos trabajos que el proyecto requiere.
– Funciones.h
Aqui podemos encontrar las librerías, las definiciones, las estructuras, y el nombre de cada funcion, con fines de ordenamiento, y fácil entendimiento de lo que el proyecto estipula.
– Archivo.csv
Archivo externo, con extencion .csv, que se usa para cargar un grafo, son datos del usuario que especifican las características de distintas bodegas.
– Makefile
Este nos permite ejecutar nuestro proyecto desde el terminal.
Ademas, Nuestro proyecto hizo uso de algunas librerías adicionales para realizar operaciones.
Aparte de las librerías ya conocidas como:
contiene las funciones básicas de C.
#include <stdio.h>
Hice uso de algunos comandos aparte de los conocidos, como, atoi, atof, atol para realizar conversiones de string a distintos tipos de datos.
#include
<stdlib.h>
me permitio comparar srings
#include
<string.h>
libreria con operadores matemáticos,
usadas en haversine
#include <math.h>
Algoritmos usados:
Se hizo uso de una lista de adyacencia para representar el grafo, anteriormente mencionado.
Aparte del grafo se hicieron uso de algunos algoritmos para realizar trabajos específicos.
– Haversine:
La fórmula del semiverseno es una importante ecuación para la navegación astronómica, en cuanto al cálculo de la distancia de círculo máximo entre dos puntos de un globo sabiendo su longitud y su latitud.
Se uso haversine dentro del programa para poder calcular la posición del usuario y localizar la bodega mas cercana a su ubicación.
Floyd Warshall:
Es un algoritmo de análisis sobre grafos para encontrar el camino mínimo en grafos dirigidos
este algoritmo se uso para establecer el camino mas corto entre el origen y el destino.
Se hace uso de una matriz que es operada las veces que su vértice lo indica.
Se usa una serie de comparaciones entre variables de la matriz para establecer una tabla con todos los caminos mas cortos del grafo.
Análisis de Resultados:
a continuación se presentara los objetivos alcanzados y los no alcanzados, razones y métodos empleados.
Objetivos Alcanzados:
ConnectWarehouse: Se logro conectar 2 bodegas entre si, con un distancia establecida, ademas de indicar si estas bodegas ya estaban conectadas o no.
DisconnectWarehouse: Se logro desconectar 2 bodegas, y validar la existencia de estas bodegas dentro del grafo.
LoadFile: El programa es capaz de cargar un archivo .csv y crear un nuevo grafo a partir de estos datos.
DeleteWarehouse: El programa puede eliminar una bodega, y eliminar todas las conexiones que esta tenia.
PrinthGraph: Imprime un recorrido en anchura, se implemento la Cola, para poder realizar la impresión.
Haversine: El programa realiza las operaciones matemáticas necesarias para operar haversine, y dar como resultado la bodega mas cercana a tu ubicación
Floyd-Warshall: El programa es capaz de ejecutar cuantas tablas sea necesaria a la hora de encontrar el camino mas corto, ademas de realizar las impresiones que se requieren y de resaltar las lineas que se mantienen.
Objetivos no alcanzados:
El programa no puede hacer un Pause y un clear, para limpiar el terminal.
Razones:
No se encontró una alternativa para System.pause y system.clear propios de windows.
Manual de usuario:
Al iniciar el programa Veremos el menú del usuario:
1- Conectar:
Esta opción nos permite conectar una bodega con otra, indicando un distancia entre ellas
Si los Ids ya se encuentra conectados, se retornara un aviso.
2- Desconectar:
Esta opción desconecta 2 bodegas conectadas, Si las bodegas no han sido conectadas anteriormente el programa lo especificara.
3- Agregar:
Con esta opción podremos conectar una bodega nueva, para ello tendremos que brindar algunos datos de la bodega tales como
– ID
– Nombre
– Latitud
– Longitud
– Tipo (puede ser auxiliar o central)
4- Eliminar:
Nos permite eliminar una bodega mediante ID.
Precaución- Si Usted elimina una bodega, eliminara también todas las conexiones que esta tenia, a su ves eliminaras la coneccion de otras bodegas hacia esta.
5- Imprimir Lista de adyacencia:
Al imprimir la lista de adyacencia se mostrara una lista de este estilo:
Donde la primera fila indicara los ID de los vectores, y al lado derecho de cada vector se ubicaran sus aristas.
Usamos “ // ” para definir a un valor nulo.
6- Imprimir Anchura:
Al imprimir Anchura veremos un tabla con tres indices.
1: GRAFO, es donde se almacenara el resultado del recorrido en anchura de arriba hacia abajo.
2: POP, Es el ultimo valor que sacamos de la cola, para efectos de revisión
3: COLA, El estado de la cola, es donde se encuentran los nodos que tengo que visitar y ver si se pueden agregar nuevos nodos descubiertos.
7- Cargar:
Carga un archivo .csv y lo agrega al grafo.
8- NextWarehouse:
Indicando tu Latitud y tu longitud determina la bodega mas cercana a tu posición.
Ademas de indicarte la distancia minina en la que se encuentra tu paquete y el nombre de la bodega en el que se encuentra.
Imprime también todas las tablas necesarias para llegar a la solución final de las distancias mínimas.
Lecciones aprendidas:
El uso de listas de adyacencias, matrices, y estructuras tipo grafo.
Ademas de reforzar los temas de arreglos, listas, y punteros.
Este proyecto, puso a prueba mis conocimientos en C, y estoy muy satisfecho de haberlo logrado, me hizo investigar muchas cosas, distintos tipos de comandos y librerías que me permitieran resolver los problemas que se me presentaron.
Agrego también que aprendí a usar el makefile, y de organizar mejor mi código, mediante un header, separando mis funciones, de mis estructuras y menú.
Estructura de datos 