Transform OSM data to simple cities, villages nodes and edges that connect those nodes.

Hi

I need a fast algorithm and input data to it to calculate for user what cities and villages are on the track from one city to another.

I realized that this is not simple especialy if speed of the calculation is crucial. I was thinking about fetching OSM data for one country and transform it to the graph with nodes and edges. Let's name this graph IG - Input Graph.

Now I would like to proces this IG to OG (output graph) that contains only cities/villages nodes and edges that are calculated based on IG roads. In simple words I need a graph that let me calculate in fast way the answer to question: If I start from city nr 3 and want to drive to city nr 7 what city/village will I be passing? The answers are:

1. You will be passing cities/villages: 5, 6, 7
2. You will be passing cities/villages: 2, 4, 6, 7
3. You will be passing cities/villages: 5, 4, 6, 7

The city / village nodes are retrieved from OSM file. The Output Graph edges should have weight calculated based on the Input Graph edges. The measure of the weight is in general distance in meters from one node to the next.

My question is. Does somebody was working on something like this. I don't want to duplicate somebodys work. Ofcourse everybody are welcome to help me do it in right way.