Neo4j + GDS
Encontrando caminhos mais rápidos e mais baratos — Artigo 18
Sumário: Desenvolvimento de APIs em Go
Próximo Artigo: (Em andamento)
Artigo Anterior: Go + Neo4j — Modelando o Brasil em Grafos
Introdução
No último artigo, aprendemos um pouco sobre Grafos e sobre o banco de dados Neo4j, além de modelarmos de forma simplificada a malha rodoviária brasileira. Nesta continuação, vamos utilizar o plugin GDS (Graph Data Science) para encontrar caminhos em nosso grafo. Mas antes, evoluímos um pouco nossa solução, e precisamos falar sobre isso.
Dentro das melhorias em nossa modelagem, temos: mais cidades, mais formas de locomoção e mais propriedades nas arestas. Nosso grafo agora possui 67 cidades e 294 arestas, entre elas: rodovias, pontes aéreas, trajetórias de barco e trajetórias de trem. O grafo também agora inclui uma ilha (Fernando de Noronha) e algumas cidades que fazem fronteira com o Brasil. Nossas arestas agora possuem os seguintes parâmetros, conforme apresentado no código 1.
Como pode ser visto no código 1, a label das arestas pode ter 4 valores distintos agora: road, water, air e train. Com esses valores, podemos filtrar os caminhos por diferentes modalidades. Por exemplo, encontrar o menor caminho entre duas cidades utilizando apenas transporte de barco.
Para fim de melhorar modelagem, nessa versão, as arestas possuem 6 propriedades:
- Distância em km entre as duas cidades;
- Velocidade média em km/h que se trafega naquela aresta;
- Delay de embarque em horas;
- Razão de preço de locomoção naquela modalidade;
- Duração média para percorrer a aresta;
- Preço para percorrer a aresta.
Você pode notar que temos valores não normalizados, pois, se eu sei a velocidade média de tráfego e a distância, obviamente consigo calcular a duração do percurso. Estamos mantendo esses dados desnormalizados porque isso facilita para o GDS encontrar melhores caminhos com base em diferentes parâmetros. Dessa forma, podemos identificar: os menores caminhos, os caminhos mais baratos e os caminhos mais rápidos. Antes de começarmos a encontrar caminhos no grafo, vamos ver como ficou nosso modelo. Na imagem 1, temos o grafo com todas as alterações.
Na imagem 1, temos as capitais representadas em retângulos azuis, as demais cidades brasileiras em verde, as ilhas em roxo e os países vizinhos em vermelho. As arestas pretas representam rodovias, as arestas azuis indicam trajetórias por rio ou mar, as arestas amarelas correspondem a pontes aéreas e as arestas marrons representam trajetórias de trem. Para melhorar a compreensão, o vídeo 1 mostra o funcionamento da solução criada, e a seção seguinte aborda os subgrafos das regiões do Brasil.
Sub-grafos
Um subgrafo é um particionamento de um grafo maior. Aqui, temos os subgrafos das regiões: Sul, Sudeste, Centro-Oeste, Norte e Nordeste do Brasil.
Sul
Como pode ser visto na imagem 2, nosso grafo agora pode ter mais de uma forma de locomoção entre duas cidades, como é o caso entre Porto Alegre e Florianópolis, onde temos trajetos de rodovia e ponte aérea.
Sudeste
Na imagem 3, temos o subgrafo que possui arestas que partem de cidades da região Sudeste do Brasil. Vale ressaltar que a aresta entre Belo Horizonte e Vitória exibe o número 3. Isso é uma feature da biblioteca frontend para agrupar 3 arestas distintas, que, neste caso, são: rodovia, ponte aérea e trem.
Centro-Oeste
Na imagem 4, temos a região Centro-Oeste, que é a mais conectada do Brasil, segundo nossa modelagem simplificada.
Norte
Na imagem 5, temos a região Norte, onde é possível notar que existem cidades como Tabatinga, Tefé e Coari, que só são acessíveis via Rio Amazonas, saindo de Manaus. Também é possível observar a Guiana Francesa, que faz fronteira com Oiapoque.
Nordeste
Na imagem 6, temos a presença de Fernando de Noronha, que é uma ilha acessível por barco e por ponte aérea.
Modelagem
Para encontrar informações sobre distâncias entre cidades e formas de locomoção, utilizei a API do Google e os sites Decolar e Rome2Rio para aproximar alguns valores.
Na imagem 7, temos um exemplo do DataFrame que foi trabalhado para modelar as arestas entre cada cidade. Utilizei este Jupyter Notebook para realizar alguns cálculos e fiz várias simplificações (não sou cientista de dados).
Questões Sobre a Modelagem
- Assumi valores padrão para a velocidade de locomoção em alguns cenários: pontes aéreas (860 km/h) e rodovias (100 km/h). Certamente, isso está errado.
- Encontrei informações sobre distância e tempo de viagens de barco para algumas arestas. Como são poucas, calculei a velocidade média. Antes, havia assumido um valor padrão aqui também, mas o erro era significativo, pois existem trajetos que são percorridos em velocidades muito distintas.
- Somente encontrei um trecho de trem significativo entre Belo Horizonte e Vitória.
- Defini uma propriedade de delay, que marca o tempo necessário para embarcar e seguir o trajeto. Achei relevante computar isso, pois pontes aéreas geralmente necessitam de mais controle de embarque. Isso pode gerar diferenças entre a menor rota e a rota mais rápida.
- Os preços das rotas de rodovia foram definidos com base em uma média que encontrei no Rome2Rio; certamente, isso não se aplica a todo o Brasil.
- Os preços das rotas de avião estão mais corretos e são baseados em dados da Decolar. A variação de preço entre rotas mais comuns, como Rio de Janeiro/São Paulo, e menos comuns, como Natal/Fernando de Noronha, é significativa. Certamente, isso também se aplica aos trajetos de rodovias.
Graph Data Science (GDS)
Para aplicar algoritmos no banco Neo4j, vamos utilizar o plugin GDS, que pode ser instalado durante a execução do banco de dados via Docker, conforme apresentado nos códigos 2 e 3.
Para instalar o GDS via docker run, podemos adicionar a variável de ambiente NEO4J_PLUGINS='["graph-data-science"]', que irá baixar e instalar o plugin na imagem Docker, conforme apresentado no código 2.
A mesma instalação do plugin pode ser feita via docker-compose.yml, definindo o mesmo plugin com a variável de ambiente NEO4J_PLUGINS, conforme apresentado no código 3.
Com o GDS instalado, temos a possibilidade de rodar vários algoritmos dentro do nosso banco de dados, com diferentes enfoques, como:
- Centrality;
- Community Detection;
- Similarity;
- Path Finding;
- DAG Algorithms;
- Node Embeddings;
- Topological Link Prediction.
No objeto de estudo deste artigo, vamos nos concentrar nos algoritmos de Path Finding. Dentro dessa categoria, temos os seguintes algoritmos que podemos aplicar: Delta-Stepping Single-Source, Dijkstra Source-Target, Dijkstra Single-Source, A*, Yen, Breadth First Search, Depth First Search, Random Walk, Bellman-Ford Single-Source, Minimum Weight Spanning Tree, Minimum Directed Steiner Tree, Minimum Weight K-Spanning Tree, All Pair e Longest Path for DAG.
Dentro desses algoritmos, poderíamos utilizar alguns, mas vamos optar pelo Dijkstra Source-Target, que conseguirá resolver o problema.
Dijsktra Source-Target
Para conseguir executar o algoritmo de Dijkstra dentro do banco utilizando o GDS, precisamos primeiro criar uma projeção GDS, que é uma versão do nosso grafo em memória. Para isso, podemos executar o código 4, que pode ser feito manualmente ou de forma automatizada pela API.
No código 4, criamos a projeção GDS. Note que, na linha 1, não especificamos o tipo de aresta; dessa forma, ele consegue computar caminhos entre todos os tipos de arestas.
Na linha 3, definimos o nome de nossa projeção e, nas linhas 7 e 8, estabelecemos quais serão os parâmetros que poderemos utilizar para otimizar os caminhos. Ou seja, conseguiremos encontrar caminhos mais curtos, mais rápidos e mais baratos. Com a projeção criada, podemos executar o algoritmo de Dijkstra, conforme apresentado no código 5.
Como pode ser visto na linha 5 do código 5, ao executarmos a query, definimos qual é nossa propriedade de peso, que, neste exemplo, é distance, mas poderiam ser quaisquer valores definidos anteriormente na projeção.
Performance
Para nosso pequeno grafo de 67 cidades e 294 arestas, a execução do algoritmo de Dijkstra é praticamente instantânea, com as chamadas à API Go levando em média 20 ms. Vale ressaltar que isso não é um cenário válido para um benchmark.
Encontrado Caminhos
Com o setup do banco de dados feito corretamente e com o GDS funcionando, podemos começar a encontrar caminhos no grafo. Aqui estão alguns exemplos.
Menor Caminho (Tabatinga x Fernando de Noronha)
Na imagem 8, temos o menor caminho entre Tabatinga (a cidade mais a oeste do Amazonas) e Fernando de Noronha. O trajeto inclui trechos de barco pelo Rio Amazonas (Tabatinga, Tefé, Coari, Manaus), trechos de avião (Manaus, Belém, São Luís, Fortaleza), trechos de rodovia (Fortaleza, Mossoró e Natal) e, por último, um trecho que pode ser feito de barco ou avião (Natal e Fernando de Noronha).
Caminho Mais Rapido (Tabatinga x Fernando de Noronha)
Na imagem 9, temos o caminho mais rápido. Vale notar que o trecho de avião muda para definir a parte final de carro a partir de Recife e não de Fortaleza, reduzindo o tempo de 7 horas e 30 minutos de carro para apenas 4 horas. A etapa final (Natal/Fernando e Noronha) escolhida é de avião, pois leva menos tempo do que de barco.
Caminho Mais Barato (Tabatinga x Fernando de Noronha)
Na imagem 10, temos o caminho mais barato. Dessa vez, nenhum trecho de avião está sendo utilizado. O trajeto vai de barco de Tabatinga até Santarém, depois segue de carro até Natal e finaliza de barco até Fernando de Noronha.
Menor Caminho (Belém x Macapá)
Na imagem 11, temos o menor caminho entre Macapá e Belém, que é feito de avião.
Caminho Mais Rapido (Belém x Macapá)
Na imagem 12, temos o caminho mais rápido entre Macapá e Belém, que, neste cenário, é o mesmo que o menor caminho de avião.
Caminho Mais Barato (Belém x Macapá)
Na imagem 13, temos o caminho mais barato entre Macapá e Belém, que, neste cenário, é feito de balsa.
Único Caminho Por Rodovia (Belém x Macapá)
Na imagem 14, temos uma situação curiosa. Filtrando as arestas para encontrar o menor caminho entre Belém e Macapá utilizando apenas rodovias, encontramos um trajeto que passa pela Guiana, Suriname e Guiana Francesa. Isso ocorre porque Macapá é a capital mais isolada do país e não possui uma ponte que a conecte com o resto do Brasil.
Conclusões e Próximas Etapas
Neste artigo, vimos como utilizar o plugin GDS para o banco de dados Neo4j e executar algoritmos dentro dele. Observamos que o plugin possui uma grande quantidade de algoritmos que auxiliam em diversos cenários, possibilitando a realização inclusive de path finding. Aplicamos o algoritmo de Dijkstra para encontrar os melhores caminhos, baseados em diferentes parâmetros, como: menor distância, menor tempo e menor custo.
Neste episódio, também criamos uma API que é capaz de calcular essas rotas. No próximo episódio, vamos consumir essa API para utilizá-la como uma ferramenta de estimativa de custos de entrega.
Referências
https://neo4j.com/docs/graph-data-science/current/introduction/
