Algorithm

1. create the two-nearest-neighbors graph $N_2$ using the first data set. That is, let each station be connected to the two closest stations.
2. for a path in the second data set, assume that the train must have been traveling along a geodesic (shortest path between two vertices) on $N_2$, and fill in the missing stations accordingly.

Example: BART

If our partial path is (MacArthur, Lafayette) then we will fill it in as (MacArthur, Rockridge, Orinda, Lafayette), which is correct. There is an edge between Rockridge and Ashby, but that's okay.

Algorithm

1. create the two-nearest-neighbors graph $N_2$ using the first data set. That is, let each station be connected to the two closest stations.
2. for a path in the second data set, assume that the train must have been traveling along a geodesic (shortest path between two vertices) on $N_2$, and fill in the missing stations accordingly.

Example: BART

On input the partial path (MacArthur, Lafayette), the Algorithm outputs

(MacArthur, Rockridge, Orinda, Lafayette), 

which is correct, even though $N_2$ has a spurious edge between Rockridge and Ashby.