{{{id=1|
%hide
switch_uw_paren = [(-122.31059522108626, 47.655569012202584), (-122.31049329714369, 47.660643780526165), (-122.31082589106154, 47.659243706816177), (-122.3088195987184, 47.658372932358915), (-122.31036455111098, 47.657433491347746), (-122.31045038179946, 47.656459706766412), (-122.31167883352828, 47.656530166742648), (-122.31082052664357, 47.654564478399642), (-122.31092781500416, 47.653971866661763), (-122.31127113775807, 47.653538244056122), (-122.3106274075945, 47.652540898398406), (-122.31000513510304, 47.652222900125913), (-122.30957598166066, 47.652974529285707), (-122.30837435202199, 47.652895030559215), (-122.30882496313649, 47.653444292016928), (-122.31005877928334, 47.653733374674204), (-122.30887860731679, 47.654557251467686), (-122.3090073533495, 47.653964639647789), (-122.30947942213612, 47.65530884702877), (-122.30920047239857, 47.656566300026832), (-122.30649680571156, 47.660800947746885), (-122.30661482290822, 47.659529144245155), (-122.30771989302235, 47.659146151893808), (-122.30720490889149, 47.658777609431525), (-122.30647534803944, 47.658437969956985), (-122.30722636656361, 47.657845402179525), (-122.30827779249745, 47.657122749446771), (-122.30716199354725, 47.656559073371909), (-122.30780572371083, 47.656342273261274), (-122.30628222899037, 47.657195015170117), (-122.30585307554799, 47.657614154393244), (-122.30484456495839, 47.657614154393244), (-122.30530590490895, 47.658828193845075), (-122.30534882025319, 47.656956537903476), (-122.30581016020375, 47.656501260097102), (-122.30842799620228, 47.65579304228558), (-122.30693668799, 47.655366661623802), (-122.30775207953053, 47.654824647281991), (-122.30521470980244, 47.655251032369598), (-122.3064860768755, 47.654849941409729), (-122.30639488176899, 47.65422842500783), (-122.30582088903981, 47.654383804801803), (-122.3057833381136, 47.653914050522232), (-122.30634660200673, 47.653588833545498), (-122.30585843996602, 47.653234706089599), (-122.30766624884205, 47.651254438912922), (-122.30756968931752, 47.651724217117334), (-122.30691523031788, 47.651435123337805), (-122.30455488638478, 47.651839854181056), (-122.30503768400746, 47.652034991145463), (-122.30531663374501, 47.6522373546347), (-122.30487675146657, 47.652490307893501), (-122.30456561522084, 47.653682785324563), (-122.3036214776476, 47.653588833545449), (-122.30456561522084, 47.654253719424332), (-122.30447978453236, 47.654607839969849), (-122.30409354643422, 47.655619599724467), (-122.30333179907399, 47.655756908466095), (-122.30408281759816, 47.656147152391924), (-122.30421156363087, 47.657007124081218), (-122.30372876600819, 47.658127234034147), (-122.30285973028731, 47.659991621830194), (-122.30369657949996, 47.659265385662628), (-122.3045334287126, 47.660414351664201), (-122.30927557425093, 47.660345703462404)]

switch_path1_paren = [(-122.30766624884205, 47.651254438912922), (-122.30691523031788, 47.651435123337805), (-122.30756968931752, 47.651724217117334), (-122.30455488638478, 47.651839854181056), (-122.30503768400746, 47.652034991145463), (-122.31000513510304, 47.652222900125913), (-122.30531663374501, 47.6522373546347), (-122.30487675146657, 47.652490307893501), (-122.3106274075945, 47.652540898398406), (-122.30837435202199, 47.652895030559215), (-122.30957598166066, 47.652974529285707), (-122.30585843996602, 47.653234706089599), (-122.30882496313649, 47.653444292016928), (-122.31127113775807, 47.653538244056122), (-122.3036214776476, 47.653588833545449), (-122.30634660200673, 47.653588833545498), (-122.30456561522084, 47.653682785324563), (-122.31005877928334, 47.653733374674204), (-122.3057833381136, 47.653914050522232), (-122.3090073533495, 47.653964639647789), (-122.31092781500416, 47.653971866661763), (-122.30639488176899, 47.65422842500783), (-122.30456561522084, 47.654253719424332), (-122.30582088903981, 47.654383804801803), (-122.30887860731679, 47.654557251467686), (-122.31082052664357, 47.654564478399642), (-122.30447978453236, 47.654607839969849), (-122.30775207953053, 47.654824647281991), (-122.3064860768755, 47.654849941409729), (-122.30521470980244, 47.655251032369598), (-122.30947942213612, 47.65530884702877), (-122.30693668799, 47.655366661623802), (-122.31059522108626, 47.655569012202584), (-122.30409354643422, 47.655619599724467), (-122.30333179907399, 47.655756908466095), (-122.30842799620228, 47.65579304228558), (-122.30408281759816, 47.656147152391924), (-122.30780572371083, 47.656342273261274), (-122.31045038179946, 47.656459706766412), (-122.30581016020375, 47.656501260097102), (-122.31167883352828, 47.656530166742648), (-122.30716199354725, 47.656559073371909), (-122.30920047239857, 47.656566300026832), (-122.30534882025319, 47.656956537903476), (-122.30421156363087, 47.657007124081218), (-122.30827779249745, 47.657122749446771), (-122.30628222899037, 47.657195015170117), (-122.31036455111098, 47.657433491347746), (-122.30585307554799, 47.657614154393244), (-122.30484456495839, 47.657614154393244), (-122.30722636656361, 47.657845402179525), (-122.30372876600819, 47.658127234034147), (-122.3088195987184, 47.658372932358915), (-122.30647534803944, 47.658437969956985), (-122.30720490889149, 47.658777609431525), (-122.30530590490895, 47.658828193845075), (-122.30771989302235, 47.659146151893808), (-122.31082589106154, 47.659243706816177), (-122.30369657949996, 47.659265385662628), (-122.30661482290822, 47.659529144245155), (-122.30285973028731, 47.659991621830194), (-122.30927557425093, 47.660345703462404), (-122.3045334287126, 47.660414351664201), (-122.31049329714369, 47.660643780526165), (-122.30649680571156, 47.660800947746885)]


switch_path2_paren = [(-122.31049329714369, 47.660643780526165), (-122.30927557425093, 47.660345703462404), (-122.30649680571156, 47.660800947746885), (-122.3045334287126, 47.660414351664201), (-122.30285973028731, 47.659991621830194), (-122.30369657949996, 47.659265385662628), (-122.30372876600819, 47.658127234034147), (-122.30421156363087, 47.657007124081218), (-122.30408281759816, 47.656147152391924), (-122.30333179907399, 47.655756908466095), (-122.30409354643422, 47.655619599724467), (-122.30447978453236, 47.654607839969849), (-122.30456561522084, 47.654253719424332), (-122.30456561522084, 47.653682785324563), (-122.3036214776476, 47.653588833545449), (-122.30487675146657, 47.652490307893501), (-122.30455488638478, 47.651839854181056), (-122.30503768400746, 47.652034991145463), (-122.30531663374501, 47.6522373546347), (-122.30691523031788, 47.651435123337805), (-122.30766624884205, 47.651254438912922), (-122.30756968931752, 47.651724217117334), (-122.31000513510304, 47.652222900125913), (-122.3106274075945, 47.652540898398406), (-122.31127113775807, 47.653538244056122), (-122.31092781500416, 47.653971866661763), (-122.31082052664357, 47.654564478399642), (-122.31059522108626, 47.655569012202584), (-122.31167883352828, 47.656530166742648), (-122.31036455111098, 47.657433491347746), (-122.31082589106154, 47.659243706816177), (-122.30771989302235, 47.659146151893808), (-122.30661482290822, 47.659529144245155), (-122.30530590490895, 47.658828193845075), (-122.30484456495839, 47.657614154393244), (-122.30534882025319, 47.656956537903476), (-122.30581016020375, 47.656501260097102), (-122.30521470980244, 47.655251032369598), (-122.30582088903981, 47.654383804801803), (-122.3057833381136, 47.653914050522232), (-122.30634660200673, 47.653588833545498), (-122.30585843996602, 47.653234706089599), (-122.30837435202199, 47.652895030559215), (-122.30957598166066, 47.652974529285707), (-122.31005877928334, 47.653733374674204), (-122.30947942213612, 47.65530884702877), (-122.31045038179946, 47.656459706766412), (-122.3088195987184, 47.658372932358915), (-122.30456561522084, 47.653682785324563), (-122.30647534803944, 47.658437969956985), (-122.30585307554799, 47.657614154393244), (-122.30628222899037, 47.657195015170117), (-122.3064860768755, 47.654849941409729), (-122.30639488176899, 47.65422842500783), (-122.30882496313649, 47.653444292016928), (-122.3090073533495, 47.653964639647789), (-122.30887860731679, 47.654557251467686), (-122.30920047239857, 47.656566300026832), (-122.30827779249745, 47.657122749446771), (-122.30722636656361, 47.657845402179525), (-122.30716199354725, 47.656559073371909), (-122.30780572371083, 47.656342273261274), (-122.30693668799, 47.655366661623802), (-122.30775207953053, 47.654824647281991), (-122.30842799620228, 47.65579304228558)]


switch_path3_paren = [(-122.31082589106154, 47.659243706816177), (-122.31049329714369, 47.660643780526165), (-122.30927557425093, 47.660345703462404), (-122.30771989302235, 47.659146151893808), (-122.30720490889149, 47.658777609431525), (-122.30647534803944, 47.658437969956985), (-122.30722636656361, 47.657845402179525), (-122.30628222899037, 47.657195015170117), (-122.30585307554799, 47.657614154393244), (-122.30534882025319, 47.656956537903476), (-122.30581016020375, 47.656501260097102), (-122.30716199354725, 47.656559073371909), (-122.30780572371083, 47.656342273261274), (-122.30842799620228, 47.65579304228558), (-122.30920047239857, 47.656566300026832), (-122.30827779249745, 47.657122749446771), (-122.3088195987184, 47.658372932358915), (-122.31036455111098, 47.657433491347746), (-122.31045038179946, 47.656459706766412), (-122.31059522108626, 47.655569012202584), (-122.31082052664357, 47.654564478399642), (-122.31092781500416, 47.653971866661763), (-122.31127113775807, 47.653538244056122), (-122.3106274075945, 47.652540898398406), (-122.31000513510304, 47.652222900125913), (-122.30957598166066, 47.652974529285707), (-122.30882496313649, 47.653444292016928), (-122.3090073533495, 47.653964639647789), (-122.30887860731679, 47.654557251467686), (-122.30947942213612, 47.65530884702877), (-122.31005877928334, 47.653733374674204), (-122.30837435202199, 47.652895030559215), (-122.30756968931752, 47.651724217117334), (-122.30766624884205, 47.651254438912922), (-122.30691523031788, 47.651435123337805), (-122.30531663374501, 47.6522373546347), (-122.30503768400746, 47.652034991145463), (-122.30487675146657, 47.652490307893501), (-122.30455488638478, 47.651839854181056), (-122.30456561522084, 47.653682785324563), (-122.30456561522084, 47.654253719424332), (-122.30447978453236, 47.654607839969849), (-122.30521470980244, 47.655251032369598), (-122.30582088903981, 47.654383804801803), (-122.3057833381136, 47.653914050522232), (-122.30634660200673, 47.653588833545498), (-122.30585843996602, 47.653234706089599), (-122.30639488176899, 47.65422842500783), (-122.3064860768755, 47.654849941409729), (-122.30693668799, 47.655366661623802), (-122.30775207953053, 47.654824647281991), (-122.30409354643422, 47.655619599724467), (-122.30408281759816, 47.656147152391924), (-122.30333179907399, 47.655756908466095), (-122.30421156363087, 47.657007124081218), (-122.30484456495839, 47.657614154393244), (-122.30372876600819, 47.658127234034147), (-122.30369657949996, 47.659265385662628), (-122.30285973028731, 47.659991621830194), (-122.3045334287126, 47.660414351664201), (-122.30530590490895, 47.658828193845075), (-122.30661482290822, 47.659529144245155), (-122.30649680571156, 47.660800947746885), (-122.31167883352828, 47.656530166742648), (-122.3036214776476, 47.653588833545449)]


switch_path4_paren = [(-122.30691523031788, 47.651435123337805), (-122.30756968931752, 47.651724217117334), (-122.30766624884205, 47.651254438912922), (-122.30837435202199, 47.652895030559215), (-122.30882496313649, 47.653444292016928), (-122.3090073533495, 47.653964639647789), (-122.30887860731679, 47.654557251467686), (-122.30947942213612, 47.65530884702877), (-122.31059522108626, 47.655569012202584), (-122.31045038179946, 47.656459706766412), (-122.31036455111098, 47.657433491347746), (-122.30920047239857, 47.656566300026832), (-122.30827779249745, 47.657122749446771), (-122.30780572371083, 47.656342273261274), (-122.30716199354725, 47.656559073371909), (-122.30628222899037, 47.657195015170117), (-122.30585307554799, 47.657614154393244), (-122.30534882025319, 47.656956537903476), (-122.30581016020375, 47.656501260097102), (-122.30521470980244, 47.655251032369598), (-122.30447978453236, 47.654607839969849), (-122.30456561522084, 47.654253719424332), (-122.30456561522084, 47.653682785324563), (-122.3036214776476, 47.653588833545449), (-122.30487675146657, 47.652490307893501), (-122.30503768400746, 47.652034991145463), (-122.30531663374501, 47.6522373546347), (-122.30455488638478, 47.651839854181056), (-122.30585843996602, 47.653234706089599), (-122.30634660200673, 47.653588833545498), (-122.30639488176899, 47.65422842500783), (-122.30582088903981, 47.654383804801803), (-122.3057833381136, 47.653914050522232), (-122.3064860768755, 47.654849941409729), (-122.30693668799, 47.655366661623802), (-122.30775207953053, 47.654824647281991), (-122.30842799620228, 47.65579304228558), (-122.30722636656361, 47.657845402179525), (-122.30720490889149, 47.658777609431525), (-122.30771989302235, 47.659146151893808), (-122.30661482290822, 47.659529144245155), (-122.30647534803944, 47.658437969956985), (-122.30530590490895, 47.658828193845075), (-122.30484456495839, 47.657614154393244), (-122.30421156363087, 47.657007124081218), (-122.30408281759816, 47.656147152391924), (-122.30409354643422, 47.655619599724467), (-122.30333179907399, 47.655756908466095), (-122.30372876600819, 47.658127234034147), (-122.30369657949996, 47.659265385662628), (-122.30285973028731, 47.659991621830194), (-122.3045334287126, 47.660414351664201), (-122.30649680571156, 47.660800947746885), (-122.30927557425093, 47.660345703462404), (-122.31049329714369, 47.660643780526165), (-122.31082589106154, 47.659243706816177), (-122.3088195987184, 47.658372932358915), (-122.31167883352828, 47.656530166742648), (-122.31082052664357, 47.654564478399642), (-122.31092781500416, 47.653971866661763), (-122.31127113775807, 47.653538244056122), (-122.3106274075945, 47.652540898398406), (-122.31000513510304, 47.652222900125913), (-122.30957598166066, 47.652974529285707), (-122.31005877928334, 47.653733374674204)]


switch_path5_paren = [(-122.30691523031788, 47.651435123337805), (-122.30756968931752, 47.651724217117334), (-122.30766624884205, 47.651254438912922), (-122.30837435202199, 47.652895030559215), (-122.30882496313649, 47.653444292016928), (-122.3090073533495, 47.653964639647789), (-122.30887860731679, 47.654557251467686), (-122.30947942213612, 47.65530884702877), (-122.31059522108626, 47.655569012202584), (-122.31045038179946, 47.656459706766412), (-122.30920047239857, 47.656566300026832), (-122.30827779249745, 47.657122749446771), (-122.30780572371083, 47.656342273261274), (-122.30842799620228, 47.65579304228558), (-122.30775207953053, 47.654824647281991), (-122.30693668799, 47.655366661623802), (-122.3064860768755, 47.654849941409729), (-122.30639488176899, 47.65422842500783), (-122.30582088903981, 47.654383804801803), (-122.3057833381136, 47.653914050522232), (-122.30634660200673, 47.653588833545498), (-122.30585843996602, 47.653234706089599), (-122.30531663374501, 47.6522373546347), (-122.30503768400746, 47.652034991145463), (-122.30455488638478, 47.651839854181056), (-122.30487675146657, 47.652490307893501), (-122.3036214776476, 47.653588833545449), (-122.30456561522084, 47.653682785324563), (-122.30456561522084, 47.654253719424332), (-122.30447978453236, 47.654607839969849), (-122.30521470980244, 47.655251032369598), (-122.30581016020375, 47.656501260097102), (-122.30534882025319, 47.656956537903476), (-122.30585307554799, 47.657614154393244), (-122.30628222899037, 47.657195015170117), (-122.30716199354725, 47.656559073371909), (-122.30722636656361, 47.657845402179525), (-122.30720490889149, 47.658777609431525), (-122.30771989302235, 47.659146151893808), (-122.30661482290822, 47.659529144245155), (-122.30647534803944, 47.658437969956985), (-122.30530590490895, 47.658828193845075), (-122.30484456495839, 47.657614154393244), (-122.30421156363087, 47.657007124081218), (-122.30408281759816, 47.656147152391924), (-122.30409354643422, 47.655619599724467), (-122.30333179907399, 47.655756908466095), (-122.30372876600819, 47.658127234034147), (-122.30369657949996, 47.659265385662628), (-122.30285973028731, 47.659991621830194), (-122.3045334287126, 47.660414351664201), (-122.30649680571156, 47.660800947746885), (-122.30927557425093, 47.660345703462404), (-122.31049329714369, 47.660643780526165), (-122.31082589106154, 47.659243706816177), (-122.3088195987184, 47.658372932358915), (-122.31036455111098, 47.657433491347746), (-122.31167883352828, 47.656530166742648), (-122.31082052664357, 47.654564478399642), (-122.31092781500416, 47.653971866661763), (-122.31127113775807, 47.653538244056122), (-122.3106274075945, 47.652540898398406), (-122.31000513510304, 47.652222900125913), (-122.30957598166066, 47.652974529285707), (-122.31005877928334, 47.653733374674204)]


street_boundary = [(47.66118198469434,-122.31192827224731),(47.652813588135544,-122.31205701828003),(47.65054420627862,-122.30733633041382),(47.6519318654979,-122.3033881187439),(47.661196436723344,-122.30089902877807),(47.66118198469434,-122.31192827224731)]

switch_street_boundary = [(-122.31192827224731, 47.661181984694338), (-122.31205701828003, 47.652813588135544), (-122.30733633041382, 47.650544206278617), (-122.3033881187439, 47.6519318654979), (-122.30089902877808, 47.661196436723344), (-122.31192827224731, 47.661181984694338)]

def dist(P,Q):
    '''calculate the distance between two points.'''
    d = sqrt((P[1]-Q[1])**2+(P[0]-Q[0])**2)
    return d
        
def in_order_tour(L):
    ''' Returns the total distance of a tour to each point traveled in order from first to last.'''
    tour_dist = []
    for n in range(1,len(L)):
        distn = dist(L[n-1],L[n])
        tour_dist.append(distn)
    return sum(tour_dist)

def closest_point(P,L):
    ''' Returns the closest point to P, from the list of points L.'''
    closest_point = L[0]
    for x in range(1,len(L)):
        if dist(P,L[x])<dist(P,closest_point):
            closest_point = L[x]
    return closest_point

def closest_point_tour(P,L):
    '''Returns a tour using the closest point to your current point.'''
    # Requires a starting point P
    # Also prints the path used to yield the distance returned.
    L2 = L[:]
    L2.append(P)
    tour_points = [P]
    L2.remove(P)
    while len(L2)>0:
        td = len(tour_points)
        a = tour_points[td-1]
        n = closest_point(a,L2)
        tour_points.append(n)
        L2.remove(n)
    return tour_points

def shortest_closest_point_tour(L):
    '''Returns the shortest path from closest_point_tour(P,L) by comparing all possible starting points P.'''
    L2 = L[:]
    shortest_path = in_order_tour(L2)
    start_point = L2[0]
    for x in range(len(L2)):
        if closest_point_tour(L2[x],L2)<shortest_path:
            shortest_path = closest_point_tour(L2[x],L2)
            start_point = L2[x]
    print 'Distance in degrees:', shortest_path, start_point

def graph_path(L):
    points_graph = point(L,color='black',size=25)
    path_graph = line(L,color='red')
    start_point = text('Start',L[0],color='green',fontsize=12,vertical_alignment='top')
    end_point = text('End',L[len(L)-1],color='green',fontsize=12,vertical_alignment='top')
    streets = line(switch_street_boundary,color='blue',thickness=2)
    street1 = text('15th Ave. NE',(-122.31205701828003,47.65730869671061),color='black',fontsize=12,horizontal_alignment='left')
    street2 = text('NE 45th St.',(-122.30645656585693,47.661254244799366),color='black',fontsize=12,vertical_alignment='top')
    street3 = text('Montlake Blvd.',(-122.30203628540039,47.65613798222676),color='black',fontsize=12,horizontal_alignment='right')
    street4 = text('NE Pacific St.',(-122.31057643890381,47.652004138405346),color='black',fontsize=12,vertical_alignment='bottom')
    street5 = text('NE Pacific Pl.',(-122.30538368225097,47.650732120623),color='black',fontsize=12,vertical_alignment='bottom')
    show(plot(points_graph)+plot(path_graph)+start_point+end_point+streets+street1+street2+street3+street4+street5,axes=false)
    print "Total Distance:",in_order_tour(L)*69.047,"miles"
    print "Total Distance:",in_order_tour(L),"degrees"
///
}}}

{{{id=3|
graph_path(switch_path1_paren)
///
<html><font color='black'><img src='cell://sage0.png'></font></html>
Total Distance: 14.7350627986609 miles
Total Distance: 0.213406271071313 degrees
}}}

{{{id=4|
graph_path(switch_path2_paren)
///
<html><font color='black'><img src='cell://sage0.png'></font></html>
Total Distance: 6.01658542376526 miles
Total Distance: 0.0871375356462303 degrees
}}}

{{{id=5|
graph_path(switch_path3_paren)
///
<html><font color='black'><img src='cell://sage0.png'></font></html>
Total Distance: 5.54990988679737 miles
Total Distance: 0.0803787258939182 degrees
}}}

{{{id=6|
graph_path(switch_path4_paren)
///
<html><font color='black'><img src='cell://sage0.png'></font></html>
Total Distance: 4.84542957735968 miles
Total Distance: 0.0701758161449401 degrees
}}}

{{{id=7|
graph_path(switch_path5_paren)
///
<html><font color='black'><img src='cell://sage0.png'></font></html>
Total Distance: 4.60266319654149 miles
Total Distance: 0.0666598577279461 degrees
}}}

{{{id=8|
%hide
@interact
def graph_closest_point_path(start_point=(0..len(switch_uw_paren)), L=input_box(default=switch_uw_paren)):
  try:
    chosen_path = closest_point_tour(L[start_point],L)
    chosen_path_graph = line(chosen_path,color='red')
    chosen_path_points = point(chosen_path,color='black',size=20)
    interact_start_point = text('Start',chosen_path[0],color='green',fontsize=12,vertical_alignment='top')
    interact_end_point = text('End',chosen_path[len(L)],color='green',fontsize=12,vertical_alignment='top')
    streets = line(switch_street_boundary,color='blue',thickness=2)
    street1 = text('15th Ave. NE',(-122.31205701828003,47.65730869671061),color='black',fontsize=12,horizontal_alignment='left')
    street2 = text('NE 45th St.',(-122.30645656585693,47.661254244799366),color='black',fontsize=12,vertical_alignment='top')
    street3 = text('Montlake Blvd.',(-122.30203628540039,47.65613798222676),color='black',fontsize=12,horizontal_alignment='right')
    street4 = text('NE Pacific St.',(-122.31057643890381,47.652004138405346),color='black',fontsize=12,vertical_alignment='bottom')
    street5 = text('NE Pacific Pl.',(-122.30538368225097,47.650732120623),color='black',fontsize=12,vertical_alignment='bottom')
    show(plot(chosen_path_graph)+plot(chosen_path_points)+interact_start_point+interact_end_point+streets+street1+street2+street3+street4+street5, axes=False)
    print 'Total Distance:',in_order_tour(chosen_path)*69.047,'miles'
    print 'Total Distance:',in_order_tour(chosen_path),'miles'
  except:
    print "..."
///
}}}

{{{id=10|

///
}}}