Random maps/graphs and OSM

Question

Hi all,

just wondering if you have any suggestions here. I need a lot of sample maps/graphs to test my shortest path search solution (I was told I should have >100 of them). My code is supposed to work in a simulator, which uses OpenStreetMap maps of urban setting, limiting the total number of junctions to a few thousand. the problem is, there are only two or three maps provided with the simulator. The way I see it, I have a few choices here:

1. Write my own random graph generator. Possibly lots of work (do you think? --I've never done it before) and reinventing the wheel.
2. Use off-the-shelf solution. I'm not aware of any that would generate me map-like graphs (well, at least I didn't find it in JUNG :-) )
3. In some automated way grab them from OSM. I don't really intend to myself go and pick out a 100+ urban maps that would satisfy <15000 nodes requirement. I don't think that would be easy to automate either, though.

I would assume that 3 would be tough to do. Any advice on some off-the-shelf solution? or comments about writing my own? I'm not an experienced programmer by any measure, but given a few days...

Thanks a lot!

Answer 1

The first thought:

You have a known problem and you need to test its solution. Generate lots of test data, find correct solutions with verified algorithm, then run your algorithm against generated data set and compare results. (or just download verified dijkstra algorithm implementation, I believe that implementing this algorithm is your task)

The second thought:

Random-generated data set is not the best way to test algorithms. You need to think about cases when your algorithm can fail and create correspondent tests. For example, graph with 1 node, graph with cycles, linear graph i.e. N1---N2---N3-...-Nn, complete graph with maximum nodes number. I think if you create these 4 tests and 2-3 small random tests it'll be enough to be sure that your algorithm is implemented correctly.