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's gravatar image

Sadeer
1768914
accept rate: 0%

edited 06 Feb '15, 15:42

aseerel4c26's gravatar image

aseerel4c26 ♦
31.9k16236548

2

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

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

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

  1. 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.
  2. 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.
  3. (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%20Ramm's gravatar image

Frederik Ramm ♦
68.3k806211063
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
1

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

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's gravatar image

Sandeep40
111
accept rate: 0%

edited 27 Feb '16, 22:41

Your answer
toggle preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

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

Question tags:

×242
×108
×75
×63
×16

question asked: 19 Jan '13, 16:56

question was seen: 54,683 times

last updated: 27 Feb '16, 22:41

powered by OSQA