Notebook11_MarkovChainAnalysis.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "intro",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "# Markov chain analysis of the US airport network\n",
    "\n",
    "One way to view the airline transportation infrastructure is in the form of a directed _network_ or _graph_, in which vertices are airports and edges are the direct-flight segments that connect them. For instance, if there is a direct flight from Atlanta's Hartsfield-Jackson International Airport (\"ATL\") to Los Angeles International Airport (\"LAX\"), then the airport network would have a directed edge from ATL to LAX."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "intro_1",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "Given the airport network, one question we might ask is, which airports are most critical to disruption of the overall network? That is, if an airport is shut down, thereby leading to all inbound and outbound flights being cancelled, will that catastrophic event have a big impact or a small impact on the overall network?\n",
    "\n",
    "You would expect \"importance\" to be related to whether an airport has lots of inbound or outgoing connections. In graph lingo, that's also called the _degree_ of a vertex or node. But if there are multiple routes that can work around a highly connected hub (i.e., a vertex with a high indegree or outdegree), that might not be the case. So let's try to use a PageRank-like scheme to see what we get and compare that to looking at degree."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "intro_2",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "As it happens, the US Bureau of Transportation Statistics collects data on all flights originating or arriving in the United States. In this notebook, you'll use this data to build an airport network and then use Markov chain analysis to rank the networks by some measure of \"criticality.\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "intro_3",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "> Sources: This notebook is adapted from the following: https://www.mongodb.com/blog/post/pagerank-on-flights-dataset. The dataset you will use was taken from the repository available here: https://www.transtats.bts.gov/DL_SelectFields.asp?Table_ID=236"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "formalize",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## The formal analysis problem\n",
    "\n",
    "Let's model the analysis problem as follows.\n",
    "\n",
    "Consider a \"random flyer\" to be a person who arrives at an airport $i$, and then randomly selects any direct flight that departs from $i$ and arrives at $j$. We refer to the direct flight from $i$ to $j$ as the _flight segment_ $i \\rightarrow j$. Upon arriving at $j$, the flyer repeats the process of randomly selecting a new segment, $j \\rightarrow k$. He or she repeats this process forever."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "formalize_transition_scalar",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "Let $x_i(t)$ be the probability that the flyer is at airport $i$ at time $t$. Take $t$ to be an integer count corresponding to the number of flight segments that the flyer has taken so far, starting at $t=0$. Let $p_{ij}$ be the probability of taking segment $i \\rightarrow j$, where $p_{ij} = 0$ means the segment $i \\rightarrow j$ is unavailable or does not exist. If there are $n$ airports in all, numbered from $0$ to $n-1$, then the probability that the flyer will be at airport $i$ at time $t+1$, given all the probabilities at time $t$, is\n",
    "\n",
    "$$\n",
    "  x_i(t+1) = \\sum_{j=0}^{n-1} p_{ji} \\cdot x_j(t).\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "formalize_transition_vector",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "Let $P \\equiv [p_{ij}]$ be the matrix of transition probabilities and $x(t) = [x_i(t)]$ the column vector of prior probabilities. Then we can write the above more succinctly for all airports as the matrix-vector product,\n",
    "\n",
    "$$\n",
    "  x(t+1) = P^T x(t).\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "formalize_steady_state",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "Since $P$ is a probability transition matrix then there exists a steady-state distribution, $x^*$, which is the limit of $x(t)$ as $t$ goes to infinity:\n",
    "\n",
    "$$\\displaystyle \\lim_{t \\rightarrow \\infty} x(t) = x^* \\equiv [x_i^*].$$\n",
    "\n",
    "The larger $x_i^*$, the more likely it is that the random flyer is to be at airport $i$ in the steady state. Therefore, we can take the \"importance\" or \"criticality\" of airport $i$ in the flight network to be its steady-state probability, $x_i^*$.\n",
    "\n",
    "Thus, our data pre-processing goal is to construct $P$ and our analysis goal is to compute the steady-state probability distribution, $x^*$, for a first-order Markov chain system."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "modules",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Modules you'll need\n",
    "\n",
    "For this notebook, let's use Pandas for preprocessing the raw data and SciPy's sparse matrix libraries to implement the analysis.\n",
    "\n",
    "> One of the cells below defines a function, `spy()`, that can be used to visualize the non-zero structure of a sparse matrix."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "nbgrader": {
     "grade": false,
     "grade_id": "setup",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import scipy as sp\n",
    "import scipy.sparse\n",
    "\n",
    "import pandas as pd"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "nbgrader": {
     "grade": false,
     "grade_id": "setup_spy",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline\n",
    "\n",
    "def spy(A, figsize=(6, 6), markersize=0.5):\n",
    "    \"\"\"Visualizes a sparse matrix.\"\"\"\n",
    "    fig = plt.figure(figsize=figsize)\n",
    "    plt.spy(A, markersize=markersize)\n",
    "    plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "nbgrader": {
     "grade": false,
     "grade_id": "display",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "from IPython.display import display, Markdown # For pretty-printing tibbles"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "nbgrader": {
     "grade": false,
     "grade_id": "tibble_stuff",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "def canonicalize_tibble(X):\n",
    "    var_names = sorted(X.columns)\n",
    "    Y = X[var_names].copy()\n",
    "    Y.sort_values(by=var_names, inplace=True)\n",
    "    Y.reset_index(drop=True, inplace=True)\n",
    "    return Y\n",
    "\n",
    "def tibbles_are_equivalent (A, B):\n",
    "    A_canonical = canonicalize_tibble(A)\n",
    "    B_canonical = canonicalize_tibble(B)\n",
    "    cmp = A_canonical.eq(B_canonical)\n",
    "    return cmp.all().all()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "download_intro",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Part 0: Downloading, unpacking, and exploring the data\n",
    "\n",
    "You'll need some data for this assignment. The following code cell will check for it in your local environment, and if it doesn't exist, attempt to download it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "import requests\n",
    "import os\n",
    "import hashlib\n",
    "import io\n",
    "\n",
    "def on_vocareum():\n",
    "    return os.path.exists('.voc')\n",
    "\n",
    "def download(file, local_dir=\"\", url_base=None, checksum=None):\n",
    "    local_file = \"{}{}\".format(local_dir, file)\n",
    "    if not os.path.exists(local_file):\n",
    "        if url_base is None:\n",
    "            url_base = \"https://cse6040.gatech.edu/datasets/\"\n",
    "        url = \"{}{}\".format(url_base, file)\n",
    "        print(\"Downloading: {} ...\".format(url))\n",
    "        r = requests.get(url)\n",
    "        with open(local_file, 'wb') as f:\n",
    "            f.write(r.content)\n",
    "            \n",
    "    if checksum is not None:\n",
    "        with io.open(local_file, 'rb') as f:\n",
    "            body = f.read()\n",
    "            body_checksum = hashlib.md5(body).hexdigest()\n",
    "            assert body_checksum == checksum, \\\n",
    "                \"Downloaded file '{}' has incorrect checksum: '{}' instead of '{}'\".format(local_file,\n",
    "                                                                                           body_checksum,\n",
    "                                                                                           checksum)\n",
    "    print(\"'{}' is ready!\".format(file))\n",
    "    \n",
    "if on_vocareum():\n",
    "    URL_BASE = \"https://cse6040.gatech.edu/datasets/us-flights/\"\n",
    "    DATA_PATH = \"../resource/lib/publicdata/\"\n",
    "else:\n",
    "    URL_BASE = \"https://github.com/cse6040/labs-fa17/raw/master/lab11-markov_chains/\"\n",
    "    DATA_PATH = \"\"\n",
    "\n",
    "datasets = {'L_AIRPORT_ID.csv': 'e9f250e3c93d625cce92d08648c4bbf0',\n",
    "            'L_CITY_MARKET_ID.csv': 'f430a16a5fe4b9a849accb5d332b2bb8',\n",
    "            'L_UNIQUE_CARRIERS.csv': 'bebe919e85e2cf72e7041dbf1ae5794e',\n",
    "            'us-flights--2017-08.csv': 'eeb259c0cdd00ff1027261ca0a7c0332',\n",
    "            'flights_atl_to_lax_soln.csv': '4591f6501411de90af72693cdbcc08bb',\n",
    "            'origins_top10_soln.csv': 'de85c321c45c7bf65612754be4567086',\n",
    "            'dests_soln.csv': '370f4c632623616b3bf26b6f79993fe4',\n",
    "            'dests_top10_soln.csv': '4c7dd7edf48c4d62466964d6b8c14184',\n",
    "            'segments_soln.csv': '516a78d2d9d768d78bfb012b77671f38',\n",
    "            'segments_outdegree_soln.csv': 'b29d60151c617ebafd3a1c58541477c8'\n",
    "           }\n",
    "\n",
    "for filename, checksum in datasets.items():\n",
    "    download(filename, local_dir=DATA_PATH, url_base=URL_BASE, checksum=checksum)\n",
    "    \n",
    "print(\"\\n(All data appears to be ready.)\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-8e9b52d96a466a12",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "**Airport codes.** Let's start with the airport codes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "nbgrader": {
     "grade": false,
     "grade_id": "show_airport_codes",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "airport_codes = pd.read_csv(\"{}{}\".format(DATA_PATH, 'L_AIRPORT_ID.csv'))\n",
    "airport_codes.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "download_flight_segments_intro",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "**Flight segments.** Next, let's load a file that contains all of US flights that were scheduled for August 2017."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "nbgrader": {
     "grade": false,
     "grade_id": "flights",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "flights = pd.read_csv('{}{}'.format(DATA_PATH, 'us-flights--2017-08.csv'))\n",
    "print(\"Number of flight segments: {} [{:.1f} million]\".format (len(flights), len(flights)*1e-6))\n",
    "del flights['Unnamed: 7'] # Cleanup extraneous column\n",
    "flights.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "download_time_range",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "Each row of this tibble is a _(direct) flight segment_, that is, a flight that left some origin and arrived at a destination on a certain date. As noted earlier, these segments cover a one-month period (August 2017)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 0** (3 points). As a warmup to familiarize yourself with this dataset, determine all direct flight segments that originated at Atlanta's Hartsfield-Jackson International Airport and traveled to Los Angeles International. Store the result in a dataframe named `flights_atl_to_lax`, which should be the corresponding subset of rows from `flights`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "nbgrader": {
     "grade": false,
     "grade_id": "flights_atl_to_lax",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "#\n",
    "# YOUR CODE HERE\n",
    "#\n",
    "\n",
    "# Displays a few of your results\n",
    "print(\"Your code found {} flight segments.\".format(len(flights_atl_to_lax)))\n",
    "display(flights_atl_to_lax.head())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "nbgrader": {
     "grade": true,
     "grade_id": "flights_atl_to_lax_test",
     "locked": true,
     "points": 3,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "# Test cell: `flights_atl_to_lax_test`\n",
    "\n",
    "if False:\n",
    "    flights_atl_to_lax.to_csv('flights_atl_to_lax_soln.csv', index=False)\n",
    "flights_atl_to_lax_soln = pd.read_csv('{}{}'.format(DATA_PATH, 'flights_atl_to_lax_soln.csv'))\n",
    "\n",
    "assert tibbles_are_equivalent(flights_atl_to_lax, flights_atl_to_lax_soln), \\\n",
    "       \"Sorry, your solution does not match the instructor's solution.\"\n",
    "\n",
    "print(\"\\n(Passed!)\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "download_aggregation",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "**Aggregation.** Observe that an (origin, destination) pair may appear many times. That's because the dataset includes a row for _every_ direct flight that occurred historically and there may have been multiple such flights on a given day.\n",
    "\n",
    "However, for the purpose of this analysis, let's simplify the problem by collapsing _all_ historical segments $i \\rightarrow j$ into a single segment. Let's also do so in a way that preserves the number of times the segment occurred (i.e., the number of rows containing the segment)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "download_outline_agg_task",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "To accomplish this task, the following code cell uses the [`groupby()`](http://pandas.pydata.org/pandas-docs/stable/generated/pandas.DataFrame.groupby.html) function available for Pandas tables and the [`count()`](http://pandas.pydata.org/pandas-docs/stable/groupby.html) aggregator in three steps:\n",
    "\n",
    "1. It considers just the flight date, origin, and destination columns.\n",
    "2. It _logically_ groups the rows having the same origin and destination, using `groupby()`.\n",
    "3. It then aggregates the rows, counting the number of rows in each (origin, destination) group."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "nbgrader": {
     "grade": false,
     "grade_id": "segments",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "flights_cols_subset = flights[['FL_DATE', 'ORIGIN_AIRPORT_ID', 'DEST_AIRPORT_ID']]\n",
    "segment_groups = flights_cols_subset.groupby(['ORIGIN_AIRPORT_ID', 'DEST_AIRPORT_ID'], as_index=False)\n",
    "segments = segment_groups.count()\n",
    "segments.rename(columns={'FL_DATE': 'FL_COUNT'}, inplace=True)\n",
    "segments.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "download_segments_sanity",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "As a last sanity check, let's verify that the counts are all at least 1."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "nbgrader": {
     "grade": false,
     "grade_id": "segments_check_counts",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "assert (segments['FL_COUNT'] > 0).all()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "download_actual_intro",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "**Actual (as opposed to \"all possible\") origins and destinations.** Although there are many possible airport codes stored in the `airport_codes` dataframe (over six thousand), only a subset appear as actual origins in the data. The following code cell determines the actual origins and prints their number."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "nbgrader": {
     "grade": false,
     "grade_id": "origins",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "origins = segments[['ORIGIN_AIRPORT_ID', 'FL_COUNT']].groupby('ORIGIN_AIRPORT_ID', as_index=False).sum()\n",
    "origins.rename(columns={'FL_COUNT': 'ORIGIN_COUNT'}, inplace=True)\n",
    "print(\"Number of actual origins:\", len(origins))\n",
    "origins.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "download_rank_intro",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "To get an idea of what airports are likely to be the most important in our Markov chain analysis, let's rank airports by the total number of _outgoing_ segments, i.e., flight segments that originate at the airport."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "exericse_1",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "**Exercise 1** (3 points). Construct a dataframe, `origins_top10`, containing the top 10 airports in descending order of outgoing segments. This dataframe should have three columns:\n",
    "\n",
    "* `ID`: The ID of the airport\n",
    "* `Count`: Number of outgoing segments.\n",
    "* `Description`: The plaintext descriptor for the airport that comes from the `airport_codes` dataframe.\n",
    "\n",
    "> _Hint_: Look up and read about `numpy.argsort()`, which you can also apply to any Pandas Series object."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "nbgrader": {
     "grade": false,
     "grade_id": "origin_ranks",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "#\n",
    "# YOUR CODE HERE\n",
    "#\n",
    "\n",
    "# Prints the top 10, according to your calculation:\n",
    "origins_top10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "nbgrader": {
     "grade": true,
     "grade_id": "origin_ranks_test",
     "locked": true,
     "points": 3,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "# Test cell: `origin_ranks_test`\n",
    "\n",
    "if False:\n",
    "    origins_top10.to_csv('origins_top10_soln.csv', index=False)\n",
    "origins_top10_soln = pd.read_csv('{}{}'.format(DATA_PATH, 'origins_top10_soln.csv'))\n",
    "\n",
    "print(\"=== Instructor's solution ===\")\n",
    "display(origins_top10_soln)\n",
    "    \n",
    "assert tibbles_are_equivalent(origins_top10, origins_top10_soln), \\\n",
    "       \"Your table does not have the same entries as the solution.\"\n",
    "\n",
    "counts_0_9 = origins_top10['Count'].iloc[:9].values\n",
    "counts_1_10 = origins_top10['Count'].iloc[1:].values\n",
    "assert (counts_0_9 >= counts_1_10).all(), \\\n",
    "       \"Are your rows sorted in descending order?\"\n",
    "\n",
    "print(\"\\n(Passed!)\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "exercise_2",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "**Exercise 2** (2 points). The preceding code computed a tibble, `origins`, containing all the unique origins and their number of outgoing flights. Write some code to compute a new tibble, `dests`, which contains all unique destinations and their number of _incoming_ flights. Its columns should be named `DEST_AIRPORT_ID` (airport code) and `DEST_COUNT` (number of direct inbound segments).\n",
    "\n",
    "The test cell that follows prints the number of unique destinations and the first few rows of your result, as well as some automatic checks."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "nbgrader": {
     "grade": false,
     "grade_id": "dests",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "#\n",
    "# YOUR CODE HERE\n",
    "#\n",
    "\n",
    "print(\"Number of unique destinations:\", len(dests))\n",
    "dests.head()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "nbgrader": {
     "grade": true,
     "grade_id": "dests_test",
     "locked": true,
     "points": 2,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "# Test cell: `dests_test`\n",
    "\n",
    "if False:\n",
    "    dests.to_csv('dests_soln.csv', index=False)\n",
    "dests_soln = pd.read_csv('{}{}'.format(DATA_PATH, 'dests_soln.csv'))\n",
    "\n",
    "assert tibbles_are_equivalent(dests, dests_soln), \"Your solution does not match the instructors'.\"\n",
    "\n",
    "print(\"\\n(Passed!)\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "exercise_3",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "**Exercise 3** (2 points). Compute a tibble, `dests_top10`, containing the top 10 destinations (i.e., rows of `dests`) by inbound flight count. The column names should be the same as `origins_top10` and the rows should be sorted in decreasing order by count."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "nbgrader": {
     "grade": false,
     "grade_id": "dests_top10",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "#\n",
    "# YOUR CODE HERE\n",
    "#\n",
    "\n",
    "print(\"Your computed top 10 destinations:\")\n",
    "dests_top10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "nbgrader": {
     "grade": true,
     "grade_id": "dests_top10_test",
     "locked": true,
     "points": 2,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "# Test cell: `dests_top10_test`\n",
    "\n",
    "if False:\n",
    "    dests_top10.to_csv('dests_top10_soln.csv', index=False)\n",
    "dests_top10_soln = pd.read_csv('{}{}'.format(DATA_PATH, 'dests_top10_soln.csv'))\n",
    "\n",
    "print(\"=== Instructor's solution ===\")\n",
    "display(dests_top10_soln)\n",
    "    \n",
    "assert tibbles_are_equivalent(dests_top10, dests_top10_soln), \\\n",
    "       \"Your table does not have the same entries as the solution.\"\n",
    "\n",
    "counts_0_9 = dests_top10['Count'].iloc[:9].values\n",
    "counts_1_10 = dests_top10['Count'].iloc[1:].values\n",
    "assert (counts_0_9 >= counts_1_10).all(), \\\n",
    "       \"Are your rows sorted in descending order?\"\n",
    "\n",
    "print(\"\\n(Passed!)\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "n_actual_intro",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "The number of actual origins does equal the number of actual destinations. Let's store this value for later use."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "nbgrader": {
     "grade": false,
     "grade_id": "n_actual",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "n_actual = len(set(origins['ORIGIN_AIRPORT_ID']) | set(dests['DEST_AIRPORT_ID']))\n",
    "print(\"Number of actual locations (whether origin or destination):\", n_actual)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "preprocess_intro",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Part 1: Constructing the state-transition matrix\n",
    "\n",
    "Now that you have cleaned up the data, let's prepare it for subsequent analysis. Start by constructing the _probability state-transition matrix_ for the airport network. Denote this matrix by $P \\equiv [p_{ij}]$, where $p_{ij}$ is the conditional probability that a random flyer departs from airport $i$ and arrives at airport $j$ given that he or she is currently at airport $i$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "preprocess_outline_tasks",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "To build $P$, let's use SciPy's sparse matrix facilities. To do so, you will need to carry out the following two steps:\n",
    "\n",
    "1. _Map airport codes to matrix indices._ An `m`-by-`n` sparse matrix in SciPy uses the zero-based values 0, 1, ..., `m`-1 and 0, ..., `n`-1 to refer to row and column indices. Therefore, you will need to map the airport codes to such index values.\n",
    "2. _Derive weights, $p_{ij}$._ You will need to decide how to determine $p_{ij}$.\n",
    "\n",
    "Let's walk through each of these steps next."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "preprocess_step_1",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "**Step 1: Mapping airport codes to integers.** Luckily, you already have a code-to-integer mapping, which is in the column `airport_codes['Code']` mapped to the dataframe's `index`.\n",
    "\n",
    "As a first step, let's make note of the number of airports, which is nothing more than the largest index value."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "nbgrader": {
     "grade": false,
     "grade_id": "n_airports",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "n_airports = airport_codes.index.max() + 1\n",
    "print(\"Note: There are\", n_airports, \"airports.\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "preprocess_add_origin_id",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "Next, let's add another column to `segments` called `ORIGIN_INDEX`, which will hold the id corresponding to the origin:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Recall:\n",
    "segments.columns"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "nbgrader": {
     "grade": false,
     "grade_id": "origin_ids",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "# Extract the `Code` column and index from `airport_codes`, storing them in\n",
    "# a temporary tibble with new names, `ORIGIN_AIRPORT_ID` and `ORIGIN_INDEX`.\n",
    "origin_indices = airport_codes[['Code']].rename(columns={'Code': 'ORIGIN_AIRPORT_ID'})\n",
    "origin_indices['ORIGIN_INDEX'] = airport_codes.index\n",
    "                               \n",
    "# Since you might run this code cell multiple times, the following\n",
    "# check prevents `ORIGIN_ID` from appearing more than once.\n",
    "if 'ORIGIN_INDEX' in segments.columns:\n",
    "    del segments['ORIGIN_INDEX']\n",
    "    \n",
    "# Perform the merge as a left-join of `segments` and `origin_ids`.\n",
    "segments = segments.merge(origin_indices, on='ORIGIN_AIRPORT_ID', how='left')\n",
    "segments.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "exercise_4",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "**Exercise 4** (1 point). Analogous to the preceding procedure, create a new column called `segments['DEST_INDEX']` to hold the integer index of each segment's _destination_."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "nbgrader": {
     "grade": false,
     "grade_id": "dest_id",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "#\n",
    "# YOUR CODE HERE\n",
    "#\n",
    "\n",
    "# Visually inspect your result:\n",
    "segments.head()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "nbgrader": {
     "grade": true,
     "grade_id": "dest_id_test",
     "locked": true,
     "points": 1,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "# Test cell: `dest_id_test`\n",
    "\n",
    "if False:\n",
    "    segments.to_csv('segments_soln.csv', index=False)\n",
    "segments_soln = pd.read_csv('{}{}'.format(DATA_PATH, 'segments_soln.csv'))\n",
    "\n",
    "assert tibbles_are_equivalent(segments, segments_soln), \\\n",
    "       \"Your solution does not match the instructors'.\"\n",
    "    \n",
    "print(\"\\n(Passed!)\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "preprocess_step_2",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "**Step 2: Computing edge weights.** Armed with the preceding mapping, let's next determine each segment's transition probability, or \"weight,\" $p_{ij}$.\n",
    "\n",
    "For each origin $i$, let $d_i$ be the number of outgoing edges, or _outdegree_. Note that this value is *not* the same as the total number of (historical) outbound _segments_; rather, let's take $d_i$ to be just the number of airports reachable directly from $i$. For instance, consider all flights departing the airport whose airport code is 10135:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "nbgrader": {
     "grade": false,
     "grade_id": "abe_departures",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "display(airport_codes[airport_codes['Code'] == 10135])\n",
    "\n",
    "abe_segments = segments[segments['ORIGIN_AIRPORT_ID'] == 10135]\n",
    "display(abe_segments)\n",
    "\n",
    "print(\"Total outgoing segments:\", abe_segments['FL_COUNT'].sum())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "nbgrader": {
     "grade": false,
     "grade_id": "display_p_i_j_example",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "k_ABE = abe_segments['FL_COUNT'].sum()\n",
    "d_ABE = len(abe_segments)\n",
    "i_ABE = abe_segments['ORIGIN_AIRPORT_ID'].values[0]\n",
    "\n",
    "display(Markdown('''\n",
    "Though `ABE` has {} outgoing segments,\n",
    "its outdegree or number of outgoing edges is just {}.\n",
    "Thus, `ABE`, whose airport id is $i={}$, has $d_{{{}}} = {}$.\n",
    "'''.format(k_ABE, d_ABE, i_ABE, i_ABE, d_ABE)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "exercise_5",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "**Exercise 5** (3 points). Add a new column named `OUTDEGREE` to the `segments` tibble that holds the outdegrees, $\\{d_i\\}$. That is, for each row whose airport _index_ (as opposed to code) is $i$, its entry of `OUTDEGREE` should be $d_i$.\n",
    "\n",
    "For instance, the rows of segments corresponding to airport ABE (code 10135 and matrix index 119) would look like this:\n",
    "\n",
    "ORIGIN_AIRPORT_ID | DEST_AIRPORT_ID | FL_COUNT | ORIGIN_INDEX | DEST_INDEX | OUTDEGREE\n",
    "------------------|-----------------|----------|--------------|------------|----------\n",
    "10135             | 10397           | 77       | 119          | 373        | 3\n",
    "10135             | 11433           | 85       | 119          | 1375       | 3\n",
    "10135             | 13930           | 18       | 119          | 3770       | 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "nbgrader": {
     "grade": false,
     "grade_id": "weights",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "# This `if` removes an existing `OUTDEGREE` column\n",
    "# in case you run this cell more than once.\n",
    "if 'OUTDEGREE' in segments.columns:\n",
    "    del segments['OUTDEGREE']\n",
    "\n",
    "#\n",
    "# YOUR CODE HERE\n",
    "#\n",
    "\n",
    "# Visually inspect the first ten rows of your result:\n",
    "segments.head(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "nbgrader": {
     "grade": true,
     "grade_id": "weights_test",
     "locked": true,
     "points": 3,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "# Test cell: `weights_test`\n",
    "\n",
    "if False:\n",
    "    segments.to_csv('segments_outdegree_soln.csv', index=False)\n",
    "    \n",
    "segments_outdegree_soln = pd.read_csv('{}{}'.format(DATA_PATH, 'segments_outdegree_soln.csv'))\n",
    "\n",
    "assert tibbles_are_equivalent(segments, segments_outdegree_soln), \\\n",
    "       \"Your solution does not appear to match the instructors'.\"\n",
    "\n",
    "print(\"\\n(Passed!)\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-ef03209a290ef1d1",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "**From outdegree to weight.** Given the outdegree $d_i$, let $p_{ij} = \\frac{1}{d_i}$. In other words, suppose that a random flyer at airport $i$ is _equally likely_ to pick any of the destinations directly reachable from $i$. The following code cell stores that value in a new column, `WEIGHT`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-03271168175f9c17",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "if 'WEIGHT' in segments:\n",
    "    del segments['WEIGHT']\n",
    "    \n",
    "segments['WEIGHT'] = 1.0 / segments['OUTDEGREE']\n",
    "display(segments.head(10))\n",
    "\n",
    "# These should sum to 1.0!\n",
    "origin_groups = segments[['ORIGIN_INDEX', 'WEIGHT']].groupby('ORIGIN_INDEX')\n",
    "assert np.allclose(origin_groups.sum(), 1.0, atol=10*n_actual*np.finfo(float).eps), \"Rows of $P$ do not sum to 1.0\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "exercise_6",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "**Exercise 6** (2 points). With your updated `segments` tibble, construct a sparse matrix, `P`, corresponding to the state-transition matrix $P$. Use SciPy's [scipy.sparse.coo_matrix()](https://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.coo_matrix.html) function to construct this matrix.\n",
    "\n",
    "The dimension of the matrix should be `n_airports` by `n_airports`. If an airport does not have any outgoing segments in the data, it should appear as a row of zeroes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "nbgrader": {
     "grade": false,
     "grade_id": "P",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "#\n",
    "# YOUR CODE HERE\n",
    "#\n",
    "\n",
    "# Visually inspect your result:\n",
    "spy(P)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "nbgrader": {
     "grade": true,
     "grade_id": "P_test",
     "locked": true,
     "points": 1,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "# Test cell: `P_test`\n",
    "\n",
    "assert type(P) is sp.sparse.coo.coo_matrix, \\\n",
    "       \"Matrix object has type {}, and is not a Numpy COO sparse matrix.\".format(type(P))\n",
    "assert P.shape == (n_airports, n_airports), \"Matrix has the wrong shape: it is {} x {} instead of {} x {}\".format(P.shape[0], P.shape[1], n_airports, n_airports)\n",
    "\n",
    "# Check row sums, which must be either 0 or 1\n",
    "n = P.shape[0]\n",
    "u = np.ones(n)\n",
    "row_sums = P.dot(u)\n",
    "is_near_zero = np.isclose(row_sums, 0.0, atol=10*n*np.finfo(float).eps)\n",
    "is_near_one = np.isclose(row_sums, 1.0, atol=10*n*np.finfo(float).eps)\n",
    "assert (is_near_zero | is_near_one).all()\n",
    "assert sum(is_near_one) == n_actual\n",
    "\n",
    "print(\"\\n(Passed!)\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "note_coo_csr",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "> **Note: Other formats.** The preceding code asked you to use coordinate (\"COO\") format to store the matrix. However, you may sometimes need to convert or use other formats. For example, SciPy provides many general graph processing algorithms in its [`csgraph` submodule](https://docs.scipy.org/doc/scipy/reference/sparse.csgraph.html). These routines expect the input graph as a sparse matrix, but one stored in compressed sparse row (\"CSR\") format rather than COO."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "steady_state",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Part 2, analysis: Computing the steady-state distribution\n",
    "\n",
    "Armed with the state-transition matrix $P$, you can now compute the steady-state distribution."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "exercise_7",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "**Exercise 7** (1 point). At time $t=0$, suppose the random flyer is equally likely to be at any airport with an outbound segment, i.e., the flyer is at one of the \"actual\" origins. Create a NumPy vector `x0[:]` such that `x0[i]` equals this initial probability of being at airport `i`.\n",
    "\n",
    "> Note: If some airport $i$ has _no_ outbound flights, then be sure that $x_i(0) = 0$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "nbgrader": {
     "grade": false,
     "grade_id": "x0",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "# Your task: Create `x0` as directed above.\n",
    "\n",
    "#\n",
    "# YOUR CODE HERE\n",
    "#\n",
    "\n",
    "# Visually inspect your result:\n",
    "def display_vec_sparsely(x, name='x'):\n",
    "    i_nz = np.argwhere(x).flatten()\n",
    "    df_x_nz = pd.DataFrame({'i': i_nz, '{}[i] (non-zero only)'.format(name): x[i_nz]})\n",
    "    display(df_x_nz.head())\n",
    "    print(\"...\")\n",
    "    display(df_x_nz.tail())\n",
    "    \n",
    "display_vec_sparsely(x0, name='x0')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "nbgrader": {
     "grade": true,
     "grade_id": "x0_test",
     "locked": true,
     "points": 1,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "# Test cell: `x0_test`\n",
    "\n",
    "assert type(x0) is np.ndarray, \"`x0` does not appear to be a Numpy array.\"\n",
    "assert np.isclose(x0.sum(), 1.0, atol=10*n*np.finfo(float).eps), \"`x0` does not sum to 1.0, but it should.\"\n",
    "assert np.isclose(x0.max(), 1.0/n_actual, atol=10*n*np.finfo(float).eps), \"`x0` values seem off...\"\n",
    "\n",
    "print(\"\\n(Passed!)\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "exercise_8",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "**Exercise 8** (2 points). Given the state-transition matrix `P`, an initial vector `x0`, and the number of time steps `t_max`, complete the function `eval_markov_chain(P, x0, t_max)` so that it computes and returns $x(t_{\\textrm{max}})$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "nbgrader": {
     "grade": false,
     "grade_id": "eval_markov_chain",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "def eval_markov_chain(P, x0, t_max):\n",
    "    #\n",
    "    # YOUR CODE HERE\n",
    "    #\n",
    "\n",
    "T_MAX = 50\n",
    "x = eval_markov_chain(P, x0, T_MAX)\n",
    "display_vec_sparsely(x)\n",
    "\n",
    "print(\"\\n=== Top 10 airports ===\\n\")\n",
    "ranks = np.argsort(-x)\n",
    "top10 = pd.DataFrame({'Rank': np.arange(1, 11),\n",
    "                      'Code': airport_codes.iloc[ranks[:10]]['Code'],\n",
    "                      'Description': airport_codes.iloc[ranks[:10]]['Description'],\n",
    "                      'x(t)': x[ranks[:10]]})\n",
    "top10[['x(t)', 'Rank', 'Code', 'Description']]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "nbgrader": {
     "grade": true,
     "grade_id": "eval_markov_chain_test",
     "locked": true,
     "points": 2,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "# Test cell: `eval_markov_chain_test`\n",
    "\n",
    "print(x.sum())\n",
    "assert np.isclose(x.sum(), 1.0, atol=T_MAX*n_actual*np.finfo(float).eps)\n",
    "\n",
    "print(\"\\nTop 10 airports by Markov chain analysis:\\n\", list(top10['Code']))\n",
    "print(\"\\nCompare that to the Top 10 by (historical) outbound segments:\\n\", list(origins_top10['ID']))\n",
    "\n",
    "A = set(top10['Code'])\n",
    "B = set(origins_top10['ID'])\n",
    "C = (A - B) | (B - A)\n",
    "print(\"\\nAirports that appear in one list but not the other:\\n{}\".format(C))\n",
    "assert C == {11618, 11433, 12266, 14771, 14869, 12889, 14747, 12892}\n",
    "\n",
    "print(\"\\n(Passed!)\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Comparing the two rankings.** Before ending this notebook, let's create a table that compares our two rankings, side-by-side, where the first ranking is the result of the Markov chain analysis and the second from a ranking based solely on number of segments."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "nbgrader": {
     "grade": false,
     "grade_id": "compare_top10s",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "top10_with_ranks = top10[['Code', 'Rank', 'Description']].copy()\n",
    "\n",
    "origins_top10_with_ranks = origins_top10[['ID', 'Description']].copy()\n",
    "origins_top10_with_ranks.rename(columns={'ID': 'Code'}, inplace=True)\n",
    "origins_top10_with_ranks['Rank'] = origins_top10.index + 1\n",
    "origins_top10_with_ranks = origins_top10_with_ranks[['Code', 'Rank', 'Description']]\n",
    "\n",
    "top10_compare = top10_with_ranks.merge(origins_top10_with_ranks, how='outer', on='Code',\n",
    "                                       suffixes=['_MC', '_Seg'])\n",
    "top10_compare"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true,
    "nbgrader": {
     "grade": false,
     "grade_id": "fin",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "**Fin!** That's it! You've determined the top 10 airports at which a random flyer ends up, assuming he or she randomly selects directly reachable destinations. How does it compare, qualitatively, to a ranking based instead on (historical) outbound segments? Which ranking is a better measure of importance to the overall airport network?\n",
    "\n",
    "Be sure to submit this notebook to get credit for it."
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Create Assignment",
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}