GeoTools
  1. GeoTools
  2. GEOT-2581

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.

      1. dijktc.tar.gz
        11 kB
        Sandeep Kumar Jakkaraju
      2. GEOT-2581.patch
        8 kB
        Justin Deoliveira

        Activity

        Hide
        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
        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
        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
        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
        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
        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
        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
        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

          • Assignee:
            Justin Deoliveira
            Reporter:
            Sandeep Kumar Jakkaraju
          • Votes:
            0 Vote for this issue
            Watchers:
            0 Start watching this issue

            Dates

            • Created:
              Updated:
              Resolved: