Skip to content

Commit facc94d

Browse files
oaaooaao
committed
add [n/algorithms]: set up Route Inspection Problem
1 parent 9654629 commit facc94d

File tree

1 file changed

+313
-0
lines changed

1 file changed

+313
-0
lines changed

‎novels/algorithms/Route Inspection Problem.ipynb

Lines changed: 313 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,313 @@
1+
{
2+
"cells": [
3+
{
4+
"cell_type": "markdown",
5+
"metadata": {},
6+
"source": [
7+
"# Route Inspection Problem\n",
8+
"### (Chinese Postman Problem)"
9+
]
10+
},
11+
{
12+
"cell_type": "markdown",
13+
"metadata": {},
14+
"source": [
15+
"Find the shortest closed path which visits every edge of a (connected) undirected graph."
16+
]
17+
},
18+
{
19+
"cell_type": "markdown",
20+
"metadata": {},
21+
"source": [
22+
"### Context"
23+
]
24+
},
25+
{
26+
"cell_type": "markdown",
27+
"metadata": {},
28+
"source": [
29+
"A **Eulerian circuit** should exist in the graph: a closed traversal which visits every edge *exactly once*.\n",
30+
"\n",
31+
"If such a circuit does not exist, generate that condition from the given graph: \n",
32+
"\n",
33+
">Find the minimal set of the graph's edges to duplicate such that the resulting multigraph **does** have a Eulerian circuit.\n",
34+
"\n",
35+
"The subset of edges must have the minimum possible total weight, or if edge weight is a non-factor, the smallest number of edges."
36+
]
37+
},
38+
{
39+
"cell_type": "markdown",
40+
"metadata": {},
41+
"source": [
42+
"### Algorithm (generalised)"
43+
]
44+
},
45+
{
46+
"cell_type": "markdown",
47+
"metadata": {},
48+
"source": [
49+
"1. Find all nodes with an odd [degree](https://en.wikipedia.org/wiki/Degree_(graph_theory)).\n",
50+
"\n",
51+
"2. Account for and minimise backtracking:\n",
52+
"\n",
53+
"> add edges to the graph such that odd-degree nodes become even\n",
54+
" \n",
55+
"> any edges added must be duplicates of graph's original edges\n",
56+
" \n",
57+
"> the added set of edges must have minimal total weight (np-hard)\n",
58+
" \n",
59+
"3. Find the Eulerian circuit in the regenerated multigraph."
60+
]
61+
},
62+
{
63+
"cell_type": "markdown",
64+
"metadata": {},
65+
"source": [
66+
"### Implementation"
67+
]
68+
},
69+
{
70+
"cell_type": "markdown",
71+
"metadata": {},
72+
"source": [
73+
"Gather dependencies:"
74+
]
75+
},
76+
{
77+
"cell_type": "code",
78+
"execution_count": 9,
79+
"metadata": {},
80+
"outputs": [],
81+
"source": [
82+
"# stdlib dependencies\n",
83+
"import itertools\n",
84+
"import copy\n",
85+
"\n",
86+
"# external libraries\n",
87+
"import networkx as nx\n",
88+
"import pandas as pd\n",
89+
"import matplotlib.pyplot as plt"
90+
]
91+
},
92+
{
93+
"cell_type": "markdown",
94+
"metadata": {},
95+
"source": [
96+
"Obtain external data (in a somewhat gorier way than normal):"
97+
]
98+
},
99+
{
100+
"cell_type": "code",
101+
"execution_count": 13,
102+
"metadata": {},
103+
"outputs": [],
104+
"source": [
105+
"import io\n",
106+
"import requests\n",
107+
"\n",
108+
"resp = requests.get('https://gist.githubusercontent.com/brooksandrew/e570c38bcc72a8d102422f2af836513b/raw/89c76b2563dbc0e88384719a35cba0dfc04cd522/edgelist_sleeping_giant.csv')\n",
109+
"data = pd.read_csv(io.StringIO(resp.content.decode('utf-8')))"
110+
]
111+
},
112+
{
113+
"cell_type": "markdown",
114+
"metadata": {},
115+
"source": [
116+
"Our edgelist appears as such:"
117+
]
118+
},
119+
{
120+
"cell_type": "code",
121+
"execution_count": 14,
122+
"metadata": {},
123+
"outputs": [
124+
{
125+
"data": {
126+
"text/html": [
127+
"<div>\n",
128+
"<style scoped>\n",
129+
" .dataframe tbody tr th:only-of-type {\n",
130+
" vertical-align: middle;\n",
131+
" }\n",
132+
"\n",
133+
" .dataframe tbody tr th {\n",
134+
" vertical-align: top;\n",
135+
" }\n",
136+
"\n",
137+
" .dataframe thead th {\n",
138+
" text-align: right;\n",
139+
" }\n",
140+
"</style>\n",
141+
"<table border=\"1\" class=\"dataframe\">\n",
142+
" <thead>\n",
143+
" <tr style=\"text-align: right;\">\n",
144+
" <th></th>\n",
145+
" <th>node1</th>\n",
146+
" <th>node2</th>\n",
147+
" <th>trail</th>\n",
148+
" <th>distance</th>\n",
149+
" <th>color</th>\n",
150+
" <th>estimate</th>\n",
151+
" </tr>\n",
152+
" </thead>\n",
153+
" <tbody>\n",
154+
" <tr>\n",
155+
" <th>0</th>\n",
156+
" <td>rs_end_north</td>\n",
157+
" <td>v_rs</td>\n",
158+
" <td>rs</td>\n",
159+
" <td>0.30</td>\n",
160+
" <td>red</td>\n",
161+
" <td>0</td>\n",
162+
" </tr>\n",
163+
" <tr>\n",
164+
" <th>1</th>\n",
165+
" <td>v_rs</td>\n",
166+
" <td>b_rs</td>\n",
167+
" <td>rs</td>\n",
168+
" <td>0.21</td>\n",
169+
" <td>red</td>\n",
170+
" <td>0</td>\n",
171+
" </tr>\n",
172+
" <tr>\n",
173+
" <th>2</th>\n",
174+
" <td>b_rs</td>\n",
175+
" <td>g_rs</td>\n",
176+
" <td>rs</td>\n",
177+
" <td>0.11</td>\n",
178+
" <td>red</td>\n",
179+
" <td>0</td>\n",
180+
" </tr>\n",
181+
" <tr>\n",
182+
" <th>3</th>\n",
183+
" <td>g_rs</td>\n",
184+
" <td>w_rs</td>\n",
185+
" <td>rs</td>\n",
186+
" <td>0.18</td>\n",
187+
" <td>red</td>\n",
188+
" <td>0</td>\n",
189+
" </tr>\n",
190+
" <tr>\n",
191+
" <th>4</th>\n",
192+
" <td>w_rs</td>\n",
193+
" <td>o_rs</td>\n",
194+
" <td>rs</td>\n",
195+
" <td>0.21</td>\n",
196+
" <td>red</td>\n",
197+
" <td>0</td>\n",
198+
" </tr>\n",
199+
" <tr>\n",
200+
" <th>...</th>\n",
201+
" <td>...</td>\n",
202+
" <td>...</td>\n",
203+
" <td>...</td>\n",
204+
" <td>...</td>\n",
205+
" <td>...</td>\n",
206+
" <td>...</td>\n",
207+
" </tr>\n",
208+
" <tr>\n",
209+
" <th>118</th>\n",
210+
" <td>v_bv</td>\n",
211+
" <td>b_bv</td>\n",
212+
" <td>bv</td>\n",
213+
" <td>0.08</td>\n",
214+
" <td>purple</td>\n",
215+
" <td>0</td>\n",
216+
" </tr>\n",
217+
" <tr>\n",
218+
" <th>119</th>\n",
219+
" <td>g_gy2</td>\n",
220+
" <td>w_gy2</td>\n",
221+
" <td>gy2</td>\n",
222+
" <td>0.05</td>\n",
223+
" <td>yellowgreen</td>\n",
224+
" <td>0</td>\n",
225+
" </tr>\n",
226+
" <tr>\n",
227+
" <th>120</th>\n",
228+
" <td>w_gy2</td>\n",
229+
" <td>b_gy2</td>\n",
230+
" <td>gy2</td>\n",
231+
" <td>0.03</td>\n",
232+
" <td>yellowgreen</td>\n",
233+
" <td>1</td>\n",
234+
" </tr>\n",
235+
" <tr>\n",
236+
" <th>121</th>\n",
237+
" <td>b_gy2</td>\n",
238+
" <td>o_gy2</td>\n",
239+
" <td>gy2</td>\n",
240+
" <td>0.07</td>\n",
241+
" <td>yellowgreen</td>\n",
242+
" <td>0</td>\n",
243+
" </tr>\n",
244+
" <tr>\n",
245+
" <th>122</th>\n",
246+
" <td>o_gy2</td>\n",
247+
" <td>y_gy2</td>\n",
248+
" <td>gy2</td>\n",
249+
" <td>0.12</td>\n",
250+
" <td>yellowgreen</td>\n",
251+
" <td>0</td>\n",
252+
" </tr>\n",
253+
" </tbody>\n",
254+
"</table>\n",
255+
"<p>123 rows × 6 columns</p>\n",
256+
"</div>"
257+
],
258+
"text/plain": [
259+
" node1 node2 trail distance color estimate\n",
260+
"0 rs_end_north v_rs rs 0.30 red 0\n",
261+
"1 v_rs b_rs rs 0.21 red 0\n",
262+
"2 b_rs g_rs rs 0.11 red 0\n",
263+
"3 g_rs w_rs rs 0.18 red 0\n",
264+
"4 w_rs o_rs rs 0.21 red 0\n",
265+
".. ... ... ... ... ... ...\n",
266+
"118 v_bv b_bv bv 0.08 purple 0\n",
267+
"119 g_gy2 w_gy2 gy2 0.05 yellowgreen 0\n",
268+
"120 w_gy2 b_gy2 gy2 0.03 yellowgreen 1\n",
269+
"121 b_gy2 o_gy2 gy2 0.07 yellowgreen 0\n",
270+
"122 o_gy2 y_gy2 gy2 0.12 yellowgreen 0\n",
271+
"\n",
272+
"[123 rows x 6 columns]"
273+
]
274+
},
275+
"execution_count": 14,
276+
"metadata": {},
277+
"output_type": "execute_result"
278+
}
279+
],
280+
"source": [
281+
"data"
282+
]
283+
},
284+
{
285+
"cell_type": "code",
286+
"execution_count": null,
287+
"metadata": {},
288+
"outputs": [],
289+
"source": []
290+
}
291+
],
292+
"metadata": {
293+
"kernelspec": {
294+
"display_name": "Python 3",
295+
"language": "python",
296+
"name": "python3"
297+
},
298+
"language_info": {
299+
"codemirror_mode": {
300+
"name": "ipython",
301+
"version": 3
302+
},
303+
"file_extension": ".py",
304+
"mimetype": "text/x-python",
305+
"name": "python",
306+
"nbconvert_exporter": "python",
307+
"pygments_lexer": "ipython3",
308+
"version": "3.7.3"
309+
}
310+
},
311+
"nbformat": 4,
312+
"nbformat_minor": 2
313+
}

0 commit comments

Comments
 (0)