<commit_before><commit_msg>graph theory<commit_after>{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import networkx as nx  # you have to install networkx 2.x through `pip install --upgrade networkx`\n",
    "import pandas as pd\n",
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style>\n",
       "    .dataframe thead tr:only-child th {\n",
       "        text-align: right;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: left;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>year</th>\n",
       "      <th>month</th>\n",
       "      <th>day</th>\n",
       "      <th>dep_time</th>\n",
       "      <th>sched_dep_time</th>\n",
       "      <th>dep_delay</th>\n",
       "      <th>arr_time</th>\n",
       "      <th>sched_arr_time</th>\n",
       "      <th>arr_delay</th>\n",
       "      <th>carrier</th>\n",
       "      <th>flight</th>\n",
       "      <th>tailnum</th>\n",
       "      <th>origin</th>\n",
       "      <th>dest</th>\n",
       "      <th>air_time</th>\n",
       "      <th>distance</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>2013</td>\n",
       "      <td>2</td>\n",
       "      <td>26</td>\n",
       "      <td>1807.0</td>\n",
       "      <td>1630</td>\n",
       "      <td>97.0</td>\n",
       "      <td>1956.0</td>\n",
       "      <td>1837</td>\n",
       "      <td>79.0</td>\n",
       "      <td>EV</td>\n",
       "      <td>4411</td>\n",
       "      <td>N13566</td>\n",
       "      <td>EWR</td>\n",
       "      <td>MEM</td>\n",
       "      <td>144.0</td>\n",
       "      <td>946</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>2013</td>\n",
       "      <td>8</td>\n",
       "      <td>17</td>\n",
       "      <td>1459.0</td>\n",
       "      <td>1445</td>\n",
       "      <td>14.0</td>\n",
       "      <td>1801.0</td>\n",
       "      <td>1747</td>\n",
       "      <td>14.0</td>\n",
       "      <td>B6</td>\n",
       "      <td>1171</td>\n",
       "      <td>N661JB</td>\n",
       "      <td>LGA</td>\n",
       "      <td>FLL</td>\n",
       "      <td>147.0</td>\n",
       "      <td>1076</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>2013</td>\n",
       "      <td>2</td>\n",
       "      <td>13</td>\n",
       "      <td>1812.0</td>\n",
       "      <td>1815</td>\n",
       "      <td>-3.0</td>\n",
       "      <td>2055.0</td>\n",
       "      <td>2125</td>\n",
       "      <td>-30.0</td>\n",
       "      <td>AS</td>\n",
       "      <td>7</td>\n",
       "      <td>N403AS</td>\n",
       "      <td>EWR</td>\n",
       "      <td>SEA</td>\n",
       "      <td>315.0</td>\n",
       "      <td>2402</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>2013</td>\n",
       "      <td>4</td>\n",
       "      <td>11</td>\n",
       "      <td>2122.0</td>\n",
       "      <td>2115</td>\n",
       "      <td>7.0</td>\n",
       "      <td>2339.0</td>\n",
       "      <td>2353</td>\n",
       "      <td>-14.0</td>\n",
       "      <td>B6</td>\n",
       "      <td>97</td>\n",
       "      <td>N656JB</td>\n",
       "      <td>JFK</td>\n",
       "      <td>DEN</td>\n",
       "      <td>221.0</td>\n",
       "      <td>1626</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>2013</td>\n",
       "      <td>8</td>\n",
       "      <td>5</td>\n",
       "      <td>1832.0</td>\n",
       "      <td>1835</td>\n",
       "      <td>-3.0</td>\n",
       "      <td>2145.0</td>\n",
       "      <td>2155</td>\n",
       "      <td>-10.0</td>\n",
       "      <td>AA</td>\n",
       "      <td>269</td>\n",
       "      <td>N3EYAA</td>\n",
       "      <td>JFK</td>\n",
       "      <td>SEA</td>\n",
       "      <td>358.0</td>\n",
       "      <td>2422</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   year  month  day  dep_time  sched_dep_time  dep_delay  arr_time  \\\n",
       "0  2013      2   26    1807.0            1630       97.0    1956.0   \n",
       "1  2013      8   17    1459.0            1445       14.0    1801.0   \n",
       "2  2013      2   13    1812.0            1815       -3.0    2055.0   \n",
       "3  2013      4   11    2122.0            2115        7.0    2339.0   \n",
       "4  2013      8    5    1832.0            1835       -3.0    2145.0   \n",
       "\n",
       "   sched_arr_time  arr_delay carrier  flight tailnum origin dest  air_time  \\\n",
       "0            1837       79.0      EV    4411  N13566    EWR  MEM     144.0   \n",
       "1            1747       14.0      B6    1171  N661JB    LGA  FLL     147.0   \n",
       "2            2125      -30.0      AS       7  N403AS    EWR  SEA     315.0   \n",
       "3            2353      -14.0      B6      97  N656JB    JFK  DEN     221.0   \n",
       "4            2155      -10.0      AA     269  N3EYAA    JFK  SEA     358.0   \n",
       "\n",
       "   distance  \n",
       "0       946  \n",
       "1      1076  \n",
       "2      2402  \n",
       "3      1626  \n",
       "4      2422  "
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "data = pd.read_csv(\"airlines.csv\")\n",
    "data.head()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style>\n",
       "    .dataframe thead tr:only-child th {\n",
       "        text-align: right;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: left;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>year</th>\n",
       "      <th>month</th>\n",
       "      <th>day</th>\n",
       "      <th>dep_time</th>\n",
       "      <th>sched_dep_time</th>\n",
       "      <th>dep_delay</th>\n",
       "      <th>arr_time</th>\n",
       "      <th>sched_arr_time</th>\n",
       "      <th>arr_delay</th>\n",
       "      <th>carrier</th>\n",
       "      <th>flight</th>\n",
       "      <th>tailnum</th>\n",
       "      <th>origin</th>\n",
       "      <th>dest</th>\n",
       "      <th>air_time</th>\n",
       "      <th>distance</th>\n",
       "      <th>std</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>2013</td>\n",
       "      <td>2</td>\n",
       "      <td>26</td>\n",
       "      <td>1807.0</td>\n",
       "      <td>1630</td>\n",
       "      <td>97.0</td>\n",
       "      <td>1956.0</td>\n",
       "      <td>1837</td>\n",
       "      <td>79.0</td>\n",
       "      <td>EV</td>\n",
       "      <td>4411</td>\n",
       "      <td>N13566</td>\n",
       "      <td>EWR</td>\n",
       "      <td>MEM</td>\n",
       "      <td>144.0</td>\n",
       "      <td>946</td>\n",
       "      <td>16:30:00</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>2013</td>\n",
       "      <td>8</td>\n",
       "      <td>17</td>\n",
       "      <td>1459.0</td>\n",
       "      <td>1445</td>\n",
       "      <td>14.0</td>\n",
       "      <td>1801.0</td>\n",
       "      <td>1747</td>\n",
       "      <td>14.0</td>\n",
       "      <td>B6</td>\n",
       "      <td>1171</td>\n",
       "      <td>N661JB</td>\n",
       "      <td>LGA</td>\n",
       "      <td>FLL</td>\n",
       "      <td>147.0</td>\n",
       "      <td>1076</td>\n",
       "      <td>14:45:00</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>2013</td>\n",
       "      <td>2</td>\n",
       "      <td>13</td>\n",
       "      <td>1812.0</td>\n",
       "      <td>1815</td>\n",
       "      <td>-3.0</td>\n",
       "      <td>2055.0</td>\n",
       "      <td>2125</td>\n",
       "      <td>-30.0</td>\n",
       "      <td>AS</td>\n",
       "      <td>7</td>\n",
       "      <td>N403AS</td>\n",
       "      <td>EWR</td>\n",
       "      <td>SEA</td>\n",
       "      <td>315.0</td>\n",
       "      <td>2402</td>\n",
       "      <td>18:15:00</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>2013</td>\n",
       "      <td>4</td>\n",
       "      <td>11</td>\n",
       "      <td>2122.0</td>\n",
       "      <td>2115</td>\n",
       "      <td>7.0</td>\n",
       "      <td>2339.0</td>\n",
       "      <td>2353</td>\n",
       "      <td>-14.0</td>\n",
       "      <td>B6</td>\n",
       "      <td>97</td>\n",
       "      <td>N656JB</td>\n",
       "      <td>JFK</td>\n",
       "      <td>DEN</td>\n",
       "      <td>221.0</td>\n",
       "      <td>1626</td>\n",
       "      <td>21:15:00</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>2013</td>\n",
       "      <td>8</td>\n",
       "      <td>5</td>\n",
       "      <td>1832.0</td>\n",
       "      <td>1835</td>\n",
       "      <td>-3.0</td>\n",
       "      <td>2145.0</td>\n",
       "      <td>2155</td>\n",
       "      <td>-10.0</td>\n",
       "      <td>AA</td>\n",
       "      <td>269</td>\n",
       "      <td>N3EYAA</td>\n",
       "      <td>JFK</td>\n",
       "      <td>SEA</td>\n",
       "      <td>358.0</td>\n",
       "      <td>2422</td>\n",
       "      <td>18:35:00</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   year  month  day  dep_time  sched_dep_time  dep_delay  arr_time  \\\n",
       "0  2013      2   26    1807.0            1630       97.0    1956.0   \n",
       "1  2013      8   17    1459.0            1445       14.0    1801.0   \n",
       "2  2013      2   13    1812.0            1815       -3.0    2055.0   \n",
       "3  2013      4   11    2122.0            2115        7.0    2339.0   \n",
       "4  2013      8    5    1832.0            1835       -3.0    2145.0   \n",
       "\n",
       "   sched_arr_time  arr_delay carrier  flight tailnum origin dest  air_time  \\\n",
       "0            1837       79.0      EV    4411  N13566    EWR  MEM     144.0   \n",
       "1            1747       14.0      B6    1171  N661JB    LGA  FLL     147.0   \n",
       "2            2125      -30.0      AS       7  N403AS    EWR  SEA     315.0   \n",
       "3            2353      -14.0      B6      97  N656JB    JFK  DEN     221.0   \n",
       "4            2155      -10.0      AA     269  N3EYAA    JFK  SEA     358.0   \n",
       "\n",
       "   distance       std  \n",
       "0       946  16:30:00  \n",
       "1      1076  14:45:00  \n",
       "2      2402  18:15:00  \n",
       "3      1626  21:15:00  \n",
       "4      2422  18:35:00  "
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "data['std'] = data.sched_dep_time.astype(str).str.replace('(\\d{2}$)', '') + ':' + data.sched_dep_time.astype(str).str.extract('(\\d{2}$)', expand=False) + ':00'\n",
    "data.head()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "FG = nx.from_pandas_edgelist(data, source='origin', target='dest', edge_attr=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "NodeView(('JFK', 'MSY', 'CMH', 'MIA', 'ATL', 'BOS', 'MSP', 'FLL', 'DEN', 'CVG', 'DTW', 'JAX', 'DCA', 'SEA', 'CLE', 'MDW', 'RDU', 'IAH', 'TPA', 'STL', 'IAD', 'DFW', 'SJU', 'SRQ', 'CLT', 'EWR', 'PBI', 'MCO', 'BHM', 'MEM', 'LGA', 'SFO', 'LAX', 'IND', 'ORD', 'RSW'))"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "FG.nodes()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "EdgeView([('JFK', 'MCO'), ('JFK', 'IAD'), ('JFK', 'DEN'), ('JFK', 'TPA'), ('JFK', 'PBI'), ('JFK', 'ATL'), ('JFK', 'BOS'), ('JFK', 'JAX'), ('JFK', 'SJU'), ('JFK', 'SRQ'), ('JFK', 'LAX'), ('JFK', 'FLL'), ('JFK', 'SEA'), ('JFK', 'CLE'), ('JFK', 'CLT'), ('JFK', 'DCA'), ('JFK', 'DTW'), ('MSY', 'EWR'), ('CMH', 'LGA'), ('MIA', 'EWR'), ('MIA', 'LGA'), ('ATL', 'LGA'), ('BOS', 'EWR'), ('MSP', 'EWR'), ('MSP', 'LGA'), ('FLL', 'LGA'), ('DEN', 'LGA'), ('CVG', 'EWR'), ('CVG', 'LGA'), ('DTW', 'LGA'), ('DCA', 'LGA'), ('SEA', 'EWR'), ('MDW', 'LGA'), ('RDU', 'EWR'), ('RDU', 'LGA'), ('IAH', 'EWR'), ('IAH', 'LGA'), ('TPA', 'EWR'), ('TPA', 'LGA'), ('STL', 'LGA'), ('IAD', 'EWR'), ('IAD', 'LGA'), ('DFW', 'EWR'), ('SJU', 'EWR'), ('CLT', 'LGA'), ('EWR', 'MCO'), ('EWR', 'SFO'), ('EWR', 'MEM'), ('EWR', 'LAX'), ('EWR', 'IND'), ('EWR', 'ORD'), ('EWR', 'RSW'), ('EWR', 'PBI'), ('PBI', 'LGA'), ('MCO', 'LGA'), ('BHM', 'LGA'), ('LGA', 'ORD')])"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "FG.edges()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "<KEY>//+<KEY>",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x119d16190>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "%matplotlib inline\n",
    "nx.draw_networkx(FG, with_labels=True, node_color='green')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'ATL': 0.05714285714285714,\n",
       " 'BHM': 0.02857142857142857,\n",
       " 'BOS': 0.05714285714285714,\n",
       " 'CLE': 0.02857142857142857,\n",
       " 'CLT': 0.05714285714285714,\n",
       " 'CMH': 0.02857142857142857,\n",
       " 'CVG': 0.05714285714285714,\n",
       " 'DCA': 0.05714285714285714,\n",
       " 'DEN': 0.05714285714285714,\n",
       " 'DFW': 0.02857142857142857,\n",
       " 'DTW': 0.05714285714285714,\n",
       " 'EWR': 0.5714285714285714,\n",
       " 'FLL': 0.05714285714285714,\n",
       " 'IAD': 0.08571428571428572,\n",
       " 'IAH': 0.05714285714285714,\n",
       " 'IND': 0.02857142857142857,\n",
       " 'JAX': 0.02857142857142857,\n",
       " 'JFK': 0.4857142857142857,\n",
       " 'LAX': 0.05714285714285714,\n",
       " 'LGA': 0.5714285714285714,\n",
       " 'MCO': 0.08571428571428572,\n",
       " 'MDW': 0.02857142857142857,\n",
       " 'MEM': 0.02857142857142857,\n",
       " 'MIA': 0.05714285714285714,\n",
       " 'MSP': 0.05714285714285714,\n",
       " 'MSY': 0.02857142857142857,\n",
       " 'ORD': 0.05714285714285714,\n",
       " 'PBI': 0.08571428571428572,\n",
       " 'RDU': 0.05714285714285714,\n",
       " 'RSW': 0.02857142857142857,\n",
       " 'SEA': 0.05714285714285714,\n",
       " 'SFO': 0.02857142857142857,\n",
       " 'SJU': 0.05714285714285714,\n",
       " 'SRQ': 0.02857142857142857,\n",
       " 'STL': 0.02857142857142857,\n",
       " 'TPA': 0.08571428571428572}"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# degree centrality measures the number of edges connected to a node\n",
    "nx.algorithms.degree_centrality(FG)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.09047619047619047"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# average density of the graph\n",
    "## Density - how many edges a graph. A complete undirect graph has 1 as density\n",
    "## Some graphs has 1+ density, such as a graph with loops\n",
    "nx.density(FG)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2.36984126984127"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# average shortest path among all the paths\n",
    "nx.average_shortest_path_length(FG)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{1: 19.307692307692307, 2: 19.0625, 3: 19.0, 17: 2.0588235294117645, 20: 1.95}"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# average of a node's neighbours' degree, for each node with degree k\n",
    "nx.average_degree_connectivity(FG)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['LAX', 'JFK', 'MCO', 'EWR', 'SEA']\n"
     ]
    }
   ],
   "source": [
    "for path in nx.all_simple_paths(FG, source='LAX', target='SEA'):\n",
    "    print(path)\n",
    "    break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['LAX', 'JFK', 'SEA']"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# find dijkstra path between LA and Seattle\n",
    "dijpath = nx.dijkstra_path(FG, source='LAX', target='SEA')\n",
    "dijpath"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['LAX', 'EWR', 'SEA']"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# find dijkstra path between LA and Seattle, weighted by air_time\n",
    "weighted_dijpath = nx.dijkstra_path(FG, source='LAX', target='SEA', weight='air_time')\n",
    "weighted_dijpath"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "\"\"\"\n",
    "For more algorithms provided by networkx: https://networkx.github.io/documentation/stable/reference/algorithms/index.html\n",
    "\n",
    "Reference: https://www.analyticsvidhya.com/blog/2018/04/introduction-to-graph-theory-network-analysis-python-codes/?utm_source=feedburner&utm_medium=email&utm_campaign=Feed%3A+AnalyticsVidhya+%28Analytics+Vidhya%29\n",
    "\"\"\""
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
{'fraction_non_alphanumeric': 0.24255213505461767, 'fraction_numerical': 0.08897715988083416, 'mean_word_length': 1.4234147515341113, 'pattern_counts': {'":': 156, '<': 470, '<?xml version=': 0, '>': 470, 'https://': 2, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4709809', 'n_tokens_mistral': 9371, 'n_tokens_neox': 8331, 'n_words': 1210}