[pgrouting-users] How many people use the wrapper functions?

pgRouting pgrouting-users
1

Hi all,

Daniel and I have been wondering if people use the wrapper function versus the core functions directly? Or if you have written your own wrapper functions? etc.

The core functions are the low level function that directly call the internal library functions.

The wrapper functions are all the additional plpgsql convenience functions that generate more complex SQL queries and then call the core functions.

I know that I never use the wrapper functions because I found them to messy and inconsistent and have hard coded values in them, etc. So I wrote my own high level wrapper functions that made it easy for me to work with the core functions.

So I thought it would be wise to ask our users what they use? and how they use pgRouting, so we do not may a decision like "Throw out the wrapper functions" without some input from the user community.

PLEASE TAKE ACTION and let us know!

Thanks,
   -Steve

2

I don’t, probably for the same reasons, if you need to use/swap multiple algorithms using wrapper functions can get really tricky.

With the amount of helper functions current available (astar example)

astar_sp
astar_sp_bbox
astar_sp_bbox_directed
astar_sp_delta
astar_sp_delta_cc
astar_sp_delta_cc_directed
astar_sp_delta_directed
astar_sp_directed
it’s just easier to lean the API, and there are great examples in the workshop to do so.

···

On Sat, May 11, 2013 at 11:20 PM, Stephen Woodbridge <woodbri@swoodbridge.com> wrote:

Hi all,

Daniel and I have been wondering if people use the wrapper function versus the core functions directly? Or if you have written your own wrapper functions? etc.

The core functions are the low level function that directly call the internal library functions.

The wrapper functions are all the additional plpgsql convenience functions that generate more complex SQL queries and then call the core functions.

I know that I never use the wrapper functions because I found them to messy and inconsistent and have hard coded values in them, etc. So I wrote my own high level wrapper functions that made it easy for me to work with the core functions.

So I thought it would be wise to ask our users what they use? and how they use pgRouting, so we do not may a decision like “Throw out the wrapper functions” without some input from the user community.

PLEASE TAKE ACTION and let us know!

Thanks,
-Steve

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

3

Hi Steve,

I used one of the wrappers, shootingstar_sp_smart I think, but had to modify
it due to problems. I think that it is the one which uses shooting star
which I've since heard doesn't work.

I think that it works for us as all we are using is length as cost to find
the length from a to b. No turn restrictions or anything.

I chose it because the wrapper let me choose a point and it split the
nearest edge and hooked up the point to that edge at the split.

Another reason I chose it was that it worked for the following situation:

          ----------\
         / \
        / \
A -----/ B
|_____________________/

Other algorithms would choose the upper edge because that is what was found
first as they tried to go from A to B. I was just learning about routing and
did not want to go figure out how to modify my network to split the long
path where there were multiple paths between nodes.

I've been following your work lately as I will be upgrading our situation to
Postgres 9 and PostGIS 2 at some point. I was waiting for you to get things
settled out before asking which algorithm I should look at to replace
shootingstar.

Thanks for your work on this project.

Worth Lutz

-----Original Message-----
From: pgrouting-dev-bounces@lists.osgeo.org
[mailto:pgrouting-dev-bounces@lists.osgeo.org] On Behalf Of Stephen
Woodbridge
Sent: Saturday, May 11, 2013 4:21 PM
To: pgRouting Users List; pgRouting Dev List
Subject: [pgrouting-dev] How many people use the wrapper functions?

Hi all,

Daniel and I have been wondering if people use the wrapper function
versus the core functions directly? Or if you have written your own
wrapper functions? etc.

The core functions are the low level function that directly call the
internal library functions.

The wrapper functions are all the additional plpgsql convenience
functions that generate more complex SQL queries and then call the core
functions.

I know that I never use the wrapper functions because I found them to
messy and inconsistent and have hard coded values in them, etc. So I
wrote my own high level wrapper functions that made it easy for me to
work with the core functions.

So I thought it would be wise to ask our users what they use? and how
they use pgRouting, so we do not may a decision like "Throw out the
wrapper functions" without some input from the user community.

PLEASE TAKE ACTION and let us know!

Thanks,
   -Steve
_______________________________________________
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
-----
No virus found in this message.
Checked by AVG - www.avg.com
Version: 2013.0.3336 / Virus Database: 3162/6317 - Release Date: 05/11/13

4

Hi Worth,

Thank you for the feedback. It is really important the people speak up on this because our current thinking is that we will probably take most of the wrapper functions and dump them into a depreciated pgrouting-legacy.sql file that will get copied to the server, but not installed when you CREATE EXTENSION pgrouting;

I have talked with Daniel about improving the documentation and may be adding a chapter that explains how to write your own wrapper function. Our thought is that if we had fewer functions that were better documented that it would be easier for people to make sense of how to use from the beginning.

Regarding shooting star, you should just start using TRSP. In fact it has the ability to specify an edge and a percentage along the edge for the start and end locations. It also about 5 times faster than shooting start.

With regards to the parallel edge problem. We have this in dijkstra and astar and it is on my list of things to fix before the release. I am not sure if trsp has this or not, but if you can make a test for it I would be interested in the results.

Thanks,
   -Steve

On 5/11/2013 7:51 PM, Worth Lutz wrote:

Hi Steve,

I used one of the wrappers, shootingstar_sp_smart I think, but had to modify
it due to problems. I think that it is the one which uses shooting star
which I've since heard doesn't work.

I think that it works for us as all we are using is length as cost to find
the length from a to b. No turn restrictions or anything.

I chose it because the wrapper let me choose a point and it split the
nearest edge and hooked up the point to that edge at the split.

Another reason I chose it was that it worked for the following situation:

           ----------\
          / \
         / \
A -----/ B
|_____________________/

Other algorithms would choose the upper edge because that is what was found
first as they tried to go from A to B. I was just learning about routing and
did not want to go figure out how to modify my network to split the long
path where there were multiple paths between nodes.

I've been following your work lately as I will be upgrading our situation to
Postgres 9 and PostGIS 2 at some point. I was waiting for you to get things
settled out before asking which algorithm I should look at to replace
shootingstar.

Thanks for your work on this project.

Worth Lutz

-----Original Message-----
From: pgrouting-dev-bounces@lists.osgeo.org
[mailto:pgrouting-dev-bounces@lists.osgeo.org] On Behalf Of Stephen
Woodbridge
Sent: Saturday, May 11, 2013 4:21 PM
To: pgRouting Users List; pgRouting Dev List
Subject: [pgrouting-dev] How many people use the wrapper functions?

Hi all,

Daniel and I have been wondering if people use the wrapper function
versus the core functions directly? Or if you have written your own
wrapper functions? etc.

The core functions are the low level function that directly call the
internal library functions.

The wrapper functions are all the additional plpgsql convenience
functions that generate more complex SQL queries and then call the core
functions.

I know that I never use the wrapper functions because I found them to
messy and inconsistent and have hard coded values in them, etc. So I
wrote my own high level wrapper functions that made it easy for me to
work with the core functions.

So I thought it would be wise to ask our users what they use? and how
they use pgRouting, so we do not may a decision like "Throw out the
wrapper functions" without some input from the user community.

PLEASE TAKE ACTION and let us know!

Thanks,
    -Steve
_______________________________________________
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
-----
No virus found in this message.
Checked by AVG - www.avg.com
Version: 2013.0.3336 / Virus Database: 3162/6317 - Release Date: 05/11/13

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

5

Hi Pavel,

Thanks you for your feedback. This is exactly why we are thinking about thinning down the list of function. The history on this was that these were originally written to explain how to use the core functions efficiently but the problem is that there are only examples and they really don't fit well to most peoples use cases. I believe (maybe erroneously) that most users have taken one or two of the wrappers and modified them for their own use cases.

One of the things that we will also be working on is a new tutorial based on the new algorithms and we hope to address some of these educational issues in that also.

Thanks again for your feedback.

I look forward to hearing from others on either side of these issues.

Thanks,
   -Steve

On 5/11/2013 4:54 PM, Pavel Iacovlev wrote:

I don't, probably for the same reasons, if you need to use/swap
multiple algorithms using wrapper functions can get really tricky.

With the amount of helper functions current available (astar example)
astar_sp
astar_sp_bbox
astar_sp_bbox_directed
astar_sp_delta
astar_sp_delta_cc
astar_sp_delta_cc_directed
astar_sp_delta_directed
astar_sp_directed
it's just easier to lean the API, and there are great examples in the
workshop to do so.

On Sat, May 11, 2013 at 11:20 PM, Stephen Woodbridge
<woodbri@swoodbridge.com <mailto:woodbri@swoodbridge.com>> wrote:

    Hi all,

    Daniel and I have been wondering if people use the wrapper function
    versus the core functions directly? Or if you have written your own
    wrapper functions? etc.

    The core functions are the low level function that directly call the
    internal library functions.

    The wrapper functions are all the additional plpgsql convenience
    functions that generate more complex SQL queries and then call the
    core functions.

    I know that I never use the wrapper functions because I found them
    to messy and inconsistent and have hard coded values in them, etc.
    So I wrote my own high level wrapper functions that made it easy for
    me to work with the core functions.

    So I thought it would be wise to ask our users what they use? and
    how they use pgRouting, so we do not may a decision like "Throw out
    the wrapper functions" without some input from the user community.

    PLEASE TAKE ACTION and let us know!

    Thanks,
       -Steve
    _________________________________________________
    Pgrouting-users mailing list
    Pgrouting-users@lists.osgeo.__org
    <mailto:Pgrouting-users@lists.osgeo.org>
    http://lists.osgeo.org/__mailman/listinfo/pgrouting-__users
    <http://lists.osgeo.org/mailman/listinfo/pgrouting-users&gt;

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

6

Steve,

Thanks for the suggestion on TSRP. I'll look at it as soon as I finish my
current project.

I'll like to add that I learned to write PL/pgSQl from reading the pgRouting
wrappers. I usually write in PHP but find that moving stuff to SQL and
PL/pgSQl can simplify my application. At least once I figure out the
intricacies of the particular query.

Having the wrapper examples is helpful to someone learning. I found that you
have to figure out how they work though because as you pointed out there
were problems and hard-coded stuff which may cause problems. I had a type
problem when I was figuring out my application.

Simple wrappers as examples to explain to someone how to set up their own
wrapper are helpful.

Worth

-----Original Message-----
From: pgrouting-dev-bounces@lists.osgeo.org
[mailto:pgrouting-dev-bounces@lists.osgeo.org] On Behalf Of Stephen
Woodbridge
Sent: Saturday, May 11, 2013 10:00 PM
To: pgRouting developers mailing list
Subject: Re: [pgrouting-dev] How many people use the wrapper functions?

Hi Worth,

Thank you for the feedback. It is really important the people speak up
on this because our current thinking is that we will probably take most
of the wrapper functions and dump them into a depreciated
pgrouting-legacy.sql file that will get copied to the server, but not
installed when you CREATE EXTENSION pgrouting;

I have talked with Daniel about improving the documentation and may be
adding a chapter that explains how to write your own wrapper function.
Our thought is that if we had fewer functions that were better
documented that it would be easier for people to make sense of how to
use from the beginning.

Regarding shooting star, you should just start using TRSP. In fact it
has the ability to specify an edge and a percentage along the edge for
the start and end locations. It also about 5 times faster than shooting
start.

With regards to the parallel edge problem. We have this in dijkstra and
astar and it is on my list of things to fix before the release. I am not
sure if trsp has this or not, but if you can make a test for it I would
be interested in the results.

Thanks,
   -Steve

On 5/11/2013 7:51 PM, Worth Lutz wrote:

Hi Steve,

I used one of the wrappers, shootingstar_sp_smart I think, but had to

modify

it due to problems. I think that it is the one which uses shooting star
which I've since heard doesn't work.

I think that it works for us as all we are using is length as cost to find
the length from a to b. No turn restrictions or anything.

I chose it because the wrapper let me choose a point and it split the
nearest edge and hooked up the point to that edge at the split.

Another reason I chose it was that it worked for the following situation:

           ----------\
          / \
         / \
A -----/ B
|_____________________/

Other algorithms would choose the upper edge because that is what was

found

first as they tried to go from A to B. I was just learning about routing

and

did not want to go figure out how to modify my network to split the long
path where there were multiple paths between nodes.

I've been following your work lately as I will be upgrading our situation

to

Postgres 9 and PostGIS 2 at some point. I was waiting for you to get

things

settled out before asking which algorithm I should look at to replace
shootingstar.

Thanks for your work on this project.

Worth Lutz

-----Original Message-----
From: pgrouting-dev-bounces@lists.osgeo.org
[mailto:pgrouting-dev-bounces@lists.osgeo.org] On Behalf Of Stephen
Woodbridge
Sent: Saturday, May 11, 2013 4:21 PM
To: pgRouting Users List; pgRouting Dev List
Subject: [pgrouting-dev] How many people use the wrapper functions?

Hi all,

Daniel and I have been wondering if people use the wrapper function
versus the core functions directly? Or if you have written your own
wrapper functions? etc.

The core functions are the low level function that directly call the
internal library functions.

The wrapper functions are all the additional plpgsql convenience
functions that generate more complex SQL queries and then call the core
functions.

I know that I never use the wrapper functions because I found them to
messy and inconsistent and have hard coded values in them, etc. So I
wrote my own high level wrapper functions that made it easy for me to
work with the core functions.

So I thought it would be wise to ask our users what they use? and how
they use pgRouting, so we do not may a decision like "Throw out the
wrapper functions" without some input from the user community.

PLEASE TAKE ACTION and let us know!

Thanks,
    -Steve
_______________________________________________
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
-----
No virus found in this message.
Checked by AVG - www.avg.com
Version: 2013.0.3336 / Virus Database: 3162/6317 - Release Date: 05/11/13

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

_______________________________________________
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
-----
No virus found in this message.
Checked by AVG - www.avg.com
Version: 2013.0.3336 / Virus Database: 3162/6317 - Release Date: 05/11/13

7

Worth,

Thanks, this is good to know and validates our thoughts on the need for a chapter in the doc on how to write wrapper functions.

I write a lot code in plpgsql for the same reasons. It also tends to be much faster to process stuff in the database. I write trivial 10-20 lines PHP scripts the do nothing more than:

1. take user input
2. connect to the database
3. issue a query to a stored procedure
4. format the results as XML or JSON

to then access these functions from web clients and other client scripts and programs.

We actually will be adding some new plpgsql function as part of 2.0 for example you might find these interesting:

pgr_analyzeGraph - analyze a topology and mark dead ends
pgr_analyzeOneway - analyze a topology and look for impossible oneways
pgr_nodeNetwork - utility that will node all intersections

Those can be useful determining issues with a road network that might cause problems when routing and nodeNetwork is a tool to potentally solve one class of problem where the road segments are not split at intersections.

pgr_isColumnInTable - utility to see if a column exists in a table
pgr_isColumnIndexed - utility to see if a column is indexed

And I'm sure there will be a few others as the release progresses.

Thanks,
   -Steve

On 5/12/2013 7:52 AM, Worth Lutz wrote:

Steve,

Thanks for the suggestion on TSRP. I'll look at it as soon as I finish my
current project.

I'll like to add that I learned to write PL/pgSQl from reading the pgRouting
wrappers. I usually write in PHP but find that moving stuff to SQL and
PL/pgSQl can simplify my application. At least once I figure out the
intricacies of the particular query.

Having the wrapper examples is helpful to someone learning. I found that you
have to figure out how they work though because as you pointed out there
were problems and hard-coded stuff which may cause problems. I had a type
problem when I was figuring out my application.

Simple wrappers as examples to explain to someone how to set up their own
wrapper are helpful.

Worth

-----Original Message-----
From: pgrouting-dev-bounces@lists.osgeo.org
[mailto:pgrouting-dev-bounces@lists.osgeo.org] On Behalf Of Stephen
Woodbridge
Sent: Saturday, May 11, 2013 10:00 PM
To: pgRouting developers mailing list
Subject: Re: [pgrouting-dev] How many people use the wrapper functions?

Hi Worth,

Thank you for the feedback. It is really important the people speak up
on this because our current thinking is that we will probably take most
of the wrapper functions and dump them into a depreciated
pgrouting-legacy.sql file that will get copied to the server, but not
installed when you CREATE EXTENSION pgrouting;

I have talked with Daniel about improving the documentation and may be
adding a chapter that explains how to write your own wrapper function.
Our thought is that if we had fewer functions that were better
documented that it would be easier for people to make sense of how to
use from the beginning.

Regarding shooting star, you should just start using TRSP. In fact it
has the ability to specify an edge and a percentage along the edge for
the start and end locations. It also about 5 times faster than shooting
start.

With regards to the parallel edge problem. We have this in dijkstra and
astar and it is on my list of things to fix before the release. I am not
sure if trsp has this or not, but if you can make a test for it I would
be interested in the results.

Thanks,
    -Steve

On 5/11/2013 7:51 PM, Worth Lutz wrote:

Hi Steve,

I used one of the wrappers, shootingstar_sp_smart I think, but had to

modify

it due to problems. I think that it is the one which uses shooting star
which I've since heard doesn't work.

I think that it works for us as all we are using is length as cost to find
the length from a to b. No turn restrictions or anything.

I chose it because the wrapper let me choose a point and it split the
nearest edge and hooked up the point to that edge at the split.

Another reason I chose it was that it worked for the following situation:

            ----------\
           / \
          / \
A -----/ B
|_____________________/

Other algorithms would choose the upper edge because that is what was

found

first as they tried to go from A to B. I was just learning about routing

and

did not want to go figure out how to modify my network to split the long
path where there were multiple paths between nodes.

I've been following your work lately as I will be upgrading our situation

to

Postgres 9 and PostGIS 2 at some point. I was waiting for you to get

things

settled out before asking which algorithm I should look at to replace
shootingstar.

Thanks for your work on this project.

Worth Lutz

-----Original Message-----
From: pgrouting-dev-bounces@lists.osgeo.org
[mailto:pgrouting-dev-bounces@lists.osgeo.org] On Behalf Of Stephen
Woodbridge
Sent: Saturday, May 11, 2013 4:21 PM
To: pgRouting Users List; pgRouting Dev List
Subject: [pgrouting-dev] How many people use the wrapper functions?

Hi all,

Daniel and I have been wondering if people use the wrapper function
versus the core functions directly? Or if you have written your own
wrapper functions? etc.

The core functions are the low level function that directly call the
internal library functions.

The wrapper functions are all the additional plpgsql convenience
functions that generate more complex SQL queries and then call the core
functions.

I know that I never use the wrapper functions because I found them to
messy and inconsistent and have hard coded values in them, etc. So I
wrote my own high level wrapper functions that made it easy for me to
work with the core functions.

So I thought it would be wise to ask our users what they use? and how
they use pgRouting, so we do not may a decision like "Throw out the
wrapper functions" without some input from the user community.

PLEASE TAKE ACTION and let us know!

Thanks,
     -Steve
_______________________________________________
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
-----
No virus found in this message.
Checked by AVG - www.avg.com
Version: 2013.0.3336 / Virus Database: 3162/6317 - Release Date: 05/11/13

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

_______________________________________________
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
-----
No virus found in this message.
Checked by AVG - www.avg.com
Version: 2013.0.3336 / Virus Database: 3162/6317 - Release Date: 05/11/13

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

8

Hi everybody,
thank you very much for the work you are doing with pgrouting. I can’t wait for the upcoming 2.0.

My experience with the wrapper functions is fairly identical to Worth Lutz:
I’m also using one of the ‘smart’ wrapper functions that enable edge to edge with the A* algorithm. I also chose just because the wrapper let me choose a point and it split the nearest edge for routing. I heavily modified the wrapper to provide all the fields I need from the edges table, to join it with other tables, to return the edges in the correct order and to reverse the two-way edges that were used in the opposite direction.
I also thank you for the suggestion to look into TRSP, I’ve been wanting to reevaluate the different algorithms once the GSOC get merged (if they will), and TRSP seems like a good match, even if I don’t actually use turn restrictions. (OT: Any idea on the performance in relation to bidirectional A* and two_q?)

I also learned what I know of PL/pgSQL by modifying the wrappers and I would have had a really hard time implementing the ‘edge splitting’ on my own. So I’m really grateful I found the wrappers. On the other hand the wrapper I used wasn’t even included in pgrouting, so I guess we’d be safe to have them outside the distribution, either in the docs or as an external download.
On the other hand it would be great to have some solutions for the fairly common request to have the result of the routing returned with a ‘order_id’ to be able to join it easily without losing order information (see http://lists.osgeo.org/pipermail/pgrouting-dev/2013-May/000924.html) and to reverse the edges that have been visited in reverse (to be able to draw them, etc.). I don’t know where this fits best, if in a basic wrapper to be customized, or in the core functions themselves.

Thanks again for you work.

Marco Quaggiotto (bikedistrict.org)

···

On Sun, May 12, 2013 at 3:41 PM, Stephen Woodbridge <woodbri@swoodbridge.com> wrote:

Worth,

Thanks, this is good to know and validates our thoughts on the need for a chapter in the doc on how to write wrapper functions.

I write a lot code in plpgsql for the same reasons. It also tends to be much faster to process stuff in the database. I write trivial 10-20 lines PHP scripts the do nothing more than:

  1. take user input
  2. connect to the database
  3. issue a query to a stored procedure
  4. format the results as XML or JSON

to then access these functions from web clients and other client scripts and programs.

We actually will be adding some new plpgsql function as part of 2.0 for example you might find these interesting:

pgr_analyzeGraph - analyze a topology and mark dead ends
pgr_analyzeOneway - analyze a topology and look for impossible oneways
pgr_nodeNetwork - utility that will node all intersections

Those can be useful determining issues with a road network that might cause problems when routing and nodeNetwork is a tool to potentally solve one class of problem where the road segments are not split at intersections.

pgr_isColumnInTable - utility to see if a column exists in a table
pgr_isColumnIndexed - utility to see if a column is indexed

And I’m sure there will be a few others as the release progresses.

Thanks,
-Steve

On 5/12/2013 7:52 AM, Worth Lutz wrote:

Steve,

Thanks for the suggestion on TSRP. I’ll look at it as soon as I finish my
current project.

I’ll like to add that I learned to write PL/pgSQl from reading the pgRouting
wrappers. I usually write in PHP but find that moving stuff to SQL and
PL/pgSQl can simplify my application. At least once I figure out the
intricacies of the particular query.

Having the wrapper examples is helpful to someone learning. I found that you
have to figure out how they work though because as you pointed out there
were problems and hard-coded stuff which may cause problems. I had a type
problem when I was figuring out my application.

Simple wrappers as examples to explain to someone how to set up their own
wrapper are helpful.

Worth

-----Original Message-----
From: pgrouting-dev-bounces@lists.osgeo.org
[mailto:pgrouting-dev-bounces@lists.osgeo.org] On Behalf Of Stephen
Woodbridge
Sent: Saturday, May 11, 2013 10:00 PM
To: pgRouting developers mailing list
Subject: Re: [pgrouting-dev] How many people use the wrapper functions?

Hi Worth,

Thank you for the feedback. It is really important the people speak up
on this because our current thinking is that we will probably take most
of the wrapper functions and dump them into a depreciated
pgrouting-legacy.sql file that will get copied to the server, but not
installed when you CREATE EXTENSION pgrouting;

I have talked with Daniel about improving the documentation and may be
adding a chapter that explains how to write your own wrapper function.
Our thought is that if we had fewer functions that were better
documented that it would be easier for people to make sense of how to
use from the beginning.

Regarding shooting star, you should just start using TRSP. In fact it
has the ability to specify an edge and a percentage along the edge for
the start and end locations. It also about 5 times faster than shooting
start.

With regards to the parallel edge problem. We have this in dijkstra and
astar and it is on my list of things to fix before the release. I am not
sure if trsp has this or not, but if you can make a test for it I would
be interested in the results.

Thanks,
-Steve

On 5/11/2013 7:51 PM, Worth Lutz wrote:

Hi Steve,

I used one of the wrappers, shootingstar_sp_smart I think, but had to

modify

it due to problems. I think that it is the one which uses shooting star
which I’ve since heard doesn’t work.

I think that it works for us as all we are using is length as cost to find
the length from a to b. No turn restrictions or anything.

I chose it because the wrapper let me choose a point and it split the
nearest edge and hooked up the point to that edge at the split.

Another reason I chose it was that it worked for the following situation:

----------
/
/
A -----/ B
|_____________________/

Other algorithms would choose the upper edge because that is what was

found

first as they tried to go from A to B. I was just learning about routing

and

did not want to go figure out how to modify my network to split the long
path where there were multiple paths between nodes.

I’ve been following your work lately as I will be upgrading our situation

to

Postgres 9 and PostGIS 2 at some point. I was waiting for you to get

things

settled out before asking which algorithm I should look at to replace
shootingstar.

Thanks for your work on this project.

Worth Lutz

-----Original Message-----
From: pgrouting-dev-bounces@lists.osgeo.org
[mailto:pgrouting-dev-bounces@lists.osgeo.org] On Behalf Of Stephen
Woodbridge
Sent: Saturday, May 11, 2013 4:21 PM
To: pgRouting Users List; pgRouting Dev List
Subject: [pgrouting-dev] How many people use the wrapper functions?

Hi all,

Daniel and I have been wondering if people use the wrapper function
versus the core functions directly? Or if you have written your own
wrapper functions? etc.

The core functions are the low level function that directly call the
internal library functions.

The wrapper functions are all the additional plpgsql convenience
functions that generate more complex SQL queries and then call the core
functions.

I know that I never use the wrapper functions because I found them to
messy and inconsistent and have hard coded values in them, etc. So I
wrote my own high level wrapper functions that made it easy for me to
work with the core functions.

So I thought it would be wise to ask our users what they use? and how
they use pgRouting, so we do not may a decision like “Throw out the
wrapper functions” without some input from the user community.

PLEASE TAKE ACTION and let us know!

Thanks,
-Steve

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

No virus found in this message.
Checked by AVG - www.avg.com
Version: 2013.0.3336 / Virus Database: 3162/6317 - Release Date: 05/11/13

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

No virus found in this message.
Checked by AVG - www.avg.com
Version: 2013.0.3336 / Virus Database: 3162/6317 - Release Date: 05/11/13

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

9

On 5/13/2013 6:17 AM, Marco Quaggiotto wrote:

Hi everybody,
thank you very much for the work you are doing with pgrouting. I can't
wait for the upcoming 2.0.

My experience with the wrapper functions is fairly identical to Worth Lutz:
I'm also using one of the 'smart' wrapper functions that enable edge to
edge with the A* algorithm. I also chose just because the wrapper let me
choose a point and it split the nearest edge for routing. I heavily
modified the wrapper to provide all the fields I need from the edges
table, to join it with other tables, to return the edges in the correct
order and to reverse the two-way edges that were used in the opposite
direction.
I also thank you for the suggestion to look into TRSP, I've been wanting
to reevaluate the different algorithms once the GSOC get merged (if they
will), and TRSP seems like a good match, even if I don't actually use
turn restrictions. (OT: Any idea on the performance in relation to
bidirectional A* and two_q?)

This code is now available in the release branch I would be interesting to get some feedback on the relative performance of the various algorithms. I have not integrated two_q, because while it worked fine, it did not improve performance over the existing algorithms. I would be happy to have someone redo this and any other tests and report back on their findings.

When we developed trsp, I compared it to dijkstra, astar, and shooting star and for point to point routes they fell into the following performance ratings:

1. astar
2. trsp
3. dijkstra
4. shootingstar

The first three were all very close together and shootingstar was about 5x slower.

This was without using turn restrictions. But you should also know that of the cost to generate a route, over 50% of the time in most cases is related to just loading the edges and building a graph. The solving of the graph is fast in most cases.

I also learned what I know of PL/pgSQL by modifying the wrappers and I
would have had a really hard time implementing the 'edge splitting' on
my own. So I'm really grateful I found the wrappers. On the other hand
the wrapper I used wasn't even included in pgrouting, so I guess we'd be
safe to have them outside the distribution, either in the docs or as an
external download.

Daniel and I have discussed adding a contrib directory, but then we get a lot of stuff, that we don't know if it work with the current release. I think we would be more inclined to have a wiki page that links to 3rd party github projects or have a tips and tricks wiki page. The ideal situation is that we link to a page the you maintain because that de-clutters the pgrouting maintained pages and files.

On the other hand it would be great to have some solutions for the
fairly common request to have the result of the routing returned with a
'order_id' to be able to join it easily without losing order information
(see
http://lists.osgeo.org/pipermail/pgrouting-dev/2013-May/000924.html) and
to reverse the edges that have been visited in reverse (to be able to
draw them, etc.). I don't know where this fits best, if in a basic
wrapper to be customized, or in the core functions themselves.

Yeah, Daniel raised this to me also. It can be done and it is not had to do it is just a lot of work because:

1. all the C api code needs a minor change
2. all the types, and C wrappers need to be updated
3. all the docs need to be updated
4. all the test results need to be updated

So basically I have to touch 90% of the files. That said, I am still thinking about potentially doing this and abstracting our types. I turns out that we only have two major types:

seq | id1 | id2 | cost
seq | id1 | id2 | geom

This would greatly simplify things and it would be up to the algorithm to decide what is put into id1 and id2, these could be node_id or edge_id or a mix.

So I could make this change and add the seq number all at the same time. I'll see if I can work this in, but no promises.

Thank you for your feedback.

-Steve

Thanks again for you work.

Marco Quaggiotto (bikedistrict.org <http://bikedistrict.org>)

On Sun, May 12, 2013 at 3:41 PM, Stephen Woodbridge
<woodbri@swoodbridge.com <mailto:woodbri@swoodbridge.com>> wrote:

    Worth,

    Thanks, this is good to know and validates our thoughts on the need
    for a chapter in the doc on how to write wrapper functions.

    I write a lot code in plpgsql for the same reasons. It also tends to
    be much faster to process stuff in the database. I write trivial
    10-20 lines PHP scripts the do nothing more than:

    1. take user input
    2. connect to the database
    3. issue a query to a stored procedure
    4. format the results as XML or JSON

    to then access these functions from web clients and other client
    scripts and programs.

    We actually will be adding some new plpgsql function as part of 2.0
    for example you might find these interesting:

    pgr_analyzeGraph - analyze a topology and mark dead ends
    pgr_analyzeOneway - analyze a topology and look for impossible oneways
    pgr_nodeNetwork - utility that will node all intersections

    Those can be useful determining issues with a road network that
    might cause problems when routing and nodeNetwork is a tool to
    potentally solve one class of problem where the road segments are
    not split at intersections.

    pgr_isColumnInTable - utility to see if a column exists in a table
    pgr_isColumnIndexed - utility to see if a column is indexed

    And I'm sure there will be a few others as the release progresses.

    Thanks,
       -Steve

    On 5/12/2013 7:52 AM, Worth Lutz wrote:

        Steve,

        Thanks for the suggestion on TSRP. I'll look at it as soon as I
        finish my
        current project.

        I'll like to add that I learned to write PL/pgSQl from reading
        the pgRouting
        wrappers. I usually write in PHP but find that moving stuff to
        SQL and
        PL/pgSQl can simplify my application. At least once I figure out the
        intricacies of the particular query.

        Having the wrapper examples is helpful to someone learning. I
        found that you
        have to figure out how they work though because as you pointed
        out there
        were problems and hard-coded stuff which may cause problems. I
        had a type
        problem when I was figuring out my application.

        Simple wrappers as examples to explain to someone how to set up
        their own
        wrapper are helpful.

        Worth

        -----Original Message-----
        From: pgrouting-dev-bounces@lists.__osgeo.org
        <mailto:pgrouting-dev-bounces@lists.osgeo.org>
        [mailto:pgrouting-dev-bounces@__lists.osgeo.org
        <mailto:pgrouting-dev-bounces@lists.osgeo.org>] On Behalf Of Stephen
        Woodbridge
        Sent: Saturday, May 11, 2013 10:00 PM
        To: pgRouting developers mailing list
        Subject: Re: [pgrouting-dev] How many people use the wrapper
        functions?

        Hi Worth,

        Thank you for the feedback. It is really important the people
        speak up
        on this because our current thinking is that we will probably
        take most
        of the wrapper functions and dump them into a depreciated
        pgrouting-legacy.sql file that will get copied to the server,
        but not
        installed when you CREATE EXTENSION pgrouting;

        I have talked with Daniel about improving the documentation and
        may be
        adding a chapter that explains how to write your own wrapper
        function.
        Our thought is that if we had fewer functions that were better
        documented that it would be easier for people to make sense of
        how to
        use from the beginning.

        Regarding shooting star, you should just start using TRSP. In
        fact it
        has the ability to specify an edge and a percentage along the
        edge for
        the start and end locations. It also about 5 times faster than
        shooting
        start.

        With regards to the parallel edge problem. We have this in
        dijkstra and
        astar and it is on my list of things to fix before the release.
        I am not
        sure if trsp has this or not, but if you can make a test for it
        I would
        be interested in the results.

        Thanks,
             -Steve

        On 5/11/2013 7:51 PM, Worth Lutz wrote:

            Hi Steve,

            I used one of the wrappers, shootingstar_sp_smart I think,
            but had to

        modify

            it due to problems. I think that it is the one which uses
            shooting star
            which I've since heard doesn't work.

            I think that it works for us as all we are using is length
            as cost to find
            the length from a to b. No turn restrictions or anything.

            I chose it because the wrapper let me choose a point and it
            split the
            nearest edge and hooked up the point to that edge at the split.

            Another reason I chose it was that it worked for the
            following situation:

                         ----------\
                        / \
                       / \
            A -----/ B
            |_____________________/

            Other algorithms would choose the upper edge because that is
            what was

        found

            first as they tried to go from A to B. I was just learning
            about routing

        and

            did not want to go figure out how to modify my network to
            split the long
            path where there were multiple paths between nodes.

            I've been following your work lately as I will be upgrading
            our situation

        to

            Postgres 9 and PostGIS 2 at some point. I was waiting for
            you to get

        things

            settled out before asking which algorithm I should look at
            to replace
            shootingstar.

            Thanks for your work on this project.

            Worth Lutz

            -----Original Message-----
            From: pgrouting-dev-bounces@lists.__osgeo.org
            <mailto:pgrouting-dev-bounces@lists.osgeo.org>
            [mailto:pgrouting-dev-bounces@__lists.osgeo.org
            <mailto:pgrouting-dev-bounces@lists.osgeo.org>] On Behalf Of
            Stephen
            Woodbridge
            Sent: Saturday, May 11, 2013 4:21 PM
            To: pgRouting Users List; pgRouting Dev List
            Subject: [pgrouting-dev] How many people use the wrapper
            functions?

            Hi all,

            Daniel and I have been wondering if people use the wrapper
            function
            versus the core functions directly? Or if you have written
            your own
            wrapper functions? etc.

            The core functions are the low level function that directly
            call the
            internal library functions.

            The wrapper functions are all the additional plpgsql convenience
            functions that generate more complex SQL queries and then
            call the core
            functions.

            I know that I never use the wrapper functions because I
            found them to
            messy and inconsistent and have hard coded values in them,
            etc. So I
            wrote my own high level wrapper functions that made it easy
            for me to
            work with the core functions.

            So I thought it would be wise to ask our users what they
            use? and how
            they use pgRouting, so we do not may a decision like "Throw
            out the
            wrapper functions" without some input from the user community.

            PLEASE TAKE ACTION and let us know!

            Thanks,
                  -Steve
            _________________________________________________
            pgrouting-dev mailing list
            pgrouting-dev@lists.osgeo.org
            <mailto:pgrouting-dev@lists.osgeo.org>
            http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
            <http://lists.osgeo.org/mailman/listinfo/pgrouting-dev&gt;
            -----
            No virus found in this message.
            Checked by AVG - www.avg.com <http://www.avg.com>
            Version: 2013.0.3336 / Virus Database: 3162/6317 - Release
            Date: 05/11/13

            _________________________________________________
            pgrouting-dev mailing list
            pgrouting-dev@lists.osgeo.org
            <mailto:pgrouting-dev@lists.osgeo.org>
            http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
            <http://lists.osgeo.org/mailman/listinfo/pgrouting-dev&gt;

        _________________________________________________
        pgrouting-dev mailing list
        pgrouting-dev@lists.osgeo.org <mailto:pgrouting-dev@lists.osgeo.org>
        http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
        <http://lists.osgeo.org/mailman/listinfo/pgrouting-dev&gt;
        -----
        No virus found in this message.
        Checked by AVG - www.avg.com <http://www.avg.com>
        Version: 2013.0.3336 / Virus Database: 3162/6317 - Release Date:
        05/11/13

        _________________________________________________
        pgrouting-dev mailing list
        pgrouting-dev@lists.osgeo.org <mailto:pgrouting-dev@lists.osgeo.org>
        http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
        <http://lists.osgeo.org/mailman/listinfo/pgrouting-dev&gt;

    _________________________________________________
    pgrouting-dev mailing list
    pgrouting-dev@lists.osgeo.org <mailto:pgrouting-dev@lists.osgeo.org>
    http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
    <http://lists.osgeo.org/mailman/listinfo/pgrouting-dev&gt;

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

10

On 5/11/2013 1:20 PM, Stephen Woodbridge wrote:

Daniel and I have been wondering if people use the wrapper function
versus the core functions directly? Or if you have written your own
wrapper functions? etc.

We use the astar wrapper functions.

There are a few hardcoded things, such as the geometry column being the_geom, but naming our columns to fit really saved us a lot of time over my reinventing that same stuff.

If you do get rid of them, please update the docs to point to them with a note as to "this wrapper function will do A*, swap in your columns for geometry name and cost, and you're off to a good start"

--
Greg Allensworth, Web GIS Developer
BS A+ Network+ Security+ Linux+ Server+
GreenInfo Network - Information and Mapping in the Public Interest
564 Market Street, Suite 510 San Francisco CA 94104
PH: 415-979-0343 x302 FX: 415-979-0371 email: gregor@greeninfo.org
Web: www.GreenInfo.org www.MapsPortal.org

Subscribe to MapLines, our e-newsletter, at www.GreenInfo.org

11

I also learned what I know of PL/pgSQL by modifying the wrappers and I

would have had a really hard time implementing the 'edge splitting' on
my own. So I'm really grateful I found the wrappers. On the other hand
the wrapper I used wasn't even included in pgrouting, so I guess we'd be
safe to have them outside the distribution, either in the docs or as an
external download.

Daniel and I have discussed adding a contrib directory, but then we get a
lot of stuff, that we don't know if it work with the current release. I
think we would be more inclined to have a wiki page that links to 3rd party
github projects or have a tips and tricks wiki page. The ideal situation is
that we link to a page the you maintain because that de-clutters the
pgrouting maintained pages and files.

The idea of the "pgrouting-contrib" repository was to provide a place for a
collection of user-contributed wrapper functions.
But as you can see, the repository has been mostly inactive and there was
no second wrapper added ever to the initial one.
So this was probably not a smart way to solve this :wink:

Github Wiki pages are also somehow difficult to organize.
Maybe Gist (https://gist.github.com/) + list on a Wiki page would be better
... but in the end it's important that someone is willing to share his code.

I don't want to maintain the current (arbitrary) wrapper functions just to
have some examples, but I know that it is difficult to find good resources
about writing in pl/pgsql, and it's usually best to learn from good
examples.
Right now I think that having some useful recipes and code snippets in the
documentation would be best. And we could start the list of "Gists" with a
few good wrapper examples, and then hope that more people will contribute
with even better examples.

Daniel

--
Georepublic UG & Georepublic Japan
eMail: daniel.kastl@georepublic.de
Web: http://georepublic.de

12

I think that the "Gists" idea is a good one. I like the idea of having some
simple wrapper examples which demonstrate a concept. They do not have to be
the solution to everyone's problem.

An example of this would be the method demonstrated in the "only" wrapper in
the "pgrouting-contrib" directory: How to split the nearest edge to a point
and route from the point to the split point and then to the same situation
at the other end.

I'm sure there are other simple concepts which could be demonstrated in a
similar fashion.

Worth

  _____

From: pgrouting-dev-bounces@lists.osgeo.org
[mailto:pgrouting-dev-bounces@lists.osgeo.org] On Behalf Of Daniel Kastl
Sent: Monday, May 13, 2013 12:46 PM
To: pgRouting developers mailing list
Subject: Re: [pgrouting-dev] How many people use the wrapper functions?

I also learned what I know of PL/pgSQL by modifying the wrappers and I
would have had a really hard time implementing the 'edge splitting' on
my own. So I'm really grateful I found the wrappers. On the other hand
the wrapper I used wasn't even included in pgrouting, so I guess we'd be
safe to have them outside the distribution, either in the docs or as an
external download.

Daniel and I have discussed adding a contrib directory, but then we get a
lot of stuff, that we don't know if it work with the current release. I
think we would be more inclined to have a wiki page that links to 3rd party
github projects or have a tips and tricks wiki page. The ideal situation is
that we link to a page the you maintain because that de-clutters the
pgrouting maintained pages and files.

The idea of the "pgrouting-contrib" repository was to provide a place for a
collection of user-contributed wrapper functions.

But as you can see, the repository has been mostly inactive and there was no
second wrapper added ever to the initial one.

So this was probably not a smart way to solve this :wink:

Github Wiki pages are also somehow difficult to organize.

Maybe Gist (https://gist.github.com/) + list on a Wiki page would be better
... but in the end it's important that someone is willing to share his code.

I don't want to maintain the current (arbitrary) wrapper functions just to
have some examples, but I know that it is difficult to find good resources
about writing in pl/pgsql, and it's usually best to learn from good
examples.

Right now I think that having some useful recipes and code snippets in the
documentation would be best. And we could start the list of "Gists" with a
few good wrapper examples, and then hope that more people will contribute
with even better examples.

Daniel

--
Georepublic UG & Georepublic Japan
eMail: <mailto:daniel.kastl@georepublic.de> daniel.kastl@georepublic.de
Web: <http://georepublic.de/&gt; http://georepublic.de

  _____

No virus found in this message.
Checked by AVG - www.avg.com
Version: 2013.0.3336 / Virus Database: 3162/6320 - Release Date: 05/13/13

13

On Tue, May 14, 2013 at 2:07 AM, Worth Lutz <wal3@mindspring.com> wrote:

** ** **

I think that the “Gists” idea is a good one. I like the idea of having
some simple wrapper examples which demonstrate a concept. They do not have
to be the solution to everyone’s problem.

The advantages Gists are:

   - they can be discussed (comments beneath the source)
   - they keep a reference to the author
   - they can be forked
   - no need to handle permissions for writing as it had to be for a
   "contrib" repository

So we could copy the current wrapper functions into Gists and then everyone
could help to make them better.

"Highlights" could then also be linked in the manual or used for the
tutorial.

You can already start:
https://github.com/pgRouting/pgrouting/wiki/Writing-functions :wink:

Daniel

****

** **

An example of this would be the method demonstrated in the “only” wrapper
in the “pgrouting-contrib” directory: How to split the nearest edge to a
point and route from the point to the split point and then to the same
situation at the other end.****

** **

I’m sure there are other simple concepts which could be demonstrated in a
similar fashion.****

** **

Worth****

** **
------------------------------

*From:* pgrouting-dev-bounces@lists.osgeo.org [mailto:
pgrouting-dev-bounces@lists.osgeo.org] *On Behalf Of *Daniel Kastl
*Sent:* Monday, May 13, 2013 12:46 PM

*To:* **pgRouting developers mailing list**
*Subject:* Re: [pgrouting-dev] How many people use the wrapper functions?
****

** **

** **

I also learned what I know of PL/pgSQL by modifying the wrappers and I

would have had a really hard time implementing the 'edge splitting' on
my own. So I'm really grateful I found the wrappers. On the other hand
the wrapper I used wasn't even included in pgrouting, so I guess we'd be
safe to have them outside the distribution, either in the docs or as an
external download.****

** **

Daniel and I have discussed adding a contrib directory, but then we get a
lot of stuff, that we don't know if it work with the current release. I
think we would be more inclined to have a wiki page that links to 3rd party
github projects or have a tips and tricks wiki page. The ideal situation is
that we link to a page the you maintain because that de-clutters the
pgrouting maintained pages and files.****

** **

The idea of the "pgrouting-contrib" repository was to provide a place for
a collection of user-contributed wrapper functions.****

But as you can see, the repository has been mostly inactive and there was
no second wrapper added ever to the initial one.****

So this was probably not a smart way to solve this ;-)****

** **

Github Wiki pages are also somehow difficult to organize. ****

Maybe Gist (https://gist.github.com/) + list on a Wiki page would be
better ... but in the end it's important that someone is willing to share
his code.****

** **

I don't want to maintain the current (arbitrary) wrapper functions just to
have some examples, but I know that it is difficult to find good resources
about writing in pl/pgsql, and it's usually best to learn from good
examples.****

Right now I think that having some useful recipes and code snippets in the
documentation would be best. And we could start the list of "Gists" with a
few good wrapper examples, and then hope that more people will contribute
with even better examples.****

** **

****

Daniel****

****

** **

--
Georepublic UG & Georepublic ****Japan****
eMail: daniel.kastl@georepublic.de
Web: http://georepublic.de ****
  ------------------------------

No virus found in this message.
Checked by AVG - www.avg.com
Version: 2013.0.3336 / Virus Database: 3162/6320 - Release Date: 05/13/13*
***

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

--
Georepublic UG & Georepublic Japan
eMail: daniel.kastl@georepublic.de
Web: http://georepublic.de

14

I having some problems with the tsp

I have a matrix {{0,31,22,42},{31,0,90,2},{22,90,0,27},{42,2,27,0}}, starting at node 2, I get the answer
seq | id
-----±—
0 | 2
1 | 3
2 | 1
3 | 0
(4 rows)
using the matrix

{{0,22,42,31},{22,0,27,90},{42,27,0,2},{31,90,2,0}} starting at node 4 I get the answer
seq | id
-----±—
0 | 0
1 | 1
2 | 2
3 | 3
The matrix is topological identicial, I start off at the same topological node, so I was expecting the same answer, also I was expecting all nodes to be in the result set ie nodes 1,2,3 and 4, for some strange reason I get 0.

Is there some mistake in my data?

regards

Dave.

15

Just looked at the write up for the tsp, ok the answer will be in the range 0-(X-1) where X is the number of points provided, the returned index starts of at zero in set as one as found in postgres arrays. But I do not understand the remark id, 'index into the matrix' the matrix is a two dimension so I I don't understand how the index is desgined to work!

On 23/06/13 10:04, Dave Potts wrote:

I having some problems with the tsp

I have a matrix {{0,31,22,42},{31,0,90,2},{22,90,0,27},{42,2,27,0}}, starting at node 2, I get the answer
seq | id
-----+----
   0 | 2
   1 | 3
   2 | 1
   3 | 0
(4 rows)
using the matrix

{{0,22,42,31},{22,0,27,90},{42,27,0,2},{31,90,2,0}} starting at node 4 I get the answer
seq | id
-----+----
   0 | 0
   1 | 1
   2 | 2
   3 | 3
The matrix is topological identicial, I start off at the same topological node, so I was expecting the same answer, also I was expecting all nodes to be in the result set ie nodes 1,2,3 and 4, for some strange reason I get 0.

Is there some mistake in my data?

regards

Dave.

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

16

On 6/23/2013 5:19 AM, Dave Potts wrote:

Just looked at the write up for the tsp, ok the answer will be in the
range 0-(X-1) where X is the number of points provided, the returned
index starts of at zero in set as one as found in postgres arrays. But
I do not understand the remark id, 'index into the matrix' the matrix
is a two dimension so I I don't understand how the index is desgined to
work!

Since the the matrix is symmetric NxN, index refers to a row or column, so the resultant path would be for you first example below would be:

0,2: 20
1,3: 2
2,1: 90
3,0: 42

or a path from 2 -> 3 -> 1 -> 0 for a cost of (20+2+90+42) = 154

On 23/06/13 10:04, Dave Potts wrote:

I having some problems with the tsp

I have a matrix {{0,31,22,42},{31,0,90,2},{22,90,0,27},{42,2,27,0}},
starting at node 2, I get the answer
seq | id
-----+----
   0 | 2
   1 | 3
   2 | 1
   3 | 0
(4 rows)
using the matrix

So as you figured out, 4 is invalid, and probably should throw an error (write a ticket for this) as the nodes are 0-3.

-Steve

{{0,22,42,31},{22,0,27,90},{42,27,0,2},{31,90,2,0}} starting at node
4 I get the answer
seq | id
-----+----
   0 | 0
   1 | 1
   2 | 2
   3 | 3
The matrix is topological identicial, I start off at the same
topological node, so I was expecting the same answer, also I was
expecting all nodes to be in the result set ie nodes 1,2,3 and 4, for
some strange reason I get 0.

Is there some mistake in my data?

regards

Dave.

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

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

17

On 6/24/2013 6:27 PM, Dave Potts wrote:

On 24/06/13 23:30, Stephen Woodbridge wrote:

Thank you for your comments on the TSP.

1. Please find attach an sql hacking for running the matrix tsp from a
request, it works with the quote example, which is based on the one from
the tsp page.

Thanks, I will look this over. I think that Daniel and I have come to the idea that we want snippets and user tips, tricks and hacks put in gists or maybe a contrib library or some place other than the core product to make the code more lean and mean and easier to maintain. And over time if there are things that we or the larger community feel are critical to be supported in the core that we will then look at adding them. We just went through the painful process of shedding a lot of cruft from the product.

2. Is there any way of saying in the TSP that there is not a link
between two nodes? Because if there is, there is method on the listed on
http://en.wikipedia.org/wiki/Traveling_salesman_problem#Asymmetric_TSP
for turning a Asmmetric problem in to a normal TSP problem by just
increasing the size of the matrix! But you need a way of saying a link
is impossible!

I have already tried the value of -1 but that got thrown out as an error.

The wikipedia page is using -infinity to say the at A === A', it should work with using zero instead in our code.

At the moment, the algorithm seems to be very fragile (ie: fails) about putting in a cost like infinity or a very large number to mean that you can not follow that link. But you can try to put in a number large for this, if it has problems it will respond with the find eulerian path error.

3. There is a spelling mistake on the
http://docs.pgrouting.org/dev/src/tsp/doc/index.html page, 'containig'

Checked in. thanks.

If your still on hoilday, please enjoy the rest of it.

I'm back, now trying to dig out of the backlog of email and phone messages.

Thanks,
   -Steve

regards

Dave
<http://en.wikipedia.org/wiki/Traveling_salesman_problem#Asymmetric_TSP&gt;

On 6/23/2013 5:19 AM, Dave Potts wrote:

Just looked at the write up for the tsp, ok the answer will be in the
range 0-(X-1) where X is the number of points provided, the returned
index starts of at zero in set as one as found in postgres arrays. But
I do not understand the remark id, 'index into the matrix' the matrix
is a two dimension so I I don't understand how the index is desgined to
work!

Since the the matrix is symmetric NxN, index refers to a row or
column, so the resultant path would be for you first example below
would be:

0,2: 20
1,3: 2
2,1: 90
3,0: 42

or a path from 2 -> 3 -> 1 -> 0 for a cost of (20+2+90+42) = 154

On 23/06/13 10:04, Dave Potts wrote:

I having some problems with the tsp

I have a matrix {{0,31,22,42},{31,0,90,2},{22,90,0,27},{42,2,27,0}},
starting at node 2, I get the answer
seq | id
-----+----
   0 | 2
   1 | 3
   2 | 1
   3 | 0
(4 rows)
using the matrix

So as you figured out, 4 is invalid, and probably should throw an
error (write a ticket for this) as the nodes are 0-3.

-Steve

{{0,22,42,31},{22,0,27,90},{42,27,0,2},{31,90,2,0}} starting at node
4 I get the answer
seq | id
-----+----
   0 | 0
   1 | 1
   2 | 2
   3 | 3
The matrix is topological identicial, I start off at the same
topological node, so I was expecting the same answer, also I was
expecting all nodes to be in the result set ie nodes 1,2,3 and 4, for
some strange reason I get 0.

Is there some mistake in my data?

regards

Dave.

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

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

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

18

On 25/06/13 00:57, Stephen Woodbridge wrote:
Attempting a solution to the ASP using the current method with an array hack seems somewhat easier that converting this program to the modern world http://www.netlib.org/toms/750(Solution to asp in Fortran!!!!!)

Dave.

On 6/24/2013 6:27 PM, Dave Potts wrote:

On 24/06/13 23:30, Stephen Woodbridge wrote:

Thank you for your comments on the TSP.

1. Please find attach an sql hacking for running the matrix tsp from a
request, it works with the quote example, which is based on the one from
the tsp page.

Thanks, I will look this over. I think that Daniel and I have come to the idea that we want snippets and user tips, tricks and hacks put in gists or maybe a contrib library or some place other than the core product to make the code more lean and mean and easier to maintain. And over time if there are things that we or the larger community feel are critical to be supported in the core that we will then look at adding them. We just went through the painful process of shedding a lot of cruft from the product.

2. Is there any way of saying in the TSP that there is not a link
between two nodes? Because if there is, there is method on the listed on
http://en.wikipedia.org/wiki/Traveling_salesman_problem#Asymmetric_TSP
for turning a Asmmetric problem in to a normal TSP problem by just
increasing the size of the matrix! But you need a way of saying a link
is impossible!

I have already tried the value of -1 but that got thrown out as an error.

The wikipedia page is using -infinity to say the at A === A', it should work with using zero instead in our code.

At the moment, the algorithm seems to be very fragile (ie: fails) about putting in a cost like infinity or a very large number to mean that you can not follow that link. But you can try to put in a number large for this, if it has problems it will respond with the find eulerian path error.

3. There is a spelling mistake on the
http://docs.pgrouting.org/dev/src/tsp/doc/index.html page, 'containig'

Checked in. thanks.

If your still on hoilday, please enjoy the rest of it.

I'm back, now trying to dig out of the backlog of email and phone messages.

Thanks,
  -Steve

regards

Dave
<http://en.wikipedia.org/wiki/Traveling_salesman_problem#Asymmetric_TSP&gt;

On 6/23/2013 5:19 AM, Dave Potts wrote:

Just looked at the write up for the tsp, ok the answer will be in the
range 0-(X-1) where X is the number of points provided, the returned
index starts of at zero in set as one as found in postgres arrays. But
I do not understand the remark id, 'index into the matrix' the matrix
is a two dimension so I I don't understand how the index is desgined to
work!

Since the the matrix is symmetric NxN, index refers to a row or
column, so the resultant path would be for you first example below
would be:

0,2: 20
1,3: 2
2,1: 90
3,0: 42

or a path from 2 -> 3 -> 1 -> 0 for a cost of (20+2+90+42) = 154

On 23/06/13 10:04, Dave Potts wrote:

I having some problems with the tsp

I have a matrix {{0,31,22,42},{31,0,90,2},{22,90,0,27},{42,2,27,0}},
starting at node 2, I get the answer
seq | id
-----+----
   0 | 2
   1 | 3
   2 | 1
   3 | 0
(4 rows)
using the matrix

So as you figured out, 4 is invalid, and probably should throw an
error (write a ticket for this) as the nodes are 0-3.

-Steve

{{0,22,42,31},{22,0,27,90},{42,27,0,2},{31,90,2,0}} starting at node
4 I get the answer
seq | id
-----+----
   0 | 0
   1 | 1
   2 | 2
   3 | 3
The matrix is topological identicial, I start off at the same
topological node, so I was expecting the same answer, also I was
expecting all nodes to be in the result set ie nodes 1,2,3 and 4, for
some strange reason I get 0.

Is there some mistake in my data?

regards

Dave.

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

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

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