Extrair dados de um ficheiro em formato TSP

O problema do caixeiro viajante é um exemplo clássico para as diferentes meta-heurísticas, de inspirarão biológica ou não, mostrarem o seu desempenho. Existem sítio específicos na Internet com exemplos concretos de conjunto de cidades (veja-se, por exemplo, http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/tsp/). Esses ficheiros estão num formato especial, pelo que é preciso escrever um programa para extrair as coordenadas das diferentes cidades. Um exemplo concreto de ficheiro é wi29.tsp (omitimos algumas entradas):

NAME : wi29
COMMENT : 29 locations in Western Sahara
COMMENT : Derived from National Imagery and Mapping Agency data
TYPE : TSP
DIMENSION : 29
EDGE_WEIGHT_TYPE : EUC_2D
NODE_COORD_SECTION
1 20833.3333 17100.0000
2 20900.0000 17066.6667
3 21300.0000 13016.6667
4 21600.0000 14150.0000
…
28 27433.3333 12400.0000
29 27462.5000 12992.2222
EOF

Como se pode ver as 7 primeiras linhas e a última têm informação irrelevante para o problema, pelo que uma solução possível será:

def le_coordenadas_tsp(ficheiro):
    """ Devolve a matriz das coordenadas a partir de ficheiro em formato tsp."""
    fich_in = open(ficheiro)
    tudo = fich_in.readlines()
    coordenadas = []
    for linha in tudo[7:-1]:
 n,x,y = linha[:-1].split()
 coordenadas.append((float(x),float(y)))
    fich_in.close()
    return coordenadas

A solução acima o que faz é obter de uma só vez a lista das linhas, ignorar as 7 primeiras e a última e construir uma lista com as coordenadas.

Com a lista das coordenadas podemos, por exemplo, construir um dicionário, em que as chaves são um identificador único da cidade (um inteiro entre 0 e o número de cidades menos um), e os valores um duplo com as coordenadas.

def dicio_cidades(coordenadas):
    """ Cria um dicionário com as cidades e suas coordenadas."""
    dicio = {}
    for i, (x,y) in enumerate(coordenadas):
 dicio[i] = (x,y)
    return dicio

Esta solução tem o inconveniente de ser um pouco rígida, em particular se o cabeçalho for diferente do habitual. Podemos no entanto criar uma solução mais conveniente de modo bastante simples:

def get_coordinates_tsp(filename):
    """ 
    General parser for tsp files.
    Obtain the cities' coordinates from a file in tsp format.
    """ 
    with open(filename) as f_in:
        coordinates = []
        line = f_in.readline()
        while not line.startswith('NODE_COORD_SECTION'):
            line = f_in.readline()
        line = f_in.readline()
        while not line.startswith('EOF'):
            n,x,y = line[:-1].split()
            coordinates.append((float(x),float(y)))
            line = f_in.readline()
        f_in.close()
    return coordinates

Este programa aplica-se a todos os ficheiros semelhantes ao anterior, mas identifica a zona com a informação relevante não pelo número de linha do ficheiro, mas antes por palavras chaves (no caso NODE_COORD_SECTION e EOF).