A routing list. Hot. Can I has use Graphserver to precompute the routes? It's fast as all getout. And I made it to do just this.<br><br>A few things:<br><br>An all-pairs routing graph will be proportional to the number of graph nodes (nodes shared by more than one way) squared. I assume this is a bit higher than 4 million, but probably less than 10x higher. I'm guessing there are about five nodes per way, so the number is 4e6*5=20e6

The average route length will be half the width of the graph. The width of this graph is 180 degrees longitude, so the average route length will be as long as 90 degrees longitude, or 10018 kilometers. If the average way is three kilometers long, that's over L=3000 ways per the average route. Half are smaller. Half are larger.

N is 3, B is 2 20 * 10e6 * (3000 * 2) * 3 = 360 billion bytes "gigabytes".  So yeah, that's doable too with a little more effort. I've seen bigger MP3 collections. It's important to note that you don't actually need to compute or store N^2 routes. If you take the shortest-path-tree of a node, and then take the shortest-path-tree of a nearby node, and take the intersection of the two SPTs, you'll find that there's a great deal of overlap between the two that you don't need to compute twice. You'll note this is how our brains figure out routing. When we're in an unfamiliar place we don't figure out a route all the way to the destination; we just figure out a route to a nearby known-place and then do a table lookup for the rest of the route. I don't know how exactly to take advantage of this fact: it's a matter of some fairly exciting research that either has been done or needs to be done in order to pull this off in an open-source way. I'd love to take a swing at it.

<br><br>-B<br><br><br><div><span class="gmail_quote">On 9/27/07, <b class="gmail_sendername">Steve Coast</b> <<a href="mailto:steve@asklater.com">steve@asklater.com</a>> wrote:</span><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">

(please reply to the new routing list, sent to dev so that you know<br>it's there)<br><br>We have about 4 million ways.<br><br>An all pairs routing graph has therefore 16 million entries. We<br>assume a route from a to b may be different than from b to a due to

<br>one way streets, turn restrictions etc.<br><br>Almost every route is going to be something like "take street a,b,c,<br>get on a motorway, come off and do streets d,e,f". That is, almost<br>every route is going to be fairly simple. Let us a assign L to be the

length of route in number of ways traversed. Of course many routes won't exist (you can't drive across oceans). Let us assign N to be the number of types of route, and lets say N is 3 for car, walk, cycle.

<br><br>Let us assign B to be the the number of bytes per way id. B=2, 16<br>bits can currently encode all ways.<br><br>The total disk space to store all routes is therefore<br><br>~= 4 * 10e6 * (L * B) * N<br><br>I'm going to go out on a limb here, and almost any route I've got

<br>directions for is about 10 steps. Some will be more of course, but<br>many will be much less.<br><br>~= 4 * 10e6 * (10 * 2) * 3 ~= 240 million bytes.<br><br>Anyway the key point is we can pre-compute all routes and serve them

<br>from one box fairly easily if we want to. Even if you add an order of<br>magnitude complexity, it's doable.<br><br>This, I'm told, is exactly what Google do. But their dataset is a bit<br>bigger.<br><br>have fun,

<br><br>SteveC | <a href="mailto:steve@asklater.com">steve@asklater.com</a> | <a href="http://www.asklater.com/steve/">http://www.asklater.com/steve/</a><br><br><br><br>_______________________________________________<br>dev mailing list

<br><a href="mailto:dev@openstreetmap.org">dev@openstreetmap.org</a><br><a href="http://lists.openstreetmap.org/cgi-bin/mailman/listinfo/dev">http://lists.openstreetmap.org/cgi-bin/mailman/listinfo/dev</a><br></blockquote>

</div><br>