Isomap

Distances along the manifold

Euclidean distance can be misleading on a curved manifold: two points on opposite ends of a rolled-up sheet look close in space even though they are far apart along the surface. Isomap measures distance along the surface instead, then embeds those geodesic distances with classical MDS.

Implement isomap(X, n_neighbors, n_components). Return coordinates of shape (n, n_components).

1. Build the k-nearest-neighbor graph. Connect each point to its n_neighbors nearest points by Euclidean distance. Make the graph symmetric, so an edge exists if either endpoint lists the other.
2. Set edge weights to the Euclidean distance between the endpoints.
3. Compute all-pairs shortest path lengths with Floyd-Warshall. These are the geodesic distances.
4. If any geodesic distance is infinite, raise ValueError because the graph is disconnected.
5. Run classical MDS on the geodesic distance matrix and keep n_components coordinates.

Constraints

• 1 ≤ n_neighbors < n, otherwise raise ValueError.
• 1 ≤ n_components ≤ n, otherwise raise ValueError.
• Do not modify X.

Hints