CIty Data Python

def parse_city(line):
    "Parse a line of data, as in http://www.realestate3d.com/gps/latlong.htm , and return a city code and long-lat"
    code, lat, long, name = line.split(None, 3)
    cityname, state = name.split(',')
    scode=code[1:-1]
    return scode, (float(long), float(lat))

UScityData = map(parse_city, """
[TCL]  33.23   87.62  Tuscaloosa,AL
[PHX]  33.43  112.02  Phoenix,AZ
[PGA]  36.93  111.45  Page,AZ
[TUS]  32.12  110.93  Tucson,AZ
[LIT]  35.22   92.38  Little Rock,AR
[SFO]  37.62  122.38  San Francisco,CA
[LAX]  33.93  118.40  Los Angeles,CA
[SAC]  38.52  121.50  Sacramento,CA
[SAN]  32.73  117.17  San Diego,CA
[SBP]  35.23  120.65  San Luis Obi,CA
[EKA]  41.33  124.28  Eureka,CA
[SJC]  37.37  121.92  San Jose,CA
[DEN]  39.75  104.87  Denver,CO
[DRO]  37.15  107.75  Durango,CO
[HVN]  41.27   72.88  New Haven,CT
[DOV]  39.13   75.47  Dover,DE
[DCA]  38.85   77.04  Washington/Natl,DC
[MIA]  25.82   80.28  Miami Intl,FL
[TPA]  27.97   82.53  Tampa Intl,FL
[JAX]  30.50   81.70  Jacksonville,FL
[TLH]  30.38   84.37  Tallahassee,FL
[ATL]  33.65   84.42  Atlanta,GA
[BOI]  43.57  116.22  Boise,ID
[CHI]  41.90   87.65  Chicago,IL
[IND]  39.73   86.27  Indianapolis,IN
[DSM]  41.53   93.65  Des Moines,IA
[ICT]  37.65   97.43  Wichita,KS
[LEX]  38.05   85.00  Lexington,KY
[NEW]  30.03   90.03  New Orleans,LA
[BOS]  42.37   71.03  Boston,MA
[PWM]  43.65   70.32  Portland,ME
[BGR]  44.80   68.82  Bangor,ME
[DET]  42.42   83.02  Detroit,MI
[STC]  45.55   94.07  St Cloud,MN
[MIN]  44.98   93.26  Minneapolis,MN
[DLH]  46.83   92.18  Duluth,MN
[STL]  38.75   90.37  St Louis,MO
[JAN]  32.32   90.08  Jackson,MS
[BIL]  45.80  108.53  Billings,MT
[BTM]  45.95  112.50  Butte,MT
[RDU]  35.87   78.78  Raleigh-Durh,NC
[INT]  36.13   80.23  Winston-Salem,NC
[OMA]  41.30   95.90  Omaha/Eppley,NE
[LAS]  36.08  115.17  Las Vegas,NV
[EWR]  40.70   74.17  Newark Intl,NJ
[ABQ]  35.05  106.60  Albuquerque,NM
[SAF]  35.62  106.08  Santa Fe,NM
[LRU]  32.30  106.77  Las Cruces,NM
[NYC]  40.77   73.98  New York,NY
[BUF]  42.93   78.73  Buffalo,NY
[ALB]  42.75   73.80  Albany,NY
[FAR]  46.90   96.80  Fargo,ND
[BIS]  46.77  100.75  Bismarck,ND
[CVG]  39.05   84.67  Cincinnati,OH
[COL]  39.98  82.98   Columbus, OH
[CLE]  41.42   81.87  Cleveland,OH
[OKC]  35.40   97.60  Oklahoma Cty,OK
[PDX]  45.60  122.60  Portland,OR
[MFR]  42.37  122.87  Medford,OR
[PIT]  40.35   79.93  Pittsburgh,PA
[PVD]  41.73   71.43  Providence,RI
[CHS]  32.90   80.03  Charleston,SC
[MEM]  35.05   90.00  Memphis,TN
[DAL]  32.90   97.03  Dallas,TX
[LBB]  33.65  101.82  Lubbock,TX
[IAH]  29.97   95.35  Houston,TX
[SAT]  29.53   98.47  San Antonio,TX
[ABI]  32.42   99.68  Abilene,TX
[ELP]  31.79  106.42  El Paso, TX
[SLC]  40.78  111.97  Salt Lake Ct,UT
[MPV]  44.20   72.57  Montpelier,VT
[RIC]  37.50   77.33  Richmond,VA
[SEA]  47.45  122.30  Seattle,WA
[ALW]  46.10  118.28  Walla Walla,WA
[GRB]  44.48   88.13  Green cityBay,WI
[MKE]  42.95   87.90  Milwaukee,WI
[CYS]  41.15  104.82  Cheyenne,WY
[SHR]  44.77  106.97  Sheridan,WY
[MAD]  43.07  89.400  Madison, WI
[FLG]  35.20  111.63  Flagstaff, AZ
[KAN]  39.09   94.57 Kansas City, MO
[LOU]  38.25   85.76  Louisville, KY
[PHI]  39.95 75.16    Philadelphia, PA
[NAS]  36.16  86.78    Nashville, TN
[KNO]  35.97 83.94     Knoxville, TN
[TAM]   27.97  82.46  Tampa, TN
[PRO]   41.82 71.42  Providence, RI
""".strip().splitlines())

#print UScityData

cityhash={ code : loc for (code,loc) in UScityData}
#print sorted(cityhash)
#print cityhash
print cityhash['CVG'] # (84.67, 39.05)

import math
def s_distance(loc1, loc2):
    (long1,lat1)= cityhash[loc1]
    (long2,lat2)= cityhash[loc2]
    degrees_to_radians = math.pi/180.0
    phi1 = (90.0 - lat1)*degrees_to_radians
    phi2 = (90.0 - lat2)*degrees_to_radians
    theta1 = long1*degrees_to_radians
    theta2 = long2*degrees_to_radians
    cos = (math.sin(phi1)*math.sin(phi2)*math.cos(theta1 - theta2) +
           math.cos(phi1)*math.cos(phi2))
    arc = math.acos( cos )
    return arc * 3960

print "Distance from CVG to LEX"
print s_distance('CVG','LEX')


def parse_roads(line):
    city1, city2 = line.split(',')
    return city1.strip(), city2.strip()

hiways = map(parse_roads, """
  MKE,CHI
  MKE, MAD
  MAD, CHI
  SEA,BTM
  SEA, PDX
  SEA, ALW
  PDX, SFO
  PDX, ALW
  ALW, SLC
  SFO, SLC
  SLC, LAX
  LAX, SAN
  SAN, TUS
  LAX, PHX
  TUS, PHX
  LAX, FLG
  FLG, PHX
  FLG, ABQ
  ABQ, ELP
  ELP, DAL
  ELP, SAT
  SAT, IAH
  IAH, DAL
  DAL, OKC
  ABQ, OKC
  ABQ, DEN
  SLC, DEN
  DEN, LAX
  DEN, CYS
  CYS, SLC
  CYS, BIL
  BIL, BTM
  BIL, FAR
  OKC, KAN
  DEN, KAN
  KAN, OMA
  DEN, OMA
  OMA, CHI
  OMA, FAR
  FAR, MIN
  MIN, CHI
  CHI, STL
  STL, KAN
  CHI, DET
  CHI ,IND
  IND, STL
  IND, LOU
  LOU, LEX
  IND, CVG
  CVG, LOU
  CVG, LEX
  STL, LOU
  CVG, COL
  COL, CLE
  CLE, BUF
  CLE, PIT
  CVG, PIT
  PIT, BUF
  PIT, PHI
  PHI, NYC
  PHI, DCA
  DCA, ATL
  ATL, NEW
  NEW, IAH
  NEW, MEM
  MEM, OKC
  MEM, STL
  MEM, NAS
  NAS, LOU
  LEX, KNO
  NAS, KNO
  KNO, ATL
  ATL, TAM
  ATL, NEW
  ATL, JAX
  JAX, MIA
  JAX, DCA
  ATL, DCA
  KNO, DCA
  DCA, PHI
  NYC, ALB
  BUF, ALB
  ALB, BOS
  NYC, BOS
  BOS, PRO
  NYC, PRO
""".strip().splitlines())

#print "Distance ", hiways[0]
#print s_distance(hiways[0][0],hiways[0][1])

#Test road distances
#for e in hiways:
#    print e, s_distance(e[0],e[1])

min=1000
minroad = 0
for e in hiways:
    if s_distance(e[0],e[1]) < min :
        min = s_distance(e[0],e[1])
        minroad = e
print minroad, min
"""
from math import *

def dist(lat1,lon1,lat2,lon2):
    lat1=(90.0-lat1)*pi/180
    lat2=(90.0-lat2)*pi/180
    lon1=lon1*pi/180
    lon2=lon2*pi/180
    return 3963.189 * acos(sin(lat1)*cos(lon1)*sin(lat2)*cos(lon2)+
     sin(lat1)*sin(lon1)*sin(lat2)*sin(lon2)+cos(lat1)*cos(lat2))

def dist2(lat1,lon1,lat2,lon2):
    dlon = (lon2 - lon1)*pi/180
    dlat = (lat2 - lat1)*pi/180
    a = (sin(dlat/2))**2 + cos(lat1) * cos(lat2) * (sin(dlon/2))**2
    c = 2 * asin(min(1,sqrt(a)))
    R=3963.189
    d = R * c
    return d

cities= [['Akron-Canton',40,55,81,26],['Ashtabula',41,51,80,48],
['Athens',39,20,82,6],
['BowlingGreen',41,23,83,38],
['Cambridge',40,4,81,35],
['Chillicothe',39,21,83,0],
['Cincinnati',39,9,84,31],
['Cleveland',41,24,81,51],
['Columbus',40,0,82,53],
['Dayton',39,54,84,13],
['Defiance',41,17,84,23],
['Findlay',41,1,83,40],
['Fremont',41,20,83,7],
['Hamilton',39,24,84,35],
['Lancaster',39,44,82,38],
['Lima',40,42,84,2],
['Mansfield',40,49,82,31],
['Marion',40,36,83,10],
['Middletown',39,31,84,25],
['Newark',40,1,82,28],
['Norwalk',41,16,82,37],
['Portsmouth',38,45,82,55],
['Sandusky',41,27,82,43],
['Springfield',39,50,83,50],
['Steubenville',40,23,80,38],
['Toledov',41,36,83,48],
['Warren',41,20,80,51],
['Wooster',40,47,81,55],
['Youngstown',41,16,80,40],
['Zanesville',39,57,81,54]]

distmat=[ \
 [   0,  72, 115, 119,  59, 136, 203,  39,  99, 162, 155, 116,  92, 196, 103, 136,  57,  93, 184,  82,  66, 169,  76, 146,  55, 131,  41,  26,  46,  71 ],
 [  72,   0, 186, 150, 129, 207, 270,  62, 168, 223, 189, 159, 125, 261, 175, 185, 114, 150, 249, 153, 102, 241, 102, 211, 101, 155,  35,  93,  40, 143 ],
 [ 115, 186,   0, 163,  57,  48, 130, 143,  62, 119, 180, 142, 148, 132,  39, 139, 104, 104, 124,  51, 136,  59, 149,  98, 106, 180, 153, 100, 153,  43 ],
 [ 119, 150, 163,   0, 140, 144, 161,  92, 103, 107,   9,  25,  27, 146, 125,  51,  70,  59, 135, 112,  53, 186,  47, 107, 171,  17, 144,  98, 154, 134 ],
 [  59, 129,  57, 140,   0,  90, 168,  93,  69, 140, 169, 127, 118, 166,  60, 136,  71,  91, 155,  46,  99, 115, 112, 120,  54, 157,  95,  52,  95,  18 ],
 [ 136, 207,  48, 144,  90,   0,  82, 154,  45,  75, 152, 120, 137,  84,  32, 108, 104,  86,  76,  54, 134,  41, 146,  55, 144, 161, 177, 114, 180,  71 ],
 [ 203, 270, 130, 161, 168,  82,   0, 209, 105,  54, 147, 136, 168,  17, 108, 110, 156, 123,  25, 124, 177,  90, 185,  59, 223, 173, 245, 178, 250, 150 ],
 [  39,  62, 143,  92,  93, 154, 209,   0, 110, 161, 131,  98,  65, 199, 122, 123,  53,  88, 187, 101,  40, 191,  45, 150,  94, 101,  52,  42,  62, 100 ],
 [  99, 168,  62, 103,  69,  45, 105, 110,   0,  71, 118,  81,  93,  99,  22,  77,  59,  44,  88,  22,  88,  86, 100,  51, 121, 120, 141,  74, 145,  52 ],
 [ 162, 223, 119, 107, 140,  75,  54, 161,  71,   0,  96,  82, 114,  39,  84,  56, 109,  73,  28,  93, 126, 105, 132,  20, 192, 119, 202, 135, 209, 122 ],
 [ 155, 189, 180,  39, 169, 152, 147, 131, 118,  96,   0,  41,  65, 130, 141,  44, 102,  79, 122, 133,  91, 191,  87, 104, 205,  37, 183, 133, 193, 159 ],
 [ 116, 159, 142,  25, 127, 120, 136,  98,  81,  82,  41,   0,  36, 121, 104,  29,  61,  38, 111,  93,  57, 161,  57,  82, 164,  40, 148,  92, 157, 118 ],
 [  92, 125, 148,  27, 118, 137, 168,  65,  93, 114,  65,  36,   0, 154, 113,  64,  47,  50, 143,  97,  26, 179,  22, 110, 145,  39, 117,  73, 127, 115 ],
 [ 196, 261, 132, 146, 166,  84,  17, 199,  99,  39, 130, 121, 154,   0, 106,  94, 146, 111,  12, 120, 165, 100, 172,  49, 220, 157, 237, 170, 243, 147 ],
 [ 103, 175,  39, 125,  60,  32, 108, 122,  22,  84, 141, 104, 113, 106,   0,  99,  75,  66,  96,  21, 106,  69, 118,  64, 115, 142, 145,  81, 148,  41 ],
 [ 136, 185, 139,  51, 136, 108, 110, 123,  77,  56,  44,  29,  64,  94,  99,   0,  79,  46,  84,  95,  83, 147,  86,  60, 180,  63, 171, 111, 180, 123 ],
 [  57, 114, 104,  70,  71, 104, 156,  53,  59, 109, 102,  61,  47, 146,  75,  79,   0,  37, 134,  55,  31, 144,  45,  97, 103,  85,  93,  31, 101,  68 ],
 [  93, 150, 104,  59,  91,  86, 123,  88,  44,   3,  79,  38,  50, 111,  66,  46,  37,   0,  99,  54,  54, 128,  63,  63, 134,  76, 131,  66, 138,  80 ],
 [ 184, 249, 124, 135, 155,  76,  25, 187,  88,  28, 122, 111, 143,  12,  96,  84, 134,  99,   0, 109, 153,  96, 160,  38, 209, 147, 225, 158, 231, 137 ],
 [  82, 153,  51, 112,  46,  54, 124, 101,  22,  93, 133,  93,  97, 120,  21,  95,  55,  54, 109,   0,  86,  90, 100,  73, 100, 129, 124,  60, 128,  30 ],
 [  66, 102, 136,  53,  99, 134, 177,  40,  88, 126,  91,  57,  26, 165, 106,  83,  31,  54, 153,  86,   0, 174,  13, 117, 120,  65,  91,  49, 101,  98 ],
 [ 169, 241,  59, 186, 115,  41,  90, 191,  86, 105, 191, 161, 179, 100,  69, 147, 144, 128,  96,  90, 174,   0, 187,  89, 166, 202, 209, 150, 210,  99 ],
 [  76, 102, 149,  47, 112, 146, 185,  45, 100, 132,  87,  57,  22, 172, 118,  86,  45,  63, 160, 100,  13, 187,   0, 126, 131,  57,  97,  62, 107, 112 ],
 [ 146, 211,  98, 107, 120,  55,  59, 150,  51,  20, 104,  82, 110,  49,  64,  60,  97,  63,  38,  73, 117,  89, 126,   0, 173, 122, 187, 120, 193, 102 ],
 [  55, 101, 106, 171,  54, 144, 223,  94, 121, 192, 205, 164, 145, 220, 115, 180, 103, 134, 209, 100, 120, 166, 131, 173,   0, 185,  66,  72,  61,  73 ],
 [ 131, 155, 180,  17, 157, 161, 173, 101, 120, 119,  37,  40,  39, 157, 142,  63,  85,  76, 147, 129,  65, 202,  57, 122, 185,   0, 154, 113, 164, 151 ],
 [  41,  35, 153, 144,  95, 177, 245,  52, 141, 202, 183, 148, 117, 237, 145, 171,  93, 131, 225, 124,  91, 209,  97, 187,  66, 154,   0,  67,  10, 110 ],
 [  26,  93, 100,  98,  52, 114, 178,  42,  74, 135, 133,  92,  73, 170,  81, 111,  31,  66, 158,  60,  49, 150,  62, 120,  72, 113,  67,   0,  73,  57 ],
 [  46,  40, 153, 154,  95, 180, 250,  62, 145, 209, 193, 157, 127, 243, 148, 180, 101, 138, 231, 128, 101, 210, 107, 193,  61, 164,  10,  73,   0, 111 ],
 [  71, 143,  43, 134,  18,  71, 150, 100,  52, 122, 159, 118, 115, 147,  41, 123,  68,  80, 137,  30,  98,  99, 112, 102,  73, 151, 110,  57, 111,   0 ] ]

"""
cities =[['a'],['b'],['c']]
distmat = [[0,1,2],
           [1,0,4],
           [2,4,0] ]
"""

class city_class:
   def __init__(self, cityName, index, distanceList ):
      self.name = cityName
      self.index = index
      self._distance = distanceList
      self.maxRadius = 0

   def pr( self ):
      print self.name, self.index
   def distance(self, city ):
      "QUICK LOOKUP"
      return self._distance[ city.index ]


class greedy_class(city_class):
   def __init__(self, cityList, distanceMatrix, locList=[] ):
      self.cityClassList = [ city_class(cityList[x],x,distanceMatrix[x] ) \
                             for x in range(len(cityList)) ]
      self.locList = locList

   def pr( self ):
      print "CITY LIST:"
      for city in self.cityClassList:
         city.pr()
      print "LOCATION LIST:"
      for city in self.locList:
         city.pr()

   def maxRadius(self, city):
      " Find the farthest radius for this city "
      max_radius = 0
      max_index = -1
      for city2 in self.cityClassList:
         thisDistance = city.distance( city2 )
         if thisDistance > max_radius:
            isMaxDistance = 1
            for city3 in self.locList:
               if city3.distance(city2) > thisDistance:
                  isMaxDistance = 0
                  break
            if isMaxDistance == 1:
               max_radius = thisDistance
               max_index = city2.index
      city.maxRadius = max_radius
      return max_radius


   def process( self, K ):
      """ Ireratively remove the cities with the largest radius, add to
          location list as most effective (distribution) points """
      for iteration in range(K):
	 print "Iteration ",iteration
         greatest_city = self.cityClassList[0]
         greatest_radius = self.maxRadius( self.cityClassList[0] )
         for city in self.cityClassList[1:]:
            this_radius = self.maxRadius( city )
            if this_radius > greatest_radius:
                    greatest_radius = this_radius
                    greatest_city = city
         #early exit if no more good picks are to be had:
         if greatest_radius > 0 :
            self.locList.append( greatest_city )
            self.cityClassList.remove(greatest_city)
         else:
            return self.locList
      return self.locList




def main():
   print "MAIN"
   cityList = [ cities[x][0] for x in range(len(cities)) ]
   A = greedy_class( cityList, distmat )
   #A.pr()
   locList = A.process(5)
   for item in locList:
      print item.name


if __name__ == '__main__':
   main()