Simulando reconhecimento de padrões através de caminhos ótimos em grafos (classificação supervisionada)

O objetivo deste trabalho é usar o conceito de caminhos ótimos, e usar o algoritmo Dijkstra para achar os caminhos minímos. Partindo desse caminhos mínimos pretende-se detectar padrões e comunidades. 

• Materiais utilizados:

Mais uma vez usamos a linguagem Python para fazer os algoritmos e simular a detecção das comidades. No Windows, usamos o Python(x,y), que engloba uma série de bibliotecas e alguns ambientes de desenvolvimento. Spyder é um destes ambientes e foi utilizado para a programação e execução dos algoritmos. Abaixo estão os links para mais informações sobre o ambiente de programação, sobre a biblioteca NetworkX também usada neste trabalho para facilitar a manipulação dos grafos e também a ferramenta Setuptools que permite de forma fácil instalar bibliotecas Python, em especial a NetworkX que não vem inclusa no pacote do Python(x,y). links: 
 - https://code.google.com/p/pythonxy/ .
 - https://networkx.github.io/ .
 - https://pypi.python.org/pypi/setuptools 

• Grafo:

O grafo utilizado neste trabalho é um grafo ponderado de 59 vértices que relaciona a distâncias entre as cidades na Alemanha

• Desenvolvimento:

Nesta seção apresentaremos alguns aspectos teóricos bem como os resultados obtidos na execução do algoritmo.

• Caminhos Mínimos

Para inicio de conversa, precisamos saber o que é um caminho ótimo:

Definição: Caminho ótimo é o caminho que minima o custo de ir de um vértice para outro. 

Toda aresta tem um determinado custo, sendo assim, é possível que passar por um determinado pode ser mais caro do que passar por outro lugar. 

• Dijkstra

O algoritmo Dijkstra é bem parecido com o algoritmo de Prim, usa os conceitos de lambda que controla o custo de cada aresta, e de predecessor que é o vértice anterior ao vértice corrente. A parte fundamental do algoritmo, é a primitiva bastante conhecida em Teoria dos Grafos que é a "relaxar um vértice". Relaxar um vértice quer responder a pergunta, "É uma boa ideia passar pelo vértice v para chegar ao vértice y?". E respondendo essa pergunta, conseguimos saber se aquele caminho é um caminho ótimo ou não.

• Implementação

Na primeira parte, implementamos a função cria, que se encarrega de ler um arquivo de texto com a matriz de adjacência e os pesos, e cria o grafo ponderado corresponde aos dados no arquivo de texto usando a biblioteca networkx. Na linha 11, é criado o grafo G, e posteriormente adicionado ao grafo G todas as arestas. A ultima linha de código chama a função Dijkstra que vai executar o algoritmo. 

Posteriormente, é definida a função Gera_Arvore_Peso. É criado um novo grafo vazio, e no loop da linha 4 é adicionado nesse novo grafo todos vértices com seus predecessores. Após o loop pega-se a posição dos nós, e chama a função  plot_weighted_graph.

Agora, a parte central de toda a implementação, o algoritmo Dijkstra, da linha 3 a linha 5 é definido um loop, onde todos os lambdas são atualizados para infinito, e todos predecessores são atualizados para 0. Na linha 7, o lambda da raiz é atualizado para 0, para que ele seja retirado primeiro da fila de prioridades, e seu predecessor atualizado pra 0. Posteriormente, é definida uma lista Q contendo todos os nós do grafo.

Na linha 15, é definido um laço while onde ele rodará até que a lista tenha só um elemento, ou seja, vai rodar para todos os vértices. Na linha 16, a lista Q (que contém todos os lambdas) é ordenada, e posteriormente é retirado o de menor lambda, Na linha 19, e 20, é retirado o vértice de menor prioridade da lista de prioridades, e é inserido na árvore.


Na linha 22 é definido um laço de repetição, que roda para todos os vizinhos do vértice u (de menor lambda) , e é definido o v como sendo "rótulo/numero" do vértice vizinho que coincide com a linha/coluna deste vértice na matriz de adjacência. Posteriormente, a aresta (u,v) é relaxada, ou seja, é respondida a pergunta: "O custo de chegar a v passando por u é menor que o custo atual do caminho para chegar em v?" Se for, atualiza o lambda, e o predecessor de v.

• Resultados

Foi selecionado os vértices: 0, 29, 58

Percebe-se que o vértice 58 conseguiu definir um grupo bem maior que os outros vértices. O vértice 0 ainda conseguiu um certo número de elementos, e o vértice 29 foi o que menos conseguiu vértices em seu grupo.

Foi selecionado os vértices: 58, 57, 56

Percebe-se que o vértice 58 conseguiu definir um grupo grande e os vértices 56 e 57 conseguiram definir grupos bem menores. 

Refletindo sobre a identificação de padrões dá pra perceber que o vértice 58 conseguiu grupos maiores dos que os outros vértices nos dois experimentos. Concluindo assim que alguns vértices tem a capacidade  de definir o comportamento de outros vértices e formar grupos com comportamentos semelhantes.