# 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)]