This page was generated from docsrc/notebooks/shortest-path-visualization.ipynb. Interactive online version: Binder badge


If any part of this notebook is used in your research, please cite with the reference found in README.md.


Generating regular lattices and visualizing shortest paths

Creating data for testing and demonstrating routes

Author: James D. Gaboardi jgaboardi@gmail.com

This notebook is a walk-through for:

  1. Instantiating a simple network through a generated regular lattice

  2. Generating shortest path geometric objects

  3. Visualizing shortest paths

[1]:
%load_ext watermark
%watermark
2020-10-22T17:31:03-04:00

CPython 3.8.5
IPython 7.18.1

compiler   : Clang 10.0.1
system     : Darwin
release    : 19.6.0
machine    : x86_64
processor  : i386
CPU cores  : 8
interpreter: 64bit
[2]:
import libpysal
from libpysal.cg import Point
import matplotlib
import matplotlib.pyplot as plt
import spaghetti

%matplotlib inline
%watermark -w
%watermark -iv
watermark 2.0.2
matplotlib 3.3.2
libpysal   4.3.0
spaghetti  1.5.1

[3]:
try:
    from IPython.display import set_matplotlib_formats
    set_matplotlib_formats("retina")
except ImportError:
    pass

1. Demonstration with a synthetic network

1.1 Instantiate a network from a 4x4 regular lattice

[4]:
lattice = spaghetti.regular_lattice((0,0,3,3), 2, exterior=True)
ntw = spaghetti.Network(in_data=lattice)

1.2. Extract network elements and visualize them

[5]:
vertices, arcs = spaghetti.element_as_gdf(ntw, vertices=True, arcs=True)
[6]:
base = arcs.plot(linewidth=3, alpha=0.25, color="k", zorder=0, figsize=(10, 10))
vertices.plot(ax=base, markersize=20, color="red", zorder=1);
../_images/notebooks_shortest-path-visualization_8_0.png

1.3. Instantiate several synthetic observations and snap them to the network

[7]:
synth_obs = [Point([0.2, 1.3]), Point([0.2, 1.7]), Point([2.8, 1.5])]
ntw.snapobservations(synth_obs, "synth_obs")

1.4. Extract point patterns and visualize plot

Note the labeling for network elements and observations

[8]:
# true locations of synthetic observations
pp_obs = spaghetti.element_as_gdf(ntw, pp_name="synth_obs")
# snapped locations of synthetic observations
pp_obs_snapped = spaghetti.element_as_gdf(ntw, pp_name="synth_obs", snapped=True)

1.4.1. Defined helper functions for labeling

[9]:
def arc_labels(a, b, s):
    """Label each leg of the tour."""
    def _lab_loc(_x):
        """Helper for labeling location."""
        return _x.geometry.interpolate(0.5, normalized=True).coords[0]
    kws = {"size": s, "ha": "center", "va": "bottom"}
    a.apply(lambda x: b.annotate(text=x.id, xy=_lab_loc(x), **kws), axis=1)

def vert_labels(v, b, s):
    """Label each network vertex."""
    def _lab_loc(_x):
        """Helper for labeling vertices."""
        return _x.geometry.coords[0]
    kws = {"size": s, "ha": "left", "va": "bottom", "weight": "bold"}
    v.apply(lambda x: b.annotate(text=x.id, xy=_lab_loc(x), **kws), axis=1)

def obs_labels(o, b, s, c="g"):
    """Label each point pattern observation."""
    def _lab_loc(_x):
        """Helper for labeling observations."""
        return _x.geometry.coords[0]
    kws = {"size": s, "ha": "left", "va": "bottom", "style": "oblique", "c":c}
    o.apply(lambda x: b.annotate(text=x.id, xy=_lab_loc(x), **kws), axis=1)
[10]:
base = arcs.plot(alpha=0.2, linewidth=5, color="k", figsize=(10, 10), zorder=0)
vertices.plot(ax=base, color="r", zorder=1)
pp_obs.plot(ax=base, color="g", zorder=2)
pp_obs_snapped.plot(ax=base, color="g", marker="s", zorder=2)
# arc labels
arc_labels(arcs, base, 12)
# vertex labels
vert_labels(vertices, base, 14)
# synthetic observation labels
obs_labels(pp_obs, base, 14);
../_images/notebooks_shortest-path-visualization_15_0.png

1.5. Generate observation shortest path trees

[11]:
d2d_dist, tree = ntw.allneighbordistances("synth_obs", gen_tree=True)
d2d_dist
[11]:
array([[nan, 0.4, 3.8],
       [0.4, nan, 3.8],
       [3.8, 3.8, nan]])

Note that a tag of (-0.1, -0.1) labels the points as being snapped to the same network arc

[12]:
tree
[12]:
{(0, 1): (-0.1, -0.1), (0, 2): (2, 13), (1, 2): (4, 14)}

1.6. Generate shortest paths as libpysal.cg.Chain objects

[13]:
paths = ntw.shortest_paths(tree, "synth_obs")
paths
[13]:
[[(0, 1), <libpysal.cg.shapes.Chain at 0x7fbd904208b0>],
 [(0, 2), <libpysal.cg.shapes.Chain at 0x7fbd9042c0a0>],
 [(1, 2), <libpysal.cg.shapes.Chain at 0x7fbd9042c370>]]

1.7. Extract the shortest paths within geopandas.GeoDataFrame and plot

[14]:
paths_gdf = spaghetti.element_as_gdf(ntw, routes=paths)
paths_gdf
[14]:
geometry O D id
0 LINESTRING (0.00000 1.30000, 0.00000 1.70000) 0 1 (0, 1)
1 LINESTRING (0.00000 1.30000, 0.00000 1.00000, ... 0 2 (0, 2)
2 LINESTRING (0.00000 1.70000, 0.00000 2.00000, ... 1 2 (1, 2)
[15]:
paths_gdf.plot(figsize=(7, 7), column=paths_gdf.index.name, cmap="Paired", linewidth=5);
../_images/notebooks_shortest-path-visualization_24_0.png

1.8. Plot the routes within the context of the network

[16]:
base = arcs.plot(alpha=0.2, linewidth=5, color="k", figsize=(10, 10), zorder=0)
paths_gdf.plot(ax=base, column="id", cmap="Paired", linewidth=5, zorder=1)
vertices.plot(ax=base, color="r", zorder=2)
pp_obs.plot(ax=base, color="g", zorder=3)
pp_obs_snapped.plot(ax=base, color="g", marker="s", zorder=2)
# arc labels
arc_labels(arcs, base, 12)
# vertex labels
vert_labels(vertices, base, 14)
# synthetic observation labels
obs_labels(pp_obs, base, 14);
../_images/notebooks_shortest-path-visualization_26_0.png

2. Demostration with emprical datasets

2.1 Instantiate an emprical network, extract elements, and visualize

[17]:
ntw = spaghetti.Network(in_data=libpysal.examples.get_path("streets.shp"))
vertices, arcs = spaghetti.element_as_gdf(ntw, vertices=True, arcs=True)
[18]:
base = arcs.plot(linewidth=10, alpha=0.25, color="k", figsize=(10, 10))
vertices.plot(ax=base, markersize=100, alpha=0.25, color="red");
../_images/notebooks_shortest-path-visualization_29_0.png

2.2 Snap emprical observations and extract the point patterns as geopandas.GeoDataFrames

[19]:
ntw.snapobservations(libpysal.examples.get_path("schools.shp"), "schools")
pp_obs = spaghetti.element_as_gdf(ntw, pp_name="schools")
pp_obs_snapped = spaghetti.element_as_gdf(ntw, pp_name="schools", snapped=True)

2.3 Plot empirical data

[20]:
base = arcs.plot(alpha=0.2, linewidth=5, color="k", figsize=(15, 15), zorder=0)
vertices.plot(ax=base, markersize=5, color="r", zorder=1)
pp_obs.plot(ax=base, markersize=5, color="g", zorder=2)
pp_obs_snapped.plot(ax=base, markersize=5, marker="s", color="g", zorder=2)
# arc labels
arc_labels(arcs, base, 6)
# vertex labels
vert_labels(vertices, base, 7)
# synthetic observation labels
obs_labels(pp_obs, base, 12);
../_images/notebooks_shortest-path-visualization_33_0.png

2.4 Generate shortest path routes and extract them

[21]:
d2d_dist, tree = ntw.allneighbordistances("schools", gen_tree=True)
paths = ntw.shortest_paths(tree, "schools")
paths_gdf = spaghetti.element_as_gdf(ntw, routes=paths)
paths_gdf.head()
[21]:
geometry O D id
0 LINESTRING (727287.664 879867.386, 727294.797 ... 0 1 (0, 1)
1 LINESTRING (727287.664 879867.386, 727294.797 ... 0 2 (0, 2)
2 LINESTRING (727287.664 879867.386, 727294.797 ... 0 3 (0, 3)
3 LINESTRING (727287.664 879867.386, 727294.797 ... 0 4 (0, 4)
4 LINESTRING (727287.664 879867.386, 727281.557 ... 0 5 (0, 5)

2.5 Plot the shortest path routes

[22]:
paths_gdf.plot(figsize=(7, 7), column="id", cmap="Paired", linewidth=5);
../_images/notebooks_shortest-path-visualization_37_0.png

2.6. Plot all shortest path routes within the context of the network

[23]:
base = arcs.plot(alpha=0.2, linewidth=5, color="k", figsize=(10, 10), zorder=0)
pp_obs.plot(ax=base, color="g", zorder=2)
pp_obs_snapped.plot(ax=base, color="g", marker="s", zorder=2)
paths_gdf.plot(ax=base, column="id", cmap="Paired", linewidth=10, alpha=0.25)
# synthetic observation labels
obs_labels(pp_obs, base, 12);
../_images/notebooks_shortest-path-visualization_39_0.png

2.7. Plot the shortest path routes originating from observation 0

[24]:
obs0 = 0
pp_ob0 = pp_obs[pp_obs["id"]==obs0]
pp_obX0 = pp_obs[pp_obs["id"]!=obs0]
orig_ob0 = paths_gdf[paths_gdf["O"]==obs0]
[25]:
base = arcs.plot(alpha=0.2, linewidth=5, color="k", figsize=(10, 10), zorder=0)
pp_obX0.plot(ax=base, color="g", zorder=2)
pp_obs_snapped.plot(ax=base, color="k", marker="s", zorder=2)
pp_ob0.plot(ax=base, markersize=20, marker="s", color="r", zorder=2)
# routes originating from observation 0
orig_ob0.plot(ax=base, color="b", linewidth=10, alpha=0.25);
# synthetic observation labels
obs_labels(pp_obX0, base, 12, c="g");
# synthetic observation labels
obs_labels(pp_ob0, base, 12, c="r");
../_images/notebooks_shortest-path-visualization_42_0.png

2.8. Plot the shortest path routes arriving at observation 4

Since the point pattern is symmetric, origins equal destinations and the shortest paths IDs are sorted and pruned out. Therefore, we have to stipluate either O or D of 4 in this case.

[26]:
obs4 = 4
pp_ob4 = pp_obs[pp_obs["id"]==obs4]
pp_obX4 = pp_obs[pp_obs["id"]!=obs4]
orig_ob4 = paths_gdf[(paths_gdf["O"]==obs4)| (paths_gdf["D"]==obs4)]
[27]:
base = arcs.plot(alpha=0.2, linewidth=5, color="k", figsize=(10, 10), zorder=0)
pp_obX4.plot(ax=base, color="g", zorder=2)
pp_obs_snapped.plot(ax=base, color="k", marker="s", zorder=2)
pp_ob4.plot(ax=base, markersize=20, marker="s", color="r", zorder=2)
# routes originating from observation 4
orig_ob4.plot(ax=base, color="b", linewidth=10, alpha=0.25);
# synthetic observation labels
obs_labels(pp_obX4, base, 12, c="g");
# synthetic observation labels
obs_labels(pp_ob4, base, 12, c="r");
../_images/notebooks_shortest-path-visualization_45_0.png