//
you're reading...
Uncategorized

A Network Dataset Project for Modeling US Interstate Highway System using Python

I wanted to motivate the learning of algorithms by linking them to some real world applications. The application area is logistics and the modeling of InterCity transit costs and distances. Here are some details of a programming assignment I gave to my Algorithms class Fall 2014.
Programming project. Using the data set and starter code below you will answer the following questions. Spoiler Note: the solutions are embedded at bottom.

a) Define the dilation between a pair of cities as the ratio of the network distance
divided by the spherical distance. Determine the city that has minimum dilation with Cincinnati. Calculate the dilation for every city with Cincinnati and produce a list of cites ordered by their dilation with CVG.

b) The eccentricity e(v) of a graph vertex v in a connected graph G is the maximum network distance between v and any other vertex u of G. Determine the city that has minimum eccentricity. Produce a list of cites ordered by their
eccentricity value.

c) Determine the unique clustering of cities that corresponds to the 10 clusters of
maximum separation. List the cities in each of these clusters.

# We start with a function to parse each line of our dataset:

def parse_city(line):
  code, lat, long, name = line.split(None, 3)
  cityname, state = name.split(',')
  scode=code[1:-1]
  return scode, (float(long), float(lat))

# Our city data is embedded in function that maps the line parser to each line of data

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,NE
[LAS] 36.08 115.17 Las Vegas,NV
[EWR] 40.70 74.17 Newark,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())




# Our aim is to study functions that give us transit costs for each pair of cities. So we first turn to making the city to location function by using a hash table that has (key,value) pairs using citycodes for keys and citylocaton as values.


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

# We write a function that calculates the spherical (crow-fly) milage distance between pairs of cities using long,lat data #

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 in miles"
print s_distance('CVG','LEX')


# We will now parse each line of our route dataset

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 "Spherical Distance between two cities", 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])


#Find nearest pair of cities that share a route 
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


#Create the graph using adjacency lists/dicts
G={}
for e in hiways:
 if e[0] in G.keys():
   G[e[0]] = G[e[0]] + [ e[1] ]
 else:
   G[e[0]] =[e[1]]
 
 if e[1] in G.keys():
   G[e[1]]= G[e[1]] + [ e[0] ]
 else:
   G[e[1]] =[e[0]]


#An alternative in which store edges and weights together
for e  in  hiways:
 if e[0] in G.keys():
   G[e[0]][e[1]] = s_distance(e[0],e[1])
 else:
   G[e[0]]={ e[1] : s_distance(e[0],e[1])}
 
 if e[1] in G.keys():
   G[e[1]][e[0]] = s_distance(e[0],e[1])
 else:
   G[e[1]] ={e[0]: s_distance(e[0],e[1])}



def BreadthFirstLevels(G,root):
 visited = set()
 currentLevel = [root]
 visited.add(root)
 while currentLevel:
   nextLevel = set()
   for v in currentLevel:
     for w in G[v]:
        if w not in visited:
           nextLevel.add(w)
           visited.add(w)
   yield nextLevel
   currentLevel = nextLevel


i=1
for l in BreadthFirstLevels(G, 'CVG'):
  print "LEVEL:",i
  print l
  i+=1
 
"""
LEVEL: 1
set(['IND', 'LEX', 'PIT', 'COL', 'LOU'])
LEVEL: 2
set(['KNO', 'PHI', 'STL', 'CHI', 'NAS', 'CLE', 'BUF'])
LEVEL: 3
set(['MKE', 'MIN', 'MEM', 'ALB', 'ATL', 'DET', 'KAN', 'DCA', 'MAD', 'NYC', 'OMA'])
LEVEL: 4
set(['JAX', 'FAR', 'PRO', 'BOS', 'OKC', 'DEN', 'TAM', 'NEW'])
LEVEL: 5
set(['CYS', 'BIL', 'IAH', 'ABQ', 'MIA', 'DAL', 'LAX', 'SLC'])
LEVEL: 6
set(['SAN', 'SFO', 'PHX', 'BTM', 'ALW', 'ELP', 'FLG', 'SAT'])
LEVEL: 7
set(['TUS', 'SEA', 'PDX'])
LEVEL: 8
set([])


The City of Maximum Dilation: DET
Sorted Dilation:
[('LOU', 1.0), ('COL', 1.0), ('LEX', 1.0), ('IND', 1.0), ('PIT', 1.0), ('FAR', 1.0187334940164066), ('BUF', 1.019632899124331), ('PHI', 1.0201626680233045), ('NAS', 1.021597991791423), ('CLE', 1.024469546194307), ('MIN', 1.0254304847143794), ('SFO', 1.0260973245482636), ('DEN', 1.0261015540483052), ('SLC', 1.0280199300666333), ('TAM', 1.0288737471340277), ('LAX', 1.030577958540265), ('MAD', 1.0351860567987587), ('ATL', 1.0421607873927496), ('KAN', 1.0438201969716825), ('NYC', 1.04573078299378), ('KNO', 1.0460828350758788), ('MIA', 1.046938775612828), ('PRO', 1.0478739209471177), ('CHI', 1.0489611341275544), ('SEA', 1.053001952155493), ('BOS', 1.0586541543434251), ('MKE', 1.0624417580154306), ('STL', 1.0649322927281915), ('BTM', 1.0677888572085026), ('MEM', 1.07140833864397), ('JAX', 1.0725149933253113), ('ALB', 1.0733327528367296), ('BIL', 1.076431786905992), ('FLG', 1.0986467156583777), ('ABQ', 1.1049003406567166), ('PDX', 1.1074378797397215), ('SAN', 1.1088004893158874), ('ALW', 1.11777126898799), ('CYS', 1.1210902689849596), ('NEW', 1.123177365475306), ('OMA', 1.1299559838838495), ('PHX', 1.133692180158462), ('OKC', 1.138869642856025), ('ELP', 1.2035185650324423), ('TUS', 1.2208905654873623), ('SAT', 1.256558334539226), ('IAH', 1.2577494164554461), ('DAL', 1.276757343086596), ('DCA', 1.5770775583386814), ('DET', 2.028281765662398)] 

THE CITY WITH MIN ECCENTRICITY IS: OMA
SORTED ECCENTRICITY
[('OMA', 1612.8234888537486), ('KAN', 1629.3862435330366), ('FAR', 1852.0032420613002), ('STL', 1856.4318856348855), ('OKC', 1924.8240834880826), ('CHI', 1928.2989831781151), ('DEN', 1996.2402332913173), ('MKE', 2001.981959385611), ('MAD', 2048.6890348400016), ('MIN', 2067.7403036278115), ('IND', 2084.993454877695), ('CYS', 2093.0370096551706), ('DAL', 2100.659461493453), ('LOU', 2107.042780616127), ('MEM', 2112.973138103988), ('ABQ', 2120.103747103827), ('SAT', 2139.4838600718413), ('LEX', 2150.601478667984), ('DET', 2168.18405456948), ('NAS', 2262.0192653404183), ('COL', 2293.207641147922), ('KNO', 2305.805053760364), ('IAH', 2326.0914092375524), ('ELP', 2340.8452983711577), ('BIL', 2371.0438840254683), ('SLC', 2377.2811322743164), ('FLG', 2404.6036480450857), ('CLE', 2408.4794628130926), ('PIT', 2450.0769448610727), ('NEW', 2459.9350275242527), ('ATL', 2468.448254832558), ('PHX', 2528.946229295445), ('BTM', 2562.340268205977), ('BUF', 2600.185559314687), ('TUS', 2639.44250522563), ('PHI', 2703.550151588067), ('DCA', 2733.548179820819), ('JAX', 2738.186604724871), ('LAX', 2747.60718613095), ('NYC', 2787.655317515039), ('ALB', 2850.306457669652), ('SAN', 2856.8011691222246), ('ALW', 2862.2120343631195), ('TAM', 2877.871398697029), ('PRO', 2939.0991782867036), ('SFO', 2975.610668854556), ('BOS', 2976.0421989129973), ('SEA', 3037.9423155306195), ('MIA', 3073.0064343892172), ('PDX', 3073.006434389218)]

NUMBER OF SETS 10, Clusters of maximum separation:
 {'DEN': ['DEN', 'CYS'], 'NEW': ['NEW', 'SAT', 'IAH', 'DAL', 'OKC', 'MEM', 'MKE', 'CHI', 'MAD', 'NAS', 'IND', 'CVG', 'LOU', 'LEX', 'COL', 'CLE', 'PIT', 'KNO', 'ATL', 'BUF', 'STL', 'KAN', 'OMA', 'DET', 'DCA', 'PHI', 'NYC', 'ALB', 'BOS', 'PRO', 'JAX', 'MIA'], 'FLG': ['FLG', 'TUS', 'PHX', 'ABQ', 'ELP'], 'BIL': ['BIL', 'BTM'], 'FAR': ['FAR', 'MIN'], 'SEA': ['SEA', 'PDX', 'ALW'], 'TAM': ['TAM'], 'SLC': ['SLC'], 'LAX': ['LAX', 'SAN'], 'SFO': ['SFO']} """
Advertisements

Discussion

No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: