JB Tenenbaum, V Silva, JC Langford - science, 2000

```python import matplotlib.pyplot as plt from mpl_toolkits.mplot3d import Axes3D import numpy as np from scipy.spatial import KDTree from networkx import Graph, shortest_path import networkx as nx

1. Generate data

N = 2000 K=7 x = np.random.rand(N,2) def F(X):

   if X.ndim == 1:
     X = X[None,:]
   X1 = X[:,0]
   X2 = X[:,1]
   Y1 = (X1 + 0.5)*np.cos(10*X1)
   Y2 = X2
   Y3 = (X1 + 0.5)*np.sin(10*X1)
   return np.column_stack((Y1, Y2, Y3))

y = F(x)

1. Find points

x_left_id = np.argmin(np.sum((x - [0.15,0.15])**2, axis=1)) x_right_id = np.argmin(np.sum((x - [0.85,0.85])**2, axis=1)) x_left = x[x_left_id] x_right = x[x_right_id]

1. Build KNN graph on y

knn = KDTree(y) G_y = nx.Graph() for i in range(N):

   idx = knn.query([y[i]], k=K)[1][0]
   for j in idx:
       G_y.add_edge(i,j)

G_x = nx.Graph()

1. Convert edges from G_y to G_x

for e in G_y.edges:

   G_x.add_edge(e[0], e[1])

1. Get shortest path nodes

path_x = shortest_path(G_x, x_left_id, x_right_id, 'weight') path_y = [p for p in shortest_path(G_y, x_left_id, x_right_id, 'weight')]

1. Plot

fig = plt.figure(figsize=(20, 20))

1. A

ax = fig.add_subplot(221, projection='3d') ax.scatter(y[:,0], y[:,1], y[:,2], c='k') ax.scatter(F(x_left)[0,0], F(x_left)[0,1], F(x_left)[0,2], c='b', marker='o', s=100) ax.scatter(F(x_right)[0,0], F(x_right)[0,1], F(x_right)[0,2], c='b', marker='o', s=100) t = np.linspace(0,1,1000) ax.plot(F(x_left + t[:,None]*(x_right-x_left))[:,0],

       F(x_left + t[:,None]*(x_right-x_left))[:,1],
       F(x_left + t[:,None]*(x_right-x_left))[:,2], c='b')

ax.set_title('A')

1. B

ax = fig.add_subplot(222, projection='3d') ax.scatter(y[:,0], y[:,1], y[:,2], c='k') for e in G_y.edges:

   ax.plot(y[e,0], y[e,1], y[e,2], c='grey')

ax.plot(np.array(y)[path_y,0], np.array(y)[path_y,1], np.array(y)[path_y,2], c='r') ax.set_title('B')

1. C

ax = fig.add_subplot(212) ax.scatter(x[:,0], x[:,1], c='k') for e in G_x.edges:

   ax.plot(x[e,0], x[e,1], c='grey')  

ax.plot([x_left[0], x_right[0]], [x_left[1], x_right[1]], c='b') ax.plot(np.array(x)[path_x,0], np.array(x)[path_x,1], c='r') ax.set_title('C')

plt.tight_layout() plt.show()