Skip to content

Instantly share code, notes, and snippets.

@ljwolf
Created January 14, 2015 01:27
Show Gist options
  • Save ljwolf/7498bb6eab38b199d1bd to your computer and use it in GitHub Desktop.
Save ljwolf/7498bb6eab38b199d1bd to your computer and use it in GitHub Desktop.
Floyd Warshall for PySAL Networks
import pysal as ps
#Lots of reload for dev.
try:
reload(network)
except:
import network
try:
reload(analysis)
except:
import analysis
try:
reload(util)
except:
import util
from collections import defaultdict
ntw = network.Network(ps.examples.get_path('geodanet/streets.shp'))
dist = defaultdict(lambda : defaultdict(lambda : np.inf)) #defaultdict requires callable args
pred = defaultdict(dict)
#populate initial predecessor and distance dictionaries
for node,neighbors in ntw.adjacencylist.iteritems():
for neighbor in neighbors:
if (node,neighbor) in ntw.edge_lengths.keys():
dist[node][neighbor] = ntw.edge_lengths.get((node,neighbor))
pred[neighbor].update({node : [node]})
elif (neighbor, node) in ntw.edge_lengths.keys():
dist[node][neighbor] = ntw.edge_lengths.get((neighbor,node))
pred[neighbor].update({node : [node]})
dist[node][node] = 0
pred[node][node] = np.NaN
#update precedence and distance using intermediate paths
for inter in ntw.node_list:
for start in ntw.node_list:
for dest in ntw.node_list:
try:
if dist[start][dest] > dist[start][inter] + dist[inter][dest]:
dist[start][dest] = dist[start][inter] + dist[inter][dest]
pred[start][dest] = pred[start][inter] + pred[inter][dest]
except KeyError:
pass
@ljwolf
Copy link
Author

ljwolf commented Jan 14, 2015

I've noticed this doesn't format the predecessor list in the same way the current network.alldistances results are formatted. It makes comparison more difficult. but, the distance lists are the same for all observations, so hopefully the predecessor list isn't screwed up. Manually checking a few and I don't see problems.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment