//
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
[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]
phi1 = (90.0 - lat1)*degrees_to_radians
phi2 = (90.0 - lat2)*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

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

hiways = map(parse_roads, """
MKE, 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])

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

#Find nearest pair of cities that share a route
min=1000
for e in hiways:
if s_distance(e[0],e[1]) < min :
min = s_distance(e[0],e[1])

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

visited = set()
currentLevel = [root]
while currentLevel:
nextLevel = set()
for v in currentLevel:
for w in G[v]:
if w not in visited:
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']} """```