Hi Curt.
Your method is not ideal as my "hand made" intersections, because it's not
handle one way restrictions, but for the long distances 50 km(miles) and
more difference should be quite small.
If it is working for Germany, it should work for the smalles area.
I just need more details what do you mean by cluster? From theory I know
what it is. But GeoTools basic/linear, directed graph do not have such named
class. There are GraphPartitioner and GraphWalker classes. Does graph
partition = cluster?
If you are able to provide me with more code, please, it will be easier to
understand your method to build a well connected graph.
What I discovered with Geo API classes:
Let's assume there is 10 Kms beetween 2 points. When I load roads within a
small BBOX, intersect lines, make a graph it is connecting nearest nodes
with DijkstraPathFinder.In the most cases. Sometimes I need to select next
to nearest source/destination node in order to get a path. Results are quite
similar with a public services.
But when I load more nodes/egdes from database (widest area) and repeat the
same for my points - nodes are not connected anymore. I've repeated this
trick for hundreds of source/destination pairs. I can't expain why it's
happen.
y java machine has up to 1 gb and application do not reports any of troubles
with memory or CPU resources.
2010/6/21 Curt Nowak <no...@bwl.uni-hildesheim.de>
> 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: routing-boun...@openstreetmap.org [mailto:
> routing-boun...@openstreetmap.org] Im Auftrag von Oleg Demchenko
> Gesendet: Sonntag, 20. Juni 2010 21:21
> An: routing@openstreetmap.org
> 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
> Routing@openstreetmap.org
> http://lists.openstreetmap.org/listinfo/routing
>
--
All the best
Oleg Demchenko
_______________________________________________
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing
