graphhopper/graphhopper — pull request #158 by khuebner (2014-03-05 14:13:42+00:00)
Title: Preparing support of turn restrictions (4): Introducing edge-based routing algorithms

This pull requests contents changes in AStar, Djikstra, DijkstraBidirectionRef and AStarBidirection which let those algorithms traverse edges instead of nodes. The edge-based behavior is necessary in order to fully support turn restrictions and P-turns in the resulting paths. Following changes have been made:

The prior implementation used the id of the adjacent node to access the map of shortest weights during traversal. An edge-based version of the same algorithms would use the id of the current edge instead of its adjacent node. Therefore, I added a method `createIdentifier(EdgeIterator)` in `AbstractRoutingAlgorithm` in order to move the desired traversal behavior to the super class. Additionally, the traversal mode can be defined in `AbstractRoutingAlgorithm`, which is either NODE_BASED (default behavior), EDGE_BASED or EDGE_BASED_DIRECTION_SENSITIVE (description can be found in the source). Several tiny adjustments in the inheriting routing algorithms have been made in order to support the different traversal modes.

Additionally, the adapted algorithms now consider turn restrictions/costs if the graph stores them in its extended storage. However, tests for turn restrictions/costs have not been written yet. This pull request solely aims to introduce the edge-based behavior to present routing algorithms.