GeoTools

Improvement DijkstrasPathFinder to into account Turn Costs

Details

  • Type: Improvement Improvement
  • Status: Closed Closed
  • Priority: Major Major
  • Resolution: Fixed
  • Affects Version/s: None
  • Fix Version/s: 2.5.7, 2.6-M2
  • Component/s: graph extension
  • Labels:
    None
  • Testcase included:
    yes

Description

This is an improvement suggestion for the Dijsktra's Algorithm.
We can add turn costs asscoiated with each pair of adjacent edges to the total cost.

Attachments

  1. GZip Archive
    dijktc.tar.gz
    30/Jun/09 5:04 AM
    11 kB
    Sandeep Kumar Jakkaraju
  2. Text File
    GEOT-2581.patch
    05/Jul/09 11:09 PM
    8 kB
    Justin Deoliveira

Activity

Ascending order - Click to sort in descending order
Hide
Permalink
Justin Deoliveira added a comment -
Hi, thanks for the contributions. Is this a patch? Or a completely new set of classes? Maybe a bit more of a description would be helpful of what is contained. Thanks.
Show
Justin Deoliveira added a comment - Hi, thanks for the contributions. Is this a patch? Or a completely new set of classes? Maybe a bit more of a description would be helpful of what is contained. Thanks.
Hide
Permalink
Sandeep Kumar Jakkaraju added a comment -
This is set of new Classes DijkstraPathFinderWithTurnCosts.
It is based on minor modifications to the classes corresponding to DijkstrasPathFinder.
It also includes a Unit Test Case.
Show
Sandeep Kumar Jakkaraju added a comment - This is set of new Classes DijkstraPathFinderWithTurnCosts. It is based on minor modifications to the classes corresponding to DijkstrasPathFinder. It also includes a Unit Test Case.
Hide
Permalink
Justin Deoliveira added a comment -
Hi Sandeep,

Took a quick look at the patch. I think the idea of adding a turn cost is a great one, however the implementation of it has some issues. The DijsktraWithTurnCost seems to be a 99% copy of the regular Dijkstra. In general we try to promote code reuse as much as possible, as duplication on this scale has a high maintainence burden.

As I see it, we should be able to modify the regular Dijkstra code to account for turn costs directly, rather than create a seperate set of classes for it. If I understand correctly all that would be needed is:

1. Add the TurnWeighter class to DijkstraIterator (perhaps rename it to NodeWeighter? since the term Turn seems specific to road networks)
2. Modify the DijkstraIterator constructor to optionally take a NodeWeighter instance as well
3. Modify DijkstraIterator.cont() more or less the same way you have in the copy of it

Am I missing anything? I think this way the end result will eliminate the duplication but at the same time account for turn cost, which is a very cool feature! :)
Show
Justin Deoliveira added a comment - Hi Sandeep, Took a quick look at the patch. I think the idea of adding a turn cost is a great one, however the implementation of it has some issues. The DijsktraWithTurnCost seems to be a 99% copy of the regular Dijkstra. In general we try to promote code reuse as much as possible, as duplication on this scale has a high maintainence burden. As I see it, we should be able to modify the regular Dijkstra code to account for turn costs directly, rather than create a seperate set of classes for it. If I understand correctly all that would be needed is: 1. Add the TurnWeighter class to DijkstraIterator (perhaps rename it to NodeWeighter? since the term Turn seems specific to road networks) 2. Modify the DijkstraIterator constructor to optionally take a NodeWeighter instance as well 3. Modify DijkstraIterator.cont() more or less the same way you have in the copy of it Am I missing anything? I think this way the end result will eliminate the duplication but at the same time account for turn cost, which is a very cool feature! :)
Hide
Permalink
Sandeep Kumar Jakkaraju added a comment -
Hi Justin

I agree that this change needs to be incorportated in the Dijkstra's directly.
You have listed all the changes correctly. So please go-ahead the commit the changes if it is ok.

Thanks

Sandeep Kumar Jakkaraju
Show
Sandeep Kumar Jakkaraju added a comment - Hi Justin I agree that this change needs to be incorportated in the Dijkstra's directly. You have listed all the changes correctly. So please go-ahead the commit the changes if it is ok. Thanks Sandeep Kumar Jakkaraju
Hide
Permalink
Sandeep Kumar Jakkaraju added a comment -
 

Can we make changes in the orginal DijkstraPathFinder with a new method calculateCost() and re use the entire class for the one with turn penalties overriding this method ?

Let me know if you want me to work on how to incorporate this change in the existing classes.
Show
Sandeep Kumar Jakkaraju added a comment -   Can we make changes in the orginal DijkstraPathFinder with a new method calculateCost() and re use the entire class for the one with turn penalties overriding this method ? Let me know if you want me to work on how to incorporate this change in the existing classes.
Hide
Permalink
Justin Deoliveira added a comment -
I went ahead and merged it in Sandeep, it turned out to be fairly straight forward. I have committed to both 2.5.x and trunk, so if you want to look it over and make sure it meets yours needs that would be great.
Show
Justin Deoliveira added a comment - I went ahead and merged it in Sandeep, it turned out to be fairly straight forward. I have committed to both 2.5.x and trunk, so if you want to look it over and make sure it meets yours needs that would be great.
Hide
Permalink
Justin Deoliveira added a comment -
Attaching the final version of the patch.
Show
Justin Deoliveira added a comment - Attaching the final version of the patch.
Hide
Permalink
Andrea Aime added a comment -
Mass closing all issues that have been in "resolved" state for 2 months or more without any feedback or update
Show
Andrea Aime added a comment - Mass closing all issues that have been in "resolved" state for 2 months or more without any feedback or update

People

Vote (0)
Watch (0)

Dates

  • Created:
    Updated:
    Resolved:
Atlassian JIRA (v4.4.3#663-r165197) | Report a problem
Powered by a free Atlassian JIRA open source license for Codehaus. Try JIRA - bug tracking software for your team.