Oleg, Curt, > 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)
Dijkstras algorithm isn't the right hammer for the screw here. Breadth-first search is a lot more efficient. http://www.ics.uci.edu/~eppstein/161/960220.html > 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. --Dennis _______________________________________________ Routing mailing list [email protected] http://lists.openstreetmap.org/listinfo/routing
