EDA-PW2

Autors:

Diogo Pinto & Ricardo Cruz

Course: EDA2

Phase 2 - Objectives

Completed

1

Definição de uma estrutura de dados dinâmica para representação da localização de um conjunto de clientes e meios de mobilidade elétrica, recorrendo a um grafo.

Our approach:

Nodes	Latitude	Longitude
A	41.536719	-8.627301
B	41.537748	-8.622770
C	41.537628	-8.621906
D	41.531540	-8.618960
E	41.452470	-8.562170
F	41.494751	-8.644610

Non-oriented graph with weights (distance)

2.1

Armazenamento/leitura dos dados em ficheiro de texto (valores de simulação) e binários (preservar dados).

Reading from a text file:

We use fgets(), you can check on Pickups.c the region READ.

Saving to a binary file:

void writeNodeToFile(Node* nodes_head) {
    FILE* file = fopen("nodes.bin", "wb");
    Node* current = nodes_head;
    while (current != NULL) {
        fwrite(current, sizeof(Node), 1, file);
        current = current->next;
    }
    fclose(file);
}

This way the graph is saved with all nodes and edges.

2.2

Dado a localização de um cliente, listar os meios de mobilidade elétrica de um determinado tipo existentes num determinado raio.

Given the graph and the data we have, wich is latitude and longitude, we decided to use the Haversine Formula. This way we calculate the distance of two different points, the client location versus the pickup points locations.

Here's the formula:

With math.h we are able to use the Haversine Formula.

flowchart TD
  A[Graph] -->B(Select node with latitude and longitude)
  B --> C{Haversine and if distance is <= 5km}
  C --> D[Node ID]
  C -->E[Location]
  C --> F[Distance]

Loading

In the middle of the process, we consult (listTransportsByLocation at Pickups.c) the transports double linked list and with the location and status equal to available (4) we can list the nearest pick up points with available transports.

Dijkstra

3

Using the Dijkstra its possible to find the shortest path between nodes.

• List all the transports and their location ID with battery under 50%
• Count the number of nodes in the graph
• Find the nodes with the specified IDs
• Set the distance of the starting node to 0
• Find the unvisited node with the smallest current distance
• If there are no more unvisited nodes, exit the loop
• Check if the current node is one of the required nodes and all required nodes have been visited
• Update the distances of the neighboring nodes
• Check if all required nodes have been visited
• If all required nodes have been visited, print the shortest path