Skip to content

Commit

Permalink
rev [n/algorithms]: route inspection: data prep + graph building
Browse files Browse the repository at this point in the history
  • Loading branch information
@oaao
oaao committed Nov 25, 2019
1 parent facc94d commit f32a039
Showing 1 changed file with 247 additions and 9 deletions.
256 changes: 247 additions & 9 deletions novels/algorithms/Route Inspection Problem.ipynb
View file
Original file line number Diff line number Diff line change
Expand Up @@ -63,7 +63,14 @@
"cell_type": "markdown",
"metadata": {},
"source": [
"### Implementation"
"----"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Data Preparation"
]
},
{
Expand Down Expand Up @@ -98,27 +105,159 @@
},
{
"cell_type": "code",
"execution_count": 13,
"execution_count": 15,
"metadata": {},
"outputs": [],
"source": [
"import io\n",
"import requests\n",
"import requests as r\n",
"\n",
"NODE_CSV = 'https://gist.githubusercontent.com/brooksandrew/f989e10af17fb4c85b11409fea47895b/raw/a3a8da0fa5b094f1ca9d82e1642b384889ae16e8/nodelist_sleeping_giant.csv'\n",
"EDGE_CSV = 'https://gist.githubusercontent.com/brooksandrew/e570c38bcc72a8d102422f2af836513b/raw/89c76b2563dbc0e88384719a35cba0dfc04cd522/edgelist_sleeping_giant.csv'\n",
"\n",
"resp = requests.get('https://gist.githubusercontent.com/brooksandrew/e570c38bcc72a8d102422f2af836513b/raw/89c76b2563dbc0e88384719a35cba0dfc04cd522/edgelist_sleeping_giant.csv')\n",
"data = pd.read_csv(io.StringIO(resp.content.decode('utf-8')))"
"nodes = pd.read_csv(io.StringIO(r.get(NODE_CSV).content.decode('utf-8')))\n",
"edges = pd.read_csv(io.StringIO(r.get(EDGE_CSV).content.decode('utf-8')))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Our edgelist appears as such:"
"Previewing data:"
]
},
{
"cell_type": "code",
"execution_count": 14,
"execution_count": 20,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
"<div>\n",
"<style scoped>\n",
" .dataframe tbody tr th:only-of-type {\n",
" vertical-align: middle;\n",
" }\n",
"\n",
" .dataframe tbody tr th {\n",
" vertical-align: top;\n",
" }\n",
"\n",
" .dataframe thead th {\n",
" text-align: right;\n",
" }\n",
"</style>\n",
"<table border=\"1\" class=\"dataframe\">\n",
" <thead>\n",
" <tr style=\"text-align: right;\">\n",
" <th></th>\n",
" <th>id</th>\n",
" <th>X</th>\n",
" <th>Y</th>\n",
" </tr>\n",
" </thead>\n",
" <tbody>\n",
" <tr>\n",
" <th>0</th>\n",
" <td>b_bv</td>\n",
" <td>1486</td>\n",
" <td>732</td>\n",
" </tr>\n",
" <tr>\n",
" <th>1</th>\n",
" <td>b_bw</td>\n",
" <td>716</td>\n",
" <td>1357</td>\n",
" </tr>\n",
" <tr>\n",
" <th>2</th>\n",
" <td>b_end_east</td>\n",
" <td>3164</td>\n",
" <td>1111</td>\n",
" </tr>\n",
" <tr>\n",
" <th>3</th>\n",
" <td>b_end_west</td>\n",
" <td>141</td>\n",
" <td>1938</td>\n",
" </tr>\n",
" <tr>\n",
" <th>4</th>\n",
" <td>b_g</td>\n",
" <td>1725</td>\n",
" <td>771</td>\n",
" </tr>\n",
" <tr>\n",
" <th>...</th>\n",
" <td>...</td>\n",
" <td>...</td>\n",
" <td>...</td>\n",
" </tr>\n",
" <tr>\n",
" <th>72</th>\n",
" <td>y_gy2</td>\n",
" <td>1939</td>\n",
" <td>1182</td>\n",
" </tr>\n",
" <tr>\n",
" <th>73</th>\n",
" <td>y_rc</td>\n",
" <td>1429</td>\n",
" <td>1491</td>\n",
" </tr>\n",
" <tr>\n",
" <th>74</th>\n",
" <td>y_rh</td>\n",
" <td>717</td>\n",
" <td>1852</td>\n",
" </tr>\n",
" <tr>\n",
" <th>75</th>\n",
" <td>y_rs</td>\n",
" <td>1805</td>\n",
" <td>1246</td>\n",
" </tr>\n",
" <tr>\n",
" <th>76</th>\n",
" <td>y_rt</td>\n",
" <td>977</td>\n",
" <td>1666</td>\n",
" </tr>\n",
" </tbody>\n",
"</table>\n",
"<p>77 rows × 3 columns</p>\n",
"</div>"
],
"text/plain": [
" id X Y\n",
"0 b_bv 1486 732\n",
"1 b_bw 716 1357\n",
"2 b_end_east 3164 1111\n",
"3 b_end_west 141 1938\n",
"4 b_g 1725 771\n",
".. ... ... ...\n",
"72 y_gy2 1939 1182\n",
"73 y_rc 1429 1491\n",
"74 y_rh 717 1852\n",
"75 y_rs 1805 1246\n",
"76 y_rt 977 1666\n",
"\n",
"[77 rows x 3 columns]"
]
},
"execution_count": 20,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"nodes"
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {},
"outputs": [
{
Expand Down Expand Up @@ -272,13 +411,112 @@
"[123 rows x 6 columns]"
]
},
"execution_count": 14,
"execution_count": 21,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"edges"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"----"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Graph Creation"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Begin by generating an empty graph:"
]
},
{
"cell_type": "code",
"execution_count": 34,
"metadata": {},
"outputs": [],
"source": [
"g = nx.Graph()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Add edges and hydrate with edge attributes:"
]
},
{
"cell_type": "code",
"execution_count": 37,
"metadata": {},
"outputs": [],
"source": [
"for _, row in edges.iterrows():\n",
" g.add_edge(\n",
" row[0], # from node\n",
" row[1], # to node\n",
" attr_dict=row[2:].to_dict()\n",
" )"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Now hydrate the graph with desired node attributes:"
]
},
{
"cell_type": "code",
"execution_count": 65,
"metadata": {},
"outputs": [],
"source": [
"attrs = {\n",
" row['id']: row[1:].to_dict()\n",
" for _, row in nodes.iterrows()\n",
"}\n",
"\n",
"nx.set_node_attributes(g, attrs)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"In brief, the graph we've ended up with:"
]
},
{
"cell_type": "code",
"execution_count": 66,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"(77, 123)"
]
},
"execution_count": 66,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"data"
"g.number_of_nodes(), g.number_of_edges()"
]
},
{
Expand Down

0 comments on commit f32a039

Please sign in to comment.