K Shortest Loopless Paths

De Wiki-II

O K Shortest Loopless Paths (KSP) é um algoritmo proposto por Yen [1] capaz de encontrar os K caminhos mais curtos entre dois nodos de um dado grafo.

O KSP foi escrito em Python (versão 2.7.2+) e é disponibilizado no GitHub através do seguinte endereço:

https://github.com/maslab-ufrgs/ksp

A única dependência do script é o pacote py-expression-eval, utilizado na interpretação dos arquivos de grafo.

Tabela de conteúdo 1 Funcionamento 1.1 Exemplo 1 1.2 Exemplo 2 2 Instruções para definição do arquivo de grafo 3 Instruções para chamar o KSP a partir de outros programas 4 Links externos 5 Referências 6 Créditos

Funcionamento

Para executar o algoritmo KSP, o seguinte comando deve ser executado através do terminal:

python KSP.py [-h] -f FILE -k K [-l OD_LIST]

Onde:

• -f FILE: é o arquivo de grafo
• -k K: quantidade de caminhos mais curtos desejados
• -l OD_LIST: é uma lista de pares OD, separados por ";" (ponto-e-vírgula), e com os nodos separados por "|" (pipe)

Exemplo 1

Obter os 4 caminhos mais curtos para todos os pares OD da rede OW (assumindo que o arquivo da rede está no mesmo diretório do script KSP.py). No terminal, a partir do diretório do KSP, ao digitar:

python KSP.py -f OW.net -k 4

obtém-se:

ksptable = [
	[ # A|L flow
		['A-C', 'C-G', 'G-J', 'J-I', 'I-L'], # cost 28.0
		['A-C', 'C-G', 'G-J', 'J-L'], # cost 29.0
		['A-C', 'C-F', 'F-I', 'I-L'], # cost 31.0
		['A-C', 'C-D', 'D-G', 'G-J', 'J-I', 'I-L'] # cost 33.0
	],
	[ # A|M flow
		['A-C', 'C-D', 'D-H', 'H-K', 'K-M'], # cost 26.0
		['A-C', 'C-G', 'G-J', 'J-K', 'K-M'], # cost 28.0
		['A-C', 'C-G', 'G-H', 'H-K', 'K-M'], # cost 28.0
		['A-D', 'D-H', 'H-K', 'K-M'] # cost 29.0
	],
	[ # B|L flow
		['B-D', 'D-G', 'G-J', 'J-I', 'I-L'], # cost 32.0
		['B-D', 'D-G', 'G-J', 'J-L'], # cost 33.0
		['B-A', 'A-C', 'C-G', 'G-J', 'J-I', 'I-L'], # cost 35.0
		['B-A', 'A-C', 'C-G', 'G-J', 'J-L'] # cost 36.0
	],
	[ # B|M flow
		['B-E', 'E-H', 'H-K', 'K-M'], # cost 23.0
		['B-D', 'D-H', 'H-K', 'K-M'], # cost 25.0
		['B-D', 'D-E', 'E-H', 'H-K', 'K-M'], # cost 30.0
		['B-E', 'E-D', 'D-H', 'H-K', 'K-M'] # cost 32.0
	]
]

Exemplo 2

Obter os 4 caminhos mais curtos apenas para o par AL da rede OW (assumindo que o arquivo da rede está no mesmo diretório do script KSP.py). No terminal, a partir do diretório do KSP, ao digitar:

python KSP.py -f OW.net -l 'A|L' -k 4

obtém-se:

ksptable = [
	[ # A|L flow
		['A-C', 'C-G', 'G-J', 'J-I', 'I-L'], # cost 28.0
		['A-C', 'C-G', 'G-J', 'J-L'], # cost 29.0
		['A-C', 'C-F', 'F-I', 'I-L'], # cost 31.0
		['A-C', 'C-D', 'D-G', 'G-J', 'J-I', 'I-L'] # cost 33.0
	]
]

Instruções para definição do arquivo de grafo

Consulte a especificação de arquivos de rede.

Instruções para chamar o KSP a partir de outros programas

Para chamar o KSP a partir de outros programas escritos em Python, basta importar o KSP e chamá-lo da seguinte forma:

import KSP

routes = KSP.getKRoutesNetFile(graph_file, origin, destination, K)

Onde:

• graph_file é o caminho do arquivo de rede (string);
• origin é o nodo de origem (string);
• destination é o nodo de destino (string);
• K é a quantidade de caminhos mais curtos desejados (int).

A função acima lê o arquivo de rede e gera as k rotas para o par OD fornecido. Para calcular para mais pares OD, basta chamar a função novamente. No entanto, note que construir a rede a partir do arquivo para cada par OD é ineficiente. Logo, pode-se construir a rede separadamente e então chamar uma variante da função acima que recebe as listas já processadas de nós, arestas e pares OD:

import KSP

V, E, OD = KSP.generateGraph(graph_file)

for od in OD:
    origin, destination = od.split('|')
    routes = KSP.getKRoutes(V, E, origin, destination, K)

O resultado do algoritmo (em ambos os casos) é uma lista dupla, onde cada posição corresponde a uma tupla <caminho, custo>. Considerando os exemplos anteriores (com a rede OW), a saída para o par AL com K=4 seria a seguinte:

[  [['A-C', 'C-G', 'G-J', 'J-I', 'I-L'], 28.0], 
   [['A-C', 'C-G', 'G-J', 'J-L'], 29.0], 
   [['A-C', 'C-F', 'F-I', 'I-L'], 31.0], 
   [['A-C', 'C-D', 'D-G', 'G-J', 'J-I', 'I-L'], 33.0]   ]

Um exemplo detalhado do KSP para esta finalidade está disponível no arquivo de exemplo ksp_calling_example.py, contido no mesmo diretório do algoritmo.

Links externos

Explicação simplificada do algoritmo KSP na Wikipedia (em inglês)

Referências

[1] Yen, J.Y.: Finding the k shortest loopless paths in a network. Management Science 17(11) (1971) 712-716.

Créditos

O script KSP.py foi criado por Gabriel de Oliveira Ramos em 10 de Fevereiro de 2014.