@Marcus: You're right: It does not consider oneway-streets. But it will never delete too many nodes. Thus you will end up with a graph that is at least much better suited for the given problem. The only case where oneway-streets would still lead to no (legal) route between to nodes would then be if someone had added a oneway-street that leads to a new node (or, of course, due to deleting/changing of ways). I'd hope there are not too many of these in the map.
@Dennis: Did you mean "Depth-First-Search" as described in your link? I don't see why that would make a difference here, though. Either way, my personal implementation only iterates X times and then restarts from a new node. It simply connects two clusters if it finds out they share a node. This way I save a lot of memory, too. Curt -----Ursprüngliche Nachricht----- Von: [email protected] [mailto:[email protected]] Im Auftrag von Marcus Wolschon Gesendet: Montag, 21. Juni 2010 13:39 An: [email protected] Betreff: Re: [Routing] Find shortest path using OSM format file for a country. -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Am 21.06.2010 13:28, schrieb Curt Nowak: > Hi Oleg, > > in order to get a well connected graph (i.e. a graph in which > every node is reachable from every other node in that graph) I use > the follwowing procedure: > > ... > > If your map contains m disjunct well connected graphs, you will > end up with m clusters. Then I simply delete all but the largest > cluster. In my findings (map of Germany) this main cluster > contains ~99% of the nodes if I remember correctly, so I don't > really mind deleting the rest. > > Curt I think your idea falls apart when there are oneway-streets. Something we have lots of. It may however not be of practical relevance. Marcus -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAkwfT10ACgkQf1hPnk3Z0cTmMgCgkqo3GlawVi+7oST+pyFprXsG ibwAn2E6upkTOjyx28aF2r2cCddsgyz4 =2GcD -----END PGP SIGNATURE-----
_______________________________________________ Routing mailing list [email protected] http://lists.openstreetmap.org/listinfo/routing
