[pgrouting-users] Problems with SHORTEST_PATH and
SHORTEST_PATH_SOOTING_STAR
pvela at uci.cu
pvela at uci.cu
Thu Apr 2 15:19:52 EDT 2009
Hello: Velería and other colleagues of the list.
In the first place desire to thank them for their useful answers
I have come confronting problems with the use of the functions for some
days: SHORTEST_PATH and
SHORTEST_PATH_SOOTING_STAR, when trying to implement in analysis of the
grafo having in all in sense of circulation of the roads.
I configured my database of arches with the fields required by both
functions and I upgraded the
values correctly. Even so, the obtained result was unstable, in occasions it
gave like part of the
result, arches with COST: 999999999, that is to say, they incorporated to
the solution arches of ONEWAY in inverse orientation.
In these moments, we are able to identify exactly that makes critical the
calculation, under what conditions I obtain a not wanted result.
Figura 1
1 I 2 IX
o-------o--------o 8
| | <<<-----------
| II | _____________ _______________
| |/ IV \ / VI \
3 o--------o 4 o 5 6 o------------o 7
III \_____________/ \_______________/ VIII
V VII
------------->>>
Table 1
Id Source Tarjet Cost Reverse_Cost oneway
---------------------------------------------------------
I 1 2 100 100 true
II 2 3 120 120 true
III 3 4 90 90 true
IV 5 4 200 99999999 false
V 4 5 205 99999999 false
VI 6 5 210 99999999 false
VII 5 6 215 99999999 false
VIII 6 7 400 400 true
IX 4 8 121 121 true
The problem with SHORTEST_PATH
The problem is presented, when arches ONEWAY is analyzed, similar to the
arches: IV, V, VI and VII
(to see Figure 1). These arches have the particularity of sharing the same
couple of vertexes.
Because the function is working with the parameter: has_reverse_cost = true,
analyzes each arch in both addresses and it usually discards the
inverse sense with cost exaggerated ej: 9999999999.
But when they share the same couple of vertexes, both ARCHES are analyzed
and you returns as
solution, the first ARCH that finds, according to the (Order By) of the
consultation. (In this case for ID).
For example.
Using SHORTEST_PATH, to go of the vertex 3 at the 7.
The result will be:
vertex_id edge_id cost
--------------------------------------------
3 III 90
4 IV 99999999
5 VI 99999999
6 VIII 400
7 -1 0
Now, we will invest the analysis. We will go of the vertex 7 at the 3 and we
will obtain the
following result:
vertex_id edge_id cost
--------------------------------------------
7 VIII 400
6 VI 210
5 IV 200
4 III 90
3 -1 0
As you it can appreciate, the same arches are included in the solution. The
algorithm becomes critical when to the consultation of: What Arch it
is understood among the vertexes: example: 4 and 5, the answer is: IV
(inverse) and V (direct). two arches are obtained and I don't unite.
The algorithm takes one of the two resulting ARCHES, without analyzing
its cost,
the approach that is assumed is the ORDER, the ARCH that first
appears it will be the result.
First, I want to have transmitted the problem that occupies me with this
function and second that some colleague can give us a hand with this,
clearly although in our opinion, if we are not mistaken in our
hypothesis of the problem, the solution should imply modifications in
the code of the function.
The problem with SHORTEST_PATH_SOOTING_STAR
Excuse, colleagues to approach two questions in oneself mail, but both are
you tune and in graph and the chart of arches, they will serve me as
illustration.
Good, regarding the function SHORTEST_PATH_SOOTING_STAR, in previous days
outlines this problem in the list and I was recommended to illustrate
it better, and I will make it very shortly, through an example, taking
like reference the previous graph:
Arch of Beginning: II
Destination arch: I
The exit arch (II) it is traced of the vertex: 2 at the 3. being I and II
two Bi-directional Arches, the solution should be: 2 >> 1, but like it
is impossible to leave of an Arch (BI-Derectional), in address
contrary to their layout, that is to say, of the Final Vertex to the
Initial Vertex and to assume like Weight, the reverse_cost.
The solution that we would have, according to the previous graph, would be
the following one: II
III >> IX >> I.
We carry out a test, modifying the reverse_cost =99999 of the following arch
(example: > III) and the following result was obtained: II >> II >> I.
Returns for the beginning arch, but it includes it twice (direct and
inverse).
Our concern, if they are properly established the cost values and
reverse_cos and the parameters of the function were selected: directed
and has_reverse_cost: Why the analysis cannot detect a better route,
following the inverse orientation of a BI-DIRECTIONAL Arch.
I wait they can understand each other and to help
Thank you colleagues, and excuse me to extend
Greetings Paul
More information about the Pgrouting-users
mailing list