It can be fairly complicated to get a routing algorithm right specially if it is suppose to remain flexible to what values it might contain. The current solution to similar problems in the functional languages environment is called generative testing.
It basically allows a computer to generate test cases based on properties that the function should fulfill. For example: return the same output given the same input.
If we want to keep a stable yet flexible implementation I think it is important to have at least some base properties covered up so that we can rely on them rather than doing manual testing (how I was doing it).
I think we should restrict the testing to single-edge directed graph since those are the ones that we are interested in for OSM routing.
Right now I can think of the following properties for a routing algorithm using Dijkstra's solution:
given the same input, the algorithm should return exactly the same output
the distance between the source and any destination should never be less than zero
the distance between the source and itself should always be zero
if the source is the same as the destination the algorithm should only explore the source node, i.e. stop immediately since the answer is trivial
it is possible to not find a path between a source and a destination as long as it complies with the first property.
OPTIONAL (these are a bit more complicated so we can postpone them)
the distance between any node on the way to the destination and the destination should always be less than the distance to the source
the distance between any settled node and the source should always be less than the distance to the destination (probably duplicate of point above :P )
It can be fairly complicated to get a routing algorithm right specially if it is suppose to remain flexible to what values it might contain. The current solution to similar problems in the functional languages environment is called
generative testing.It basically allows a computer to generate test cases based on properties that the function should fulfill. For example:
return the same output given the same input.If we want to keep a stable yet flexible implementation I think it is important to have at least some base properties covered up so that we can rely on them rather than doing manual testing (how I was doing it).
I think we should restrict the testing to single-edge directed graph since those are the ones that we are interested in for OSM routing.
Right now I can think of the following properties for a routing algorithm using Dijkstra's solution:
OPTIONAL (these are a bit more complicated so we can postpone them)
References: