29
$\begingroup$

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!).

Improve this question
$\endgroup$
11
  • 1
    $\begingroup$ There's the open graph archive: graph-archive.org/doku.php?id=start and a paper explaining the project: arxiv.org/abs/1109.1465 $\endgroup$
    – Joe
    Apr 9, 2012 at 5:22
  • 1
    $\begingroup$ @Raphael Random graphs often don't make representative test cases for real world graphs: these tend to be complex networks. $\endgroup$
    – Gilles 'SO- stop being evil'
    Apr 9, 2012 at 21:07
  • 2
    $\begingroup$ @joe / Pratik - why not posting as an answer? $\endgroup$
    – Ran G.
    Apr 10, 2012 at 21:08
  • 3
    $\begingroup$ @RanG. An answer should not be just a link. $\endgroup$
    – Gilles 'SO- stop being evil'
    Apr 10, 2012 at 22:13
  • 1
    $\begingroup$ @Gilles, I didn't mean posting the comments as-is, but rather (using your link:) "A link to a potential solution is always welcome, but please add context around the link". Currently, there is no option to comment on those links, and vote on them. I'm sure some of those links are very useful and answer the question asked, but nobody can upvote the good ones (in a meaningful way). $\endgroup$
    – Ran G.
    Apr 10, 2012 at 22:21

2 Answers 2

Reset to default
17
$\begingroup$

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.

Improve this answer
$\endgroup$
2
$\begingroup$

I've been visiting all the links provided by Nick. They do look wonderful indeed and I have added all those sites to my bookmarks. Hope that the following link especially designed to test search algorithms suits your needs as well:

Pathfinding Benchmarks by Nathan Sturtevant. It contains various maps from different video games and also other artificial benchmakrs such as mazes and graphs with random obstacles.

If you are, in particular, interested in this sort of domains, then you might want to take part in the Grid-Based Path Planning Competition next year (the results of the first edition of the competition are available at GPPC 2012)

Cheers,

Improve this answer
$\endgroup$
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.