# Dijkstra's algorithm
def get_min(D):
"""
returns the (value, key) pair that minimizes
the value within the dictionary D
this is linear (it would be faster if it were cleverer... maybe)
** ALSO removes the returned data from D **
"""
if len(D) == 0:
raise ValueError, "Call of getMin from {}"
min_value = 1.0e200 # good enough for now...
min_key = "no key"
for key in D:
val = D[key]
if val < min_value:
min_key = key
min_value = val
D.pop(min_key)
return min_value, min_key
def dijkstra(G,start,end=None):
"""
Find shortest paths from the start vertex to all
vertices nearer than or equal to the end.
If end is None, it will find the single-source shortest
paths to all vertices reachable from start.
The graph G should be a dictionary whose keys are the
source vertices and whose values are dictionaries of
destination vertices and costs. See test().
G[v][w] returns the distance from v to w.
Adapted from http://code.activestate.com/recipes/119466-dijkstras-algorithm-for-shortest-paths/
by David Eppstein, UC Irvine, 4 April 2002
... but different because this does not require support
code outside of Python's standard library (but it's slower)
"""
D = {} # dictionary of final distances
P = {} # dictionary of predecessors
Q = {} # our partially-explored nodes, not yet finalized
# we'll pay the linear cost of finding the min each time...
Q[start] = 0
while True:
if len(Q) == 0:
break # all vertices reached
dist, v = get_min(Q) # get next nearest node to expand
D[v] = dist # finalized distance
if v == end: break # found the one we wanted
for w in G[v]: # for each neighbor of v
vwLength = D[v] + G[v][w] # dist to w through v
if w in D:
if vwLength < D[w]:
raise ValueError, "Dijkstra: found better path to already-final vertex"
elif w not in Q or vwLength < Q[w]: # it's better!
Q[w] = vwLength # update best dist to w so far
P[w] = v # update w's predecessor
return (D,P)
def test1():
"""
test of shortest path on a known graph
the graph
"""
G = {'s':{'u':10, 'x':5},
'u':{'v':1, 'x':2},
'v':{'y':4},
'x':{'u':3, 'v':9, 'y':2},
'y':{'s':7, 'v':6}}
# the shortest path from 's' to 'v' should be 's','x','u','v' == 9
start = 's'
end = 'v'
D, P = dijkstra(G,start,end)
# D are all the distances (as far as 'v') (by vertex)
# P are all the predecessors (by vertex)
print "distances are", D
print "predecessors are", P
# get the path
path = []
while end != start:
path.append(end)
end = P[end]
path.append(start)
path.reverse()
print "path is", path
def binary_search(lo, hi, f):
"""
binary search adapted from
http://stackoverflow.com/questions/212358/binary-search-in-python
this one searches within the integers [lo,hi] to find the
largest value, mid, such that f(mid) is true
if no values work, lo is returned
"""
best = lo
while lo <= hi:
#print "lo,hi:", lo, hi
mid = (lo+hi)/2 # won't overflow in Python
if f(mid):
best = mid # mid did work
lo = mid+1
else:
hi = mid-1 # mid didn't work...
return best
def test2():
"""
test of binary search
"""
for answer in range(-1,1002):
if answer != binary_search(0, 1000, lambda x: x <= answer):
print "Failed for", answer
print "Done!"
def convex_hull(points):
"""Computes the convex hull of a set of 2D points.
Input: an iterable sequence of (x, y) pairs representing the points.
Output: a list of vertices of the convex hull in counter-clockwise order,
starting from the vertex with the lexicographically smallest coordinates.
Implements Andrew's monotone chain algorithm. O(n log n) complexity.
Taken from http://www.algorithmist.com/index.php/Monotone_Chain_Convex_Hull.py
"""
points = sorted(set(points)) # sort & remove duplicates
if len(points) <= 1: # trivial convex hull
return points
# 2D cross product of OA and OB vectors,
# i.e. z-component of their 3D cross product.
# Returns a positive value, if OAB makes a counter-clockwise turn,
# negative for clockwise turn, and zero if the points are collinear.
def cross(o, a, b):
return (a[0] - o[0]) * (b[1] - o[1]) - \
(a[1] - o[1]) * (b[0] - o[0])
# Build lower hull
lower = []
for p in points:
while len(lower) >= 2 and \
cross(lower[-2], lower[-1], p) <= 0: # need to retract?
lower.pop() # retract
lower.append(p) # else append the next point
# Build upper hull
upper = []
for p in reversed(points):
while len(upper) >= 2 and \
cross(upper[-2], upper[-1], p) <= 0: # need to retract?
upper.pop() # retract
upper.append(p) # else append the next point
# Concatenation of the lower and upper hulls gives the convex hull.
# Last point of each list is omitted
# because it is repeated at the beginning of the other list.
return lower[:-1] + upper[:-1]
def test3():
"""
Example: convex hull of a 10-by-10 grid.
"""
print " ", convex_hull([(i/10, i%10) for i in range(100)])
print "should be", [(0, 0), (9, 0), (9, 9), (0, 9)]