Subway-Report.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img align='right' width='200' style=\"float:right;\" src=\"./Images/0000.Subway-Time.png\" />\n",
    "\n",
    "<div style=\"text-align:center;margin:0;font-size:12px;color:#c1121f\" align='center'>\n",
    "    <b> Data Science = Solving Problems = Happiness </b>\n",
    "</div>\n",
    "<div align='center'>\n",
    "    <h1> The Subway Challenge</h1>\n",
    "</div>\n",
    "<div align='center'>\n",
    "    Denzel S. Williams\n",
    "</div>\n",
    "<div align='center'>\n",
    "    <i>Springboard Data Science Track '21</i>\n",
    "</div>\n",
    "<div align='center'>\n",
    "    <a href=\"https://linkedin.com/in/williamdst\">\n",
    "        <img align='center' src=\"https://img.shields.io/badge/LinkedIn-0077B5?style=for-the-badge&logo=linkedin&logoColor=white\" width=\"75\" />\n",
    "    </a>\n",
    "    <a href=\"https://nbviewer.jupyter.org/github/Williamdst/The-Subway-Challenge/blob/main/Subway-Report.ipynb\">\n",
    "        <img align='center' src=\"https://img.shields.io/badge/Markdown-000000?style=for-the-badge&logo=markdown&logoColor=white\" width='80'/>\n",
    "    </a>\n",
    "    <a href=\"https://github.com/Williamdst/The-Subway-Challenge/blob/main/Subway-Presentation.pdf\" />\n",
    "        <img align='center' src=\"https://img.shields.io/badge/Microsoft_PowerPoint-B7472A?style=for-the-badge&logo=microsoft-powerpoint&logoColor=white\" width='150' />\n",
    "    </a>\n",
    "</div> "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h2>0. Introduction </h2>\n",
    "To set a record in the Subway Challenge a participant must navigate the entire New York City Subway system (network) in the shortest time possible. The challenge requires competitors to stop at all 472 stations in the network and no person currently holds that record <a href=\"https://en.wikipedia.org/wiki/Subway_Challenge#Guinness_Record_times\"> [1] </a>. The most recent record of 21H:28M:14S was set on July 22, 2016 by Matthew Ahn for the 469-Station Challenge <a href=\"https://www.timeout.com/newyork/blog/solo-straphanger-sets-new-all-station-subway-world-record-090616\"> [2]</a>. Aside from beginning at Far Rockaway-Mott Avenue and ending at Flushing-Main Street, the route and methodology he used to beat the record is unknown. <br></br>\n",
    "\n",
    "<p style='text-align:center'> <b>The goal of this project is to use graph theory to determine a set of paths that could potentially be used to beat the current record.</b> </p>\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h2>1. Understanding the Problem </h2>\n",
    "To solve this problem a graph representation of the subway system needs to be constructed. The system can be modeled as a weighted undirected graph, where the weights on the edges are the time it takes to get from one station to the next. Since you can travel in both directions on each line the direction is not needed (there is one station that is an exception). The actual map of the system needs to be translated into nodes and edges; to simplify this translation the <a href=\"https://new.mta.info/map/5336\">Late-Night Subway Service</a> map is used. In the late-night subway map all stations are served though not all lines run; most lines run local, making all stops. The late-night map is a starting point to attempt beating the challenge. The map cannot be used, as is, to beat the challenge because the map is only valid from 00:00 - 06:00 every day. The results of the late-night map will tell you <b>what</b> to do, but not <b>how</b> to do it. <br></br>\n",
    "\n",
    "Once 06:00 hits, all trains are activated, and express routes are implemented. For example, the late-night A-Train might go to certain stops, but it skips over them in the day. In the day, the A-Train is an express train and staying on it for the entire line wouldn’t take you to every stop. At some point you would have to get off and make a transfer to the local C-train to check off the stops that the A-Train skips. This is the main reason why the objective is to determine a set of paths and not just a single path. The only weight the program understands is the time between stations, it doesn't understand that train switching is expensive. Every time you get off a train you must wait for the next one to arrive, which adds to the overall time. Therefore, the program can only return a set of potential options that a human would then need to filter through."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<p style='text-align:right'> <b>1.0.A Chinese Postman Problem</b> </p>\n",
    "\n",
    "Like any route-inspection style problem, the Subway Challenge is about decision making, specifically what are you going to do at junctions, stations where you can transfer to a different line, or in the graph theoretical sense, nodes with degree greater than 2. Let's look at the simple network below to understand the idea. The challenge is to stop at every station, and you plan on starting at A. You can basically ignore stations B and C because to get from A to D you don't have a choice but to stop at those stations. It's when you get to station D a choice has to be made. Do you go to F first, come back to D, and then go to E or do you go to E first, come back and go to F. Taking the ABC<b>DFD</b>E route will cost you 28, compared to the 20 it will cost you taking route ABC<b>DED</b>F. What makes the Subway Challenge tricky is that taking the optimal DED route requires you to get off the blue train you started on and wait for the red train, then again in reverse. Whereas the less optimal route only requires one transfer. If the wait time at D for a train is over 8 then the suboptimal DFD route becomes the optimal route.\n",
    "\n",
    "<figure style='text-align:center'>\n",
    "    <img src=\"https://raw.githubusercontent.com/Williamdst/Capstone-2/main/Images/0000.Network-Simple.png\" style='max-width:50%'/>\n",
    "    <figcaption style='text-align:center'> Figure 1. Simple Graph to Understand the Problem </figcaption>\n",
    "</figure>\n",
    "\n",
    "Revisiting the idea of ignoring stations B and C; at those stations you have no choices and on your way to D you will pass them anyway. If that is the case, then you can reduce the number of nodes in network by consolidated them into a single edge (<i>Figure 2</i>). Doing this changes how the challenge is viewed. The nodes in the network used to be every station, now the nodes are only the stations where you must decide on an action, but you still must get to every station. Therefore, in terms of the graph, you need to travel <b>every edge at least once</b>. By meeting that condition you will automatically stop at every station. This modification officially turns our problem into a <b>Chinese Postman Problem</b> (CPP). In simplest terms, the Chinese postman problem aims is to find a path that visits every edge of a graph.\n",
    "\n",
    "<figure style='text-align:center'>\n",
    "    <img src=\"https://raw.githubusercontent.com/Williamdst/Capstone-2/main/Images/0001.Network-Simple-Reduced.png\" style='max-width:50%'/>\n",
    "    <figcaption style='text-align:center'> Figure 2. The Simple Graph Reduced </figcaption>\n",
    "</figure>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h2> 2. Modifying a Prepackaged Solution </h2>\n",
    "In 2017, Andrew Brooks was tackling a similar problem which he solved using the NetworkX 2.0 library <a href=\"https://www.datacamp.com/community/tutorials/networkx-python-graph-tutorial\"> [3]</a>. Thankfully, he packaged his solution into the <a href=\"https://github.com/brooksandrew/postman_problems\">postman_problems</a>. With this package, you can plug in your own network and solve the CPP problem. Unfortunately, the Subway Challenge isn't a typical CPP problem. The postman always wants to return to his vehicle, so the CPP finds a path that ends where it began. The Subway Challenge has no such requirement, the sole condition is to travel to all the edges at least once. Andrew's postman_package solves the CPP as is, therefore plugging in the subway network wouldn't work because it would always output a sub-optimal solution. However, with a little bit of network theory, the NetworkX 2.5 update, and some tweaks to his package, we could build on his work to solve the problem."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<p style='text-align:center'> <b> 2.1 The Graph Theory Behind Andrew's Solution</b> </p>    \n",
    "In graph theory, a path is a sequence of vertices with the property that each vertex in the sequence is adjacent to the vertex next to it. A circuit is a path that begins and ends at the same vertex. Thinking in terms of racing, a path is a street race. You don't necessarily end up at the same point where you started (although you could) and all the streets are connected to each other. A circuit is a NASCAR race, where you always end where you start. A Euler circuit not only has to meet the conditions of a regular circuit (starting and ending at the same place) it has the added conditions that you have to use <b>every edge</b> of the graph AND you can only use <b>each edge once</b>. This is where the where the issues begin as there is a theorem that states: <br />\n",
    "<p style='text-align:center'> A connected graph $G$ has an Euler Circuit if and only if every vertex has even degree <p>\n",
    "In Andrew's problem there are many nodes that have odd degrees, which means there isn't a Euler circuit. To get around this, his solution was to turn odd-degree nodes even by adding artificial edges to those nodes. Then with all even-degree nodes, NetworkX finds the Euler circuit."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<p style='text-align:right'> <b>2.1.A Understanding The Steps</b> </p>\n",
    "First, he loads in the edge list and then creates the graph from the edge list. The graph that we will use to understand his methodology is shown below. The graph is a weighted undirected graph where the orange nodes are the odd degree nodes.\n",
    "\n",
    "<figure style='text-align:center'>\n",
    "    <img src=\"https://raw.githubusercontent.com/Williamdst/Capstone-2/main/Images/0002.Network-Follow.png\" style='max-width:20%'/>\n",
    "    <figcaption style='text-align:center'> Figure 3. The Graph for the Follow-Along </figcaption>\n",
    "</figure>\n",
    "\n",
    "<b>The theorem states that only graphs where all nodes are even degree qualify to have Euler circuits, so his first efforts are to make all the nodes even.</b> He starts by first creating a separate graph where the odd nodes are artificially paired together. The artificial edges are shown in red and the weights on them represent the <b>fastest</b> time to get from the nodes using <b>actual paths</b> (<i>In this separate graph the even degree nodes and their connections don't exist</i>).\n",
    "\n",
    "<figure style='text-align:center'>\n",
    "    <img src=\"https://raw.githubusercontent.com/Williamdst/Capstone-2/main/Images/0003.Network-Follow-Odd-Augment.png\" style='max-width:20%'/>\n",
    "    <figcaption style='text-align:center'> Figure 4. Odd Nodes Complete Graph via Artificial Paths </figcaption>\n",
    "</figure>\n",
    "\n",
    "All the paths in red aren't necessary, because to turn an odd-degree node even you only need to add a single path. This is where the idea of a matching comes into play, specifically a minimum weight matching. Listed below are three diverse ways to think about matchings:\n",
    "<ol>\n",
    "    <li> A matching is a subset of edges in which no node occurs more than once. </li>\n",
    "    <li> A matching is a graph where all the nodes have a degree of 0 or 1. </li>\n",
    "    <li> A matching is a subgraph of a graph where there are no edges adjacent to each other </li>\n",
    "</ol>\n",
    "\n",
    "The weight of a matching is the sum of the weights of its edges; the cardinality is the number of matched edges. What we are looking for is a matching that has <b>maximum cardinality</b> but <b>minimum weight</b>. Based on the previous graph there are only three choices for matchings (<i>Figure 5</i>) and the one that is ultimately chosen is the middle one with the minimum weight of 11.\n",
    "\n",
    "<figure style='text-align:center'>\n",
    "    <img src=\"https://raw.githubusercontent.com/Williamdst/Capstone-2/main/Images/0004.Network-Follow-Matchings.png\" style='max-width:50%'/>\n",
    "    <figcaption style='text-align:center'> Figure 5. Matchings with Maximum Cardinality</figcaption>\n",
    "</figure>\n",
    "\n",
    "Edges AE and AF are added to the original graph and now all the nodes are even. Remember, the AE edge doesn't exist, so when the algorithm says to follow the AE path, in actuality you go from node A to B to E. <b>The point of the previous steps stems from the fact that there is no choice but to reuse a path, so we need to find which path/s require the least amount of work to double back</b>. The final augmented graph is shown below. From here the NetworkX 2.0 package is used to return the circuit.\n",
    "\n",
    "<figure style='text-align:center'>\n",
    "    <img src=\"https://raw.githubusercontent.com/Williamdst/Capstone-2/main/Images/0005.Network-Follow-Final-Augment.png\" style='max-width:20%'/>\n",
    "    <figcaption style='text-align:center'> Figure 6. The Final Augmented Graph</figcaption>\n",
    "</figure>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<p style='text-align:center'> <b> 2.2 The Graph Theory To Build on Andrew's Solution</b> </p>\n",
    "Andrew's solution solves for the Euler circuit, we are looking for a Euler Path. A Euler Path is a path that has the added conditions of using <b>every edge</b> of the graph <b>exactly once.</b> The difference is that an Euler Path doesn’t have to end where it began. There is a different theorem on Euler Paths that will guide the modification: <br />\n",
    "\n",
    "<p style='text-align:center'> If a graph $G$ has an Euler Path, then it must have <b>exactly two odd vertices.</b></p>\n",
    "\n",
    "Essentially, odd-degree nodes are dead-ends. There is going to come a time when you reach the node and there are no more edges leftover to leave. In a Euler Path these dead ends serve as the starting and ending nodes."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<p style='text-align:right'> <b>2.2.A Understanding The Steps</b> </p>\n",
    "\n",
    "The difference in our problem is that all but two of the odd-degree nodes must become even. Doing that was simple, all the odd nodes were found and two were removed from the list to be conserved. From there all of Andrew’s steps were the same, except the function used from NetworkX 2.5 was the <code>eulerian_path</code> function. The two conserved odd-degree nodes act as the starting point and the ending point of the path. Naturally, the question then became, which two odd-degree nodes do we conserve. Choosing where to start and where to end is part of the difficulty of the Subway Challenge.\n",
    "\n",
    "The only start and end pair known is Matthew Ahn's pair and there is no guarantee that it is optimal. Therefore, every odd-degree node could be a potential start node and a potential end node and thus there are  $\\dbinom{O}{2}$ configurations to check, where $O$ is the number of odd-degree nodes. For every configuration, both odd-degree nodes are conserved and then the path is returned for that configuration. Using the same follow along graph from <i>Figure 3</i> the $\\dbinom{4}{2} = 6$ start-end configurations: A-E, A-F, A-G, E-F, E-G, and F-G are shown below.\n",
    "\n",
    "<figure style='text-align:center'>\n",
    "    <img src=\"https://raw.githubusercontent.com/Williamdst/Capstone-2/main/Images/0006.Network-Path-Configs.png\" style='max-width:60%'/>\n",
    "    <figcaption style='text-align:center'> Figure 7. All Possible Start-End Euler Paths w/ Augmented Edges</figcaption>\n",
    "</figure>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<table>\n",
    "    <tr>\n",
    "        <th></th>\n",
    "        <th></th>\n",
    "        <th></th>\n",
    "    </tr>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<table>\n",
    "    <tr>\n",
    "        <th></th>\n",
    "        <th></th>\n",
    "        <th></th>\n",
    "    </tr>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h2> 3. Modeling the MTA Subway System </h2>\n",
    "<div>\n",
    "    <p>    \n",
    "The bulk of the work is translating the map into nodes and edges, saving them as CSV files that the program can understand. Referring to <i>Figures 1&2</i>, not every station needs to be modeled, only the stations where a choice must be made. Of the 472 stations in the system there are only 79 decision stations. The lines on the night map are grouped into colors:\n",
    "    </p>\n",
    "</div>\n",
    "\n",
    "<img align='right' width='500' style=\"float:right;\" src=\"https://raw.githubusercontent.com/Williamdst/Capstone-2/main/Images/0007.MTA-Night.jpg\" />\n",
    "\n",
    "<div style=\"text-align:center;margin:0;font-size:12px;color:#c1121f\" align='center'>\n",
    "    <table>\n",
    "    <tr>\n",
    "        <th>Red Lines</th>\n",
    "        <td>1</td>\n",
    "        <td>2</td>\n",
    "        <td>3</td>\n",
    "    </tr>\n",
    "    <tr>\n",
    "        <th>Green Lines</th>\n",
    "        <td>4</td>\n",
    "        <td>5</td>\n",
    "        <td>6</td>\n",
    "    </tr>\n",
    "    <tr>\n",
    "        <th>Purple Line</th>\n",
    "        <td>7</td>\n",
    "    </tr>\n",
    "    <tr>\n",
    "        <th>Blue Lines</th>\n",
    "        <td>A</td>\n",
    "        <td>E</td>\n",
    "    </tr>\n",
    "    <tr>\n",
    "        <th>Orange Lines</th>\n",
    "        <td>D</td>\n",
    "        <td>F</td>\n",
    "        <td>M</td>\n",
    "    </tr>\n",
    "    <tr>\n",
    "        <th>L.Green Line</th>\n",
    "        <td>G</td>\n",
    "    </tr>\n",
    "     <tr>\n",
    "        <th>Brown Line</th>\n",
    "        <td>J</td>\n",
    "    </tr>\n",
    "     <tr>\n",
    "        <th>Grey Lines</th>\n",
    "        <td>L</td>\n",
    "        <td>S</td>\n",
    "    </tr>\n",
    "    <tr>\n",
    "        <th>Yellow Lines</th>\n",
    "        <td>N</td>\n",
    "        <td>Q</td>\n",
    "        <td>R</td>\n",
    "    </tr>\n",
    "</table>\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<p style='text-align:right'> <b> 3.0.A Modeling the Nodes (Stations)</b> </p>\n",
    "\n",
    "For every decision station on a line, the Station ID, Station Name, Borough, and Line were documented. Additionally, each station on a line was given a \"node-number\" (there are stations that have multiple node numbers). For example, look at South Ferry Station (<i>Red Line - Bottom Middle</i>) and Canal St on the Blue Line (<i>Middle-Left</i>). South Ferry is the first stop on the 1 line and Canal St is the 10th station on the A line as well as the 9th station on the E line. Their values in the CSV were:\n",
    "    <table>\n",
    "        <tr>\n",
    "            <th>stationID</th>\n",
    "            <th>stopName</th>\n",
    "            <th>borough</th>\n",
    "            <th>lines</th>\n",
    "            <th>nodes</th>\n",
    "        </tr>\n",
    "        <tr>\n",
    "            <td>330</td>\n",
    "            <td>South Ferry</td>\n",
    "            <td>Manhattan</td>\n",
    "            <td>X1</td>\n",
    "            <td>1001</td>\n",
    "        </tr>\n",
    "        <tr>\n",
    "            <td>169</td>\n",
    "            <td>Canal St</td>\n",
    "            <td>Manhattan</td>\n",
    "            <td>A:E</td>\n",
    "            <td>A010:E009</td>\n",
    "        </tr>\n",
    "    </table>\n",
    "The A and E train stop at Canal St, so both the \"lines\" and \"nodes\" column have more than one value, separated by a colon. The colon was used as a separator so that the values could be read independently when loaded into Neo4j (<code>Load-Neo4j-Cypher-Query.sql</code>). Look at the more complex station, W 4 St-Wash Sq (<i>Blue/Orange Line - Upper Left</i>) where four trains stop at this station: A, D, E, and F train. As before, in the \"lines\" column and the \"nodes\" column, every train and their node number were documented:\n",
    "    <table>\n",
    "        <tr>\n",
    "            <th>stationID</th>\n",
    "            <th>stopName</th>\n",
    "            <th>borough</th>\n",
    "            <th>lines</th>\n",
    "            <th>nodes</th>\n",
    "        </tr>\n",
    "        <tr>\n",
    "            <td>167</td>\n",
    "            <td>W 4 St-Wash Sq</td>\n",
    "            <td>Manhattan</td>\n",
    "            <td>A:D:E:F</td>\n",
    "            <td>A011:D005:E008:F008</td>\n",
    "        </tr>\n",
    "    </table>\n",
    "On the blue line Canal St was A010 and W 4 St-Wash Sq was A011, but what happened to Spring St. Spring St isn't a decision station because if you were traveling from Canal to W 4-St you wouldn't have a choice but to stop at Spring St."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<p style='text-align:right'> <b> 3.0.B Modeling the Edges (Routes)</b> </p>\n",
    "Modeling the edges was similar to modeling the stations. When modeling stations, each row is a single station and the properties of that station. When modeling edges, each row is a single edge and the properties of that edge. Edges are defined by the two nodes it is connected to, so the first thing needed are the Start Station ID and the Stop Station ID. The three other properties were the routes (same idea as the \"lines\" column), the nodes (the node numbers), and the distance. In this case, the distance was the <b>time</b> it takes to traverse the edge, or in other words, the time to go from one station to the next. The edge that connects Canal St to W 4 St-Wash Sq is shown below:\n",
    " <table>\n",
    "        <tr>\n",
    "            <th>startID</th>\n",
    "            <th>stopID</th>\n",
    "            <th>startNode</th>\n",
    "            <th>stopNode</th>\n",
    "            <th>routes</th>\n",
    "            <th>distance</th>\n",
    "        </tr>\n",
    "        <tr>\n",
    "            <td>169</td>\n",
    "            <td>167</td>\n",
    "            <td>A010:E009</td>\n",
    "            <td>A011:E008</td>\n",
    "            <td>A:E</td>\n",
    "            <td>4</td>\n",
    "        </tr>\n",
    "    </table>\n",
    "Although you can traverse this edge on either the A or E train, it is important that this edge is <b>not</b> duplicated in the edge list. If the edge is duplicated, then the program will read it as two separate edges and will solve the problem under the impression that it must traverse the edge twice. After removing all the duplicates there were 104 edges modeled. <br></br>\n",
    "\n",
    "Looking at Fulton St <i>(Bottom Right)</i>, there is a single name for all four dots because Fulton St is a station complex, however when it comes to the challenge Fulton St counts as four different stations. This idea may be obvious with Fulton St, but there are other intersections that look like a single station but count as multiple stations in the Challenge. The official 472 stations recognized by the MTA can be found in the <code>Stations-Official-472.csv</code> file. <br />\n",
    "\n",
    "The black lines connecting the dots are free subway transfers which are paths, not in the graph theory sense, that allow riders to directly walk between two stations. For example, you are on the A train and you get off at Fulton St, you can then walk over to Fulton St on the 3 train. I'm sure these subway transfers are extremely useful when solving the challenge, however they can't be used to model the network at this time. Why? The subway transfers are optional, not a requirement like the other edges. If those transfers were added to the graph, then the program will solve the problem under the impression that it must traverse the edge."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h2> 4. The Routes </h2>\n",
    "Of the 79 stations, there were 58 odd-degree nodes resulting in $\\dbinom{58}{2} = 1653$ start-end configurations. To store all of the configurations and their stats, a simple SQLite database was integrated in the program.\n",
    "\n",
    "<figure style='text-align:center'>\n",
    "    <img src=\"./Images/0017.Route-ERD.png\" align='center', style=\"max-width:40%\">\n",
    "    <figcaption> </figcaption>\n",
    "</figure>\n",
    "\n",
    "If you never had to double back and could teleport to whatever station you needed to, the time it would take to traverse each of the 104 edges exactly one time would be 14.75 hours (884m). The rest of the time is spent going back over edges you already traveled; in Matthew Ahn's case that was nearly 7 hours. The columns that are used to pick a route are distance_walked and distance_doublebacked. The reason that edges_walked isn't a major concern is because it matters <b>what</b> edge you had to double back over. You can't make the claim that a route with 150 edges_walked is better than a 151-edge route, because that one edge may be the worst edge in the network.\n",
    "\n",
    "The node that was in 8 of the 10 top routes, either as the start or the end station, was 416 Wakefield-241 St (The last stop of the 2 train). What's more interesting is that all the nodes paired with it were also extreme stations, meaning, they were at the end of a line. More than that, those extremes were aggressively extreme, not only were they at the end of a line, but they were also at the end of lines that had no transfer opportunities and took over 15m to reach. The route that Matthew took started and ended at two very aggressive extremes and the path that contained those two extremes took 21.06 hours (37th ranked route)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<p style='text-align:right'> <b> 4.0.A The \"Best\" Routes</b> </p>\n",
    "As was stated before, picking out the best route isn't as straight-forward as querying the database, finding the path with minimal distance, and following the directions. Remember, the program doesn't understand the cost of excessive transfers, that there are transfers that provide shortcuts, and the network topology isn't static. The one major insight that can be used to filter out routes is that aggressively extreme stations are where you want to start and where you want to end, which leaves about only 10 choices (45 configurations). The steps for the best routes aren’t listed in this report because each route has over 145 steps, but there is a <code>Describe-Route.sql</code> file in the repository that contains the query to use to list out all the steps for any path. The most properties of the most interesting paths are shown in the table below:\n",
    "\n",
    "<table>\n",
    "    <tr>\n",
    "        <th></th>\n",
    "        <th> Start Station </th>\n",
    "        <th> Stop Station </th>\n",
    "        <th> Time (Hrs) </th>\n",
    "        <th> Route Rank </th>\n",
    "    </tr>\n",
    "    <tr>\n",
    "        <th> Gold Route </th>\n",
    "        <td>Wakefield-241 St <i>(2-Train)</i></td>\n",
    "        <td>Woodlawn <i>(4-Train)</i></td>\n",
    "        <td>20.65</td>\n",
    "        <td>1</td>\n",
    "    </tr>\n",
    "    <tr>\n",
    "        <th> Silver Route </th>\n",
    "        <td>Wakefield-241 St <i>(2-Train)</i></td>\n",
    "        <td>Norwood-205 St <i>(D-Train)</i></td>\n",
    "        <td>20.66</td>\n",
    "        <td>2</td>\n",
    "    </tr>\n",
    "    <tr>\n",
    "        <th> Bronze Route </th>\n",
    "        <td>Wakefield-241 St <i>(2-Train)</i></td>\n",
    "        <td>Pelham Bay Park <i>(6-Train)</i></td>\n",
    "        <td>20.7</td>\n",
    "        <td>3</td>\n",
    "    </tr>\n",
    "     <tr>\n",
    "        <th> The Worst Route </th>\n",
    "        <td>Sutphin Blvd-Archer Av-JFK Aiport <i>(E-Train)</i></td>\n",
    "        <td>Coney Island-Stillwell Av <i>(D-Train)</i></td>\n",
    "        <td>22.35</td>\n",
    "        <td>1653</td>\n",
    "    </tr>\n",
    "    <tr>\n",
    "        <th> Matthew Ahn's Route </th>\n",
    "        <td>Far Rockaway-Mott Av <i>(A-Train)</i></td>\n",
    "        <td>Flushing-Main St <i>(7-Train)</i></td>\n",
    "        <td>21.06</td>\n",
    "        <td>37</td>\n",
    "    </tr>\n",
    "    <tr>\n",
    "        <th> My Most Convenient Starting Route </th>\n",
    "        <td>Far Rockaway-Mott Av <i>(A-Train)</i></td>\n",
    "        <td>Norwood-205 St <i>(D-Train)</i></td>\n",
    "        <td>20.95</td>\n",
    "        <td>16</td>\n",
    "    </tr>\n",
    "    <tr>\n",
    "        <th> My Most Convenient Ending Route </th>\n",
    "        <td>Wakefield-241 St <i>(2-Train)</i></td>\n",
    "        <td>Far Rockaway-Mott Av <i>(A-Train)</i></td>\n",
    "        <td>20.75</td>\n",
    "        <td>4</td>\n",
    "    </tr>\n",
    "    <tr>\n",
    "        <th> My Most Convenient Route Overall </th>\n",
    "        <td>Rockaway Park-Beach 116st <i>(A-Train)</i></td>\n",
    "        <td>Far Rockaway-Mott Av <i>(A-Train)</i></td>\n",
    "        <td>21.63</td>\n",
    "        <td>606</td>\n",
    "    </tr>\n",
    "</table>\n",
    "\n",
    "<div style=\"line-height:11px\">\n",
    "    <p style=\"text-align:right;font-style:italic;color:#c1121f\"> <b> Data Science = Solving Problems = Happiness </b> </p>\n",
    "    <p style=\"text-align:right;\"> <b> Denzel S. Williams </b> </p>\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<hr>\n",
    "<h3> A1. Project Improvements & Extenstions </h3>\n",
    "\n",
    "<b>Subway Transfers & Running Edges </b> <br />\n",
    "In future installments of the project, I would like to implement those subway transfers into the solution. Additionally, part of Matthew Ahn's record involved him running between stations that aren't connected because that was the fastest way to get there. Using that idea, \"Running Transfers\" could be artificially added to the network. These running transfers would be especially useful in the Bronx.\n",
    "\n",
    "<b>Solve the Full Problem</b> <br />\n",
    "This project only focused on the Late-Night Subway Map and although the order of stations might be transferrable, the edges are not. There are routes that don't go to certain stations at certain times in the day and there are express lines that can be utilized when double backing. Solving the full problem may require an entirely new solution method because there is a mix of optional edges and required edges. \n",
    "\n",
    "<b>Wait Times & Time Varying Networks</b> <br />\n",
    "To arrive at a complete solution in its entirety, the program would need to understand how the network changes over time. Not only how the edge set changes from express to local, but how long the wait time for the next train will occur at a decision point, which also changes over time."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h3>A2. The Graphs of the Lines in Neo4j</h3>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<figure style='text-align:center'>\n",
    "    <img src=\"./Images/0008.Red.png\" style=\"max-width:40%\" />\n",
    "    <figcaption style='text-align:center'> Figure A1. The Red Lines</figcaption>\n",
    "</figure>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<figure style='text-align:center'>\n",
    "    <img src=\"./Images/0009.Green.png\" style=\"max-width:40%\" />\n",
    "    <figcaption style='text-align:center'> Figure A2. The Green Lines</figcaption>\n",
    "</figure>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<figure style='text-align:center'>\n",
    "    <img src=\"./Images/0010.Purple.png\" style=\"max-width:60%\" />\n",
    "    <figcaption style='text-align:center'> Figure A3. The Purple Lines</figcaption>\n",
    "</figure>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<figure style='text-align:center'>\n",
    "    <img src=\"./Images/0011.Blue.png\" style=\"max-width:60%\" />\n",
    "    <figcaption style='text-align:center'> Figure A4. The Blue Lines</figcaption>\n",
    "</figure>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<figure style='text-align:center'>\n",
    "    <img src=\"./Images/0012.Orange.png\" style=\"max-width:60%\" />\n",
    "    <figcaption style='text-align:center'> Figure A5. The Orange Lines</figcaption>\n",
    "</figure>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<figure style='text-align:center'>\n",
    "    <img src=\"./Images/0013.L.Green.png\" style=\"max-width:40%\" />\n",
    "    <figcaption style='text-align:center'> Figure A6. The L.Green Lines</figcaption>\n",
    "</figure>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<figure style='text-align:center'>\n",
    "    <img src=\"./Images/0014.Brown.png\" style=\"max-width:60%\" />\n",
    "    <figcaption style='text-align:center'> Figure A7. The Brown Lines</figcaption>\n",
    "</figure>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<figure style='text-align:center'>\n",
    "    <img src=\"./Images/0015.Grey.png\" style=\"max-width:40%\" />\n",
    "    <figcaption style='text-align:center'> Figure A8. The Grey Lines</figcaption>\n",
    "</figure>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<figure style='text-align:center'>\n",
    "    <img src=\"./Images/0016.Yellow.png\" style=\"max-width:60%\" />\n",
    "    <figcaption style='text-align:center'> Figure A9. The Yellow Lines</figcaption>\n",
    "</figure>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h3>A3. References </h3>\n",
    "<ol style=\"margin: 10px 0;\">\n",
    "    <li> “Subway Challenge.” Wikipedia, Wikimedia Foundation, 3 Mar. 2021, <a href=\"en.wikipedia.org/wiki/Subway_Challenge#Guinness_Record_times\"> en.wikipedia.org/wiki/Subway_Challenge#Guinness_Record_times </a>. </li> \n",
    "    <li>Snowden, Scott. “Solo Straphanger Sets New, All-Station Subway World Record.” Time Out New York, Time Out, 6 Sept. 2016, <a href=\"www.timeout.com/newyork/blog/solo-straphanger-sets-new-all-station-subway-world-record-090616\"> www.timeout.com/newyork/blog/solo-straphanger-sets-new-all-station-subway-world-record-090616 </a>. </li>\n",
    "    <li>\"Intro to Graph Optimization with NetworkX in Python.\" DataCamp Community, <a href=\"www.datacamp.com/community/tutorials/networkx-python-graph-tutorial\"> www.datacamp.com/community/tutorials/networkx-python-graph-tutorial</a>. </li> \n",
    "    <li>Brooks, Andrew. “Intro to Graph Optimization: Solving the Chinese Postman Problem.” Andrew Brooks, 7 Oct. 2017, <a href=\"brooksandrew.github.io/simpleblog/articles/intro-to-graph-optimization-solving-cpp/\"> brooksandrew.github.io/simpleblog/articles/intro-to-graph-optimization-solving-cpp/ </a>. </li>\n",
    "</ol>"
   ]
  },
  {
   "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.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}