GMaps-Gera_Matriz.py

#!/usr/bin/python3

# Este código é parte de um programa que resolve o problema do caixeiro
#viajante para o grafo das sub-regiões do estado de São Paulo utilizando o
#algoritmo 2-Otimal, ou seja, deseja-se, a partir de uma sub-região do estado,
#percorrer todas as outras, voltando à região inicial de modo a percorrer a
#mínima distância possível.

# A matriz de distâncias é gerada com os valores obtidos com o auxílio da
#distanceMatrix (http://code.google.com/apis/maps/documentation/distancematrix)
#da API do Google Maps.

# Exemplo de uso:
#   http://maps.googleapis.com/maps/api/distancematrix/json?origins=Sao+Paulo|Campinas&destinations=Araraquara|Sao+Jose+dos+Campos&mode=driving&language=pt-BR&units=metric&sensor=false
#Este link retorna um arquivo JSON. Para descobrir a distância entre as cidades
#basta olhar a chave "value" (em metros) dentro de "distance".
# Ordem em que as distâncias aparecem:
#Sao Paulo -> Araraquara | Sao Paulo -> Sao Jose dos Campos
#Campinas  -> Araraquara | Campinas  -> Sao Jose dos Campos

# Procurar evitar confusões como a cidade Franca-SP e o país França.
# O Problema do Caixeiro Viajante (PCV) para estradas reais é naturalmente
#assimétrico, pois o grafo é um dígrafo. Porém, por simplicidade e para usar o
#algoritmo 2-otimal, podemos considerar que as distâncias de ida são iguais às
#de volta, ou seja, w(v1v2) = w(v2v1)

# Limites:
# -> Existe um limite de 2048 caracteres no link, mas não é preocupante
# -> A API do Google Maps impõe um limite de 100 elementos por request,
#portanto devemos montar a matriz através de pelo menos 2 requests:
#1o: Matriz1(15x06): [0..14]*[0..5]
#2o: Matriz2(08x08): [7..14]*[6..13]
# A figura quadriculado exemplifica a composição das duas matrizes em uma só

import json
import urllib
import urllib.request
import numpy

with open('cidades.txt', encoding='utf-8') as arquivo:
    cidades = arquivo.read()

cidades = cidades.splitlines()

# 1o request
origem = cidades[0]
for i in range(1, 15):
    origem = origem + '|' + cidades[i]

destino = cidades[0]
for i in range(1, 6):
    destino = destino + '|' + cidades[i]

link1 = ('http://maps.googleapis.com/maps/api/distancematrix/json?origins=' +
        origem + '&destinations=' + destino +
        '&mode=driving&language=pt-BR&units=metric&sensor=false')

# 2o request
origem = cidades[7]
for i in range(8, 15):
    origem = origem + '|' + cidades[i]

destino = cidades[6]
for i in range(7, 14):
    destino = destino + '|' + cidades[i]

link2 = ('http://maps.googleapis.com/maps/api/distancematrix/json?origins=' +
        origem + '&destinations=' + destino +
        '&mode=driving&language=pt-BR&units=metric&sensor=false')

json1 = urllib.request.urlopen(link1).read().decode('utf-8')
json2 = urllib.request.urlopen(link2).read().decode('utf-8')

matriz1 = json.loads(json1)
matriz2 = json.loads(json2)

#Cria a Matriz final M15x15
M = numpy.zeros(shape=(15, 15))

for origem in range(0, 15):
    for destino in range(0, 6):
        if (destino < origem):
            M[origem, destino] = matriz1['rows'][origem]['elements'][destino]['distance']['value']

for origem in range(7, 15):
    for destino in range(6, 14):
        if (destino < origem):
            M[origem, destino] = matriz2['rows'][origem - 7]['elements'][destino-6]['distance']['value']

# A matriz M é diagonal inferior. Transforma M em matriz simétrica
for linha in range(0, 15):
    for coluna in range(0, 15):
        if (coluna > linha):
            M[linha, coluna] = M[coluna, linha]

# Imprime a matriz
for linha in range(0, 15):
    for coluna in range(0, 15):
        print(int(M[linha, coluna]), end=' ' )
    print()