11

City streets can be represented as graphs with crossings as vertices and roads as edges. And, naturally, that's the representation traffic routing services (like Google Maps) are based on.

These graphs can be recovered from the road layers available on OpenStreetMap or elsewhere. For example, see https://gis.stackexchange.com/questions/104452/how-to-build-a-graph-from-a-map.

Are there any repositories of the ready-made graphs for cities that would let me to avoid going through this conversion process?

2
  • 2
    There is a partial source for Königsberg, at least some of the bridges.
    – PyRulez
    Jun 18, 2015 at 21:47
  • This would actually be fairly useful data to have. What cities do you seek specifically? I might try to code something up (and release the results) just for fun.
    – user3856
    Aug 7, 2015 at 13:34

2 Answers 2

4

This doesn't answer your question and may not even be accurate, but here's some starter code, if we assume that a "vertex" in your graph is a "node shared by at least two ways" (which means dead ends/cul de sacs are NOT considered vertexes).

To convert OSM data to a trivial undirected G(V,E) graph (no edge lengths, no names, etc):

  • Find which nodes appear in more than one way:
bzfgrep 'nd ref' albuquerque_new-mexico.osm.bz2|sort|uniq -d>multinodes.txt
  • Create a file that contains the above PLUS the string "<way". One way (ha ha) to do this:
echo "<way" >> multinodes.txt
  • Find the ways that have these repeated nodes:
bzfgrep -f multinodes.txt albuquerque_new-mexico.osm.bz2 > multinodes2.txt
  • And how they connect:
perl -ne 'chomp; if (/<way/) {print "\n"; next} else {/ref="(\d+)"/; print "$1 "}' multinodes2.txt > multinodes3.txt
  • Each line now shows a list of pairwise connected vertexes.

  • NOTE: Lines with a single vertex represent nodes that connect to dead ends. You can probably ignore them.

I'm bored and would be happy to do this (and perhaps a bit more) for free for any city in https://mapzen.com/data/metro-extracts

2

I have found 2 repositories with graphs

  • Real Datasets for Spatial Databases There are 5 spatial graphs. Each graph is build from two files: list of nodes with x and y coordinates and list of edges with distances. This format is quite useful for tests and debugging: you can load small number of nodes (e.g. 20) then load only edges used by that subset of nodes.
  • Stanford Large Network Dataset Collection I don't know anything about this repostiory (never used it) however they have graphs from various areas of research (social networks, roads, wikipedia pages)
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.