[pgrouting-users] Problems with SHORTEST_PATH and SHORTEST_PATH_SOOTING_STAR Part II

[pvela at uci.cu]

Hello: 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
  o-------o--------o 8
          |        |    IX     <<<-----------
          | 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