[GraphHopper] Making efficient use of DijkstraOneToMany

[Peter K]

Am 20.05.2013 23:01, schrieb Peter K:
> Hi Chris,
>
>> I'm looking at using DijkstraOneToMany to get path costs (just the
>> sum of the edge weights, not the whole path) from a single origin to
>> all nodes closer than some fixed cost limit.
>>
>> I know about findEndNode(), but am not sure if I need to walk the
>> graph of nodes myself, calling findEndNode() and weight() on each
>> node, or if there is a way to walk exhaustively with only a limit as
>> the termination point.
>>
>> Ideally, I'd have something like findEndNodesAndCosts() that would
>> return a map of node ID to path cost for all nodes less than the cost
>> cutoff set with DijkstraOneToMany.limit(). What would be the
>> suggested implementation of this?
>
> You already have all you need, I think. At the end of a call ala
> findEndNode(node, -1) you need to iterate through the changed nodes only:
>
> for(int i = 0; i < changedNodes.size(); i++) {
>    int nodeIndex = changedNodes.get(i);
>    // info: changedNodes could contain duplicates
>    map.put(nodeIndex, weights[nodeIndex])
> }

hmmh, I think you'll have to remove all nodes from the priority queue
too. As for those nodes (except the first one) it is not guaranteed to
already have the minimum weight.
You could do that either via iterating over the queue and then do map.remove

OR

via introducing a new visitedNodes set and do somethink like this pseudo
code:
// eg. with a TIntHashSet
visitedNodes.forEach(-> int nodeIndex) {
     map.put(nodeIndex, weights[nodeIndex])
}
// but e.g. GHBitSetImpl would be the best in terms of memory usage:
for each changedNodes but only if in visitedNodes -> int nodeIndex {
     map.put(nodeIndex, weights[nodeIndex])
}

Regards,
Peter.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/graphhopper/attachments/20130521/458da710/attachment-0001.html>