Longer city tours (solution)#

Links: notebook, html, PDF, python, slides, GitHub

Solutions to the bigger examples for the challenge: find the shortest path through a set of streets.

%matplotlib inline
import matplotlib.pyplot as plt
plt.style.use("ggplot")

from jyquickhelper import add_notebook_menu
add_notebook_menu()

Level 1 #

from ensae_projects.datainc.data_geo_streets import get_seattle_streets, shapely_records
from ensae_projects.datainc.data_geo_streets import seattle_streets_set_small, folium_html_street_map

name = get_seattle_streets()
shapes, records, fields = shapely_records(name)
edges_index, edges, vertices, distances = seattle_streets_set_small(shapes, records)
folium_html_street_map(edges_index, shapes, html_width="50%", zoom_start=15)

from ensae_projects.datainc.data_geo_streets import plot_streets_network
plot_streets_network(edges_index, edges, vertices, shapes, figsize=(10,10));

../_images/city_tour_long_solution_5_0.png

from ensae_projects.challenge.city_tour import best_euler_path
couples, solution, distance = best_euler_path(edges_index=edges_index, edges=edges,
                                              distances=distances, vertices=vertices, fLOG=print)
"distance", distance

[best_euler_path] distance_vertices #edges=24
[best_euler_path] bellman_distances
[bellman_distances] iteration=1 modif=74 #dist=122 sum_values=0.26812913941842903 avg=0.0021977798312985985
[bellman_distances] iteration=2 modif=102 #dist=214 sum_values=0.6638654574495177 avg=0.0031021750348108304
[bellman_distances] iteration=3 modif=130 #dist=298 sum_values=1.3475652021993083 avg=0.004522030879863451
[bellman_distances] iteration=4 modif=100 #dist=306 sum_values=1.3653257205807 avg=0.004461848760067647
[bellman_distances] iteration=5 modif=64 #dist=306 sum_values=1.2780455413890799 avg=0.0041766194163041824
[bellman_distances] iteration=6 modif=42 #dist=306 sum_values=1.2282394949878546 avg=0.0040138545587838385
[bellman_distances] iteration=7 modif=24 #dist=306 sum_values=1.207369883828586 avg=0.003945653215126098
[bellman_distances] iteration=8 modif=12 #dist=306 sum_values=1.1964121229039824 avg=0.003909843538901903
[bellman_distances] iteration=9 modif=10 #dist=306 sum_values=1.1840886861931539 avg=0.0038695708699122678
[bellman_distances] iteration=10 modif=6 #dist=306 sum_values=1.1840669671109263 avg=0.0038694998925193668
[bellman_distances] iteration=11 modif=2 #dist=306 sum_values=1.1840669671109263 avg=0.0038694998925193668
[bellman_distances] iteration=12 modif=2 #dist=306 sum_values=1.1840644116345598 avg=0.003869491541289411
[bellman_distances] iteration=13 modif=0 #dist=306 sum_values=1.1840644116345598 avg=0.003869491541289411
[best_euler_path] degrees and distances between odd vertices
[best_euler_path] matching #odd=6, #odd_dist=30
[best_euler_path] build solution
[best_euler_path] order edges to get the path #edges=31
[best_euler_path] done.

('distance', 0.04360778144581235)

from ensae_projects.challenge.city_tour import euler_path
plot_streets_network(edges_index, edges, vertices, shapes, order=solution, figsize=(10,10));

../_images/city_tour_long_solution_7_0.png

Level 2 #

from ensae_projects.datainc.data_geo_streets import seattle_streets_set_level2
edges_index, edges, vertices, distances = seattle_streets_set_level2(shapes, records)
folium_html_street_map(edges_index, shapes, html_width="80%", zoom_start=14)

from ensae_projects.challenge.city_tour import best_euler_path
couples, solution, distance = best_euler_path(edges_index=edges_index, edges=edges,
                                              distances=distances, vertices=vertices, fLOG=print)
"distance", distance

[best_euler_path] distance_vertices #edges=129
[best_euler_path] bellman_distances
[bellman_distances] iteration=1 modif=472 #dist=730 sum_values=1.3426775505752198 avg=0.0018392843158564654
[bellman_distances] iteration=2 modif=896 #dist=1560 sum_values=4.509671272151574 avg=0.002890814918045881
[bellman_distances] iteration=3 modif=2714 #dist=3814 sum_values=21.436393955580577 avg=0.005620449385312159
[bellman_distances] iteration=4 modif=5352 #dist=7136 sum_values=67.61389258158759 avg=0.009475041000783014
[bellman_distances] iteration=5 modif=4934 #dist=7140 sum_values=63.907784995637684 avg=0.008950670167456258
[bellman_distances] iteration=6 modif=4524 #dist=7140 sum_values=61.71585793972974 avg=0.008643677582595202
[bellman_distances] iteration=7 modif=4032 #dist=7140 sum_values=60.16494600016438 avg=0.008426463025233106
[bellman_distances] iteration=8 modif=3538 #dist=7140 sum_values=58.65108198958743 avg=0.008214437253443618
[bellman_distances] iteration=9 modif=3064 #dist=7140 sum_values=57.23220051767171 avg=0.008015714358217326
[bellman_distances] iteration=10 modif=2676 #dist=7140 sum_values=55.93916546577031 avg=0.007834617012012648
[bellman_distances] iteration=11 modif=2220 #dist=7140 sum_values=54.8619203668688 avg=0.007683742348300953
[bellman_distances] iteration=12 modif=1850 #dist=7140 sum_values=53.88565811083889 avg=0.007547010939893402
[bellman_distances] iteration=13 modif=1518 #dist=7140 sum_values=53.10678224301025 avg=0.007437924683894993
[bellman_distances] iteration=14 modif=1172 #dist=7140 sum_values=52.44868349843554 avg=0.007345753991377527
[bellman_distances] iteration=15 modif=880 #dist=7140 sum_values=51.93813330975093 avg=0.007274248362710215
[bellman_distances] iteration=16 modif=652 #dist=7140 sum_values=51.60396788188214 avg=0.007227446482056322
[bellman_distances] iteration=17 modif=494 #dist=7140 sum_values=51.42044975004631 avg=0.007201743662471472
[bellman_distances] iteration=18 modif=360 #dist=7140 sum_values=51.229579334128026 avg=0.007175011111222413
[bellman_distances] iteration=19 modif=272 #dist=7140 sum_values=51.12190399874062 avg=0.007159930532036502
[bellman_distances] iteration=20 modif=168 #dist=7140 sum_values=51.05549678560144 avg=0.007150629801904964
[bellman_distances] iteration=21 modif=130 #dist=7140 sum_values=51.00300138561965 avg=0.007143277504988746
[bellman_distances] iteration=22 modif=84 #dist=7140 sum_values=50.980044318294766 avg=0.0071400622294530485
[bellman_distances] iteration=23 modif=44 #dist=7140 sum_values=50.96567438582126 avg=0.007138049633868524
[bellman_distances] iteration=24 modif=20 #dist=7140 sum_values=50.95015411488475 avg=0.007135875926454446
[bellman_distances] iteration=25 modif=18 #dist=7140 sum_values=50.940511485236094 avg=0.007134525418100293
[bellman_distances] iteration=26 modif=12 #dist=7140 sum_values=50.93584369169428 avg=0.007133871665503401
[bellman_distances] iteration=27 modif=12 #dist=7140 sum_values=50.93584369169428 avg=0.007133871665503401
[bellman_distances] iteration=28 modif=14 #dist=7140 sum_values=50.93584369169428 avg=0.007133871665503401
[bellman_distances] iteration=29 modif=6 #dist=7140 sum_values=50.93584369169428 avg=0.007133871665503401
[bellman_distances] iteration=30 modif=0 #dist=7140 sum_values=50.93584369169428 avg=0.007133871665503401
[best_euler_path] degrees and distances between odd vertices
[best_euler_path] matching #odd=34, #odd_dist=1122
[best_euler_path] build solution
[best_euler_path] order edges to get the path #edges=161
[best_euler_path] done.

('distance', 0.17361084069482008)

from ensae_projects.challenge.city_tour import euler_path
plot_streets_network(edges_index, edges, vertices, shapes, order=solution, figsize=(20,20));

../_images/city_tour_long_solution_11_0.png

Level 3 #

from ensae_projects.datainc.data_geo_streets import seattle_streets_set_level3
edges_index, edges, vertices, distances = seattle_streets_set_level3(shapes, records)
# We skip display as it takes some time
# folium_html_street_map(edges_index, shapes, html_width="80%", zoom_start=14)

from ensae_projects.challenge.city_tour import best_euler_path
if False:
    # Be prepared, it is quite long, the bellman implementation has to be improved.
    couples, solution, distance = best_euler_path(edges_index=edges_index, edges=edges,
                                                  distances=distances, vertices=vertices, fLOG=print)
    "distance", distance