MATH 3600 - HW25
Your name: Kyle Brennan, Hannah Kimbrell, Justin Ulmer
Date: April 21, 2014
Graphs
A graph is an ordered pair, G = (V,E), where V is a set of vertices and E = {{u,v} | u ε V and v ε V} is the set of Edges.
More precisely, E is a collection of subsets of V, each of size 2, and the elements of E are called edges.
We will start be defining the class of Graph objects. This class will store V and E as sets. The vertices can be any kind of immutable object. The edges in E will be ordered pairs (tuples) of vertices. Tuples have the advantage of being immutable objects. This use of immutable objects will allow us to implement the several of the methods of the Graph class using Python's extremely efficient Dictionary class.
A Graph will own the sets V and E which define it. By using the set class for V and E we eliminate the concern about multiple copies of a vertex. It is also that case that a tuple (u,v) cannot be accidentally stored more than once, but we will need to avoid accidentally storing both (u,v) and (v,u). A Graph will also own a Dictionary called Adj, which is a particularly efficient data structure for algorithms that would naturally exploit the relationships stored in the Adjacency matrix. It also provides an efficient record of the degree for each vertex. V, E, and Adj are not treated as private objects so that we can directly explore possible algorithms which use them.
In HW13 we introduced the initial version of the Graph class which was very limited while we began to explore methods to be added to the class. Methods which are both relevant to the effective use of Graphs and capable of being efficiently implemented. In that homework we developed a code for plotting a graph and two codes for determining if a graph is connected. One approach was a recursive code that used a depth-first search. The second approach used a queue and a breadth first search. The Graph class in this homework incorporates what we learned by including methods for plotting the graph, for determining whether the graph is connected, and for creating a list of the components of the graph. These last two methods are based on the breadth-first search algorithm, which requires that we include the code for the Queue class.
Be sure to check out this new Graph class by doing tab completion on one or more of the Graph objects that you create.
class Graph(object):
'''Represents a graph'''
def __init__(self, vertices, edges):
'''A Graph is defined by its set of vertices
and its set of edges.'''
self.V = set(vertices)
self.E = set([])
self.Adj = {}
self.add_edges(edges)
print '(Initializing a graph with %d vertices and %d edges)' % (len(self.V),len(self.E))
def add_vertices(self,vertex_list):
''' This method will add the vertices in the vertex_list
to the set of vertices for this graph. Since V is a
set, duplicate vertices will not be added to V. '''
for v in vertex_list:
self.V.add(v)
self.build_Adj()
def add_edges(self,edge_list):
''' This method will add a list of edges to the graph
It will insure that the vertices of each edge are
included in the set of vertices (and not duplicated).
It will also insure that edges are added to the
list of edges and not duplicated. '''
for s,t in edge_list:
if (s,t) not in self.E and (t,s) not in self.E:
self.V.add(s)
self.V.add(t)
self.E.add((s,t))
self.build_Adj()
def build_Adj(self):
self.Adj = {}
for v in self.V:
self.Adj[v] = []
for e in self.E:
s,t = e
self.Adj[s].append(t)
self.Adj[t].append(s)
def Degree(self,v):
return len(self.Adj[v])
def plot(self,Vc):
# Vc is a dictionary with the coordinates for each vertex
g = Graphics()
# Create the list of coordinates
Vcoords = [Vc[v] for v in self.V]
# Include the vertices as red dots
g += point2d(Vcoords,rgbcolor=(1,0,0),size=25)
# Include the names of the vertices
for v in self.V:
g += text(v,(1.01*Vc[v][0], 1.005*Vc[v][1]))
# Include the edges
for edge in self.E:
u,v = edge
g += line([Vc[u],Vc[v]])
return g
def build_Components(self):
Visited = {}
for v in self.V:
Visited[v] = False
components = []
Q = Queue()
for v0 in self.V:
if not Visited[v0]:
comp = []
Visited[v0] = True
Q.enqueue(v0)
while 0 < len(Q):
u = Q.dequeue()
comp.append(v)
for v in self.Adj[u]:
if not Visited[v]:
Visited[v] = True
Q.enqueue(v)
components.append(comp)
return components
def is_connected(self):
Visited = {}
for v in self.V:
Visited[v] = False
Q = Queue()
for v0 in self.V:
if not Visited[v0]:
Visited[v0] = True
Q.enqueue(v0)
while 0 < len(Q):
u = Q.dequeue()
for v in self.Adj[u]:
if not Visited[v]:
Visited[v] = True
Q.enqueue(v)
break
for v in self.V:
if not Visited[v]:
# The Graph is not connected
return False
# The Graph is connected
return True
|
|
A Queue Class
The following block defines a queue class with five methods - enqueue, dequeue, peek, clear, and display. However, instead of following the Stack class approach and having this own a private deque object, this queue is a subclass of the deque class. So this queue object is a deque. One consequence is that this queue object will inherit the methods of the deque class, which includes the clear method. This can be confirmed with the tab completion in the block following the definition of the Queue class.
import collections
''' This block defines a Queue class as a
subclass of the collections.deque class
This class inherits all the methods of
the deque class and adds the methods
enqueue, dequeue, peek, and display.
Daniel D. Warner
February 26, 2012
'''
class Queue(collections.deque):
def enqueue(self,x):
''' enqueue adds an item to the end of the queue.'''
self.appendleft(x)
def dequeue(self):
''' dequeue removes an item from the front of the queue.'''
if 0 < len(self):
return self.pop()
else:
return None
def peek(self):
if 0 < len(self):
p = self.pop()
self.append(p)
return p
else:
return None
def display(self):
print self
|
|
A Priority Queue Class
A priority queue is a container where each item is inserted with a certain priority. When an item is removed, the item with the highest priority is the item that is removed. Priority queues can be implemented using a heap. A heap is a Complete Binary Tree with a partial ordering. A complete binary tree is a binary tree where the tree is filled out from top to bottom, left to right. To be a heap, the complete binary tree must satisfy the following partial ordering criteria.
The priority of the parent must always be equal to or higher than the priority of its children.
This is often referred to as the heap property. The heap property is an invariant which must be true before and after pushing or popping an item.
There is a natural embedding of a complete binary tree into an array using the functions
- parent(n) = (n-1)//2
- leftchild(n) = 2*n + 1
- rightchild(n) = 2*n + 2
The following version of the Priority Queue makes the bubble-up and sift-down routines explicit, so that it is possible to extend the class to allow for changes in the priority and other features that are important for discrete event simulation.
This class has been extended to include the routines priority_of(object) and adjust(new_priority, object). These extensions are necessary for the efficient implementation of Dijkstra's algorithm.
class PriorityQueue():
'''
The arguments passed to a PriorityQueue must consist of
a priority and an object. It must be possible to compare
priorities using the < operator.
By adding the dictionary indx, it is possible to change
the priority of an object in the priority queue.
'''
def __init__(self):
self._pq = []
self._indx = {}
def _parent(self,n):
return (n-1)//2
def _leftchild(self,n):
return 2*n + 1
def _rightchild(self,n):
return 2*n + 2
def push(self, pri, obj):
self._pq.append((pri,obj))
n = len(self._pq)
self._indx[obj] = n-1
self._bubble_up(n-1)
# print 'push pq',self._pq
# print 'push index',self._indx
def _bubble_up(self,c):
while 0<c:
c_item = self._pq[c]
p = self._parent(c)
p_item = self._pq[p]
if c_item < p_item:
self._pq[p] = c_item
self._pq[c] = p_item
c_obj = c_item[1]
p_obj = p_item[1]
self._indx[c_obj] = p
self._indx[p_obj] = c
c = p
else:
break
def pop(self):
n = len(self._pq)
if 0==n:
obj = None
elif 1==n:
pri,obj = self._pq.pop()
self._indx[obj] = None
else:
pri,obj = self._pq[0]
self._indx[obj] = None
self._pq[0] = self._pq.pop()
pri1,obj1 = self._pq[0]
self._indx[obj1] = 0
self._sift_down(0)
# print 'pop pq',self._pq
# print 'pop index',self._indx
return pri,obj
def _sift_down(self,p):
n = len(self._pq)
while p<n:
p_item = self._pq[p]
lc = self._leftchild(p)
if n <= lc:
break
c_item = self._pq[lc]
c = lc
rc = self._rightchild(p)
if rc < n:
r_item = self._pq[rc]
if r_item < c_item:
c_item = r_item
c = rc
if p_item <= c_item:
break
self._pq[p] = c_item
self._pq[c] = p_item
c_obj = c_item[1]
p_obj = p_item[1]
self._indx[c_obj] = p
self._indx[p_obj] = c
p = c
def priority_of(self,obj):
if obj in self._indx.keys():
i = self._indx[obj]
if not i == None:
pri,obj = self._pq[i]
return pri
return None
def adjust(self, new_pri, obj):
if obj in self._indx:
i = self._indx[obj]
item = self._pq[i]
old_pri = item[0]
self._pq[i] = (new_pri,obj)
if new_pri < old_pri:
self._bubble_up(i)
else:
self._sift_down(i)
else:
self.push(new_pri,obj)
def is_not_empty(self):
if 0 < len(self._pq):
return True
else:
return False
|
|
Create a Graph, G2, then add weights to make it a Network. Finally display the Network.
# Build a simple example
V = ['A', 'B', 'C', 'D', 'E', 'F']
Vcoord = {'A':(5,80),'B':(20,40),'C':(5,-80),'D':(20,-40),'E':(12,10),'F':(-20,10)}
E2 = [('A','B'),('A','E'),('A','F'),('B','D'),('C','D'),('C','E'),('C','F')]
G2 = Graph(V,E2)
print 'G2.V',G2.V
print 'G2.E',G2.E
print 'G2.Adj',G2.Adj
g2 = G2.plot(Vcoord)
show(g2,figsize=(3,3),axes=False)
print 'Degrees'
for v in V:
print v,G2.Degree(v)
print G2.build_Components()
if G2.is_connected():
print 'G2 is connected'
else:
print 'G2 is NOT connected'
(Initializing a graph with 6 vertices and 7 edges)
G2.V set(['A', 'C', 'B', 'E', 'D', 'F'])
G2.E set([('C', 'F'), ('C', 'D'), ('A', 'F'), ('A', 'E'), ('A', 'B'),
('C', 'E'), ('B', 'D')])
G2.Adj {'A': ['F', 'E', 'B'], 'C': ['F', 'D', 'E'], 'B': ['A', 'D'],
'E': ['A', 'C'], 'D': ['C', 'B'], 'F': ['C', 'A']}
(Initializing a graph with 6 vertices and 7 edges)
G2.V set(['A', 'C', 'B', 'E', 'D', 'F'])
G2.E set([('C', 'F'), ('C', 'D'), ('A', 'F'), ('A', 'E'), ('A', 'B'), ('C', 'E'), ('B', 'D')])
G2.Adj {'A': ['F', 'E', 'B'], 'C': ['F', 'D', 'E'], 'B': ['A', 'D'], 'E': ['A', 'C'], 'D': ['C', 'B'], 'F': ['C', 'A']}
|
Degrees
A 3
B 2
C 3
D 2
E 2
F 2
[['F', 'B', 'A', 'C', 'D', 'E']]
G2 is connectedW = {('A','B'):7, ('A','E'):18, ('A','F'):19, ('B','D'):14, ('C','D'):13, ('C','E'):16, ('C','F'):21}
for edge in W.keys():
s,t = edge
w = W[edge]
W[(t,s)] = w
for edge in G2.E:
s,t = edge
w = W[(s,t)]
xs,ys = Vcoord[s]
xt,yt = Vcoord[t]
xw,yw = ((xs+xt)/2,1/2+(ys+yt)/2)
g2 += text(w,(1.1*xw,1.1*yw))
show(g2,figsize=(3,3),axes=False)
|
|
Shortest Paths
We will start by looking at 3 algorihtms for finding the shortest path between two vertices in a network. The two networks will be G2 and Atlas from the previous examples.
For G2 we will find the shortest paths from A to B, A to C, and A to D.
For Atlas we will find the shortest paths from Wilmington, NC to Memphis, TN; from Daytona Beach, FL to Lexington, KY; and from Charleston, SC to Charleston, WV.
The first algorithm is a depth-first, recursive, back-tracking search. Once a vertex has been added to the path it is no longer available. We will use a dictionary labeled, available, rather than a linear search to see if the vertex in already in the path. After we have found one path to the last vertex, we can prune all future branches of the search tree.
def Shortest_Path_df(G,W,path,available,last_v,distance,best,counts):
counts[0] += 1 # Number of vertices visited
counts[1] = max(counts[1],len(path)) # Maximum path examined
current = path[-1]
if current == last_v:
# Found a path
## print path,distance
if distance < best[1]:
best[0] = copy(path)
best[1] = distance
else:
for v in G.Adj[current]:
if available[v]:
w = W[(current,v)]
if distance+w < best[1]:
path.append(v)
available[v] = False
best,counts = Shortest_Path_df(G,W,path,available,last_v,distance+w,best,counts)
path.pop()
available[v] = True
return best,counts
def Shortest_Path_DF(G,W,first_v,last_v):
available = {}
for v in G.V:
available[v] = True
available[first_v] = False
best = [[first_v],infinity]
return Shortest_Path_df(G,W,[first_v],available,last_v,0,best,[0,0])
|
|
best,counts = Shortest_Path_DF(G2,W,'A','B')
print 'Shortest Path:',best[0]
print 'Length:',best[1]
print 'Cities examined:',counts[0],'Longest Path:',counts[1]
timeit("Shortest_Path_DF(G2,W,'A','B')")
Shortest Path: ['A', 'B'] Length: 7 Cities examined: 12 Longest Path: 5 625 loops, best of 3: 99.3 µs per loop Shortest Path: ['A', 'B'] Length: 7 Cities examined: 12 Longest Path: 5 625 loops, best of 3: 99.3 µs per loop |
best,counts = Shortest_Path_DF(G2,W,'A','C')
print 'Shortest Path:',best[0]
print 'Length:',best[1]
print 'Cities examined:',counts[0],'Longest Path:',counts[1]
timeit("Shortest_Path_DF(G2,W,'A','C')")
Shortest Path: ['A', 'E', 'C'] Length: 34 Cities examined: 7 Longest Path: 3 625 loops, best of 3: 61.3 µs per loop Shortest Path: ['A', 'E', 'C'] Length: 34 Cities examined: 7 Longest Path: 3 625 loops, best of 3: 61.3 µs per loop |
best,counts = Shortest_Path_DF(G2,W,'A','D')
print 'Shortest Path:',best[0]
print 'Length:',best[1]
print 'Cities examined:',counts[0],'Longest Path:',counts[1]
timeit("Shortest_Path_DF(G2,W,'A','D')")
Shortest Path: ['A', 'B', 'D'] Length: 21 Cities examined: 9 Longest Path: 4 625 loops, best of 3: 79.8 µs per loop Shortest Path: ['A', 'B', 'D'] Length: 21 Cities examined: 9 Longest Path: 4 625 loops, best of 3: 79.8 µs per loop |
The Breadth-First Search uses a queue that stores tuples consisting of a path and the distance.
Note that if the distance between every adjacent vertex was the same then the breadth-first search could stop as soon as it found the last vertex. However, since this isn't the case we must keep searching as long as there are candidates. It is also the case that since there are many different paths in the queue, checking for availability requires a linear search to see if the vertex is in the path.
def Shortest_Path_BF(G,W,first_v,last_v):
best = [[first_v],infinity]
Q = Queue()
Q.enqueue(([first_v],0))
q_size = 1
max_q = q_size
# Each item in the queue is a (path,distance) tuple
while 0<len(Q):
path,distance = Q.dequeue()
q_size -= len(path)
if distance < best[1]:
# This path is still a contender
current = path[-1]
for v in G.Adj[current]:
if not v in path:
new_distance = distance + W[(current,v)]
if new_distance < best[1]:
new_path = copy(path)
new_path.append(v)
if v == last_v:
# Found a path
best[0] = copy(new_path)
best[1] = new_distance
## print new_path,'\tdistance:',best[1],'\tmax queue',max_q
else:
Q.enqueue((new_path,new_distance))
q_size += len(new_path)
max_q = max(max_q,q_size)
return best,max_q
|
|
best,max_q = Shortest_Path_BF(G2,W,'A','B')
print 'Shortest Path:',best[0]
print 'Length:',best[1]
print 'Max Queue size:',max_q
timeit("Shortest_Path_BF(G2,W,'A','B')")
Shortest Path: ['A', 'B'] Length: 7 Max Queue size: 6 625 loops, best of 3: 74.5 µs per loop Shortest Path: ['A', 'B'] Length: 7 Max Queue size: 6 625 loops, best of 3: 74.5 µs per loop |
best,max_q = Shortest_Path_BF(G2,W,'A','C')
print 'Shortest Path:',best[0]
print 'Length:',best[1]
print 'Max Queue size:',max_q
timeit("Shortest_Path_BF(G2,W,'A','C')")
Shortest Path: ['A', 'E', 'C'] Length: 34 Max Queue size: 9 625 loops, best of 3: 129 µs per loop Shortest Path: ['A', 'E', 'C'] Length: 34 Max Queue size: 9 625 loops, best of 3: 129 µs per loop |
best,max_q = Shortest_Path_BF(G2,W,'A','D')
print 'Shortest Path:',best[0]
print 'Length:',best[1]
print 'Max Queue size:',max_q
timeit("Shortest_Path_BF(G2,W,'A','D')")
Shortest Path: ['A', 'B', 'D'] Length: 21 Max Queue size: 9 625 loops, best of 3: 166 µs per loop Shortest Path: ['A', 'B', 'D'] Length: 21 Max Queue size: 9 625 loops, best of 3: 166 µs per loop |
An Atlas Example
The following blocks define an Atlas of 32 cities in the Southeast.
# Index City State Latitude Longitude
southeast_cities = """
1 Atlanta GA 33.4500 84.2300
2 Augusta GA 33.2800 82.0200
3 Tifton GA 31.2700 83.3100
4 Montgomery AL 32.3000 86.4000
5 Birmingham AL 33.5670 86.7500
6 Chattanooga TN 35.0330 85.2000
7 Savannah GA 32.1330 81.2000
8 Columbia SC 33.9500 81.1170
9 Charlotte NC 35.2200 80.9300
10 Asheville NC 34.4300 82.5500
11 Knoxville TN 35.8200 83.9800
12 Charleston SC 32.9000 80.0300
13 Jacksonville FL 30.5000 81.7000
14 Tallahassee FL 30.3830 84.3670
15 Mobile AL 30.6830 88.2500
16 Meridian MS 32.3330 88.7500
17 Columbus MS 33.6345 88.4498
18 Huntsville AL 34.7793 86.6124
19 Corinth MS 34.9314 88.5235
20 Memphis TN 35.1056 90.0070
21 Nashville TN 36.1658 86.7844
22 Florence SC 34.1953 79.7628
23 Raleigh NC 35.7719 78.6389
24 Bluefield WV 37.2697 81.2225
25 Greensboro NC 36.0830 79.9500
26 Wilmington NC 34.2670 77.9170
27 Roanoke VA 37.3170 79.9670
28 Charleston WV 38.3670 81.6000
29 Lexington KY 38.0500 85.0000
30 Myrtle_Beach SC 33.6800 78.9300
31 Daytona_Beach FL 29.1800 81.0500
32 Gainsville FL 29.6800 82.2700
"""
|
|
# Edge List (source target distance)
road_map = """
Atlanta GA Augusta GA 151
Atlanta GA Tifton GA 182
Atlanta GA Montgomery AL 167
Atlanta GA Birmingham AL 148
Atlanta GA Chattanooga TN 115
Atlanta GA Savannah GA 252
Atlanta GA Columbia SC 213
Atlanta GA Charlotte NC 240
Atlanta GA Asheville NC 206
Atlanta GA Knoxville TN 215
Augusta GA Tifton GA 203
Augusta GA Savannah GA 128
Augusta GA Columbia SC 68
Augusta GA Asheville NC 217
Augusta GA Charleston SC 175
Tifton GA Montgomery AL 207
Tifton GA Birmingham AL 326
Tifton GA Jacksonville FL 166
Tifton GA Tallahassee FL 90
Tifton GA Gainsville FL 151
Montgomery AL Tallahassee FL 214
Montgomery AL Mobile AL 170
Montgomery AL Meridian MS 152
Montgomery AL Columbus MS 197
Birmingham AL Chattanooga TN 143
Birmingham AL Mobile AL 262
Birmingham AL Meridian MS 146
Birmingham AL Columbus MS 118
Birmingham AL Huntsville AL 99
Birmingham AL Corinth MS 223
Birmingham AL Memphis TN 247
Chattanooga TN Asheville NC 227
Chattanooga TN Knoxville TN 114
Chattanooga TN Huntsville AL 106
Chattanooga TN Nashville TN 128
Savannah GA Columbia SC 155
Savannah GA Charleston SC 105
Savannah GA Jacksonville FL 140
Savannah GA Tallahassee FL 299
Savannah GA Florence SC 172
Columbia SC Charlotte NC 91
Columbia SC Asheville NC 157
Columbia SC Charleston SC 112
Columbia SC Florence SC 79
Columbia SC Raleigh NC 228
Columbia SC Bluefield WV 261
Charlotte NC Asheville NC 125
Charlotte NC Raleigh NC 168
Charlotte NC Greensboro NC 97
Charlotte NC Wilmington NC 204
Asheville NC Knoxville TN 115
Asheville NC Bluefield WV 233
Asheville NC Greensboro NC 170
Asheville NC Roanoke VA 254
Knoxville TN Nashville TN 178
Knoxville TN Roanoke VA 257
Knoxville TN Charleston WV 314
Knoxville TN Lexington KY 173
Charleston SC Myrtle_Beach SC 97
Jacksonville FL Tallahassee FL 163
Jacksonville FL Daytona_Beach FL 90
Jacksonville FL Gainsville FL 73
Tallahassee FL Mobile AL 240
Tallahassee FL Gainsville FL 149
Huntsville AL Corinth MS 126
Corinth MS Memphis TN 93
Memphis TN Nashville TN 210
"""
|
|
import re
# Build the vertex_list and the vcoords
p = re.compile(r'\s+(\d+)\s+(\w+)\s+(\w+)\s+(\d+\.\d+)\s+(\d+\.\d+)')
vertex_list = []
vcoords = {}
pos = 0
while pos<len(southeast_cities):
m = p.search(southeast_cities,pos)
if m:
#print m.group()
g = m.groups()
if g[0] and g[1] and g[2] and g[3] and g[4]:
city = g[1]+', '+g[2]
vertex_list.append(city)
coord = (float(g[3]),float(g[4]))
vcoords[city] = coord
pos = m.end()
else:
break
for v in vertex_list:
c = vcoords[v]
if 14 < len(v):
print v,'\t(', c[0],',',c[1],')'
else:
print v,'\t\t(', c[0],',',c[1],')'
Atlanta, GA ( 33.45 , 84.23 ) Augusta, GA ( 33.28 , 82.02 ) Tifton, GA ( 31.27 , 83.31 ) Montgomery, AL ( 32.3 , 86.4 ) Birmingham, AL ( 33.567 , 86.75 ) Chattanooga, TN ( 35.033 , 85.2 ) Savannah, GA ( 32.133 , 81.2 ) Columbia, SC ( 33.95 , 81.117 ) Charlotte, NC ( 35.22 , 80.93 ) Asheville, NC ( 34.43 , 82.55 ) Knoxville, TN ( 35.82 , 83.98 ) Charleston, SC ( 32.9 , 80.03 ) Jacksonville, FL ( 30.5 , 81.7 ) Tallahassee, FL ( 30.383 , 84.367 ) Mobile, AL ( 30.683 , 88.25 ) Meridian, MS ( 32.333 , 88.75 ) Columbus, MS ( 33.6345 , 88.4498 ) Huntsville, AL ( 34.7793 , 86.6124 ) Corinth, MS ( 34.9314 , 88.5235 ) Memphis, TN ( 35.1056 , 90.007 ) Nashville, TN ( 36.1658 , 86.7844 ) Florence, SC ( 34.1953 , 79.7628 ) Raleigh, NC ( 35.7719 , 78.6389 ) Bluefield, WV ( 37.2697 , 81.2225 ) Greensboro, NC ( 36.083 , 79.95 ) Wilmington, NC ( 34.267 , 77.917 ) Roanoke, VA ( 37.317 , 79.967 ) Charleston, WV ( 38.367 , 81.6 ) Lexington, KY ( 38.05 , 85.0 ) Myrtle_Beach, SC ( 33.68 , 78.93 ) Daytona_Beach, FL ( 29.18 , 81.05 ) Gainsville, FL ( 29.68 , 82.27 ) Atlanta, GA ( 33.45 , 84.23 ) Augusta, GA ( 33.28 , 82.02 ) Tifton, GA ( 31.27 , 83.31 ) Montgomery, AL ( 32.3 , 86.4 ) Birmingham, AL ( 33.567 , 86.75 ) Chattanooga, TN ( 35.033 , 85.2 ) Savannah, GA ( 32.133 , 81.2 ) Columbia, SC ( 33.95 , 81.117 ) Charlotte, NC ( 35.22 , 80.93 ) Asheville, NC ( 34.43 , 82.55 ) Knoxville, TN ( 35.82 , 83.98 ) Charleston, SC ( 32.9 , 80.03 ) Jacksonville, FL ( 30.5 , 81.7 ) Tallahassee, FL ( 30.383 , 84.367 ) Mobile, AL ( 30.683 , 88.25 ) Meridian, MS ( 32.333 , 88.75 ) Columbus, MS ( 33.6345 , 88.4498 ) Huntsville, AL ( 34.7793 , 86.6124 ) Corinth, MS ( 34.9314 , 88.5235 ) Memphis, TN ( 35.1056 , 90.007 ) Nashville, TN ( 36.1658 , 86.7844 ) Florence, SC ( 34.1953 , 79.7628 ) Raleigh, NC ( 35.7719 , 78.6389 ) Bluefield, WV ( 37.2697 , 81.2225 ) Greensboro, NC ( 36.083 , 79.95 ) Wilmington, NC ( 34.267 , 77.917 ) Roanoke, VA ( 37.317 , 79.967 ) Charleston, WV ( 38.367 , 81.6 ) Lexington, KY ( 38.05 , 85.0 ) Myrtle_Beach, SC ( 33.68 , 78.93 ) Daytona_Beach, FL ( 29.18 , 81.05 ) Gainsville, FL ( 29.68 , 82.27 ) |
# Build the edge_list and the list of weights
q = re.compile(r'\s+(\w+)\s+(\w+)\s+(\w+)\s+(\w+)\s+(\d+)')
edge_list = []
weights = {}
pos = 0
while pos<len(road_map):
m = q.search(road_map,pos)
if m:
# print m.group()
g = m.groups()
if g[0] and g[1] and g[2] and g[3] and g[4]:
s = g[0]+', '+g[1]
t = g[2]+', '+g[3]
w = int(g[4])
edge_list.append((s,t))
weights[(s,t)] = w
weights[(t,s)] = w
pos = m.end()
else:
break
|
|
Atlas = Graph(vertex_list, edge_list)
g = Atlas.plot(vcoords)
for edge in Atlas.E:
s,t = edge
w = weights[(s,t)]
xs,ys = vcoords[s]
xt,yt = vcoords[t]
xw,yw = ((xs+xt)/2,(ys+yt)/2)
g += text(w,(xw,yw))
#show(G2plot,figsize=(10,10),axes=False)
show(g,figsize=(10,8),axes=False)
(Initializing a graph with 32 vertices and 67 edges) (Initializing a graph with 32 vertices and 67 edges) |
Best-First Shortest Path Algorithm
This is a heuristic algorithm for finding the shortest path in a weighted graph. It assumes that you have available a function which provides an underestimate of the best possible result. In the case of the Atlas, a natural candidate is the length of the path from the origin to the current city plus the straight line ("as the crow flies") distance from the current city to the destination. We start the algorithm with an empty path and a best distance of infinity. Then set the current city to origin.
Given a candidate path and the current city (the last city in the candidate path) we then look at the current city's neighbors. For each neighbor that is not already in the candidate path we compute the heuristic distance estimate, which is the distance along the candidate path, plus the distance from the current city to the neighbor, plus the straightline distance from the neighbor to the destination. If this heuristic distance estimate is less than the distance of the best path found so far, we append the neighbor to a copy of the candidate path and place this path along with the heuristic distance in the priority queue.
When all the neighbors have been examined, we pop the path with the shortest heuristic distance estimate from the priority queue. That path becomes the new candidate path and the last city in that path becomes the current city. Whenever the current city is the destination, we update the "best path" and its distance. We can terminate the search as soon as the heuristic distance estimate for the next path in the priority queue is larger than the actual distance of the "best path".
# Write a function that uses a best-first search strategy
# to find the shortest route between two cities in Atla
The following function computes the straight-line distance between two cities. The block also verifies that the calculation and the specified distances are consistent.
def crow_fly(network, vcoords, city1, city2):
lat1,long1 = vcoords[city1]
lat2,long2 = vcoords[city2]
# One minute of longitude at the equator is a geographical mile
# equal to 6087.025 feet
# However the road map distance are US miles equal to 5280 feet
# So the conversion factor at the equator should be
# 6087.025/5280 approximately 1.1528456
# However, we are signigicantly north of the equator and the heuristic
# requires an underestimate, so we use the smaller conversion factor
yd = (lat2 - lat1)*60*(0.86)
xd = (long2 - long1)*60*(0.86)
return sqrt(xd^2 + yd^2)
# Check consistency of the atlas distances and the lat-long conversion
print 'Checking consistency.'
AOK = True
#edges = Atlas.get_edges()
for edge in Atlas.E:
s,t = edge
d1 = crow_fly(Atlas, vcoords, s, t)
d2 = weights[edge]
if d2 < d1:
print 'Inconsistent',s,t,d1,d2
AOK = False
if AOK:
print 'The crow-fly heuristic is consistent.'
Checking consistency. The crow-fly heuristic is consistent. Checking consistency. The crow-fly heuristic is consistent. |
The following function finds the shortest path between two cities using a best-first search.
def Shortest_Path_Best(network, weights, start_city, destination):
counts = [0,0,0] # [number of cities examined, number of paths found, maximum queue size]
best = [[],infinity] # best path and best length
path = (start_city,)
PQ = PriorityQueue()
d0 = crow_fly(network,vcoords,start_city,destination)
pt = (path,0)
PQ.push(d0,pt)
q_size = len(path)
max_q = q_size
#print PQ._pq
while PQ.is_not_empty():
pri,(path,length) = PQ.pop()
q_size -= len(path)
#print pri,path,length
current = list(path)[-1]
counts[0] += 1
if current == destination:
# We have found a path
counts[1] += 1
if length <= best[1]:
best = [path, length]
# print counts,best
elif pri <= best[1]:
neighbors = network.Adj[current]
for city in neighbors:
if city not in path: # Inefficient in time but not space
w = weights[(current,city)]
new_length = length + w
new_pri = crow_fly(network,vcoords,city,destination)+new_length
if (new_pri <= best[1]):
new_path = copy(path)
p_list = list(new_path)
p_list.append(city)
new_path = tuple(p_list)
q_size += len(new_path)
max_q = max(max_q,q_size)
PQ.push(new_pri,(new_path,new_length))
else:
pass
counts[2] = max_q
return best,counts
|
|
The following code uses the three algorithms to find the shortest route from Wilmington, NC to Memphis, TN.
print "Depth-First"
best,counts = Shortest_Path_DF(Atlas,weights,'Wilmington, NC', 'Memphis, TN')
print best[0]
print 'Length:',best[1]
print 'Cities examined:',counts[0],'Longest Path:',counts[1]
timeit("Shortest_Path_DF(Atlas,weights,'Wilmington, NC', 'Memphis, TN')")
print "\nBreadth-First"
best,max_q = Shortest_Path_BF(Atlas,weights,'Wilmington, NC', 'Memphis, TN')
print best[0]
print 'Length:',best[1]
print 'Max Queue size:',max_q
timeit("Shortest_Path_BF(Atlas,weights,'Wilmington, NC', 'Memphis, TN')")
print "\nBest-First"
best,counts = Shortest_Path_Best(Atlas, weights, 'Wilmington, NC', 'Memphis, TN')
path = best[0]
length = best[1]
print path
print length, counts
timeit("Shortest_Path_Best(Atlas, weights, 'Wilmington, NC', 'Memphis, TN')")
Depth-First
['Wilmington, NC', 'Charlotte, NC', 'Asheville, NC', 'Knoxville, TN',
'Nashville, TN', 'Memphis, TN']
Length: 832
Cities examined: 1333 Longest Path: 13
125 loops, best of 3: 6.89 ms per loop
Breadth-First
['Wilmington, NC', 'Charlotte, NC', 'Asheville, NC', 'Knoxville, TN',
'Nashville, TN', 'Memphis, TN']
Length: 832
Max Queue size: 1183
125 loops, best of 3: 6.98 ms per loop
Best-First
('Wilmington, NC', 'Charlotte, NC', 'Asheville, NC', 'Knoxville, TN',
'Nashville, TN', 'Memphis, TN')
832 [84, 2, 332]
25 loops, best of 3: 9.51 ms per loop
Depth-First
['Wilmington, NC', 'Charlotte, NC', 'Asheville, NC', 'Knoxville, TN', 'Nashville, TN', 'Memphis, TN']
Length: 832
Cities examined: 1333 Longest Path: 13
125 loops, best of 3: 6.89 ms per loop
Breadth-First
['Wilmington, NC', 'Charlotte, NC', 'Asheville, NC', 'Knoxville, TN', 'Nashville, TN', 'Memphis, TN']
Length: 832
Max Queue size: 1183
125 loops, best of 3: 6.98 ms per loop
Best-First
('Wilmington, NC', 'Charlotte, NC', 'Asheville, NC', 'Knoxville, TN', 'Nashville, TN', 'Memphis, TN')
832 [84, 2, 332]
25 loops, best of 3: 9.51 ms per loop
|
Exercise 1: Using the three algorithms find the shortest route from Daytona Beach, FL to Lexington, KY.
# Find the shortest routes
# from Wilmington, NC to Memphis, TN
# from Daytona_Beach, FL to Lexington, KY
# from Charleston, SC to Charleston, WV
print "Depth-First"
best,counts = Shortest_Path_DF(Atlas,weights,'Daytona_Beach, FL', 'Lexington, KY')
print best[0]
print 'Length:',best[1]
print 'Cities examined:',counts[0],'Longest Path:',counts[1]
timeit("Shortest_Path_DF(Atlas,weights,'Daytona_Beach, FL', 'Lexington, KY')")
print "\nBreadth-First"
best,max_q = Shortest_Path_BF(Atlas,weights,'Daytona_Beach, FL', 'Lexington, KY')
print best[0]
print 'Length:',best[1]
print 'Max Queue size:',max_q
timeit("Shortest_Path_BF(Atlas,weights,'Daytona_Beach, FL', 'Lexington, KY')")
print "\nBest-First"
best,counts = Shortest_Path_Best(Atlas, weights, 'Daytona_Beach, FL', 'Lexington, KY')
path = best[0]
length = best[1]
print path
print length, counts
timeit("Shortest_Path_Best(Atlas, weights, 'Daytona_Beach, FL', 'Lexington, KY')")
Depth-First
['Daytona_Beach, FL', 'Jacksonville, FL', 'Tifton, GA', 'Atlanta, GA',
'Knoxville, TN', 'Lexington, KY']
Length: 826
Cities examined: 2612 Longest Path: 25
25 loops, best of 3: 23.3 ms per loop
Breadth-First
['Daytona_Beach, FL', 'Jacksonville, FL', 'Tifton, GA', 'Atlanta, GA',
'Knoxville, TN', 'Lexington, KY']
Length: 826
Max Queue size: 2202
25 loops, best of 3: 12.5 ms per loop
Best-First
('Daytona_Beach, FL', 'Jacksonville, FL', 'Tifton, GA', 'Atlanta, GA',
'Knoxville, TN', 'Lexington, KY')
826 [280, 6, 1377]
25 loops, best of 3: 33.6 ms per loop
Depth-First
['Daytona_Beach, FL', 'Jacksonville, FL', 'Tifton, GA', 'Atlanta, GA', 'Knoxville, TN', 'Lexington, KY']
Length: 826
Cities examined: 2612 Longest Path: 25
25 loops, best of 3: 23.3 ms per loop
Breadth-First
['Daytona_Beach, FL', 'Jacksonville, FL', 'Tifton, GA', 'Atlanta, GA', 'Knoxville, TN', 'Lexington, KY']
Length: 826
Max Queue size: 2202
25 loops, best of 3: 12.5 ms per loop
Best-First
('Daytona_Beach, FL', 'Jacksonville, FL', 'Tifton, GA', 'Atlanta, GA', 'Knoxville, TN', 'Lexington, KY')
826 [280, 6, 1377]
25 loops, best of 3: 33.6 ms per loop
|
Exercise 2: Using the three algorithms find the shortest route from Charleston, SC to Charleston, WV.
Then summarize the performance of each algorithm and list each algorithms strengths.
print "Depth-First"
best,counts = Shortest_Path_DF(Atlas,weights,'Charleston, SC', 'Charleston, WV')
print best[0]
print 'Length:',best[1]
print 'Cities examined:',counts[0],'Longest Path:',counts[1]
timeit("Shortest_Path_DF(Atlas,weights,'Charleston, SC', 'Charleston, WV')")
print "\nBreadth-First"
best,max_q = Shortest_Path_BF(Atlas,weights,'Charleston, SC', 'Charleston, WV')
print best[0]
print 'Length:',best[1]
print 'Max Queue size:',max_q
timeit("Shortest_Path_BF(Atlas,weights,'Charleston, SC', 'Charleston, WV')")
print "\nBest-First"
best,counts = Shortest_Path_Best(Atlas, weights, 'Charleston, SC', 'Charleston, WV')
path = best[0]
length = best[1]
print path
print length, counts
timeit("Shortest_Path_Best(Atlas, weights, 'Charleston, SC', 'Charleston, WV')")
Depth-First
['Charleston, SC', 'Columbia, SC', 'Asheville, NC', 'Knoxville, TN',
'Charleston, WV']
Length: 698
Cities examined: 199772 Longest Path: 25
5 loops, best of 3: 2.73 s per loop
Breadth-First
['Charleston, SC', 'Columbia, SC', 'Asheville, NC', 'Knoxville, TN',
'Charleston, WV']
Length: 698
Max Queue size: 1940
25 loops, best of 3: 11 ms per loop
Best-First
('Charleston, SC', 'Columbia, SC', 'Asheville, NC', 'Knoxville, TN',
'Charleston, WV')
698 [323, 5, 1212]
25 loops, best of 3: 39.6 ms per loop
Depth-First
['Charleston, SC', 'Columbia, SC', 'Asheville, NC', 'Knoxville, TN', 'Charleston, WV']
Length: 698
Cities examined: 199772 Longest Path: 25
5 loops, best of 3: 2.73 s per loop
Breadth-First
['Charleston, SC', 'Columbia, SC', 'Asheville, NC', 'Knoxville, TN', 'Charleston, WV']
Length: 698
Max Queue size: 1940
25 loops, best of 3: 11 ms per loop
Best-First
('Charleston, SC', 'Columbia, SC', 'Asheville, NC', 'Knoxville, TN', 'Charleston, WV')
698 [323, 5, 1212]
25 loops, best of 3: 39.6 ms per loop
|
#It looks like the 'Best-First' algorithm will run in pretty average time no matter what the input is, and the breadth-first and depth-first
#change depending on the starting point and ending point.
#It seems like the breadth-first search is stronger when the two points are closer together, and the depth-first search is stronger when the
#points are farther apart from each other.
|
|
Exercise 3. Complete the definition of the function for displaying the shortest path between two of the cities in Atlas, plotted in red on top of a copy of original display of the Atlas. Also print out the total distance for this path.
def display_path(G,W,path):
g1 = copy(g)
w_sum = 0
u = path[0]
for k in range(1,len(path)):
v = path[k]
g1 += line([vcoords[u],vcoords[v]], color='red')
u = path[k]
w_sum += 1
show(g1,figsize=[10,8],axes=False)
print 'Path length:',w_sum
|
|
Using the Shortest_Path_Best routine, find the shortest route from Wilmington, NC to Memphis, TN.
Then print out the search statistics and display the path.
print "\nBest-First"
best,counts = Shortest_Path_Best(Atlas, weights, 'Wilmington, NC', 'Memphis, TN')
path = best[0]
length = best[1]
print path
print length, counts
display_path(Atlas,weights,path)
Best-First
('Wilmington, NC', 'Charlotte, NC', 'Asheville, NC', 'Knoxville, TN',
'Nashville, TN', 'Memphis, TN')
832 [84, 2, 332]
Best-First
('Wilmington, NC', 'Charlotte, NC', 'Asheville, NC', 'Knoxville, TN', 'Nashville, TN', 'Memphis, TN')
832 [84, 2, 332]
|
Path length: 5Exercise 4. Using the Shortest_Path_Best routine, find the shortest route from Daytona_Beach, FL to Lexington, KY.
Then print out the search statistics and display the path.
print "\nBest-First"
best,counts = Shortest_Path_Best(Atlas, weights, 'Daytona_Beach, FL', 'Lexington, KY')
path = best[0]
length = best[1]
print path
print length, counts
display_path(Atlas,weights,path)
Best-First
('Daytona_Beach, FL', 'Jacksonville, FL', 'Tifton, GA', 'Atlanta, GA',
'Knoxville, TN', 'Lexington, KY')
826 [280, 6, 1377]
Best-First
('Daytona_Beach, FL', 'Jacksonville, FL', 'Tifton, GA', 'Atlanta, GA', 'Knoxville, TN', 'Lexington, KY')
826 [280, 6, 1377]
|
Path length: 5Exercise 5. Using the preceeding Shortest_Path_Best routine, find the shortest route from Charleston, SC to Charleston, WV.
Then print out the search statistics and display the path.
print "\nBest-First"
best,counts = Shortest_Path_Best(Atlas, weights, 'Charleston, SC', 'Charleston, WV')
path = best[0]
length = best[1]
print path
print length, counts
display_path(Atlas,weights,path)
Best-First
('Charleston, SC', 'Columbia, SC', 'Asheville, NC', 'Knoxville, TN',
'Charleston, WV')
698 [323, 5, 1212]
Best-First
('Charleston, SC', 'Columbia, SC', 'Asheville, NC', 'Knoxville, TN', 'Charleston, WV')
698 [323, 5, 1212]
|
Path length: 4The Floyd-Warshall Algorithm
The Floyd-Warshall algorithm calculates the shortest distance between every pair of cities. We start with a 2D array, FW.
We initialize FW to
\[
{\bf{FW}}(i,j,-1) = \left\{ {\begin{array}{*{20}c}
{EdgeCost(i,j)} \\
{\infty {\rm{ otherwise}}} \\
\end{array}} \right.
\]
Then for $k=0\ldots nV-1$
\[
{\bf{FW}}(i,j,k) = min({\bf{FW}}(i,j,k - 1),{\bf{FW}}(i,k,k - 1) + {\bf{FW}}(k,j,k - 1))
\]
# First build the dictionary that provides the index of each city
Atlas_vindex = {}
for k,v in enumerate(Atlas.V):
Atlas_vindex[v] = k
print Atlas_vindex
inf = 0
for edge in Atlas.E:
inf += weights[edge]
print inf
{'Charlotte, NC': 0, 'Raleigh, NC': 1, 'Florence, SC': 2, 'Meridian,
MS': 3, 'Chattanooga, TN': 4, 'Augusta, GA': 5, 'Jacksonville, FL': 25,
'Columbia, SC': 13, 'Tifton, GA': 8, 'Knoxville, TN': 9, 'Tallahassee,
FL': 10, 'Roanoke, VA': 11, 'Huntsville, AL': 12, 'Corinth, MS': 7,
'Atlanta, GA': 14, 'Mobile, AL': 15, 'Charleston, WV': 16, 'Nashville,
TN': 17, 'Birmingham, AL': 30, 'Montgomery, AL': 19, 'Asheville, NC':
20, 'Memphis, TN': 21, 'Charleston, SC': 22, 'Bluefield, WV': 23,
'Savannah, GA': 24, 'Myrtle_Beach, SC': 6, 'Gainsville, FL': 26,
'Columbus, MS': 27, 'Wilmington, NC': 28, 'Lexington, KY': 29,
'Greensboro, NC': 18, 'Daytona_Beach, FL': 31}
11494
{'Charlotte, NC': 0, 'Raleigh, NC': 1, 'Florence, SC': 2, 'Meridian, MS': 3, 'Chattanooga, TN': 4, 'Augusta, GA': 5, 'Jacksonville, FL': 25, 'Columbia, SC': 13, 'Tifton, GA': 8, 'Knoxville, TN': 9, 'Tallahassee, FL': 10, 'Roanoke, VA': 11, 'Huntsville, AL': 12, 'Corinth, MS': 7, 'Atlanta, GA': 14, 'Mobile, AL': 15, 'Charleston, WV': 16, 'Nashville, TN': 17, 'Birmingham, AL': 30, 'Montgomery, AL': 19, 'Asheville, NC': 20, 'Memphis, TN': 21, 'Charleston, SC': 22, 'Bluefield, WV': 23, 'Savannah, GA': 24, 'Myrtle_Beach, SC': 6, 'Gainsville, FL': 26, 'Columbus, MS': 27, 'Wilmington, NC': 28, 'Lexington, KY': 29, 'Greensboro, NC': 18, 'Daytona_Beach, FL': 31}
11494
|
The following code, build_Floyd_Warshall, Floyd-Warshall algorithm that creates the matrix of shortest distances between every pair of cities.
def build_Floyd_Warshall(G,Vindex,W):
nV = len(G.V)
# Build the nV-by-nV matrix and set the diagonal entries
# to zero, and set the off-diagonal entries to infinity,
FW = matrix(ZZ,nV)
for i in range(nV):
for j in range(nV):
if i==j:
FW[i,j] = 0
else:
FW[i,j] = inf
# print FW.str()
# Now for each edge, (s,t), set the corresponding
# entries in the matrix to the given weights
for edge in G.E:
w = weights[edge]
s,t = edge
sk = Vindex[s]
tk = Vindex[t]
FW[sk,tk] = w
FW[tk,sk] = w
# The FW matrix has been initialized so that immediate distances
# are recorded and all other distances are initialized to infinity
# Use the Floyd-Warshall algorithm to calculate the 2D array of the
# shortest distance between every pair of cities.
nV = len(G.V)
for k in range(1,nV):
for i in range(nV):
for j in range(i+1,nV):
fkij = min(FW[i,j], FW[i,k-1]+FW[k-1,j])
FW[i,j] = fkij
FW[j,i] = fkij
return FW
|
|
FW = build_Floyd_Warshall(Atlas,Atlas_vindex,weights)
timeit("FW = build_Floyd_Warshall(Atlas,Atlas_vindex,weights)")
print 'The Floyd-Warshall Matrix'
print FW
print FW.str()
5 loops, best of 3: 81 ms per loop The Floyd-Warshall Matrix 32 x 32 dense matrix over Integer Ring (type 'print obj.str()' to see all of the entries) [ 0 168 170 534 352 159 300 584 362 240 452 379 458 91 240 577 554 418 97 407 125 628 203 352 246 386 459 506 204 413 388 476] [168 0 307 702 520 296 437 752 499 408 589 547 626 228 408 745 722 586 265 575 293 796 340 489 383 523 596 674 372 581 556 613] [170 307 0 586 407 147 288 639 350 351 440 490 513 79 292 629 665 529 267 459 236 687 191 340 172 312 385 558 374 524 440 402] [534 702 586 0 289 445 716 369 359 403 366 660 245 507 294 322 717 417 631 152 500 393 619 733 546 525 510 264 738 576 146 615] [352 520 407 289 0 266 537 232 297 114 387 371 106 328 115 405 428 128 397 282 227 325 440 460 367 463 448 261 556 287 143 553] [159 296 147 445 266 0 272 498 203 332 293 471 372 68 151 488 646 394 256 318 217 546 175 329 128 268 341 417 363 505 299 358] [300 437 288 716 537 272 0 769 475 481 501 620 643 209 422 741 795 659 397 589 366 817 97 470 202 342 415 688 504 654 570 432] [584 752 639 369 232 498 769 0 529 346 619 603 126 560 347 485 660 303 629 514 459 93 672 692 599 695 680 341 788 519 223 785] [362 499 350 359 297 203 475 529 0 397 90 642 403 271 182 330 711 425 459 207 388 573 378 532 306 166 151 404 566 570 326 256] [240 408 351 403 114 332 481 346 397 0 487 257 220 272 215 519 314 178 285 382 115 388 384 348 427 563 548 375 444 173 257 653] [452 589 440 366 387 293 501 619 90 487 0 732 493 361 272 240 801 515 549 214 478 663 404 622 299 163 149 411 656 660 416 253] [379 547 490 660 371 471 620 603 642 257 732 0 477 411 460 776 571 435 424 627 254 645 523 487 566 706 779 632 583 430 514 796] [458 626 513 245 106 372 643 126 403 220 493 477 0 434 221 361 534 234 503 388 333 219 546 566 473 569 554 217 662 393 99 659] [ 91 228 79 507 328 68 209 560 271 272 361 411 434 0 213 550 586 450 188 380 157 608 112 261 155 295 368 479 295 445 361 385] [240 408 292 294 115 151 422 347 182 215 272 460 221 213 0 337 529 243 337 167 206 395 325 439 252 348 333 266 444 388 148 438] [577 745 629 322 405 488 741 485 330 519 240 776 361 550 337 0 833 533 674 170 543 509 644 776 539 403 389 367 781 692 262 493] [554 722 665 717 428 646 795 660 711 314 801 571 534 586 529 833 0 492 599 696 429 702 698 662 741 877 862 689 758 487 571 967] [418 586 529 417 128 394 659 303 425 178 515 435 234 450 243 533 492 0 463 410 293 210 562 526 495 591 576 389 622 351 271 681] [ 97 265 267 631 397 256 397 629 459 285 549 424 503 188 337 674 599 463 0 504 170 673 300 403 343 483 556 603 301 458 485 573] [407 575 459 152 282 318 589 514 207 382 214 627 388 380 167 170 696 410 504 0 373 545 492 606 419 373 358 197 611 555 298 463] [125 293 236 500 227 217 366 459 388 115 478 254 333 157 206 543 429 293 170 373 0 503 269 233 312 452 525 472 329 288 354 542] [628 796 687 393 325 546 817 93 573 388 663 645 219 608 395 509 702 210 673 545 503 0 720 736 647 739 724 365 832 561 247 829] [203 340 191 619 440 175 97 672 378 384 404 523 546 112 325 644 698 562 300 492 269 720 0 373 105 245 318 591 407 557 473 335] [352 489 340 733 460 329 470 692 532 348 622 487 566 261 439 776 662 526 403 606 233 736 373 0 416 556 629 705 556 521 587 646] [246 383 172 546 367 128 202 599 306 427 299 566 473 155 252 539 741 495 343 419 312 647 105 416 0 140 213 518 450 600 400 230] [386 523 312 525 463 268 342 695 166 563 163 706 569 295 348 403 877 591 483 373 452 739 245 556 140 0 73 570 590 736 492 90] [459 596 385 510 448 341 415 680 151 548 149 779 554 368 333 389 862 576 556 358 525 724 318 629 213 73 0 555 663 721 477 163] [506 674 558 264 261 417 688 341 404 375 411 632 217 479 266 367 689 389 603 197 472 365 591 705 518 570 555 0 710 548 118 660] [204 372 374 738 556 363 504 788 566 444 656 583 662 295 444 781 758 622 301 611 329 832 407 556 450 590 663 710 0 617 592 680] [413 581 524 576 287 505 654 519 570 173 660 430 393 445 388 692 487 351 458 555 288 561 557 521 600 736 721 548 617 0 430 826] [388 556 440 146 143 299 570 223 326 257 416 514 99 361 148 262 571 271 485 298 354 247 473 587 400 492 477 118 592 430 0 582] [476 613 402 615 553 358 432 785 256 653 253 796 659 385 438 493 967 681 573 463 542 829 335 646 230 90 163 660 680 826 582 0] 5 loops, best of 3: 81 ms per loop The Floyd-Warshall Matrix 32 x 32 dense matrix over Integer Ring (type 'print obj.str()' to see all of the entries) [ 0 168 170 534 352 159 300 584 362 240 452 379 458 91 240 577 554 418 97 407 125 628 203 352 246 386 459 506 204 413 388 476] [168 0 307 702 520 296 437 752 499 408 589 547 626 228 408 745 722 586 265 575 293 796 340 489 383 523 596 674 372 581 556 613] [170 307 0 586 407 147 288 639 350 351 440 490 513 79 292 629 665 529 267 459 236 687 191 340 172 312 385 558 374 524 440 402] [534 702 586 0 289 445 716 369 359 403 366 660 245 507 294 322 717 417 631 152 500 393 619 733 546 525 510 264 738 576 146 615] [352 520 407 289 0 266 537 232 297 114 387 371 106 328 115 405 428 128 397 282 227 325 440 460 367 463 448 261 556 287 143 553] [159 296 147 445 266 0 272 498 203 332 293 471 372 68 151 488 646 394 256 318 217 546 175 329 128 268 341 417 363 505 299 358] [300 437 288 716 537 272 0 769 475 481 501 620 643 209 422 741 795 659 397 589 366 817 97 470 202 342 415 688 504 654 570 432] [584 752 639 369 232 498 769 0 529 346 619 603 126 560 347 485 660 303 629 514 459 93 672 692 599 695 680 341 788 519 223 785] [362 499 350 359 297 203 475 529 0 397 90 642 403 271 182 330 711 425 459 207 388 573 378 532 306 166 151 404 566 570 326 256] [240 408 351 403 114 332 481 346 397 0 487 257 220 272 215 519 314 178 285 382 115 388 384 348 427 563 548 375 444 173 257 653] [452 589 440 366 387 293 501 619 90 487 0 732 493 361 272 240 801 515 549 214 478 663 404 622 299 163 149 411 656 660 416 253] [379 547 490 660 371 471 620 603 642 257 732 0 477 411 460 776 571 435 424 627 254 645 523 487 566 706 779 632 583 430 514 796] [458 626 513 245 106 372 643 126 403 220 493 477 0 434 221 361 534 234 503 388 333 219 546 566 473 569 554 217 662 393 99 659] [ 91 228 79 507 328 68 209 560 271 272 361 411 434 0 213 550 586 450 188 380 157 608 112 261 155 295 368 479 295 445 361 385] [240 408 292 294 115 151 422 347 182 215 272 460 221 213 0 337 529 243 337 167 206 395 325 439 252 348 333 266 444 388 148 438] [577 745 629 322 405 488 741 485 330 519 240 776 361 550 337 0 833 533 674 170 543 509 644 776 539 403 389 367 781 692 262 493] [554 722 665 717 428 646 795 660 711 314 801 571 534 586 529 833 0 492 599 696 429 702 698 662 741 877 862 689 758 487 571 967] [418 586 529 417 128 394 659 303 425 178 515 435 234 450 243 533 492 0 463 410 293 210 562 526 495 591 576 389 622 351 271 681] [ 97 265 267 631 397 256 397 629 459 285 549 424 503 188 337 674 599 463 0 504 170 673 300 403 343 483 556 603 301 458 485 573] [407 575 459 152 282 318 589 514 207 382 214 627 388 380 167 170 696 410 504 0 373 545 492 606 419 373 358 197 611 555 298 463] [125 293 236 500 227 217 366 459 388 115 478 254 333 157 206 543 429 293 170 373 0 503 269 233 312 452 525 472 329 288 354 542] [628 796 687 393 325 546 817 93 573 388 663 645 219 608 395 509 702 210 673 545 503 0 720 736 647 739 724 365 832 561 247 829] [203 340 191 619 440 175 97 672 378 384 404 523 546 112 325 644 698 562 300 492 269 720 0 373 105 245 318 591 407 557 473 335] [352 489 340 733 460 329 470 692 532 348 622 487 566 261 439 776 662 526 403 606 233 736 373 0 416 556 629 705 556 521 587 646] [246 383 172 546 367 128 202 599 306 427 299 566 473 155 252 539 741 495 343 419 312 647 105 416 0 140 213 518 450 600 400 230] [386 523 312 525 463 268 342 695 166 563 163 706 569 295 348 403 877 591 483 373 452 739 245 556 140 0 73 570 590 736 492 90] [459 596 385 510 448 341 415 680 151 548 149 779 554 368 333 389 862 576 556 358 525 724 318 629 213 73 0 555 663 721 477 163] [506 674 558 264 261 417 688 341 404 375 411 632 217 479 266 367 689 389 603 197 472 365 591 705 518 570 555 0 710 548 118 660] [204 372 374 738 556 363 504 788 566 444 656 583 662 295 444 781 758 622 301 611 329 832 407 556 450 590 663 710 0 617 592 680] [413 581 524 576 287 505 654 519 570 173 660 430 393 445 388 692 487 351 458 555 288 561 557 521 600 736 721 548 617 0 430 826] [388 556 440 146 143 299 570 223 326 257 416 514 99 361 148 262 571 271 485 298 354 247 473 587 400 492 477 118 592 430 0 582] [476 613 402 615 553 358 432 785 256 653 253 796 659 385 438 493 967 681 573 463 542 829 335 646 230 90 163 660 680 826 582 0] |
Once the Floyd Warshall matrix has been constructed it is an easy matter to look up the shortest distance between any two cities.
Exercise 6: Complete the following routine, short_path_FW, that uses the Floyd-Warshall matrix to determine a path that has that shortest distance between a given pair of cities.
# Determine the shortest path from the start_city to the destination
# given the global vertex_list and FW matrix.
def short_path_FW(start_city, destination):
path = []
sk = Atlas_vindex[start_city]
dk = Atlas_vindex[destination]
min_distance = FW[sk,dk]
current_dist = 0
uk = sk
city = start_city
while uk != dk:
path.append(city)
neighbors = Atlas.Adj[city]
startDist = 1000000
for next_city in neighbors:
tmp = Atlas_vindex[next_city]
toTmp = FW[uk, tmp]
tmpToDest = FW[tmp, dk]
if(tmp == dk):
startDist = toTmp
vk = tmp
city = next_city
elif((toTmp+tmpToDest) < startDist):
vk = tmp
startDist = toTmp + tmpToDest
city = next_city
current_dist += FW[uk,vk]
uk = vk
path.append(city)
return (min_distance,path)
|
|
# An extremely simple test case
short_path_FW('Atlanta, GA', 'Augusta, GA')
(151, ['Atlanta, GA', 'Augusta, GA']) (151, ['Atlanta, GA', 'Augusta, GA']) |
The following block uses the preceeding Floyd Warshall matrix and the related shortest path algorithm, to find the shortest route from Wilmington, NC to Memphis, TN.
It then prints the distance, the path and the timing results.
print short_path_FW('Wilmington, NC', 'Memphis, TN')
timeit("short_path_FW('Wilmington, NC', 'Memphis, TN')")
(832, ['Wilmington, NC', 'Charlotte, NC', 'Asheville, NC', 'Knoxville, TN', 'Nashville, TN', 'Memphis, TN']) 625 loops, best of 3: 25.3 µs per loop (832, ['Wilmington, NC', 'Charlotte, NC', 'Asheville, NC', 'Knoxville, TN', 'Nashville, TN', 'Memphis, TN']) 625 loops, best of 3: 25.3 µs per loop |
Exercise 7. Using the preceeding Floyd Warshall matrix and the related shortest path algorithm, short_path_FW, find the shortest route from Daytona_Beach, FL to Lexington, KY.
Then print the distance, the path, and the timing results.
print short_path_FW('Daytona_Beach, FL', 'Lexington, KY')
timeit("short_path_FW('Daytona_Beach, FL', 'Lexington, KY')")
(826, ['Daytona_Beach, FL', 'Jacksonville, FL', 'Tifton, GA', 'Atlanta, GA', 'Knoxville, TN', 'Lexington, KY']) 625 loops, best of 3: 27.5 µs per loop (826, ['Daytona_Beach, FL', 'Jacksonville, FL', 'Tifton, GA', 'Atlanta, GA', 'Knoxville, TN', 'Lexington, KY']) 625 loops, best of 3: 27.5 µs per loop |
Exercise 8. Using the preceeding Floyd Warshall matrix and the related shortest path algorithm, short_path_FW, find the shortest route from Charleston, SC to Charleston, WV.
Then print the distance, the path, and the timing results.
print short_path_FW('Charleston, SC', 'Charleston, WV')
timeit("short_path_FW('Charleston, SC', 'Charleston, WV')")
(698, ['Charleston, SC', 'Columbia, SC', 'Asheville, NC', 'Knoxville, TN', 'Charleston, WV']) 625 loops, best of 3: 25.7 µs per loop (698, ['Charleston, SC', 'Columbia, SC', 'Asheville, NC', 'Knoxville, TN', 'Charleston, WV']) 625 loops, best of 3: 25.7 µs per loop |