Núcleo de um GPS Alana R. Santos, Augusto M. Pinto, Guilherme A. da Silva, Guilherme N. Costa Faculdade de Computação – Universidade Federal de Uberlândia (UFU) Caixa Postal 593 – 38.408-100 – Uberlândia – MG – Brasil {alanarocha,augusto_massini,guilhermealves,guilhermenunes}@comp.ufu.br Resumo. O estudo de técnicas e algoritmos eficientes que modelam e manipulam grafos é de extrema importância para o desenvolvimento de inúmeras aplicações atualmente. Podemos citar neste contexto o uso do grafo para modelar um mapa e construir uma aplicação que faça o controle de funcionalidades básicas de um GPS. Este documento apresenta de forma geral, os algoritmos usados para a implementação de um núcleo de um GPS, bem como a análise de complexidade de cada algoritmo. 1. Introdução A principal base de dados que um GPS manipula é o mapa. Um mapa é basicamente composto por um conjunto de pontos geográficos interligados por meio de um conjunto de ruas e estradas. Neste trabalho utiliza-se o grafo para modelar um mapa qualquer. Grafo. Um grafo consiste em um conjunto de vértices e um conjunto de arestas . Cada aresta é um par ordenado de vértices, ou seja, um conjunto com exatamente dois vértices. Para implementar um mapa em um programa de computador por meio de um grafo deve-se considerar os pontos geográficos como os vértices do grafo e as interligações como as arestas. Note que neste contexto, faz-se necessário utilizar um grafo dirigido ou digrafo, desta forma é possível simular com fidelidade os diferentes sentidos que cada estrada do mapa possui. Neste contexto é primordial definirmos algumas medidas que nos auxiliarão na análise de complexidade dos algoritmos que manipulam o digrafo. Digrafo denso. Um grafo dirigido é considerado denso quando , logo . , Particularidade do digrafo que implementa um mapa. Note que em um digrafo que modela um mapa, um vértice qualquer pode possuir duas arestas e que chegam a um mesmo vértice . Logo concluímos que a quantidade máxima de arestas pode ultrapassar o número , i. e., . 1.1 Metodologia O grafo foi implementado utilizando lista de adjacência, i. e., existe um array de listas com posições, onde para cada posição deste array há uma lista dos vértices adjacentes a . Esta abordagem é considerada eficiente no que se refere a consumo de espaço. Em alguns algoritmos fez-se necessário a utilização de estruturas de dados auxiliares. A seguir listamos tais estruturas e como foram implementadas: (a) estrutura do tipo fila com implementação utilizando a abordagem dinâmica com encadeamento circular (a fila aponta para o último elemento, este por sua vez aponta para o primeiro elemento da fila) e (b) uma estrutura do tipo pilha com implementação utilizando a abordagem dinâmica/encadeada. A seguir é apresentado as estruturas em linguagem C que modelam o grafo/mapa para uso nas operações do núcleo do GPS. int visited[maxV]; // nodos visitados typedef struct road { char name[30]; // nome da estrada float distance; // distância entre as cidades que a estrada faz a // ligação } Road; // dados da estrada typedef struct node { char name[STRING_MAX_SIZE]; // nome da cidade int people; // população struct edge *adj; } City; // dados da cidade typedef struct edge // nodo do grafo { int v; // id da cidade de destino (nodo do grafo) int w; // id da cidade de origem (nodo do grafo) Road data; // metadados da aresta (informações da estrada) struct edge *next; // ponteiro para próximo nodo } Edge; typedef Edge *link; typedef struct graph { int V; // quantidade de nodos int E; // quantidade de arestas City *cities; // lista de adjacência, um vetor de links } *Graph; Figura 5. Definições das estruturas que modelam o digrafo/mapa em linguagem C 2. Complexidade de Tempo 2.1 Quantidade de cidades e estradas ALGORITMO: CONTAGEM DE VÉRTICES E ARESTAS EM UM GRAFO Entrada: : grafo Saída: : quantidade de vértices; : quantidade de arestas Custo 1 1 valor do campo de número vértices de 2 1 valor do campo de número de arestas de Vezes 1 1 3 devolva 1 e 1 Claramente este algoritmo tem complexidade de tempo , pois se somarmos o consumo de tempo de execução de todas as linhas, expresso pela coluna ‘Vezes’ obtemos , que no pior caso é , i. e., tempo constante. 2.2 Cidades isoladas ALGORITMO: DESCOBERTA DE VÉRTICES ISOLADOS EM UM GRAFO Entrada: : grafo, : acumulador Saída: Um vetor com o nome dos vértices isolados Custo 1 acc 0 1 2 aloque espaço para vetor 1 3 para 0 até faça 1 4 aloque espaço para posição do vetor 1 5 aloque espaço para um vetor 1 6 para 0 até faça 1 7 [] 0 1 8 para i ← 0, j ← 0 até faça 1 9 10 11 se nodo possui somente uma aresta de entrada então [] 1 para cada vértice adjacente a i faça [ ] 12 13 14 15 16 17 18 para i ← 0, j ← 0 até se acc 1 1 1 1 1 1 ∑ ∑ 1 faça [ ] = então [ ] nome de acc + 1 +1 Vezes 1 1 1 1 1 1 1 [] devolva 0 0 0 1 Se somarmos o consumo de tempo de execução de todas as linhas, expresso pela coluna ‘Vezes’, obteremos o tempo gasto pelo algoritmo no pior caso, como mostrado abaixo. ∑ Sabemos que ∑ , logo temos Claramente , onde é a quantidade de vértices do grafo. O gráfico abaixo expressa o tempo médio gasto para a execução do algoritmo em grafos de tamanhos variados. Os testes foram realizados em uma máquina de processador dual-core de clock 2.2 GHz e 4 Gb de memória RAM DDR2. 0,012 milissegundos 0,01 0,008 0,006 0,004 0,002 0 5 10 20 40 80 |V| Figura 2. Tempo médio gasto para execução do algoritmo de descoberta de vértices isolados em um grafo 2.3 Caminhamento em largura a partir de uma cidade A execução do algoritmo a seguir exige um array para armazenar os vértices (nodos) que foram ou não visitados. Ele é implementado usando uma abordagem estática e seu tamanho é ALGORITMO: CAMINHAMENTO EM LARGURA EM UM GRAFO Entrada: : grafo; : nodo raiz do caminhamento Saída: O caminhamento realizado 1 2 3 4 5 6 7 8 inicialize uma fila insira o nodo raiz em enquanto não for vazia faça se primeiro elemento de não foi visitado então visite o nodo para cada vértice adjacente a faça se não foi visitado então insira em Custo 1 1 1 1 1 1 1 1 Vezes 1 1 Se somarmos o consumo de tempo de execução de todas as linhas, expresso pela coluna ‘Vezes’, obteremos o tempo gasto pelo algoritmo no pior caso, como mostrado abaixo. Claramente , onde é a quantidade de vértices e a quantidade de arestas do grafo. O gráfico abaixo expressa o tempo médio gasto para a execução do algoritmo em grafos de tamanhos variados. Os testes foram realizados em uma máquina de processador dual-core de clock 2.2 GHz e 4 Gb de memória RAM DDR2. 0,002 0,0018 milisegundos 0,0016 0,0014 0,0012 0,001 0,0008 0,0006 0,0004 0,0002 0 5 10 20 40 80 |V| Figura 3. Tempo médio gasto para execução do algoritmo de caminhamento em largura 2.4 Caminhamento em profundidade a partir de uma cidade A execução do algoritmo a seguir exige um array para armazenar os vértices (nodos) que foram ou não visitados. Ele é implementado usando uma abordagem estática e seu tamanho é ALGORITMO: CAMINHAMENTO EM PROFUNDIDADE EM UM GRAFO Entrada: : grafo; : nodo raiz do caminhamento Saída: O caminhamento realizado Custo 1 visite o nodo raiz 1 2 para cada vértice adjacente a k faça 1 3 se não foi visitado então 1 4 1 execute o algoritmo partindo do nodo Vezes Se somarmos o consumo de tempo de execução de todas as linhas, expresso pela coluna ‘Vezes’, obteremos o tempo gasto pelo algoritmo no pior caso, como mostrado abaixo. Claramente vértices e a quantidade de arestas do grafo. , onde é a quantidade de Note que no pior caso, i. e., em um grafo denso temos que 2.5 Caminho entre as cidades e ALGORITMO: CAMINHO ENTRE DOIS NODOS DE UM GRAFO Entrada: : grafo; vetor de Strings onde será armazenado as estradas do caminho; inteiro auxiliar para índice do vetor vet; um ponteiro para a primeira aresta da origem; : inteiro que armazena a posição da cidade destino no vetor do grafo. Saída: Inteiro, onde 1 significa que foi encontrado um caminho e 0 se não for encontrado. Custo Vezes 1 se = nulo então 1 2 retorna 0 1 1 3 se (destino de A) = B então 1 1 4 [ ] 1 1 [ ] 5 1 1 6 para ate , proxima aresta faça 1 7 se destino de A for visitado então 1 1 8 [ ] 1 1 9 incrementa 1 1 10 visita a cidade de destino de i 1 1 se chama recursivamente a função mudando A para primeira aresta da cidade destino apontada por i então devolva senão decrementa ind 11 12 13 14 15 16 fim para devolva 1 1 1 1 1 1 Para cada aresta de um vértice a função pode ser chamada, recursivamente, no máximo vezes, portanto, no pior caso o algoritmo tem complexidade, . O gráfico abaixo expressa o tempo médio gasto para a execução do algoritmo em grafos de tamanhos variados. Os testes foram realizados em uma máquina de processador dual-core de clock 2.2 GHz e 4 Gb de memória RAM DDR2. 0,12 milisegundos 0,1 0,08 0,06 0,04 0,02 0 5 10 20 40 80 |V| Figura 4. Tempo médio gasto para execução do algoritmo de descoberta de caminho entre dois vértices quaisquer. 2.6 Caminho entre as cidades e que não passe pela cidade Esse algoritmo é similar ao de encontrar um caminho entre duas cidades quaisquer, entretanto adicionando uma atribuição de visita a cidade a qual se deseja não passar. Logo, a complexidade é de . 2.7 Menor caminho entre as cidades e ALGORITMO: CUSTO MÍNIMO ENTRE VÉRTICES DE UM DIGRAFO (ALG. DIJKSTRA) Entrada: : grafo; : nodo raiz do caminho; Saída: : um vetor com o custo mínimo de sair de até qualquer nodo de Custo Vezes 1 aloque espaço para vetor de custos dos vértices 1 1 2 para cada posição até de faça 1 3 custo de 1 4 ID da cidade de origem até 1 5 custo de k 1 1 6 nome da estrada para chegar em 1 1 7 inicialize a fila 1 1 8 insira em 1 1 9 enquanto não estiver vazia faça 1 10 retire primeiro elemento de 1 11 para cada nodo v adjacente a faça 1 ∑ 12 se custo de então 1 ∑ 13 custo de peso da aresta + custo de 1 14 15 16 17 insira em senão se peso da aresta + custo de custo de custo faça peso da aresta + custo de 1 1 ∑ ∑ 18 1 devolva 1 Se somarmos o consumo de tempo de execução de todas as linhas, expresso pela coluna ‘Vezes’, obteremos o tempo gasto pelo algoritmo no pior caso, como mostrado abaixo. ∑ Sabemos que ∑ Mas no pior caso, grafo denso, , logo temos , . Logo temos. Claramente , onde é a quantidade de vértices do grafo. ALGORITMO: COMPOSIÇÃO DO MENOR CAMINHO APÓS O CÁLCULO DE CUSTO MÍNIMO Entrada: : um vetor com o custo mínimo de até todos os outros nodos de : nodo raiz do caminho; : nodo de destino Saída: : string com menor caminho entre e Custo Vezes 1 se custo de então 1 1 2 devolva 1 1 3 inicialize a pilha 1 1 4 1 1 5 6 7 8 9 10 11 12 13 14 label de label da aresta de custo mínimo de entrada de enquanto faça empilhe posição em label de label da aresta de custo mínimo de entrada de empilhe em enquanto não for vazia faça desempilhe S concatene com o label de devolva 1 1 1 1 1 1 1 1 1 1 1 1 1 Se somarmos o consumo de tempo de execução de todas as linhas, expresso pela coluna ‘Vezes’, obteremos o tempo gasto pelo algoritmo no pior caso, como mostrado abaixo. Claramente quantidade de vértices do grafo. , onde é a A complexidade total da funcionalidade de obter-se o caminho mais curto entre duas cidades quaisquer é dado pela agregação da complexidade dos dois algoritmos apresentados acima. Logo a complexidade total de tempo é { } . O gráfico abaixo expressa o tempo médio gasto para a execução do algoritmo em grafos de tamanhos variados. Os testes foram realizados em uma máquina de processador dual-core de clock 2.2 GHz e 4 Gb de memória RAM DDR2. 0,0006 milisegundos 0,0005 0,0004 0,0003 0,0002 0,0001 0 5 10 20 40 80 |V| Figura 5. Tempo médio gasto para execução da funcionalidade de encontrar o menor caminho entre dois vértices quaisquer 3. Complexidade de Espaço 3.1 Quantidade de cidades e estradas A complexidade de espaço do algoritmo é constante, ou seja, é representada por . Isto só é possível porque o número de vértices e arestas no grafo é conhecido. O grafo é implementado usando lista de adjacência e a estrutura que modela o grafo possui dois campos destinados para armazenar a quantidade de vértices e de arestas . Portanto o algoritmo só precisa acessar esses valores e retorná-los. 3.2 Cidades isoladas O espaço utilizado pelo algoritmo é determinado pelo tamanho do vetor de strings e pelo vetor . O primeiro vetor armazena o label dos vértices (nome das cidades) isolados, é estático, logo seu tamanho é para todos os casos, onde é uma constante que define o tamanho máximo de uma string. O vetor armazena a informação se um vértice é ou não isolado, é um vetor estático e seu tamanho é . A complexidade de espaço é portanto . 3.3 Caminhamento em largura a partir de uma cidade A complexidade de espaço do algoritmo é determinada pelo tamanho da fila e pelo array . Para a realização do caminhamento é necessário adicionar os vértices do grafo na fila , logo, no pior caso, teremos com no máximo elementos. Ao visitar os vértices que estão em é necessário atualizar o seu respectivo valor em , como não é possível saber a priori, quais vértices terão seus valores em alterado, faz-se necessário o armazenamento de um array de posições. Portanto a complexidade de espaço pode ser representada por . 3.4 Caminhamento em profundidade a partir de uma cidade A complexidade de espaço do algoritmo é determinado pela quantidade de chamadas recursivas na pilha do sistema e pelo tamanho do array . No pior caso o algoritmo terá que fazer chamadas recursivas, pois o grafo é denso e nas primeiras vezes a condição se da linha 3 será satisfeita e ele fará as referidas chamadas. Ao visitar os vértices é necessário atualizar o seu respectivo valor em , como não é possível saber a priori, quais vértices terão seus valores em alterado, faz-se necessário o armazenamento de um array de posições. Portanto a complexidade de espaço pode ser representada por 3.5 Caminho entre as cidades e Este algoritmo possui complexidade de espaço representado pelo tamanho gasto pelo array de strings que armazena os labels das arestas (nomes das estradas). O array é estático e deve ser capaz de armazenar no máximo , ou seja, a complexidade de espaço é dado por . 3.6 Caminho entre as cidades e que não passe pela cidade Este é similar ao algoritmo de encontrar um caminho entre duas cidades quaisquer, entretanto adicionando uma atribuição de visita a cidade a qual se deseja não passar. Logo sua complexidade de espaço é a mesma do algoritmo sem a restrição, ou seja, . 3.7 Menor caminho entre as cidades e A complexidade de espaço é determinada pelo tamanho das seguintes estruturas usadas no algoritmo: a fila , o vetor de etiquetas (custos de cada vértice) e a pilha . O vetor tem tamanho constante em todos os casos, logo é necessário alocar espaços na memória para armazenar o custo de cada vértice. A fila e a pilha tem tamanhos variáveis no decorrer da execução do programa, ambas são dinamicamente encadeadas, porém, no pior caso, onde o grafo é denso, tanto quanto terão no máximo elementos. Logo a complexidade total de espaço é dado por .