Escrito por: Siddy Zen

Para usar o MongoDB como banco de dados de back-end em seu projeto em Django, basta adicionar esta única linha em seu arquivo settings.py:

DATABASES = {'default': {      'ENGINE': 'djongo',      'NAME': 'nome-do-banco',   }}

É muito simples!

A seguir, faça login no home admin (localhost:8000/admin/) e comece a adicionar "embedded documents" (documentos incorporados, em português) no MongoDB usando a interface gráfica de administrador:

Em outubro de 2017, o MongoDB concluiu a última fase para se tornar uma companhia de capital aberto, abrindo seu IPO com um preço inicial de $24 e conseguindo $192 milhões no processo. O capital da empresa vem crescendo desde então.

O MongoDB oferece um software de banco de dados de código aberto. Ele é muito útil para start-ups que estão buscando iniciar nos negócios apesar do pouco orçamento inicial disponível. Uma análise no Google Trends das pesquisas pelo termo MongoDB revelam um aumento constante na busca do termo.

O MongoDB tem se tornado um banco de dados cada vez mais popular. Bancos de dados e sistemas de gerenciamento de bancos de dados (SGBDs) existem há mais de cinco décadas. Surgiram no início dos anos 1960 e a opção mais popular foi o banco de dados relacional.

Porém, o MongoDB vem se intitulando como um sistema de banco de dados "não-relacional" e tem feito uma grande propaganda sobre essa abordagem de armazenamento de dados que utiliza. Então, o que exatamente é importante aqui?

MongoDB x SQL

Praticamente todos os sistemas de bancos de dados relacionais utilizam a Linguagem de Consulta Estruturada (SQL), ou uma versão otimizada dela, para se comunicar com o software de gerenciamento de dados. Muitos cursos universitários são dedicados exclusivamente à compreensão e domínio da sintaxe do SQL.

O SQL tornou-se a linguagem padrão para o trabalho com qualquer software de banco de dados, seja ele proprietário ou de código aberto. Então, surgiu o MongoDB e decidiu demonstrar um completo desrespeito a essa linguagem ancestral de poder, criando sua própria sintaxe de consulta.

A língua é a de Mordor, a qual não vou pronunciar aqui., mas isto em língua comum quer dizer, aproximadamente: "Um anel para todos governar, um anel para encontrá-los, um anel para todos trazer e na escuridão aprisioná-los." – Gandalf (de O Senhor dos Anéis)

MongoDB sem esquemas x esquemas do SQL: em um banco de dados em SQL, é impossível adicionar dados enquanto você não definir tabelas e tipos de campos no que é chamado de esquema (em inglês, schema). Em um banco de dados do MongoDB, os dados podem ser adicionados em qualquer lugar, a qualquer momento. Não há necessidade de especificar com antecedência um documento de design ou mesmo uma coleção de documentos.

Documentos do MongoDB  x tabelas do SQL: bancos de dados em SQL fornecem uma coleção de tabelas de dados relacionados. Cada linha é um registro diferente. O design é rígido: não podemos usar a mesma tabela para armazenar informações diferentes ou inserir uma string onde um número é esperado.

O banco de dados do MongoDB armazena apenas documentos de pares campo-valor, semelhantes ao formato JSON. Documentos similares podem ser armazenados em uma coleção de documentos, que é análoga a uma tabela do SQL. Entretanto, você pode armazenar qualquer tipo de dado em um documento — o MongoDB não vai reclamar. As tabelas em SQL implementam um modelo de dados rígido, o que torna mais difícil que erros sejam cometidos. O MongoDB é mais flexível e permissivo, mas a possibilidade de armazenar qualquer tipo de dado em qualquer lugar pode levar a erros de consistência.

Existe uma infinidade de conteúdo na internet argumentando que o MongoDB não é um superconjunto do SQL. Softwares que rodam em SQL não podem ser migrados para MongoDB. Vou me arriscar aqui afirmando que, no contexto do Django, MongoDB é um superconjunto do SQL.

Então, por que essa crença popular de que MongoDB não é um superconjunto do SQL existe, para começo de conversa?

O MongoDB requer desnormalização de dados: o MongoDb não oferece suporte a JOIN. Isso significa que vamos precisar desnormalizar nossos documentos. Documentos desnormalizados implicam maior velocidade nas consultas, mas atualizar informações nos campos do documento, em múltiplos documentos desnormalizados, é significativamente mais lento.

Não existem JOINs: consultas do SQL oferecem uma poderosa cláusula JOIN. Podemos obter dados relacionados em várias tabelas usando uma única instrução SQL. Em bancos de dados não relacionais como o MongoDB, não existem JOINs. Isso que dizer que você precisa executar muitas consultas e depois fazer a união dos dados manualmente em seu código.

Sem transações: em bancos de dados SQL, duas ou mais atualizações podem ser executadas em uma transação – um invólucro que segue o princípio do "tudo ou nada", que garante sucesso ou falha das operações. Se executarmos duas atualizações individualmente, uma pode ter sucesso e a outra pode falhar – deixando nossos dados fora de sincronia. Colocar as mesmas atualizações em uma transação garante que ambas tenham sucesso ou ambas falhem.

Sem restrições de chave estrangeira: a maioria dos bancos de dados de SQL permite que você assegure a integridade dos dados usando restrições de chave estrangeira. Isso garante que todas as linhas tenham uma chave estrangeira válida no código que corresponde a uma entrada na tabela de join, e garante que um registro da tabela de join não seja removido caso uma ou mais linhas ainda possuam referência a ele.

O esquema impõe essas regras ao banco de dados. É impossível que desenvolvedores e usuários adicionem, editem, ou removam registros, o que poderia resultar em dados inválidos ou registros órfãos. As mesmas opções para integridade de dados não estão disponíveis no MongoDB. Você pode armazenar o que quiser, independentemente de quaisquer outros documentos. Idealmente, um único documento serviria como a única fonte de informação sobre um item.

A necessidade de um modelo de banco de dados

Objetos são a abstração de dados que Python usa. Todos os dados em um programa em Python são representados por objetos ou pelas relações que eles têm entre si. Embora objetos sejam uma boa maneira de representar dados, um problema surge quando queremos tornar os dados persistentes. A quantidade de dados pode ser enorme, e precisa ser recuperada da memória persistente de maneira rápida e eficiente. Logo, será necessário usar um software de banco de dados para armazenar esses objetos. Um possível software de banco de dados é um que seja relacional, baseado em SQL.

Um mapeador objeto-relacional (ORM) é uma biblioteca de código que automatiza a transferência de dados armazenados em tabelas de banco de dados relacionais em objetos Python que são usados no código Python. ORMs fornecem uma abstração em alto nível de um banco de dados relacional, o que permite que um desenvolvedor digite código Python em vez de sintaxe SQL para criar, ler, atualizar e excluir dados e esquemas de seu banco de dados. Desenvolvedores podem usar linguagem de programação Python, com a qual estão familiarizados, ao invés de escrever declarações em SQL ou procedimentos armazenados.

Um exemplo de framework ORM para Python é o SQLAlchemy. Esse ORM possui um método de associar classes definidas pelo usuário em Python a tabelas de banco de dados, e instâncias dessas classes (objetos) a linhas em suas respectivas tabelas. Ele também possui um sistema que, de modo transparente, sincroniza todas as alterações de estado entre objetos e linhas que estão a eles relacionadas. Frameworks para a web, como o Flask, usam o SQLAlchemy para armazenar dados de maneira persistente.

Django ORM: o Django vem com seu próprio ORM, ou modelo, para ser mais específico . O modelo é a única fonte definitiva de informações sobre seus dados. Ele contém os campos e comportamentos essenciais dos dados que você está armazenando. Geralmente, cada modelo mapeia para uma única tabela de banco de dados. O modelo também torna possível alternar entre vários bancos de dados relacionais, como Oracle SQL, MySQL ou MSSQL.

Usando o ORM do Django para adicionar documentos ao MongoDB

Digamos que você deseja criar uma plataforma de blogs usando Django e MongoDB como back-end.

No arquivo app/models.py do blog, defina o modelo BlogContent:

from djongo import modelsfrom djongo.models import forms

class BlogContent(models.Model):    comment = models.CharField(max_length=100)    author = models.CharField(max_length=100)    class Meta:        abstract = True

Para acessar o modelo usando o Django Admin, você precisa de uma definição de formulário para o modelo acima. Defina desta maneira:

class BlogContentForm(forms.ModelForm):    class Meta:        model = BlogContent        fields = (            'comment', 'author'        )

Agora, incorpore seu BlogContent dentro de um BlogPost usando o EmbeddedModelField, assim:

class BlogPost(models.Model):    h1 = models.CharField(max_length=100)    content = models.EmbeddedModelField(        model_container=BlogContent,        model_form=BlogContentForm    )   

Pronto! Rode o Django Admin em localhost:8000/admin/ e essa tela vai aparecer:

Depois, assuma que você quer "estender" o campo author para conter mais informações além do nome. Suponhamos que você precise tanto do nome quanto do e-mail. Basta tornar o campo author em um campo "embedded" ao invés de  "char":

class Author(models.Model):    name = models.CharField(max_length=100)    email = models.CharField(max_length=100)    class Meta:        abstract = Trueclass AuthorForm(forms.ModelForm):    class Meta:        model = Author        fields = (            'name', 'email'        )

class BlogContent(models.Model):    comment = models.CharField(max_length=100)    author = models.EmbeddedModelField(        model_container=Author,        model_form=AuthorForm    )    class Meta:        abstract = True

Se um post de blog tiver conteúdo diverso de vários autores, defina um novo modelo:

class MultipleBlogPosts(models.Model):    h1 = models.CharField(max_length=100)    content = models.ArrayModelField(        model_container=BlogContent,        model_form=BlogContentForm    )

Rode o Django Admin com as atualizações. Agora você tem:

Formas de integrar Django ao MongoDB

O ORM do Django consiste em várias camadas de abstração empilhadas uma em cima da outra.

Como desenvolvedor para a web, você pode encarar o desafio de conectar o Django ao MongoDB de duas maneiras. Dê uma olhada na stack do framework Django acima para tentar adivinhar possíveis pontos de conexão.

Use um modelo compatível com o MongoDB

Você pode evitar completamente o uso de modelos Django "com tudo incluso" em seu projeto. Em vez disso, use um framework de terceiros como MongoEngine ou Ming em seus projetos do Django.

Tenha em mente, porém, que escolher um modelo diferente significa perder:

• Mais de 1500 desenvolvedores que contribuem no núcleo do projeto
• Correções a cada hora e resolução de chamados

Você então diminuiria a expertise nos modelos existentes do Django e aumentaria no novo framework de modelos. Talvez a maior desvantagem, no entanto, resida no fato de que seu projeto não vai poder usar nenhum dos pacotes do django.contrib! Esqueça o uso de Admin, Sessions, Users, Auth e outros módulos desse pacote em seu projeto.

Algumas dessas desvantagens são compensadas quando bifurcamos uma nova ramificação no próprio Django. O Django-nonrel, por exemplo, é uma ramificação independente que adiciona ao Django suporte a banco de dados NoSQL. Ele permite que aplicações do Django portáteis sejam escritas. Entretanto, a interface admin não funciona completamente. Além disso, não existe uma comunidade ativa de fato desenvolvendo o projeto.

Django MongoDB Engine é outro back-end com MongoDB para Django, que é uma bifurcação do MongoEngine ODM.

Djongo – transpilador de Django SQL para MongoDB

Outra abordagem é traduzir a sintaxe da consulta SQL gerada pelo ORM do Django em comandos do pymongo. O Djongo é um desses compiladores de consultas SQL para MongoDB. Ele traduz toda string de consulta SQL em um documento de consulta do mongoDB. O resultado é que todos os modelos do Django e modelos relacionados funcionam assim. Por conta disso, temos as seguintes vantagens:

• Reuso dos modelos Django: o Django é um framework estável em contínuo desenvolvimento e aprimoramento. O ORM do Django é um tanto quanto extenso e dotado de vários recursos . Definir um ORM de terceiros para trabalhar com o MongoDB significa reproduzir todo o ORM do Django novamente. O novo ORM precisa se alinhar constantemente com o ORM do Django. Diversas funcionalidades do Django nunca vão ser incluídas em um ORM de terceiros. A ideia com o Djongo é reutilizar recursos existentes do ORM do Django, traduzindo então consultas SQL para a sintaxe do MongoDB.
• A sintaxe do SQL nunca vai mudar: independentemente de futuras adições no Django, com o Djongo, seu projeto não vai ter problemas no futuro!

Fazendo o Django funcionar com o MongoDB

Emulando o esquema no MongoDB: embora não haja suporte a esquemas no MongoDB, isso pode ser emulado. O Djongo fornece o suporte a esquemas necessário no Django, usando e definindo uma combinação de regras de validação do MongoDB e criando uma coleção __schema__. A coleção __schema__ armazena informações para suportar recursos como a chave SQL AUTOINCREMENT.

Suporte a JOIN no MongoDB: na versão 3.2, o MongoDB introduziu o operador $lookup. Ele realiza um left outer join com uma coleção no mesmo banco de dados para filtrar documentos da coleção "unida" (em inglês, joined) para processamento. A etapa de $lookup faz uma correspondência de igualdade entre um campo dos documentos de entrada e um campo dos documentos da coleção "unida".

Para cada documento de entrada, a fase de $lookup adiciona um campo array cujos elementos são os documentos correspondentes da coleção "unida". A fase de $lookup passa, então,  esses documentos remodelados para a próxima etapa.

O Djongo usa o operador de agregação $lookup para realizar todas as consultas de JOIN relacionadas ao Django. É assim que ele faz o módulo admin e os outros módulos contrib funcionarem.

Suporte a transações no MongoDB: apesar do poder das operações atômicas de um único documento, existem casos onde transações multidocumento são necessárias. Ao se executar uma transação composta por operações sequenciais, certos problemas surgem, como nos casos em que, se operação falhar, a operação anterior dentro da transação precisa voltar a seu estado anterior — ou seja,  "tudo ou nada".

Para situações que exigem transações multidocumento, o Djongo implementa o padrão de confirmação de duas fases (documentação em inglês), fornecendo suporte para essas atualizações multidocumento. O uso de confirmação de duas fases garante a consistência dos dados e, em caso de erro , o estado que precedeu a transação pode ser recuperado.

O Djongo surgiu com seu próprio conjunto de preceitos, na verdade. Então, quais são as desvantagens de se optar pelo uso do Djongo em seu projeto Django?

Desempenho: o ORM do Django faz o trabalho pesado de converter manipulações complexas de objeto em strings de consulta no padrão SQL. Se o banco de dados do seu back-end fosse baseado em SQL, você poderia passar essa string de consulta diretamente para ele sem quase nenhum pós-processamento. Usando Djongo, entretanto, a string de consulta precisará ser convertida em um documento de consulta do MongoDB.

Isso vai exigir alguns ciclos de CPU. Porém, se ciclos adicionais de CPU são realmente um problema, você não deveria estar usando Python em primeiro lugar.

Conclusão

Apresentei diversas maneiras de se integrar Django ao MongoDB. Você encontrará uma infinidade de literatura on-line descrevendo a MongoEngine e outras variantes para fazer isso.

Concentrei-me no Djongo, que é um novo conector que torna isso possível de uma maneira diferente, é fácil de usar e simplifica o processo de migração de um back-end com SQL para o MongoDB, adicionando apenas uma linha de código.

Escrito por: Sachin Malhotra

Você sabe qual foi o volume global de tráfego aéreo em 2017? Sabe qual foi o aumento do tráfego aéreo nos últimos anos? Bem, vamos dar uma olhada em alguns dados.

De acordo com a Organização da Aviação Civil Internacional (ICAO), um recorde de 4,1 bilhões de passageiros foram transportados pelo setor de aviação em 2017. Além disso, o número de voos no mundo subiu para 37 milhões em 2017.

São muitos passageiros, e muitos voos ocupando o espaço aéreo diariamente no mundo inteiro. Como existem centenas de milhares desses voos, é provável que existam rotas diferentes que tenham mais de uma parada entre um lugar e outro.

Cada voo tem sua própria origem e destino, bem como um preço padrão de assento de classe econômica associado a ele. Vamos deixar de lado as passagens sofisticadas da classe executiva, o espaço adicional para as pernas e tudo mais!

Nesse cenário, é muito confuso escolher qual voo seria o melhor se quiséssemos ir de um lugar para outro.

Vamos ver o número de opções de voos que o StudentUniverse (oferece descontos para estudantes 😜) me proporciona, partindo de Los Angeles a Nova Délhi.

Estão sendo oferecidos 119 voos no total. Em seguida, aparece um pop-up no site informando que há outros sites que podem estar oferecendo voos semelhantes com tarifas ainda mais baratas. 😩

Uma variedade de sites e incontáveis voos – e estamos falando apenas de uma origem e destino.

Como desenvolvedor, se eu quisesse resolver esse problema, criaria um sistema para atender com eficiência às seguintes consultas:

• Número total de destinos acessíveis (com um número máximo de paradas) a partir da minha localização atual, listando também esses destinos.
  É preciso manter as opções em aberto quando se deseja viajar 😃.
• É um fato conhecido (minha opinião 😉) que rotas com escalas tendem a ser mais baratas que voos diretos.
  Assim, dada uma origem e um destino, podemos querer encontrar rotas com pelo menos 2 ou 3 paradas.
• Mais importante: qual é a rota mais barata, dada uma origem e destino?
• E.... bem, vamos deixar isso pro final 🙈.

Como você pode imaginar, existiriam potencialmente milhares de voos como resultado das duas primeiras consultas. Certamente, porém, podemos reduzir isso fornecendo alguns outros critérios para diminuir o tamanho do resultado. Para o escopo deste artigo, vamos nos concentrar nesses tipos de consultas.

Modelando a rede aérea como um grafo

O título deste artigo deixa bem claro que os grafos estariam envolvidos em algum lugar, não é mesmo?

Modelar esse problema como um problema de travessia de grafo simplifica bastante, tornando-o muito mais fácil de ser tratado. Portanto, como primeira etapa, vamos definir nosso grafo.

Modelamos o tráfego aéreo como um grafo:

• direcionado
• possivelmente cíclico
• ponderado
• de floresta. G (V, E)

Direcionado porque cada voo terá uma origem e destino designados. Isso significa muita coisa.

Cíclico porque há grande possibilidade de encontrar vários voos que partam de um determinado local e terminem no mesmo local.

Ponderado porque cada voo tem um custo associado a ele – no caso, poderia ser o custo da passagem aérea da classe econômica citada no início deste artigo.

Por fim, é um grafo de floresta porque podemos ter múltiplos componentes conectados. Não é necessário que todas as cidades do mundo tenham algum tipo de rede aérea entre elas. Assim, o grafo pode ser desconectado e, portanto, uma floresta.

Os vértices, V, seriam os locais em todo o mundo onde há aeroportos em funcionamento.

As arestas, E (do inglês, edges), representariam todos os voos que constituem o tráfego aéreo. Uma aresta u --> v simplesmente significa que você tem um voo direcionado da localização/nó u até v .

Agora que temos uma ideia de como modelar a rede aérea em um grafo, vamos prosseguir e resolver a primeira consulta básica que um usuário pode ter.

Número total de destinos acessíveis

Quem não gosta de viajar?

Como alguém que gosta de explorar lugares diferentes, seria interessante saber quais destinos são acessíveis a partir de seu aeroporto local. Novamente, haveria critérios adicionais aqui para reduzir os resultados dessa consulta. Para fins didáticos, vamos apenas encontrar todos os locais acessíveis a partir de nosso aeroporto local.

Agora que temos um grafo bem definido, podemos aplicar algoritmos de travessia para o computar.

A partir de um determinado ponto, podemos usar a busca em largura (BFS, do inglês, Breadth-First Search) ou a busca em profundidade (DFS, do inglês, Depth-First Search) para examinar o grafo ou os locais acessíveis a partir da localização inicial que tenham um número máximo de paradas. Como este artigo trata exclusivamente do algoritmo de busca em largura, vamos ver como podemos usar o famoso BFS para realizar essa tarefa.

Vamos inicializar a fila do BFS com o local fornecido como o ponto de partida. Em seguida, executamos o primeiro percurso em largura e continuamos até que a fila esteja vazia ou até que o número máximo de paradas tenha se esgotado.

Observação: se você não estiver familiarizado com a busca em largura ou com a em profundidade, recomendo que leia este artigo (texto em inglês) antes de continuar.

Vamos dar uma olhada no código que inicializa a nossa estrutura de dados do grafo. Também precisamos analisar como o algoritmo do BFS acabaria nos fornecendo todos os destinos acessíveis a partir de uma determinada origem.

from collections import defaultdict
from pprint import pprint 
class FlightNetwork:
	def __init__(self):
		self.neighbors = defaultdict(list)
		self.cost = defaultdict(list)
		
	def add_flight(self, source, destination, price):
		self.neighbors[source].append(destination)
		self.cost[source].append(price)
	
	def show_flights(self):
		print("Destinos:");pprint(dict(self.neighbors))
		print("Custo:");pprint(dict(self.cost))
        
f = FlightNetwork()
f.add_flight('Los Angeles', 'New Delhi', 200)
f.add_flight('Los Angeles', 'Japan', 87)
f.add_flight('Germany', 'New Delhi', 125)
f.add_flight('Italy', 'Los Angeles', 150)
f.add_flight('New Delhi', 'France', 100)
f.add_flight('Los Angeles', 'France', 200)
f.add_flight('Italy', 'New Delhi', 300)
f.add_flight('France', 'Norway', 175)
f.add_flight('Ireland', 'Chicago', 100)
f.add_flight('Chicago', 'Italy', 135)
f.add_flight('Los Angeles', 'Ireland', 100)
f.add_flight('Ireland', 'New Delhi', 200)
f.show_flights()
Destinos:
{	
	'Chicago': ['Italy'],
 	'France': ['Norway'],
	'Germany': ['New Delhi'],
 	'Ireland': ['Chicago', 'New Delhi'],
 	'Italy': ['Los Angeles', 'New Delhi'],
 	'Los Angeles': ['New Delhi', 'Japan', 'France', 'Ireland'],
 	'New Delhi': ['France']
 }
Custo:
{
	'Chicago': [135],
 	'France': [175],
 	'Germany': [125],
 	'Ireland': [100, 200],
 	'Italy': [150, 300],
 	'Los Angeles': [200, 87, 200, 100],
 	'New Delhi': [100]
 }

Agora que temos uma boa ideia de como o grafo deve ser inicializado, vamos dar uma olhada no código do algoritmo do BFS.

Executando o bfs na cidade de Los Angeles, o resultado seriam os seguintes destinos acessíveis:

{'Chicago', 'France', 'Ireland', 'Italy', 'Japan', 'New Delhi', 'Norway'}

Isso foi simples, não?

Veremos como podemos limitar o BFS a um número máximo de paradas mais adiante neste artigo.

Se tivéssemos uma rede aérea enorme, que é o que teríamos em um cenário de produção, então não desejaríamos necessariamente saber todos os destinos possíveis de um determinado ponto de partida.

Esse é um caso de uso quando a rede aérea for muito pequena ou pertencer apenas a poucas regiões dos Estados Unidos.

Porém, para uma rede grande, um caso de uso mais realista seria encontrar todas as rotas de voo que possuem várias paradas. Vamos examinar esse problema mais a fundo e ver como podemos resolvê-lo.

Rotas com múltiplas paradas

É um fato bastante conhecido que, normalmente, para uma determinada origem e destino, uma viagem com múltiplas paradas é mais barata que um voo direto, sem escalas.

Muitas vezes, preferimos o voo direto para evitar as escalas, em especial porque os voos com várias paradas tendem a tomar muito tempo – o que não temos.

No entanto, se você não tiver nenhum compromisso urgente e quiser economizar algum dinheiro (e se sentir confortável com o voo que tem escalas – opção oferecida por diversas companhias aéreas) poderá, na verdade, se beneficiar muito ao fazer essa escolha.

Você pode passar por alguns dos lugares mais bonitos do mundo com seus modernos aeroportos. Isso já pode ser motivação o suficiente.

Em termos do modelo de grafo sobre o qual estávamos falando, dada uma origem e um destino, precisamos criar rotas com 2 ou mais paradas para uma origem e destino fornecidos.

Para um usuário final, pode ser que a resposta abaixo não seja a melhor:

[A, C, D, B], 2 paradas, $X
[A, E, D, C, F, W, G, T, B], 8 paradas, $M
[A, R, E, G, B], 3 paradas, $K
[A, Z, X, C, V, B, N, S, D, F, G, H, B, 11 paradas, $P

Eu sei. Ninguém em sã consciência escolheria um voo com 11 paradas, mas o que estou tentando dizer é que um usuário final espera simetria. Ou seja, ele desejaria ver primeiro todos os voos com 2 paradas, depois todos os voos com 3 e assim por diante até um máximo de, digamos, 5 paradas.

Porém, todas as rotas de voo com o mesmo número de paradas entre elas devem ser exibidas juntas. Esse é um requisito necessário.

Então, vamos ver como podemos resolver isso. Dado um grafo de redes aéreas, um ponto de partida S (do inglês, source) e um destino D, precisamos realizar um percurso em nível e guardar as rotas de voo de S --> D com pelo menos 2 e no máximo 5 paradas entre elas. Isso quer dizer que precisamos realizar um percurso em nível até uma profundidade de 7 partindo do nó inicial S.

Aqui está o código para resolver esse problema:

{'A': ['C', 'B', 'F'],
 'B': ['D'],
 'C': ['B', 'M', 'E', 'F'],
 'D': ['C', 'E', 'F'],
 'E': ['F'],
 'M': ['F']}
Custo:
{'A': [10, 20, 14],
 'B': [20],
 'C': [120, 200, 145, 50],
 'D': [75, 45, 60],
 'E': [60],
 'M': [45]}
parent = f.level_order_traversal('A', 'F', (2,5))
for r in range(2, 6):
    print("\nOs voos com {} paradas no meio são os seguintes:".format(r))
    routes = f.get_route(('F', r), 'A', parent)
    for r in routes:
        print(r)
Os voos com 2 paradas no meio são os seguintes:
A-->C-->M-->F
A-->C-->E-->F
A-->B-->D-->F

Os voos com 3 paradas no meio são os seguintes:
A-->C-->B-->D-->F
A-->B-->D-->C-->F
A-->B-->D-->E-->F

Os voos com 4 paradas no meio são os seguintes:
A-->C-->B-->D-->C-->F
A-->C-->B-->D-->E-->F
A-->B-->D-->C-->E-->F
A-->B-->D-->C-->M-->F
A-->C-->B-->D-->E-->F
A-->B-->D-->C-->E-->F

Os voos com 5 paradas no meio são os seguintes:
A-->C-->B-->D-->C-->M-->F
A-->C-->B-->D-->C-->E-->F
A-->B-->D-->C-->B-->D-->F

Essa pode não ser a melhor maneira de resolver esse problema quando ele for muito grande – uma grande restrição de memória aconteceria por conta dos nós presentes na fila no momento.

Como cada nó, ou localização, pode ter milhares de voos para diferentes destinos do mundo, a fila poderia se tornar enorme se fôssemos armazenar dados reais de voos dessa maneira. Esse exemplo é apenas para demonstrar um dos casos de uso do algoritmo de busca em largura.

Por agora, vamos nos concentrar apenas no percurso e ver o que acontece na prática. O algoritmo de percurso é simples, porém, toda a complexidade espacial do percurso em nível se dá graças a elementos presentes na fila e de seu tamanho.

Existem muitas formas de se implementar esse algoritmo. Além disso, cada uma delas varia em termos de consumo máximo memória em determinado momento pelos elementos presentes na fila.

Queremos saber o consumo máximo de memória da fila em um dado momento durante o percurso em nível. Antes disso, vamos construir uma rede aérea aleatória com preços aleatórios.

from collections import defaultdict
import random
from pprint import pprint

def add_edge(s, d, adj_list):
    adj_list[s].append(d)

nodes = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I']  
adj_list = defaultdict(list)
for i, s in enumerate(nodes[:5]):
    for i in range(10 - i):
        while True:
            d = (nodes[random.randint(0, 8)], "$"+str(random.randint(50, 500)))
            if d[0] != s:
                break
        add_edge(s, d, adj_list)

Agora a implementação do percurso em nível.

import sys
def level_order_naive(source, max_level):
    queue = [(source, 0)]
    max_memory = 0
    levels = []
    while queue:
        max_memory = max(max_memory, sum(list(map(sys.getsizeof, queue))))
        element, level = queue.pop(0)
        levels.append((element, level))
        if level == max_level:
            continue
        if element in adj_list:
            for neighbor in adj_list[element]:
                queue.append((neighbor[0], level + 1))
                
    return max_memory, levels  

Essa, por sinal, é a implementação mais simples e direta do algoritmo de percurso em nível.

Junto a cada nó que adicionamos à fila, armazenamos também as informações de nível e uma tupla de (nó, nível) dentro da fila. Assim, toda a vez que removermos um elemento da fila, teremos as informações do nível em que estava.

As informações de nível, para nosso caso de uso, são o número de paradas desde a origem até esse local específico em nossa rota de voo.

A questão é que podemos fazer otimizações, já que consumo de memória no programa precisa ser levado em consideração. Aqui está uma abordagem um pouco melhorada de como se fazer o percurso em nível.

def level_order_NULL(source, max_level):
    queue = [source, None]
    max_memory = 0
    level = 0
    levels = []
    while queue:
        max_memory = max(max_memory, sum(list(map(sys.getsizeof, queue))))
        element = queue.pop(0)
        if element:
            levels.append((element, level))
        if level == max_level:
            continue
        if not element:
            level += 1
            queue.append(None)
            continue
            
        if element in adj_list:
            for neighbor in adj_list[element]:
                queue.append(neighbor[0])
                
    return max_memory, levels 

A ideia aqui é que não vamos armazenar nenhuma informação extra aos nós que estão sendo adicionados na fila. Usamos um objeto None para marcar o fim do nível. Não sabemos o tamanho de nenhum nível de antemão a não ser o do primeiro nível, que tem apenas o nosso nó source.

Assim, iniciamos a fila com [source, None] e continuamos a remover elementos. Toda vez que encontramos um elemento None, saberemos que o nível terminou e que o seguinte começou. Adicionamos outro None para marcar o final desse novo nível.

Considere o simples grafo abaixo. Vamos ver rapidamente como isso funcionaria na prática.

**************************************************** LEVEL 0 begins
level = 0, queue = [A, None]
level = 0, pop, A, push, B, C, queue = [None, B, C]
pop None ******************************************* LEVEL 1 begins
push None
level = 1, queue = [B, C, None]level = 1, pop, B, push, C, D, F, queue = [C, None, C, D, F]
level = 1, pop, C, push, D, D (lol!), queue = [None, C, D, F, D, D]
pop None ******************************************* LEVEL 2 begins
push None
level = 2, queue = [C, D, F, D, D, None] .... e assim por diante

Espero que a explicação tenha esclarecido o funcionamento do algoritmo. Esse certamente é um método interessante de se fazer o percurso em nível, monitorar níveis e não se preocupar muito com o uso de memória. Sem dúvida, reduz o volume de memória usado pelo código.

Porém, não fique muito entusiasmado pensando que isso foi uma melhoria significativa.

Quero dizer, é significativa, mas você deveria estar se fazendo duas perguntas:

1. De que tamanho foi essa melhoria?
2. Podemos melhorar ainda mais?

Vou responder as duas e começarei pela segunda. A resposta é Sim!

Podemos fazer uma melhoria aqui ao eliminar completamente a necessidade do None dentro da fila. A motivação para essa abordagem vem da própria abordagem anterior.

Se você observar atentamente o algoritmo acima, perceberá que toda vez que retiramos um None, um nível é concluído e outro está pronto para ser processado. O importante é que exista um nível seguinte inteiro dentro da fila no momento em que ocorre a remoção do None. Podemos utilizar essa ideia de considerar o tamanho da fila na lógica do percurso.

Aqui está o pseudocódigo desse algoritmo otimizado:

queue = Queue()
queue.push(S)
level = 0
while queue is not empty {
	size = queue.size()
    // size representa o número de elementos no nível atual
    for i in 1..size {
    	element = queue.pop()
        // Processe o elemento aqui
        // Realize uma série de operações queue.push() aqui
    level += 1

Aqui está o código dele.

def level_order_queue_size(source, max_level):
    queue = [source]
    max_memory = 0
    levels = []
    level = 0
    while queue:
        max_memory = max(max_memory, sum(list(map(sys.getsizeof, queue))))
        size = len(queue)
        for _ in range(size):
            element = queue.pop(0)
            levels.append((element, level))
            if level == max_level:
                continue
            if element in adj_list:
                for neighbor in adj_list[element]:
                    queue.append(neighbor[0])
        level += 1            
                
    return max_memory, levels  

O pseudocódigo é autoexplicativo. Basicamente, eliminamos a necessidade de um elemento None por nível e, ao invés disso, usamos o tamanho da fila para mudar de nível. Isso também leva a uma melhoria em relação ao último método, mas em que proporção?

Dê uma olhada no Jupyter Notebook a seguir para ver a diferença de consumo de memória entre os três métodos.

from collections import defaultdict
import random
from pprint import pprint

def add_edge(s, d, adj_list):
    adj_list[s].append(d)

nodes = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I']  
adj_list = defaultdict(list)
for i, s in enumerate(nodes[:5]):
    for i in range(10 - i):
        while True:
            d = (nodes[random.randint(0, 8)], "$"+str(random.randint(50, 500)))
            if d[0] != s:
                break
        add_edge(s, d, adj_list)
adj_list['A']
[('G', '$418'), ('F', '$75'), ('H', '$141'), ('D', '$203'), ('D', '$101'), ('I', '$51'), ('G', '$187'), ('H', '$137'), ('F', '$425'), ('F', '$69')]
import sys
def level_order_naive(source, max_level):
    queue = [(source, 0)]
    max_memory = 0
    levels = []
    while queue:
        max_memory = max(max_memory, sum(list(map(sys.getsizeof, queue))))
        element, level = queue.pop(0)
        levels.append((element, level))
        if level == max_level:
            continue
        if element in adj_list:
            for neighbor in adj_list[element]:
                queue.append((neighbor[0], level + 1))
                
    return max_memory, levels                
max_memory, levels = level_order_naive('A', 5)
max_memory, levels[50:60],len(levels)
(20224, [('H', 3), ('I', 3), ('D', 3), ('B', 3), ('B', 3), ('A', 3), ('B', 3), ('F', 3), ('I', 3), ('G', 3)], 523)
def level_order_NULL(source, max_level):
    queue = [source, None]
    max_memory = 0
    level = 0
    levels = []
    while queue:
        max_memory = max(max_memory, sum(list(map(sys.getsizeof, queue))))
        element = queue.pop(0)
        if element:
            levels.append((element, level))
        if level == max_level:
            continue
        if not element:
            level += 1
            queue.append(None)
            continue
            
        if element in adj_list:
            for neighbor in adj_list[element]:
                queue.append(neighbor[0])
                
    return max_memory, levels 
max_memory, levels = level_order_NULL('A', 5)
max_memory, levels[50:60], len(levels)
(15816, [('H', 3), ('I', 3), ('D', 3), ('B', 3), ('B', 3), ('A', 3), ('B', 3), ('F', 3), ('I', 3), ('G', 3)], 523)
def level_order_queue_size(source, max_level):
    queue = [source]
    max_memory = 0
    levels = []
    level = 0
    while queue:
        max_memory = max(max_memory, sum(list(map(sys.getsizeof, queue))))
        size = len(queue)
        for _ in range(size):
            element = queue.pop(0)
            levels.append((element, level))
            if level == max_level:
                continue
            if element in adj_list:
                for neighbor in adj_list[element]:
                    queue.append(neighbor[0])
        level += 1            
                
    return max_memory, levels              
max_memory, levels = level_order_queue_size('A', 5)
max_memory, levels[50:60], len(levels)
(15800, [('H', 3), ('I', 3), ('D', 3), ('B', 3), ('B', 3), ('A', 3), ('B', 3), ('F', 3), ('I', 3), ('G', 3)], 523)
sys.getsizeof(('A', 4))
64
sys.getsizeof(None)
16

• Monitoramos o tamanho máximo da fila a qualquer momento quando consideramos a soma dos tamanhos de cada elemento contido na fila.
• De acordo com a documentação do Python, sys.getsizeof retorna o ponteiro do objeto, ou tamanho, da referência em bytes. Assim, economizamos praticamente 4.4Kb de espaço (20224 — 15800 bytes) quando alteramos o algoritmo original do percurso em nível para usar None. Esta é apenas a economia de memória desse exemplo aleatório que usamos, e descemos apenas até o 5° nível do percurso.
• O último método economiza apenas 16 bytes em relação ao método com None. Isso acontece porque apenas eliminamos os 4 objetos None que estavam sendo usados para marcar os 4 níveis (com exceção do primeiro) que foram processados. Cada ponteiro (ponteiro para um objeto) tem um tamanho de 4 bytes no Python rodando em um ambiente de 32 bits.

Agora que temos todas essas rotas interessantes de múltiplos caminhos, partindo de nossa origem a nosso destino, e algoritmos de percurso em nível altamente eficientes para resolver esse problema, podemos analisar um problema mais lucrativo para resolver usando nosso BFS.

Qual é a rota de voo mais barata, partindo da minha origem até um determinado destino? Eis ai algo capaz de despertar o interesse de todos imediatamente. Quero dizer, quem não quer economizar dinheiro?

Caminho mínimo de uma determinada origem a um destino

Não há muita descrição a ser dada para o enunciado do problema. Precisamos apenas encontrar o caminho mínimo e deixar o usuário final satisfeito.

Algoritmicamente, dado um grafo direcionado ponderado, precisamos encontrar o caminho mínimo da origem ao destino. O mais curto ou o mais barato seriam a mesma coisa do ponto de vista do algoritmo.

Não vamos descrever uma possível solução BFS para esse problema porque por ela o problema é intratável. Vejamos o grafo abaixo para entender por que esse é o caso.

Dizemos que o BFS é o algoritmo a ser usado se quisermos encontrar o caminho mínimo em um grafo não direcionado e não ponderado (texto em inglês). O princípio do BFS é que, na primeira vez que um nó é descoberto durante o percurso, a distância entre ele e o ponto de partida se torna o caminho mínimo.

O mesmo não pode ser dito de um grafo ponderado. Considere o grafo acima. Se, por exemplo, tivéssemos que encontrar o caminho mínimo do nó A ao B numa versão não direcionada desse grafo, então o caminho mínimo seria a aresta que liga A a B. Assim, o caminho mínimo teria tamanho 1 e o BFS funcionaria com precisão.

Entretanto, estamos lidando com um grafo ponderado. Logo, a primeira descoberta de um nó durante o percurso não garante o caminho mínimo para esse nó. Por exemplo, no diagrama acima, o nó B seria descoberto logo no início porque é vizinho de A e o custo associado a esse caminho (uma aresta, nesse caso) seria 25 . Porém, esse não é o caminho mínimo. O caminho mínimo é A --> M --> E --> B , que tem tamanho 10.

A busca em largura não tem como saber se a descoberta de um nó em particular vai nos fornecer o caminho mínimo para esse nó. Portanto, a única maneira possível de o BFS (ou DFS) encontrar o caminho mínimo em um grafo ponderado é varrendo o grafo inteiro e ir registrando a distância mínima da origem até o vértice destino.

Essa solução não é viável para uma rede enorme como a nossa rede aérea, que provavelmente teria milhares de nós.

Não entraremos em detalhes sobre como podemos lidar com isso. Está fora do escopo deste artigo.

O que você faria se eu dissesse que o BFS é o algoritmo certo para encontrar o caminho mínimo em um grafo ponderado sob uma pequena condição?

via GIPHY

Caminhos mínimos com restrições

Como o grafo que teríamos para a rede aérea é enorme, sabemos que explorá-lo completamente não é uma possibilidade plausível.

Considere o problema dos caminhos mínimos a partir da perspectiva de um cliente. Quando ele quer reservar um voo, estas são as opções que ele idealmente considera:

• O voo não deve ser muito longo
• Deve caber no orçamento (muito importante)
• Pode ter algumas paradas, mas não mais do que K, onde K pode variar dependendo do cliente.
• Por fim, temos as preferências pessoais que envolvem coisas como acesso a lounges, qualidade da comida, locais de escala e espaço médio para as pernas.

O ponto principal a ser considerado aqui é o terceiro: pode ter algumas paradas, mas não mais do que K, onde K pode variar dependendo do cliente.

O cliente quer a rota de voo mais barata, mas também não quer, digamos, 20 paradas entre seu ponto de partida e seu destino. O cliente pode concordar com um máximo de 3 paradas ou, em casos extremos, talvez até 4, mas não mais do que isso.

Gostaríamos de ter um programa que descobrisse a rota de voo mais barata com no máximo K paradas para uma determinada origem e destino.

Essa questão do LeetCode foi a principal motivação para que eu escrevesse este artigo. Recomendo fortemente que você analise a questão ao menos uma vez e não confie somente no print que está acima.

"Por que o BFS funcionaria aqui?", alguém poderia perguntar. "Esse também é um grafo ponderado e o motivo pelo qual o BFS não funciona nele. Assim como discutimos na seção anterior, o conceito deveria ser o mesmo." NÃO!

O número de níveis alcançados pela busca é limitado pelo valor de K em questão, descrição fornecida no início da seção. Portanto, essencialmente, estaríamos buscando o caminho mínimo, mas não precisaríamos varrer o grafo inteiro. Vamos apenas até o nível K.

Em um cenário real, o valor de K seria menor que 5 para qualquer passageiro mentalmente são 😝.

Vamos analisar o pseudocódigo do algoritmo:

def bfs(source, destination, K):
      min_cost = dictionary representing min cost under K stops for each node reachable from source. 
      set min_cost of source to be 0
      Q = queue()
      Q.push(source)
      stops = 0
      while Q is not empty {
           size = Q.size
           for i in range 1..size {
                 element = Q.pop() 
                 if element == destination then continue
                 for neighbor in adjacency list of element {
                        if stops == K and neighbor != destination        then continue  
                        if min_cost of neighbor improves, update and add back to the queue.
                }
           }    
           stops ++ 
      }

Novamente, trata-se de um percurso em nível, e a abordagem usada aqui é a que faz uso do tamanho da fila em todos os níveis. Vamos dar uma olhada em uma versão comentada do código para resolver esse problema.

from collections import defaultdict
class Solution:
    def findCheapestPrice(self, n, flights, src, dst, K):
        """
        :type n: int
        :type flights: List[List[int]]
        :type src: int
        :type dst: int
        :type K: int
        :rtype: int
        """
        
        # Construa a estrutura de lista de adjacência para ser usada na travessia de ordem de nível. 
        adj_list = defaultdict(list)
        for s, d, cost in flights:
            adj_list[s].append((d, cost)) 
        
        # Inicie um dicionário com os valores de custo mínimo como +inf e 0 para o nó de origem. 
        min_cost = {k: float("inf") for k in range(n)}
        min_cost[src] = 0
        queue = [src]
        stops = 0
        
        # Execute o while enquanto a fila não estiver vazia, ou seja, enquanto não tivermos examinado todos os nós possíveis de acordo com as restrições. 
        while queue:
            size = len(queue)
            for _ in range(size):
                element = queue.pop(0)
                # Quando um elemento é removido da fila, seu custo atual será o custo mínimo até o momento, da origem até aquele elemento. 
                cost = min_cost[element]
                
                # Não é necessário processar os filhos do nó de destino. 
                if element == dst:
                    continue
                
                # Se esse nó tiver vizinhos
                if element in adj_list:
                    for neighbor, direct_flight_cost in adj_list[element]:
                           
                        # Não é necessário atualizar o custo mínimo se já esgotamos nossas K paradas.
                        if stops == K and neighbor != dst:
                            continue
                        
                        # Se o comprimento do caminho mínimo atual para `neighbor` puder melhorar, melhore e faça a nova fila
                        if  direct_flight_cost + cost <  min_cost[neighbor]:
                            min_cost[neighbor] = direct_flight_cost + cost
                            queue.append(neighbor)
                            
            # Incremente o nível                
            stops += 1                
        return -1 if min_cost[dst] == float("inf") else  min_cost[dst]

Essencialmente, mantemos o controle da distância mínima de cada nó em relação a uma determinada origem. A distância mínima para a origem seria 0 e +inf para todos os outros inicialmente.

Sempre que encontrarmos um nó, checamos se o comprimento mínimo do caminho em questão pode ser melhorado ou não. Se puder ser melhorado, isso significa que encontramos um caminho alternativo da origem até esse vértice que tem um custo menor - uma rota de voo mais barata até esse vértice. Colocamos esse vértice na fila novamente para que os locais e nós acessíveis a partir desse vértice também sejam atualizados (podendo ou não ser).

O ponto chave é esse:

# Não é necessário atualizar o custo mínimo se já esgotamos nossas K paradas. 
if stops == K and neighbor != dst:    continue

Assim, retiramos o nó A representado por element no código e neighbor pode tanto ser um destino como outro nó qualquer. Se já tivermos esgotado nossas K paradas com o element sendo a K-ésima parada, então não devemos processar e atualizar (possivelmente) a distância mínima para o neighbor. Isso violaria nossa condição de K  paradas nesse caso.

Como podem ver, resolvi esse problema originalmente usando programação dinâmica e levou cerca de 165ms para executar no site LeetCode. Executei usando BFS e foi megarrápido, levando apenas 45ms para executar. Essa foi motivação o suficiente para escrever este artigo para vocês.

Espero que tenham aproveitado este artigo sobre a busca em largura e algumas de suas aplicações. O foco principal foi mostrar sua aplicação ao problema do caminho mínimo em um grafo ponderado sob algumas condições😃.