{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Lecture 7: Graph algorithms I. - shortest path"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The sample dataset for this lecture is given in the `07_airports.csv` and `07_airroutes.csv` files. (The column separator is the `;` character.)\n",
    "\n",
    "* The `07_airports.csv` contains some important attributes of airports all over the planet.\n",
    "* The `07_airroutes.csv` consists of the direct flight relations between the airports, identifying them with their IATA code. The distance of the airports / length of the flight route is also given. The flights are directed, if there is a flight between both directions of two airports, then there will be two records in the file, with opposite direction."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Reading the dataset"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Read the airport data"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "First read the airports data into a pandas *DataFrame*."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import pandas as pd\n",
    "\n",
    "airports = pd.read_csv('07_airports.csv', delimiter = ';')\n",
    "display(airports)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Note:* the length of the longest runway is given in feets."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Lets set the column `iata` as the index column, so each row of data will be accessible later by indexing the airports with their IATA code."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "airports.set_index('iata', inplace=True)\n",
    "display(airports)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Remark:* the `set_index` function can be configured to modify the index in place or return a new *Dataframe* with the `inplace` parameter (defaults to `False`)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Remark:* the `set_index` function can be configured to drop or keep the index column with the `drop` parameter (defaults to `True`)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The information of the Budapest Airport can now be accessed both by numerical and associative (string) indexing:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print('The Budapest airport by the numerical index:')\n",
    "print(airports.iloc[111])\n",
    "print()\n",
    "print('The Budapest airport by the associative index:')\n",
    "print(airports.loc['BUD'])\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The number of runways the Budapest Airport can be fetched (or modified) now 4 possible ways:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(airports.iloc[111]['runways'])\n",
    "print(airports.loc['BUD']['runways'])\n",
    "print(airports['runways'][111])\n",
    "print(airports['runways']['BUD'])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Read the airroutes data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "airroutes = pd.read_csv('07_airroutes.csv', delimiter = ';')\n",
    "display(airroutes)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Note:* the distance is given in miles."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Build a graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*NetworkX* has an integrated conversion for *pandas* DataFrames which can be used.  \n",
    "Lets create a directed graph (`networkx.DiGraph`) from the flights. The edges shall be weighted with the distance of the routes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import networkx as nx\n",
    "\n",
    "flight_graph = nx.from_pandas_edgelist(airroutes, 'from', 'to', ['distance'], create_using = nx.DiGraph)\n",
    "\n",
    "print('Metadata for the BUD -> JFK edge: %s' % flight_graph['BUD']['JFK'])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Remark*: The 4<sup>th</sup> parameter defines which *Series* (columns) of the *DataFrame* shall be added to the edges as attributes. If `True`, all of the remaining columns will be added. If `None`, no edge attributes are added to the graph. Its default value is `None`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercises"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 1.** Calculate the path between 2 user given airports with the minimal number of transfers."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 2.** Calculate the shortest path by distance between 2 user given airports."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 3.** Calculate the shortest between 2 user given airports by distance, but with the following addittional conditions:\n",
    "* airports with no longer runway than 8000 feets cannot be used;\n",
    "* airports with only 1 runway has a 50% penalty of the distance."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 4.** Calculate which airports can be reached from a starting, user given airport within a reach of also user given distance (in miles). What is the shorthest path by distance to each of them?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 5.** Calculate which cities can be reached from a starting, user given city within a reach of also user given distance (in miles)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "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.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}