import re
def loadMiles():
f = open('/mnt/nfs/netapp1/fs3/sriram/python/miles.dat', 'r')
return readGraph(f, 500)
# Reads from a file, specified by the argument "fileref," formatted as miles.dat and
# builds a graph from this data.
# The graph that is built has the following structure:
# { cityName: [stateName, latitude, longitude, population, {neighbor1: distance1, neighbor2: distance2, ...},
# cityName: [stateName, latitude, longitude, population, {neighbor1: distance1, neighbor2: distance2, ...},
# ...
# ...}
# The second argumemt t specifies a threshold; only edges of length t or less are kept.
def readGraph(fileref, t):
cities = []
graph = {}
neighborIdx = 0
currentCity = None
for line in fileref.readlines():
if re.match('\*', line): # comment (ignore it)
pass
elif re.match('[a-zA-Z]', line): # line defining a city
# fill this in later
data = re.split('[\[,\]]', line)
data[1] = data[1].lstrip() # state abbrev
data[2] = int(data[2]) / 100.0 # longitude
data[3] = int(data[3]) / 100.0 # latitude
data[4] = int(data[4]) # population
currentCity = data[0] + ', ' + data[1]
cities.append(currentCity)
neighborIdx = len(cities) -2
graph[currentCity] = data[:5]
graph[currentCity].append({})
else:
dists = line.split()
for dist in dists:
dist = int(dist)
if(dist <= t):
neighborCity = cities[neighborIdx]
graph[currentCity][5][neighborCity] = dist
graph[neighborCity][5][currentCity] = dist
neighborIdx -= 1
return graph
def getMinDistanceVertex(distances, finalized):
minDistance = 2**20 #Initialize minDistance to a large number
# Scan distance-values of not yet finalized vertices
for v in distances.keys():
if((not finalized[v]) and (distances[v] < minDistance)):
minDistance = distances[v]
minVertex = v
return minVertex
# Returns the smaller of two comparable quantities
def min(x, y):
if(x <= y):
return x
else:
return y
# Takes a graph and a source vertex and computes distances of all
# vertices from the source. Uses Dijkstra's shortest path algorithm to do this.
# The function returns a size-2 list with the first item in the list being a list
# of shortest path distances from source to all vertices and the second item is a
# representation of the shortest path tree in which each vertex points to its
# predecessor in the shortest path.
def DijkstraShortestPath(g, source):
n = len(g)
# Initializes the distances of all vertices from the source to n.
# Note that n is larger than the largest valid distance.
# Also initializes the shortest path tree
distances = {}
tree = {}
for v in g.keys():
distances[v] = 2**20
tree[v] = v
distances[source] = 0
# Initializing the array the indicates whether a vertex's distance-value has been finalized
finalized = {}
numFinalized = 0
for v in g.keys():
finalized[v] = 0
# Repeatedly process the vertex at the front of the queue
while(numFinalized < n):
u = getMinDistanceVertex(distances, finalized)
#printNow(u)
finalized[u] = 1
numFinalized = numFinalized + 1
#printNow(numFinalized)
nbrs = getNeighbors(g, u)
#printNow(nbrs)
# Scan all neighbors of u
# If a neighbor v has already been finalized, ignore it.
# Otherwise, check if the distance to that be
for v in nbrs.keys():
if(not finalized[v]):
if(distances[u] + getEdgeWeight(g, u, v) < distances[v]):
distances[v] = distances[u] + getEdgeWeight(g, u, v)
tree[v] = u
return [distances, tree]
def shortestPath(g, source, dest):
[lengths, tree] = DijkstraShortestPath(g, source)
path = [dest]
cur = dest
while(cur != tree[cur]):
cur = tree[cur]
path.append(cur)
path.reverse()
return path
def getNeighbors(graph, v):
return graph[v][5]
def isEdge(graph, u, v):
return (u in graph[v][5])
def getEdgeWeight(graph, u, v):
return graph[u][5][v]
def writePathKML(g, path, filename):
outfile = open(filename, "wt")
outfile.write('\n')
outfile.write('\n')
outfile.write('')
outfile.write('\n')
src = path[0]
dst = path[-1]
# Write info. corresponding to each vertex in the graph
for city in path:
outfile.write('\n')
outfile.write('' + city + '\n')
outfile.write('' + city + '\n')
outfile.write('\n')
outfile.write('' + str(-1*g[city][3]) + ', ' + str(g[city][2]) + ', ' + '0\n')
outfile.write('\n')
outfile.write('\n')
# Ready to plot the path line
outfile.write('\n')
outfile.write('' + src + ' - ' + dst + '\n')
outfile.write('')
outfile.write('Path from ' + src + ' to ' + dst)
outfile.write('\n')
outfile.write('#smallLine\n')
outfile.write('\n')
outfile.write('1\n')
outfile.write('1\n')
outfile.write('absolute\n')
outfile.write('')
for city in path:
outfile.write(str(-1*g[city][3]) + ', ' + str(g[city][2]) + ', ' + '0 ')
outfile.write('\n')
outfile.write('\n')
outfile.write('\n')
outfile.write('')
outfile.write('')
outfile.close()
# Takes a graph whose vertices have associated longitude, latitude info. and
# write this into a given kml file
def writeVerticesKML(g, filename):
outfile = open(filename, "wt")
outfile.write('\n')
outfile.write('\n')
outfile.write('')
outfile.write('\n')
cities = g.keys()
# Write info. corresponding to each vertex in the graph
for i in range(len(cities)):
src = cities[i]
outfile.write('\n')
outfile.write('' + src + '\n')
outfile.write('' + src + '\n')
outfile.write('\n')
outfile.write('' + str(-1*g[src][3]) + ', ' + str(g[src][2]) + ', ' + '0\n')
outfile.write('\n')
outfile.write('\n')
outfile.write('')
outfile.write('')
outfile.close()