O programa para o cálculo de todos os CGs é dividido em duas partes. Na primeira é utilizada o algoritmo netwrokx.shortest_path do Networkx o qual retorna um dicionário com todos os CG.
Contudo, algums caminhos não são completos, por exemplo, na Figura abaixo há duas possibilidades de caminhos entre A e D, sendo que a saida do networkx só retorna (A,B,D e A,C). Por isso, na segunda parte eu tentei concatenar o caminho A,C com C,D para obter A,C,D. Esse algoritmo parece ser inviável.
import networkx as nx
G = nx.Graph()
G.add_edge('A','B')
G.add_edge('A','C')
G.add_edge('B','D')
G.add_edge('C','D')
G.add_edge('A','E')
G.add_edge('E','D')
paths = nx.shortest_path(G)
print paths
{
'A':
{'A': ['A'], 'C': ['A', 'C'], 'B': ['A', 'B'], 'E': ['A', 'E'], 'D': ['A', 'C', 'D']} ,
'C':
{'A': ['C', 'A'], 'C': ['C'], 'B': ['C', 'A', 'B'], 'E': ['C', 'A', 'E'], 'D': ['C', 'D']},
'B':
{'A': ['B', 'A'], 'C': ['B', 'A', 'C'], 'B':['B'], 'E': ['B', 'A', 'E'], 'D': ['B', 'D']},
'E':
{'A': ['E', 'A'], 'C': ['E', 'A', 'C'], 'B': ['E', 'A', 'B'], 'E': ['E'], 'D': ['E', 'D']},
'D':
{'A': ['D', 'C', 'A'], 'C': ['D', 'C'], 'B': ['D', 'B'], 'E': ['D', 'E'], 'D': ['D']}
}
NÃO ENCONTREI O CAMINHO A - E - D
Dados de medição dos tempos. A variável tempoRede refere-se ao tempo que o algoritmo do networkx demora para retornar o dicionário, tempoProg refere-se ao tempo que o algoritmo para concatenação demora para retornar todos os caminhos possíveis. Medi para vários números de nodos (numNodos) e vários números de arestas (numInterac).
numNodos numInterac tempoRede tempoProg
10 14 0.000472 0.020876
10 30 0.000603 0.020155
20 27 0.001183 0.525488
20 42 0.001252 0.526029
20 63 0.001076 0.484453
20 83 0.001188 0.504840
20 94 0.001333 0.508685
30 50 0.001951 3.851504
30 45 0.001949 3.777059
30 82 0.002099 4.725480
30 88 0.002229 4.840883
30 115 0.002372 5.226335
30 119 0.002377 5.254070
30 152 0.002662 5.473750
30 307 0.003586 5.582978
40 71 0.003084 25.625004
40 73 0.003204 25.022303
40 76 0.003226 24.855031
40 72 0.003163 24.205353
40 141 0.003630 30.617999
40 127 0.003575 29.735314
40 132 0.003695 29.658326
40 177 0.003761 31.689663
40 189 0.003453 33.045820
40 227 0.003576 34.944786
40 412 0.004950 35.209998
50 94 0.003787 109.795693
50 108 0.003858 114.437309
50 98 0.003807 110.602187
50 99 0.003982 114.473716
tempos = read.csv("temposR.txt", sep = " ")
y = tempos$tempoProg
x = tempos$numNodos
plot(x, y, xlab = "Número de Nodos", ylab = "Tempo (s)")
title(main = "Algoritmo para a concatenação de caminhos.")
y = tempos$tempoRede
plot(x, y, xlab = "Número de Nodos", ylab = "Tempo (s)")
title(main = "Algoritmo Networkx para o cálculo de caminhos geodésicos.")
Se quiserem testar com algum número específico de nodos ou arestas me avisem que eu tenho o programa, mas já estou convencida de que tenho que melhorar o cálculo dos CGs (se isto for possível).
O algoritmo do networkx parece linear.