|
| 1 | +import collections |
| 2 | +import csv |
| 3 | +import functools |
| 4 | +import haversine |
| 5 | +import heapq |
| 6 | + |
| 7 | +Airport = collections.namedtuple('Airport', 'code name country latitude longitude') |
| 8 | +Flight = collections.namedtuple('Flight' , 'origin destination') |
| 9 | +Route = collections.namedtuple('Route' , 'price path') |
| 10 | + |
| 11 | +class Heap(object): |
| 12 | +"""A min-heap.""" |
| 13 | + |
| 14 | +def __init__(self): |
| 15 | +self._values = [] |
| 16 | + |
| 17 | +def push(self, value): |
| 18 | +"""Push the value item onto the heap.""" |
| 19 | +heapq.heappush(self._values, value) |
| 20 | + |
| 21 | +def pop(self): |
| 22 | +""" Pop and return the smallest item from the heap.""" |
| 23 | +return heapq.heappop(self._values) |
| 24 | + |
| 25 | +def __len__(self): |
| 26 | +return len(self._values) |
| 27 | + |
| 28 | +def get_airports(path='airports.dat'): |
| 29 | +"""Return a generator that yields Airport objects.""" |
| 30 | + |
| 31 | +with open(path, 'rt') as fd: |
| 32 | +reader = csv.reader(fd) |
| 33 | +for row in reader: |
| 34 | +name = row[1] |
| 35 | +country = row[3] |
| 36 | +code = row[4] # IATA code (eg, 'BCN' for Barcelona) |
| 37 | +latitude = float(row[6]) # Decimal degrees; negative is South. |
| 38 | +longitude = float(row[7]) # Decimal degrees; negative is West. |
| 39 | +yield Airport(code, name, country, latitude, longitude) |
| 40 | +print (name, country, code) |
| 41 | + |
| 42 | +# Make it possible to easily look up airports by IATA code. |
| 43 | +AIRPORTS = {airport.code : airport for airport in get_airports()} |
| 44 | + |
| 45 | +def get_flights(path='flights.dat'): |
| 46 | +"""Return a generator that yields direct Flight objects.""" |
| 47 | + |
| 48 | +with open(path, 'rt') as fd: |
| 49 | +reader = csv.reader(fd) |
| 50 | +for row in reader: |
| 51 | +origin = row[2] # IATA code of source ... |
| 52 | +destination = row[4] # ... and destination airport. |
| 53 | +nstops = int(row[7]) # Number of stops; zero for direct. |
| 54 | +if not nstops: |
| 55 | +yield Flight(origin, destination) |
| 56 | + |
| 57 | +class Graph(object): |
| 58 | +""" A hash-table implementation of an undirected graph.""" |
| 59 | + |
| 60 | +def __init__(self): |
| 61 | +# Map each node to a set of nodes connected to it |
| 62 | +self._neighbors = collections.defaultdict(set) |
| 63 | + |
| 64 | +def connect(self, node1, node2): |
| 65 | +self._neighbors[node1].add(node2) |
| 66 | +self._neighbors[node2].add(node1) |
| 67 | + |
| 68 | +def neighbors(self, node): |
| 69 | +yield from self._neighbors[node] |
| 70 | + |
| 71 | +@classmethod |
| 72 | +def load(cls): |
| 73 | +"""Return a populated Graph object with real airports and routes.""" |
| 74 | + |
| 75 | +world = cls() |
| 76 | +for flight in get_flights(): |
| 77 | +try: |
| 78 | +origin = AIRPORTS[flight.origin] |
| 79 | +destination = AIRPORTS[flight.destination] |
| 80 | +world.connect(origin, destination) |
| 81 | +# Ignore flights to or from an unknown airport |
| 82 | +except KeyError: |
| 83 | +continue |
| 84 | +return world |
| 85 | + |
| 86 | +@staticmethod |
| 87 | +@functools.lru_cache() |
| 88 | +def get_price(origin, destination, cents_per_km=0.1): |
| 89 | +"""Return the cheapest flight without stops.""" |
| 90 | + |
| 91 | +# Haversine distance, in kilometers |
| 92 | +point1 = origin.latitude, origin.longitude, |
| 93 | +point2 = destination.latitude, destination.longitude |
| 94 | +distance = haversine.haversine(point1, point2) |
| 95 | +return distance * cents_per_km |
| 96 | + |
| 97 | +def dijkstra(self, origin, destination): |
| 98 | +"""Use Dijkstra's algorithm to find the cheapest path.""" |
| 99 | + |
| 100 | +routes = Heap() |
| 101 | +for neighbor in self.neighbors(origin): |
| 102 | +price = self.get_price(origin, neighbor) |
| 103 | +routes.push(Route(price=price, path=[origin, neighbor])) |
| 104 | + |
| 105 | +visited = set() |
| 106 | +visited.add(origin) |
| 107 | + |
| 108 | +while routes: |
| 109 | + |
| 110 | +# Find the nearest yet-to-visit airport |
| 111 | +price, path = routes.pop() |
| 112 | +airport = path[-1] |
| 113 | +if airport in visited: |
| 114 | +continue |
| 115 | + |
| 116 | +# We have arrived! Wo-hoo! |
| 117 | +if airport is destination: |
| 118 | +return price, path |
| 119 | + |
| 120 | +# Tentative distances to all the unvisited neighbors |
| 121 | +for neighbor in self.neighbors(airport): |
| 122 | +if neighbor not in visited: |
| 123 | +# Total spent so far plus the price of getting there |
| 124 | +new_price = price + self.get_price(airport, neighbor) |
| 125 | +new_path = path + [neighbor] |
| 126 | +routes.push(Route(new_price, new_path)) |
| 127 | + |
| 128 | +visited.add(airport) |
| 129 | + |
| 130 | +return float('infinity') |
| 131 | + |
| 132 | +def menu(airp='VLC'): |
| 133 | +airp = str(input('Press by code:')) |
| 134 | +return (airp) |
| 135 | + |
| 136 | +def path2csv (path): |
| 137 | +with open("output.csv", "w") as f: |
| 138 | +writer = csv.writer(f) |
| 139 | +writer.writerows(path) |
| 140 | + |
| 141 | +def csv2kml(fname): |
| 142 | +data = csv.reader(open(fname + '.csv'), delimiter = ',') |
| 143 | +#Open the file to be written. |
| 144 | +f = open('output.kml', 'w') |
| 145 | + |
| 146 | +#Writing the kml file. |
| 147 | +f.write("<?xml version='1.0' encoding='UTF-8'?>\n") |
| 148 | +f.write("<kml xmlns='http://earth.google.com/kml/2.1'>\n") |
| 149 | +f.write("<Document>\n") |
| 150 | +f.write(" <name>" + fname + '.kml' +"</name>\n") |
| 151 | +for row in data: |
| 152 | +f.write(" <Placemark>\n") |
| 153 | +f.write(" <name>" + str(row[0]) + "</name>\n") |
| 154 | +f.write(" <description>" + str(row[1]) + "</description>\n") |
| 155 | +f.write(" <Point>\n") |
| 156 | +f.write(" <coordinates>" + str(row[4]) + "," + str(row[3])+", 0""</coordinates>\n") |
| 157 | +f.write(" </Point>\n") |
| 158 | +f.write(" </Placemark>\n") |
| 159 | +f.write("</Document>\n") |
| 160 | +f.write("</kml>\n") |
| 161 | +f.close() |
| 162 | + |
| 163 | +if __name__ == "__main__": |
| 164 | + |
| 165 | +world = Graph.load() |
| 166 | +print ("Input origin airport:") |
| 167 | +airo = menu(airp='VLC') |
| 168 | +print ("Input destination airport:") |
| 169 | +aird = menu(airp='VLC') |
| 170 | +print (airo, aird) |
| 171 | +valencia = AIRPORTS['{}'.format(airo)] |
| 172 | +portland = AIRPORTS['{}'.format(aird)] |
| 173 | +distance, path = world.dijkstra(valencia, portland) |
| 174 | +for index, airport in enumerate(path): |
| 175 | +print(index, '|', airport) |
0 commit comments