Where to get graphs to test my search algorithms against?

I am implementing a set of path finding algorithms such as Dijkstra’s, Depth First, etc.

At first I used a couple of self made graphs, but now I’d like to take the challenge a bit further and thus I’m looking for either

  1. graphs used in benchmarks;
  2. graphs of real world cities (or a way to download that kind of info off google maps, or any other kind of source, if possible).

I’d like those sources to either have or allow me to easily create frontiers such that I can try my algorithms for different sized sets of graphs, if possible.

I’m looking for simple solutions, as I’d prefer not to be diverted from main goal (compare a set of different algorithms), so I’d need a quick way to convert that graph data into my own format (basically, a set of connected (x, y) points).

To be more concrete, what I’m looking for are 2D cyclic graphs. If those graphs reflect real world city streets (taking into consideration one-way streets, two-way streets, etc, better yet!).

Answer

Search the inter-webs.

SNAP is a set of networks hosted by a prof at Stanford. Several real world examples in a variety of settings.

Net Wiki is hosted by a UNC math prof., again several links to real datasets as well as links to other data resources.

OpenFlights Has airports and routes between them (spatial network).

OpenStreetMap user edited network of roads for most of the world. You can also download subsets (e.g. just roads in Ohio, or just highways in North America). Format is in xml, not super easy to parse, but its a real world ~2d cyclic network.

There are several other resources as well, you’ll just have to dig a little.

Attribution
Source : Link , Question Author : devoured elysium , Answer Author : Nick

Leave a Comment