NOTICE: is no longer in use from 1st March 2024. Please use the OpenStreetMap Community Forum


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.


asked 01 Apr '12, 10:35

Kapuch's gravatar image

accept rate: 0%

My advice: contact the developers of the many Openstreetmap routing services.

( )

Within their software developments they definitely will have dealt with the kind of graph decisions that you are thinkng about here.


permanent link

answered 01 Apr '12, 16:56

Herve5's gravatar image

accept rate: 12%

edited 01 Apr '12, 16:56

... or leave a message to the Routing mailinglist that can be found here:

(01 Apr '12, 18:57) stephan75

Thank You for advice. I just post them an email.

(01 Apr '12, 19:54) Kapuch

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Question tags:


question asked: 01 Apr '12, 10:35

question was seen: 6,966 times

last updated: 01 Apr '12, 19:54

NOTICE: is no longer in use from 1st March 2024. Please use the OpenStreetMap Community Forum