[pgrouting-users] Different comportment between 'shortest_path_astar' and 'driving_distance' functions.

Schembri_Samuel · January 16, 2012, 8:14am

Hi,

I am new user of this pgrouting users list. I hope used correctly.

I used pgrouting 1.02 on postgres 8.2.17. At this time, I can’t update Postgresql.

There is a different comportment between ‘shortest_path_astar’ and ‘driving_distance’ functions when I use reverse_cost column.

Here are graphe conditions :

For each edge without one-way : cost=reverse_cost=length
For each edge with one-way similar to digitalisation way : cost=length reverse_cost=-1 (or 100000)
For each edge with one-way inverse of digitalisation way : cost=-1 (or 100000) reverse_cost=length
All another edges are not in graphe.

shortest_path_astar:

has_reverse_cost = false :
Edges with ‘cost=-1’ are forbiden and Pgrouting don’t used them. ‘Reverse_cost’ information is not used.

has_reverse_cost = true:
Edges with ‘cost=-1’ are used if ‘reserve_cost’ is more than 0. Cost used by pgrouting is ‘reserve_cost’ column.

Edges with ‘reverse_cost=-1’ are used if ‘cost’ is more than 0. Cost used by pgrouting is ‘cost’ column.

This computing is correct.

Driving_distance:

has_reverse_cost = false :
Edges with ‘cost=-1’ are forbiden and Pgrouting don’t used them. ‘Reverse_cost’ information is not used.

has_reverse_cost = true :
Case one : Edge with ‘cost=-1’ and ‘reverse_cost=length’:
Edge can be traveled on digitalisation way ( cost =-1!!). Cost used by pgrouting is ‘Reverse_cost’ column.

Case two : Edge with cost=length and reverse_cost=-1:
Edge can be traveled on inverse digitalisation way. More, Cost used by pgrouting is ‘cost’ column.

In this two case, pgrouting don’t respect restrictions. This computing is not correct.

Could you me if this result is normal or not ?

Sorry for my bad english and best regards

Samuel – Paris

Stephen_Woodbridge1 · January 16, 2012, 2:14pm

Hi Samuel,

I'm not sure I can answer your question with doing some additional research of reading through the code, but the driving directions does not get much use and it is possible that it has a bug that noone has reported until now.

Your example seems like a really good test case. I am trying to collect simple and clear test cases so we can develop a test suite that can be run before we release code to validate changes in a release have not broken anything. If you could create a ticket and attach your test cases or just send them to me off list, I can create a ticket for them.

-Thanks,
-Steve

On 1/16/2012 3:14 AM, Schembri Samuel wrote:

Hi,
I am new user of this pgrouting users list. I hope used correctly.
I used pgrouting 1.02 on postgres 8.2.17. At this time, I can't update
Postgresql.
There is a different comportment between 'shortest_path_astar' and
'driving_distance' functions when I use reverse_cost column.
Here are graphe conditions :

  * For each edge without one-way : cost=reverse_cost=length
  * For each edge with one-way similar to digitalisation way :
    cost=length reverse_cost=-1 (or 100000)
  * For each edge with one-way inverse of digitalisation way : cost=-1
    (or 100000) reverse_cost=length
  * All another edges are not in graphe.

*shortest_path_astar:*
/has_reverse_cost = false : /
Edges with 'cost=-1' are forbiden and Pgrouting don't used them.
'Reverse_cost' information is not used.
/has_reverse_cost = true:/
Edges with 'cost=-1' are used if 'reserve_cost' is more than 0. Cost
used by pgrouting is 'reserve_cost' column.
Edges with 'reverse_cost=-1' are used if 'cost' is more than 0. Cost
used by pgrouting is 'cost' column.
T his computing is correct.
*Driving_distance:*
**
/has_reverse_cost = false : /
Edges with 'cost=-1' are forbiden and Pgrouting don't used them.
'Reverse_cost' information is not used.
/has_reverse_cost = true:/
/Case one : Edge with 'cost=-1' and 'reverse_cost=length'
Edge can be traveled on digitalisation way ( cost =-1!!). Cost used by
pgrouting is 'Reverse_cost' column.
/Case two : Edge with cost=length and reverse_cost=-1:/
Edge can be traveled on inverse digitalisation way. More, Cost used by
pgrouting is 'cost' column.
In this two case, pgrouting don't respect restrictions. This computing
is not correct.
Could you me if this result is normal or not ?
Sorry for my bad english and best regards
Samuel -- Paris
//

_______________________________________________
Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

Schembri_Samuel · January 16, 2012, 2:36pm

Hi steve,

Thank you for the response.

Why I would like to used this method. I prefer driving-distance functions because when we must compute a lot of distances with same departure point, this method is more fast than 'shortest_path_astar' method. After, I can get distance with nodes directly.

Example : get distance between shop and 100 customers.

I can create little graphe ,function, and snapshot.

How would you like receive these informations ?

Regards

Samuel

-----Message d'origine-----
De : pgrouting-users-bounces@lists.osgeo.org [mailto:pgrouting-users-bounces@lists.osgeo.org] De la part de Stephen Woodbridge
Envoyé : lundi 16 janvier 2012 15:14
À : pgrouting-users@lists.osgeo.org
Objet : Re: [pgrouting-users] Different comportment between 'shortest_path_astar' and 'driving_distance' functions.

Hi Samuel,

I'm not sure I can answer your question with doing some additional research of reading through the code, but the driving directions does not get much use and it is possible that it has a bug that noone has reported until now.

Your example seems like a really good test case. I am trying to collect simple and clear test cases so we can develop a test suite that can be run before we release code to validate changes in a release have not broken anything. If you could create a ticket and attach your test cases or just send them to me off list, I can create a ticket for them.

-Thanks,
-Steve

On 1/16/2012 3:14 AM, Schembri Samuel wrote:

Hi,
I am new user of this pgrouting users list. I hope used correctly.
I used pgrouting 1.02 on postgres 8.2.17. At this time, I can't update
Postgresql.
There is a different comportment between 'shortest_path_astar' and
'driving_distance' functions when I use reverse_cost column.
Here are graphe conditions :

  * For each edge without one-way : cost=reverse_cost=length
  * For each edge with one-way similar to digitalisation way :
    cost=length reverse_cost=-1 (or 100000)
  * For each edge with one-way inverse of digitalisation way : cost=-1
    (or 100000) reverse_cost=length
  * All another edges are not in graphe.

*shortest_path_astar:*
/has_reverse_cost = false : /
Edges with 'cost=-1' are forbiden and Pgrouting don't used them.
'Reverse_cost' information is not used.
/has_reverse_cost = true:/
Edges with 'cost=-1' are used if 'reserve_cost' is more than 0. Cost
used by pgrouting is 'reserve_cost' column.
Edges with 'reverse_cost=-1' are used if 'cost' is more than 0. Cost
used by pgrouting is 'cost' column.
T his computing is correct.
*Driving_distance:*
**
/has_reverse_cost = false : /
Edges with 'cost=-1' are forbiden and Pgrouting don't used them.
'Reverse_cost' information is not used.
/has_reverse_cost = true:/
/Case one : Edge with 'cost=-1' and 'reverse_cost=length' Edge can
be traveled on digitalisation way ( cost =-1!!). Cost used by
pgrouting is 'Reverse_cost' column.
/Case two : Edge with cost=length and reverse_cost=-1:/ Edge can be
traveled on inverse digitalisation way. More, Cost used by pgrouting
is 'cost' column.
In this two case, pgrouting don't respect restrictions. This computing
is not correct.
Could you me if this result is normal or not ?
Sorry for my bad english and best regards Samuel -- Paris //

_______________________________________________
Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

_______________________________________________
Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

Stephen_Woodbridge1 · January 16, 2012, 4:21pm

On 1/16/2012 9:36 AM, Schembri Samuel wrote:

Hi steve,

Thank you for the response.

Why I would like to used this method. I prefer driving-distance
functions because when we must compute a lot of distances with same
departure point, this method is more fast than 'shortest_path_astar'
method. After, I can get distance with nodes directly.

Example : get distance between shop and 100 customers.

Yes, this makes sense. I wrote some code a while ago that does some similar using driving distance code, but I did not check if the reverse cost were working.

I can create little graphe ,function, and snapshot.

How would you like receive these informations ?

If you want to generate a SQL dump of the above that would be great. If the results are simple enough to generate an expected results table so we can compare the actual results against the expected results that would be great, but if it is too complax than we can figure it out later.

Thanks,
-Steve

Regards

Samuel

-----Message d'origine----- De :
pgrouting-users-bounces@lists.osgeo.org
[mailto:pgrouting-users-bounces@lists.osgeo.org] De la part de
Stephen Woodbridge Envoyé : lundi 16 janvier 2012 15:14 À :
pgrouting-users@lists.osgeo.org Objet : Re: [pgrouting-users]
Different comportment between 'shortest_path_astar' and
'driving_distance' functions.

Hi Samuel,

I'm not sure I can answer your question with doing some additional
research of reading through the code, but the driving directions does
not get much use and it is possible that it has a bug that noone has
reported until now.

Your example seems like a really good test case. I am trying to
collect simple and clear test cases so we can develop a test suite
that can be run before we release code to validate changes in a
release have not broken anything. If you could create a ticket and
attach your test cases or just send them to me off list, I can create
a ticket for them.

-Thanks, -Steve

On 1/16/2012 3:14 AM, Schembri Samuel wrote:

Hi, I am new user of this pgrouting users list. I hope used
correctly. I used pgrouting 1.02 on postgres 8.2.17. At this time,
I can't update Postgresql. There is a different comportment between
'shortest_path_astar' and 'driving_distance' functions when I use
reverse_cost column. Here are graphe conditions :

* For each edge without one-way : cost=reverse_cost=length * For
each edge with one-way similar to digitalisation way : cost=length
reverse_cost=-1 (or 100000) * For each edge with one-way inverse of
digitalisation way : cost=-1 (or 100000) reverse_cost=length * All
another edges are not in graphe.

*shortest_path_astar:* /has_reverse_cost = false : / Edges with
'cost=-1' are forbiden and Pgrouting don't used them.
'Reverse_cost' information is not used. /has_reverse_cost = true:/
Edges with 'cost=-1' are used if 'reserve_cost' is more than 0.
Cost used by pgrouting is 'reserve_cost' column. Edges with
'reverse_cost=-1' are used if 'cost' is more than 0. Cost used by
pgrouting is 'cost' column. T his computing is correct.
*Driving_distance:* ** /has_reverse_cost = false : / Edges with
'cost=-1' are forbiden and Pgrouting don't used them.
'Reverse_cost' information is not used. /has_reverse_cost = true:/
/Case one : Edge with 'cost=-1' and 'reverse_cost=length' Edge
can be traveled on digitalisation way ( cost =-1!!). Cost used by
pgrouting is 'Reverse_cost' column. /Case two : Edge with
cost=length and reverse_cost=-1:/ Edge can be traveled on inverse
digitalisation way. More, Cost used by pgrouting is 'cost' column.
In this two case, pgrouting don't respect restrictions. This
computing is not correct. Could you me if this result is normal or
not ? Sorry for my bad english and best regards Samuel -- Paris //

_______________________________________________ Pgrouting-users
mailing list Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

_______________________________________________ Pgrouting-users
mailing list Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users
_______________________________________________ Pgrouting-users
mailing list Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

Schembri_Samuel · January 17, 2012, 10:26am

Hi Steve,

This is zip file with:

*Bug1.png You can see :

- Shortest_path function result : Green line
- Graph with digitalisation sens
- Id of vertex
- One way of 2 edges : red arrows

To go to vertex(48) since vertex (540), pgrouting is doing good choice because the edge (2: gid 51) has a big cost value . Full distance is 1159 meters.

*Bug2.png You can see :

- Driving distance result: blue labels and variant color : Distance ( meters)
- Edges used by pgrouting : blue line
- One way of 2 edges : red arrows

To go to vertex(48) since vertex(540), pgrouting takes the edge (2) with big cost value and he used reverse_cost value to calculate full distance.

Distance vertex must be egal to 1159.

*Dump with my graphe . (create a tif1104 schema before import)

Query:

select *
from shortest_path('
     select
      id
      ,source
      ,target
      ,cost
      ,reverse_cost,
      to_cost
      ,rule

     from
      tif1104.graphe
     where
      statut is true
      order by id',
     540,
    48,
    false,
    true )

select
*
from
driving_distance('
    select
     id
     ,source
     ,target
     ,cost
     ,reverse_cost
     ,to_cost
     ,rule
    from
     tif1104.graphe
    where
     statut is true
    order by id',
    540,
    2000,
    false,
    true)

Best regards ...