¿Se puede hacer más rápida esta búsqueda de amplitud?
Tengo un conjunto de datos que es un gran gráfico cíclico no ponderado. Los ciclos ocurren en bucles de aproximadamente 5-6 rutas. Consta de unos 8000 nodos y cada nodo tiene entre 1 y 6 conexiones (generalmente entre 4 y 5). Estoy haciendo los cálculos de la ruta más corta de un solo par y he implementado el siguiente código para hacer una búsqueda en primer lugar.
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
El código anterior utiliza el módulo de cola de Python 2.6 y getNeighbours () es simplemente una subrutina que realiza una sola llamada de MySQL y devuelve a los vecinos como una lista de tuplas, por ejemplo. (('foo',), ('bar',)). La llamada a SQL es rápida.
El código funciona bien, sin embargo, la prueba hasta las profundidades de aproximadamente 7 capas demora aproximadamente 20 segundos en ejecutarse (RAM de 4 GB de Intel de 4 GHz y OS X 10.6)
Agradecería cualquier comentario sobre cómo mejorar el tiempo de ejecución de este código.