Eu tenho um conjunto de dados que é um grande gráfico cíclico não ponderado Os ciclos ocorrem em loops de cerca de 5-6 caminhos. Consiste em cerca de 8000 nós e cada nó tem de 1-6 (geralmente cerca de 4-5) conexões. Estou fazendo cálculos de caminho mais curto de um único par e implementei o código a seguir para fazer uma pesquisa de amplitude única.

from Queue import Queue

q = Queue()
parent = {}
fromNode = 'E1123'
toNode = 'A3455'

# path finding
q.put(fromNode)
parent[fromNode] = 'Root'

while not q.empty():
  # get the next node and add its neighbours to queue
  current = q.get()
  for i in getNeighbours(current):
    # note parent and only continue if not already visited
    if i[0] not in parent:
      parent[i[0]] = current
      q.put(i[0])

  # check if destination
  if current == toNode:
    print 'arrived at', toNode
    break

O código acima usa o módulo Python 2.6 Queue e getNeighbours () é simplesmente uma sub-rotina que faz uma única chamada MySQL e retorna os vizinhos como uma lista de tuplas, por exemplo. (('foo',), ('bar',)). A chamada do SQL é rápida.

O código funciona bem, no entanto, testar para profundidades de cerca de 7 camadas leva cerca de 20 segundos para ser executado (2.5GHz Intel 4GB RAM OS X 10.6)

Eu gostaria de receber comentários sobre como melhorar o tempo de execução deste código.