Assignment 3 | Airports and Routes

In Assignment 3, you will be implementing several functions that explore data about airports and flights. The data originally comes from OpenFlights, an open source project. This handout explains the problem being solved and the tasks to complete for the assignment. Please read it carefully and in its entirety.

Introduction: OpenFlights

OpenFlights is "a tool that lets you map your flights around the world, search and filter them in all sorts of interesting ways, calculate statistics automatically, and share your flights and trips with friends and the entire world (if you wish)." This assignment utilizes airport and flight data from OpenFlights, so we recommend that you go try it out for 10 minutes. It should make understanding the rest of this assignment much easier. You don't need to create an account, just try these things:

• Find the PUQ airplane icon at the bottom of South America. It represents an airport. Click it. A chat bubble appears with information in it, including the name of the airport, the abbreviation (PUQ), the city and country, and the number of flights.
• Click the blue splat icon (looks like a paw with 4 fingers) in the bottom right of the chat bubble. This zooms you in on the airport, displays the city information at the top of the window, and shows you direct flights connected to PUQ.
• Click on the icon next to "7 routes" in the city information. This displays a table of flights from PUQ to various cities. What do the columns all mean?
• Continue to explore the website. What happens when you click on the various pieces of information in the table?

In this assignment, you will be implementing several functions that explore the flight data.

Airports, Routes and Flights

In this assignment, we will be working with three types of data:

1. Airport Data
2. Routes Data
3. Flights Data

Airport Data

Airports connect cities all over the world. Airports have two types of codes: IATA and ICAO, issued by two different organizations. We will use the IATA airport code throughout this assignment. IATA codes are three-letter codes used to efficiently identify airports (e.g. the IATA code for Toronto Pearson International Airport is YYZ). They are unique and thus useful for differentiating between different airports – for example, Los Angeles, USA has the code LAX. In contrast, Los Angeles, Chile has the code LSQ.

The airport data we are using is included for you in the data/airports.csv file. We discuss this in more detail in the What to do > Part 1 section.

Route Data

A route is a direct flight that can take you from one airport to another. The airport that you start from is called the source. The airport that you arrive at is called the destination. Both the source and the destination are expressed as IATA airport codes. For example, a route from Toronto, Canada to New York, USA could be expressed as YYZ to LGA. Note that some cities have multiple airports. For example, New York has two: LGA and JFK.

The routes data we are using is included for you in the data/routes.csv file. We discuss this in more detail in the What to do > Part 1 section.

Flight Data

Each flight has an airport they start from called the source, an airport they arrive at called the destination, a time of departure, and a duration. Within this assignment, we are assuming that the available flights (including departure time) remain the same each day. That is, if we have a flight that departs from Toronto (YYZ) to Quebec (YQB) at 12:30am today, such a flight will also be departing at 12:30am tomorrow, and the next day at 12:30am, and so on.

The flights data we are using is included for you in the data/flights.csv file. We discuss this in more detail in the What to do > Part 1 section.

Our Custom Type Annotations

Read the page on type annotations to familarize yourself with the annotation style below, if needed.

We are using a mixture of dictionaries and lists to store our airport, route and flight data.

The type annotation for a dictionary of all airport information is: Dict[str, Dict[str, str]].
The type annotation for a dictionary of all route information is: Dict[str, List[str]]
The type annotation for an individual flight's information is: Dict[str, Union[str, float]]

Rather than type those out every time, we can save them to special kinds of variables called AirportsDict, RoutesDict, and FlightDict respectively.

We have already defined these variables for you in flight_constants.py.

In order to use these type annotations, we can import the annotation from flight_constants:

from flight_constants import AirportsDict, RoutesDict, FlightDict

These types describe how you will store the airport, route and flight information. As mentioned above, they have been imported for you in the starter code, and you should use them in your type contracts.

Starter Files

a3/
   ├─── a3_checker.py
   ├─── data/
     ├─── airports.csv
     ├─── routes.csv
     ├─── flights.csv
   ├─── flight_functions.py
   ├─── flight_reader.py
   ├─── flight_constants.py
   ├─── flight_example_data.py
   ├─── pyta/
       ├─── many pyta files...
   

The following paragraphs briefly explain the files you have been given; more in-depth descriptions appear later in this handout.

Data files

We have provided airports.csv and routes.csv, which were downloaded from the OpenFlights website though they have been modified for our assignment, as well as flights.csv made specifically for this assignment. These files will be discussed in more detail in the What to do > Part 1 section.

Python files you will modify

• flight_reader.py, flight_functions.py
  The starter code for your part of this assignment is in these files. These are the files you will be writing all your assignment code in, and each of these files will be discussed in more detail in the What to do > Part 1 and What to do > Part 2 sections respectively.

Python files you will NOT modify

• flight_constants.py
  Do NOT modify this file. This file includes the code for creating new type annotations, and a constant to represent null values in the files you will be reading in your program. These will be helpful as you write your code. The data from this file have already been imported for you in the starter code.
• flight_example_data
  Do NOT modify this file. This file contains data that is to be used in docstring examples and doctests. You can see examples of them being used in the starter code in both flight_reader.py and flight_functions.py. The data from this file have already been imported for you in the starter code.
• a3_checker.py
  As with the previous assignments, we have provided a checker. Hopefully you've gotten in the habit of running it regularly!

  The checker tests two things:

  • whether your functions have the correct parameter and return types, and
  • whether your code follows the Python and CSC108 style guidelines
  We use the same style checker for the majority of the style marking of your code!

  Reminder: passing the checker does NOT mean your code will pass correctness tests. The checker checks solely for style, NOT correctness.

Writing Functions

For each function you write in this assignment, remember to follow the Function Design Recipe we have been using in class to write the functions for this assignment.

Function input

You can assume all the functions will receive input that satisfies their type contracts. The files that you will need to read will be properly formed, as described in this handout. The dictionaries and other inputs to the other functions will be valid inputs — however your functions should deal with receiving IATA codes for airports that do not appear in your dictionaries as specified later in this handout.

Top Down Design

As discussed in Week 9 in the PCRS exercise for the random story generation program, top-down design is an approach to designing and implementing the body of a function.

Top-down design has you write down, in English, what the major steps are to solving the function.

After that, repeatedly select one of the steps. If you know how to directly translate the English into Python, do so. Otherwise, write a call on a function (that doesn't exist yet!) that will do what the English says to do. Then use the Function Design Recipe to design and write that new function. When it's time to write the body of the new function, use top-down design!

Grading

We will be testing and marking each of these functions individually. So, even if you can't complete them all, you can earn marks for correctly implementing some of the functions.

What NOT to do

Before we get started, as you're working on the assignment, keep these things in mind:

• Do not add statements that call print, input, or open. (You can use print statements for testing if you want, but you MUST remove unnecessary prints before submitting your assignment because otherwise they will cause our test cases to FAIL.)
• Do not modify or add to the import statements provided in the starter code.
• Do not add any code outside of a function definition or the if __name__ == '__main__' block.
• Do not use any global variables (other than constants).
• Do not mutate objects unless specified.

What to do

Let's get started! At a high-level, your next steps are to:

• PART 1:
• Open the file flight_reader.py.
• Make sure that the file is in the same directory as all the other starter files provided.
• Complete the three functions in flight_reader.py as specified in the section labelled "Part 1" below.
• Test your Python file by using the Python shell, running the doctests, and running the a3_checker.py.
• PART 2: Repeat the above for part 2 in flight_functions.py (complete and test the functions specified in the section below).
• PART 3: Repeat the above for part 3 in flight_functions.py (complete and test the functions specified in the section below).

PART 1: flight_reader.py

The data files you will work with in this assignment are included in the starter code as data/airports.csv, data/routes.csv and data/flights.csv.

The purpose of this file's functions is to read and parse these data files. You will implement these three functions to do so:

1. read_airports(TextIO) -> AirportsDict
2. read_routes(TextIO, AirportsDict) -> RoutesDict
3. read_flights(TextIO, RoutesDict) -> List[FlightDict]

Before you start programming, read the rest of Part 1. Here are some useful tips:

• Review the “Reading Files” module from Week 7 on PCRS for help
• Review the “Populating a Dictionary” module from Week 8 on PCRS for help

Open flight_reader.py and complete the functions that are missing bodies. We have provided you with the function headers, docstring description, and doctest examples for the functions you need to implement; you do not need to add or change them. The focus of Part 1 is implementing the bodies of these functions and testing them. The rest of this section contains more information to help you implement these functions.

Missing data

When reading and storing the airport and route data, you may encounter Null values. OpenFlights represents a Null value as: \N. As a Python string, this looks like: '\\N'. We have saved this value in a constant called OPENFLIGHTS_NULL_VALUE that is defined in flight_constants.py. Use this when you need to check if a value from the data file is null (as specified in the function descriptions below).

Airport Data File: airports.csv

This section will be useful for completing read_airports in flight_reader.py.

The first line in this data file is a header line containing all the categories of information about each airport:

Airport ID,Name,City,Country,IATA,ICAO,Latitude,Longitude,Altitude,Timezone,DST,Tz,Type,Source
            

After this header line, each line in airports.csv represents information about one airport. Here is an example line:

193,"Lester B. Pearson International Airport","Toronto","Canada","YYZ","CYYZ",43.6772003174,-79.63059997559999,569,-5,"A","America/Toronto","airport","OurAirports"
            

We will mainly just be dealing with the IATA code part of the airport data, so the following table is not too important to understand for this assignment, but if you are curious about what each category means, here is a quick description of each of them:

We will store airport data as a dictionary of dictionaries (see AirportsDict description here). The outer dictionary will have keys that are IATA airport codes. The value associated with each airport code will be another dictionary (i.e., the inner dictionary). The inner dictionary will have keys that are categories of information about the airport (e.g., "Name", "City", "Country" etc.), and the values will be the information associated with each category for that airport.

For example, if our airports.csv file had two airports like so:

    Airport ID,Name,City,Country,IATA,ICAO,Latitude,Longitude,Altitude,Timezone,DST,Tz,Type,Source
    1,Apt1,Cty1,Cntry1,AA1,AAA1,-1,1,1,1,1,D1,Typ1,Src1
    2,Apt2,Cty2,Cntry2,AA2,AAA2,-2,2,2,2,2,D2,Type2,Src2
  

  {
    "AA1": {
        "Airport ID": "1",
        "Name": "Apt1",
        "City": "Cty1",
        "Country": "Cntry1",
        "IATA": "AA1",
        "ICAO": "AAA1",
        "Latitude": "-1",
        "Longitude": "1",
        "Altitude": "1",
        "Timezone": "1",
        "DST": "1",
        "Tz": "D1",
        "Type": "Typ1",
        "Source": "Src1",
    },
    "AA2": {
        "Airport ID": "2",
        "Name": "Apt2",
        "City": "Cty2",
        "Country": "Cntry2",
        "IATA": "AA2",
        "ICAO": "AAA2",
        "Latitude": "-2",
        "Longitude": "2",
        "Altitude": "2",
        "Timezone": "2",
        "DST": "2",
        "Tz": "D2",
        "Type": "Type2",
        "Source": "Src2",
    }
  }
  

Route Data File: routes.csv

This section will be useful for completing read_routes in flight_reader.py.

The first line in this data file is a header line containing all the categories of information about each airport:

Airline,Airline ID,Source airport,Source airport ID,Destination airport,Destination airport ID,Codeshare,Stops,Equipment
                

After this header line, each line in routes.csv represents route information about a direct flight from one airport to another. Here is an example line:

                              AA,24,JFK,3797,YYZ,193,Y,0,CR7
                

Note that routes are directional, meaning if an airline operates services from A to B and from B to A, then both A-B and B-A are listed. And as with airports.csv, the special value \N is used for "NULL" to indicate that no value is available.

We will mainly just be dealing with the Source airport and Destination airport columns of the route data, so most of the following table is not too important to understand for this assignment, but if you are curious about what each category means, here is a quick description of each of them:

We will store routes data as a dictionary (see RoutesDict description here). The dictionary will have keys that are IATA airport codes. The value associated with each airport code will be a list of IATA codes that represent destinations you can reach from that airport. That is, each source airport's IATA code will be a key, and any destination airport reachable from that source will be included in a list of IATA codes as its value in the dictionary.

For example, if our routes.csv file had three routes like so:

  Airline,Airline ID,Source airport,Source airport ID,Destination airport,Destination airport ID,Codeshare,Stops,Equipment
  A1,1111,AA1,1,AA2,2,,0,EQ1
  A2,2222,AA2,2,AA3,3,,0,EQ1
  A1,1111,AA1,1,AA4,4,,0,EQ1
  

  {
    "AA1": ["AA2", "AA4"],
    "AA2": ["AA3"]
  }

Flight Data File: flights.csv

This section will be useful for completing read_flights in flight_reader.py.

The first line in this data file is a header line containing all the categories of information about each flight:

Flight ID,Source airport,Destination airport,Departure time,Duration
          

After this header line, each line in flights.csv represents flight information about a direct flight from one airport to another. Here is an example line:

                1486,YQB,YYZ,0.5,4.5
          

Note that the time is represented as a float from 0.0 to 24.0, based on the 24-hour clock. So, in the above line, the departure time being 0.5 represents 00:30 in the 24-hour clock (which is equivalent to 12:30am in the 12-hour clock).

Also, as mentioned before, within this assignment, we are assuming that the available flights (including departure time) remain the same each day. That is, the above line being in flights.csv signifies that we have a flight that departs from Toronto (YYZ) to Quebec (YQB) at 12:30am (0.5) on each day.

The last column in the file represents the flight duration as a float – this is in hours, so in the above example, the flight is 4.5 hours long.

We will store flights data as a list of dictionaries (see FlightDict description here). Each dictionary will have keys that are category headings (taken from the first line of the data file), and the values are the data associated with that category.

For example, if our flights.csv file had two flights like so:

          Flight ID,Source airport,Destination airport,Departure time,Duration
          1,AA1,AA2,0.00,2.00
          2,AA2,AA3,4.00,3.50
          

            [
              {'Flight ID': '1',
               'Source airport': 'AA1',
               'Destination airport': 'AA2',
               'Departure time': 0.00,
               'Duration': 2.00},
              {'Flight ID': '2',
               'Source airport': 'AA2',
               'Destination airport': 'AA3',
               'Departure time': 4.00,
               'Duration': 3.50}
            ]
          

Function Descriptions for flight_reader.py

Based on the information above, write the function body for the following functions in flight_reader.py:

PART 2: flight_functions.py – Querying the data

In Part 2, you will complete four functions using the Function Design Recipe. We have included the type contracts and a specification of every function below; please read through them carefully.

The purpose of all these functions in Part 2 is to check parts of the existing data for certain conditions (e.g. Is there a direct flight from one airport to another? Is a sequence of airports a valid way to fly from the first airport in the sequence to the last? etc.)

Note that you must NOT mutate the arguments of these functions.

Function Descriptions for flight_functions.py (Part 2)

Open flight_functions.py and complete the following functions. We recommend that you work on them in the following order. Remember to use existing functions as helper functions if applicable.

For the three functions below, you just have to write the function body. The examples and docstring are already provided for you - you do not need to add or modify these.

For the fourth function, you must also complete the type contract and docstring. Include at least two examples that call the function you are designing in your docstring. The type contract and docstring example must be formatted correctly to be interpreted by the doctest module. You may find the existing examples from Parts 1, the other three functions in Part 2, and Part 3 to be a useful reference.

You will need to paraphrase the specifications of the function (see below) to get an appropriate docstring description. Make sure you review the Function Design Recipe and CSC108 Python Style Guidelines for the rules on how to write a docstring description.

PART 3: flight_functions.py - Designing useful algorithms

In Part 3, you will implement three useful algorithms that work with the route data:

1. get_best_flight(str, str, List[FlightDict], float) -> Optional[FlightDict]
2. find_reachable_destinations(str, int, RoutesDict) -> List[str]
3. calculate_trip_time(List[str], List[FlightDict]) -> float

{'AA1': ['AA2', 'AA4'], 'AA2': ['AA3'], 'AA3': ['AA4', 'AA1'], 'AA4': ['AA1']}

Helpful algorithm tips

Some hints for get_best_flight:

• The 'best flight' in this context doesn't just mean the earliest flight; we want the flight that will get us to our destination soonest so you need to take into account a flight's departure time, flight's duration, and the current time.
• Use the pattern we discussed in lecture for finding a minimum element by keeping track of the minimum value seen so far (see starter code for the beginnings of this pattern and finish the function body accordingly).

Some hints for find_reachable_destinations:

Let us expand one of the doctest examples:

  find_reachable_destinations('AA1', 2, routes_example_data)
  ['AA1', 'AA2', 'AA3', 'AA4']
            

The maximum number of direct flights in this example is 2 and routes_example_data is:

  {
    "AA1": ["AA2", "AA4"],
    "AA2": ["AA3"],
    "AA3": ["AA4", "AA1"],
    "AA4": ["AA1"],
  }

1. If we start at 'AA1', then there are two possible direct flights to 'AA2' and 'AA4'. So we should accumulate 'AA2' and 'AA4' (these are both destinations reachable with 1 direct flight) and move on to the next step.
2. If we were to “fly” to 'AA2', then we are now (hypothetically) at the 'AA2' airport. This means, based on routes_example_data, we can reach another airport via another direct flight: 'AA3'. So we should accumulate 'AA3' and move on to the next step.
3. If we were to “fly” to 'AA4', then we are now (hypothetically) at the 'AA4' airport. This means, based on routes_example_data, we can reach another airport via another direct flight: 'AA1' (where we came from). So we should accumulate 'AA1' and move on to the next step.
4. After “flying” to either 'AA3' or 'AA4', we have taken the maximum number of direct flights in the example (i.e., 2). So we should stop and then return what we have accumulated.

Though this was not relevant in the current example, keep in mind that the docstring explicitly says:

The list should not contain an IATA airport code more than once.

In a more complex example, like the data loaded from the file, the number of reachable destinations returned would likely be much larger than our small doctest example.

Some hints for calculate_trip_time:

This algorithm should calculate the trip time when travelling from a source airport to a destination airport, following a provided path.

Let us expand one of the doctest examples:

    calculate_trip_time(["AA4", "AA1", "AA2"], flights_example_data)
    14.0
                        

The path we're taking is from AA4 to AA1 to AA2 and flights_example_data is:

       [
        {'Flight ID': '1',
         'Source airport': 'AA1',
         'Destination airport': 'AA2',
         'Departure time': 0.00,
         'Duration': 2.00},
        {'Flight ID': '2',
         'Source airport': 'AA2',
         'Destination airport': 'AA3',
         'Departure time': 4.00,
         'Duration': 3.50},
        {'Flight ID': '3',
         'Source airport': 'AA3',
         'Destination airport': 'AA4',
         'Departure time': 7.00,
         'Duration': 2.00},
        {'Flight ID': '4',
         'Source airport': 'AA4',
         'Destination airport': 'AA1',
         'Departure time': 2.00,
         'Duration': 3.00},
        {'Flight ID': '5',
         'Source airport': 'AA1',
         'Destination airport': 'AA4',
         'Departure time': 0.00,
         'Duration': 2.00},
        {'Flight ID': '6',
         'Source airport': 'AA1',
         'Destination airport': 'AA2',
         'Departure time': 12.00,
         'Duration': 2.00}
        ]

1. For the first flight we take, we want to take the best flight available (one that will get us to our destination soonest) on a given day that starts from our source airport (available in path[0]) and goes to the next airport on our path (path[1]). Remember that a day starts at time 0.0.
2. Based on flight_example_data we see that the best flight we can take is flight ID 4 which departs at 2.00 and has a duration of 3.00. We increment the total trip time so far to be 2.0 (we assumed that we began our journey at the beginning of the day, so we had to wait 2 hours for the departure) + 3.0 (duration of the flight). Our total trip time so far is thus 5.0.
3. The next flight in our path is AA2. Note that our current source airport is AA1 (because in the last step, we flew from AA4 and landed at AA1). The current time has also now changed, taking into account our previous waiting time of 2.0 hours until departure and then the duration of the flight (3.0 hours), so the time is now 5.0. Taking this into consideration, we know that any flights in the flight data that occur after 5.0 (5:00am) are a better choice (because any earlier flights we have already missed, and would have to wait until the next day to take). So, we should first search for the best flight within all the flights remaining today.
4. Since we searched only among flights that are remaining today, we get back the flight ID 6 which goes from AA1 to AA2, departing at 12.00 (which is after the current time 5.0), and has a duration of 2.00. The total time so far is now incremented by the time we spent waiting for this departure from our current time (12-5 = 7 hours of waiting) plus the flight duration (2 hours). This makes our total trip time 14.0 hours so far.

Note: If there were no more flights from our current source to next destination available in the flights remaining today, we would have had to wait until the next day and search all the flights for one that matches our source and destination. In that case, make sure to take the extra waiting time into consideration as we wait for the next day.

5. In our case, since we have reached the end of our path, we are at our final destination, so we return 14.0 as our total trip time.
6. For all of the above steps, keep in mind that if there are any existing functions that can be used as helper functions, you should definitely use those rather than re-writing all the code.

Testing your Code

It is strongly recommended that you test each function as you write it. This will make your life easier — if you write 2–3 lines of code, then test, you know where to look for your bug! If you wait until you've written a whole lot of code, it's harder to figure out where to look.

As usual, follow the Function Design Recipe. Once you've implemented a function, run it on the examples in your docstring. Here are a few tips:

• Keep in mind the PCRS materials from Week 10 about choosing tests — how do those tips apply to your functions here?
• Can you think of any special cases for your functions? Will each function always work, or are there special cases to consider? Test each function carefully.
• Once you are happy with the behaviour of a function, move to the next function, implement it, and test it.

Marking

These are the aspects of your work that will be marked for Assignment 3:

• Correctness (80%): Your functions should perform as specified. Correctness, as measured by our tests, will count for the largest single portion of your marks. Once your assignment is submitted, we will run additional tests, not provided in the checker. Passing the checker does not mean that your code will earn full marks for correctness.
• Coding style (20%): Make sure that you follow Python style guidelines that we have introduced and the Python coding conventions that we have been using throughout the semester. Although we don't provide an exhaustive list of style rules, the checker tests for style are complete, so if your code passes the checker, then it will earn full marks for coding style with two exceptions: docstrings may be evaluated separately, and we may look for use of helper functions. For each occurrence of a PyTA error, a 1 mark deduction will be applied. For example, if a C0301 (line-too-long) error occurs 3 times, then 3 marks will be deducted.

What to Submit

The very last thing you should do before submitting is to run the checker one last time. Otherwise, you could make a small error in your final changes before submitting that causes your code to receive zero for correctness. If your code does not run, you will get a zero for correctness.

For this assignment, you will hand in two files on MarkUs:

• flight_reader.py: This should contain your implementations of the three required functions for reading files, and any helper functions that you have written for them.
• flight_functions.py: This should contain implementations of the remaining required functions, and any helper functions that you have written for them.

Once you have submitted, be sure to check that you have submitted the correct version; new or missing files will not be accepted after the due date. Remember that spelling of filenames, including case, counts. If your file is not named exactly as above, your code will receive zero for correctness.