[pgrouting-dev] New TSP API

[Stephen Woodbridge]

On 5/19/2013 9:35 AM, Daniel Kastl wrote:
>
>
>
> On Sun, May 19, 2013 at 10:16 PM, Stephen Woodbridge
> <woodbri at swoodbridge.com <mailto:woodbri at swoodbridge.com>> wrote:
>
>     Hi Dave, et al,
>
>     One of the stumbling blocks I have have had with creating a new API
>     for TSP is how we should pass the distance matrix. So I have been
>     thinking of something like this:
>
>     select * from pgr_tsp(matrix <type>, num integer, start integer);
>
>
> Hi Steve,
>
> What is "num integer" supposed to be?

This is the size of the matrix ie: matrix[num][num] that has to be solved.

>     The matrix type could be text for a SQL query that would return num
>     rows of num float8 or it could be float8[][] that is [num][num]
>     elements. And I support with a little extra work I could support
>     both of these.
>
>
> I would prefer some "regular" SQL query (if there is no strong argument
> against.
>
> What about this:
>
> SELECT * FROM pgr_tsp( 'SELECT id, start, end, cost FROM distances,
> origin int [, destination int])

I can do this, so each record is one cell. What are "start" and "end"? 
are these vertex ids or are they indices? Does the use KNOW that they 
need to also have a row for (end,start) as well as (start,end)? These 
things are less obvious and there for have more room for errors.

I suppose we could write an aggregate function that takes your query and 
returns matrix[][]. But we still need to define how to deal with null 
values in the matrix.

select pgr_makematrix(i, j, cost) from
     (select start as i, end as j, cost from distances) as foo;

Then this could be passed as the SQL to the TSP. We need to keep each 
function simple and make them chainable or we limit the usefulness of them.

Any thoughts on how to deal with NULLs in the matrix?

We could have some default rules like?
1. if the null is on a diagonal set it to zero
2. if the cell(i,j) is null and cell(j,i) is not use cell(j,i)
3. otherwise report an error

Thoughts?

-Steve


> ... which would return the matrix in an optimized order.
> I think it would be nice to be able to set origin and destination point.
> But destination could be optional.
>
> Daniel
>
>
>
>
>
>
>
>     I'm not interested in computing the distance matrix because I will
>     not be able to do it "right" for any given use case and it limits
>     how people can use the function.
>
>     Thoughts?
>
>     -Steve
>     _________________________________________________
>     pgrouting-dev mailing list
>     pgrouting-dev at lists.osgeo.org <mailto:pgrouting-dev at lists.osgeo.org>
>     http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
>     <http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>
>
>
>
>
> --
> Georepublic UG & Georepublic Japan
> eMail: daniel.kastl at georepublic.de <mailto:daniel.kastl at georepublic.de>
> Web: http://georepublic.de <http://georepublic.de/>
>
>
> _______________________________________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>