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:
FOR EACH node n in the graph
IF node does not belong to a cluster yet
DO
one iteration of the Dijkstra algorithm (start node being n)
assign every newly reached node to current_clusterID
WHILE there are still nodes reachable "via Dijkstra algorithm"
END IF
current_clusterID := current_clusterID + 1
END FOR
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
-----Ursprüngliche Nachricht-----
Von: [email protected]
[mailto:[email protected]] Im Auftrag von Oleg Demchenko
Gesendet: Sonntag, 20. Juni 2010 21:21
An: [email protected]
Betreff: [Routing] Find shortest path using OSM format file for a country.
Hi All.
I have a task to develop Java application on Windows server which estimates
shortest path available for vehicle between any coordinates given within
country. Distance between coordinates could be from 400m to 250 Km.
I've spent several weeks for the following idea: country shape file from
CloudMade loaded to PostGIS db, graph (build from features/LineString,
DirectedLineString) using appropriate line builders. Than
DijsktraShortestPathFinder. Well, I even developed a method which split
LineString on "simple" line segments (if it rings or segments) and intersect
them each other using spatial index. But graph connects nodes and find a path
for points 10-15 km each other. For bigger distance and bigger number of lines
it do not connect them all properly while building a graph and
DijsktraShortestPathFinder can't find a path.
Afterwards GEOTools and OSM developers advised me to use OSM format files,
because they already contains nodes, ways, relations, etc. I've load country
highway DB to PostgreSQL using OSMOSIS API v1.6
Could you advice, please, me how to build well connected graph and/or find a
route on reliable basis?
One of the options I've found is Traveling Salesman with Route class. It is
possible to load OSM file from disk. But how to build a graph afterwards and
how mySelector below should be implemented?
FileLoader fl = new FileLoader(new File("C:\\Install\\denmark.osm.highway"));
MemoryDataSet map = fl.parseOsm();
LatLon startCoord = new LatLon(12.180064, 55.470843);
Node startNode = NodeHelper.findNearestNode(osmData, startCoord);
LatLon targetCoord = new LatLon(12.198208, 55.516831);
Node targetNode = NodeHelper.findNearestNode(osmData, targetCoord);
TurnRestrictedMultiTargetDijkstraRouter router = new
TurnRestrictedMultiTargetDijkstraRouter();
Route theRoute = router.route(map, targetNode, startNode, mySelector);
...
--
All the best
Oleg Demchenko
_______________________________________________
Routing mailing list
[email protected]
http://lists.openstreetmap.org/listinfo/routing
