How can I convert an OSM XML file into a graph representation?

How can I convert an OSM XML file into a graph representation (such that ways become edges of the graph and intersections/junctions become the nodes of the graph)?

asked 19 Jan '13, 16:56

Sadeer
176●8●9●14
accept rate: 0%

edited 06 Feb '15, 15:42

aseerel4c26 ♦
32.2k●16●239●552

This blog post by the author of OSRM might be helpful.

(04 Feb '14, 11:24) SomeoneElse ♦

2 Answers:

Assuming you want only roads, then a possible algorithm is this:

parse all ways; throw away those that are not roads, and for the others, remember the node IDs they consist of, by incrementing a "link counter" for each node referenced.
parse all ways a second time; a way will normally become one edge, but if any nodes apart from the first and the last have a link counter greater than one, then split the way into two edges at that point. Nodes with a link counter of one and which are neither first nor last can be thrown away unless you need to compute the length of the edge.
(if you need geometry for your graph nodes) parse the nodes section of the XML now, recording coordinates for all nodes that you have retained.

If you are only working on a small data set you can of course simply read everything into memory and do the above analysis in memory.

permanent link

answered 19 Jan '13, 17:17

Frederik Ramm ♦
73.3k●86●664●1137
accept rate: 24%

"throw away those that are not roads" the devil is in the details. You can't search for ways tagged with car=yes. So if you need a graph for only cars you will probably need to look at filters used by available routers.

(21 Jan '13, 11:19) emj

@emj: Correct. You should search for ways with highway tag other than pedestrian,footway,cycleway,bridleway. And eliminate oneways with final point unconnected.

(03 May '13, 12:28) erkinalp

Hi,i am wondering why exactly we need to execute step #2 from above?

The logic is mainly implemented in the python script here : https://gist.github.com/aflaxman/287370

So if I remove lines 144-159 from the script in the link (i.e. omit the step #2 from above) I get a fine graph as well.

(02 Jul '15, 16:21) rajanskus

Depends on your definition of "graph". Usually, a graph consists of nodes and edges, where each edge connects to exactly two nodes. If you leave out step 2, you will end up with something where an edge can go from node A across node B to node C. This is not a graph, and various graph-based routing engines or network analyzers will have trouble working with that.

(09 Jul '15, 18:11) Frederik Ramm ♦

Hi, one short question...what do you exactly mean with "link counter"?

(10 Jul '15, 06:33) madalina_ias...

link counter := number of ways by which one node is used.

(24 Jul '15, 21:09) Frederik Ramm ♦

Link counter means degree of the vertex.

(22 Feb '16, 10:45) Ankita_Mehta

showing 5 of 7 show 2 more comments

0	Working with OSM and Java implementation using Jgrapht library http://www.sandeepsas.com/how-do-i-start-working-with-openstreetmap-osm/ permanent link answered 27 Feb '16, 22:39 Sandeep40 11●1 accept rate: 0% edited 27 Feb '16, 22:41

Markdown Basics

*italic* or _italic_
**bold** or __bold__
link:[text](http://url.com/ "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

learn more about Markdown

Question tags:

routing ×263
development ×110
xml ×80
.osm ×65
graph ×17

question asked: 19 Jan '13, 16:56

question was seen: 57,070 times

last updated: 27 Feb '16, 22:41

How can I convert an OSM XML file into a graph representation?

Related questions