{
 "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": [
    "from_airport = input(\"From airport: \")\n",
    "to_airport = input(\"To airport: \")\n",
    "\n",
    "if flight_graph.has_node(from_airport) and flight_graph.has_node(to_airport):\n",
    "    route = nx.shortest_path(flight_graph, from_airport, to_airport)\n",
    "    print(\"Route: %s\" % route)\n",
    "    \n",
    "    length = 0\n",
    "    for i in range(1, len(route)):\n",
    "        length += flight_graph[route[i-1]][route[i]]['distance']\n",
    "    print(\"Length: %d mi\" % length)\n",
    "else:\n",
    "    print(\"Source or destination airport was not found.\")"
   ]
  },
  {
   "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": [
    "from_airport = input(\"From airport: \")\n",
    "to_airport = input(\"To airport: \")\n",
    "\n",
    "if flight_graph.has_node(from_airport) and flight_graph.has_node(to_airport):\n",
    "    route = nx.dijkstra_path(flight_graph, from_airport, to_airport, 'distance')\n",
    "    length = nx.dijkstra_path_length(flight_graph, from_airport, to_airport, 'distance')\n",
    "    print(\"Route: %s (%d mi)\" % (route, length))\n",
    "else:\n",
    "    print(\"Source or destination airport was not found.\")"
   ]
  },
  {
   "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": [
    "def custom_distance(from_node, to_node, edge_attr):\n",
    "    if airports.loc[to_node]['longest'] < 8000:\n",
    "        return None\n",
    "    if airports.loc[to_node]['runways'] == 1:\n",
    "        return edge_attr['distance'] * 1.5\n",
    "    return edge_attr['distance']\n",
    "\n",
    "from_airport = input(\"From airport: \")\n",
    "to_airport = input(\"To airport: \")\n",
    "\n",
    "if flight_graph.has_node(from_airport) and flight_graph.has_node(to_airport):\n",
    "    route = nx.dijkstra_path(flight_graph, from_airport, to_airport, custom_distance)\n",
    "    length = nx.dijkstra_path_length(flight_graph, from_airport, to_airport, custom_distance)\n",
    "    print(\"Route: %s (%d mi)\" % (route, length))\n",
    "else:\n",
    "    print(\"Source airport was not found.\")"
   ]
  },
  {
   "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": [
    "from_airport = input(\"From airport: \")\n",
    "max_distance = int(input(\"Max distance: \"))\n",
    "\n",
    "if flight_graph.has_node(from_airport):\n",
    "    lengths, routes = nx.single_source_dijkstra(flight_graph, from_airport, None, max_distance, 'distance')\n",
    "    for to_airport in routes.keys():\n",
    "        print(\"%s -> %s: %s (%d mi)\" % (from_airport, to_airport, routes[to_airport], length[to_airport]))\n",
    "else:\n",
    "    print(\"Source or destination airport was not found.\")"
   ]
  },
  {
   "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": [
    "from_city = input(\"From city: \")\n",
    "max_distance = int(input(\"Max distance: \"))\n",
    "\n",
    "from_airports = airports[airports['city'] == from_city].index\n",
    "result = []\n",
    "for from_airport in from_airports:\n",
    "    routes = nx.single_source_dijkstra_path(flight_graph, from_airport, max_distance, 'distance')\n",
    "    to_airports = routes.keys()\n",
    "    to_cities = [airports.loc[ap]['city'] for ap in to_airports]\n",
    "    result += to_cities\n",
    "\n",
    "result_unique = set(result) # remove duplicates\n",
    "print(sorted(result_unique)) # sort the printed result"
   ]
  }
 ],
 "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
}