[pgrouting-dev] New TSP API
Stephen Woodbridge
woodbri at swoodbridge.com
Sun May 19 19:17:00 PDT 2013
OK, this took me all night to figure out how to take a query that
returns i, j, val and load it into an array. This assumes you have all
cells defined in your query because any missing cells will cause values
to shift and sub arrays to be too short which will prevent them from
assembling.
-- DROP FUNCTION array_array_agg(float[][], float[]);
CREATE OR REPLACE FUNCTION array_array_agg(float[][], float[])
RETURNS float[][] AS
$BODY$
SELECT array_cat($1, ARRAY[$2]);
$BODY$ LANGUAGE sql;
DROP AGGREGATE IF EXISTS array_agg2(float[]);
CREATE AGGREGATE array_agg2(float[])
(
sfunc = array_array_agg,
stype = float[][],
initcond = '{}'
);
drop table if exists t;
create table t (
i integer,
j integer,
v float
);
insert into t values
(0,0,0),
(0,1,1),
(0,2,2),
(0,3,3),
(1,0,1),
(1,1,0),
(1,2,3),
(1,3,2),
(2,0,2),
(2,1,3),
(2,2,0),
(2,3,4),
(3,0,3),
(3,1,2),
(3,2,4),
(3,3,0);
select array_agg2(foo.b) from (
select i, array_agg(v) as b from t group by i order by i
) as foo;
select (tsp).* from (
select pgr_tsp(matrix::double precision[], 2) as tsp from (
select array_agg2(b) as matrix from (
select i, array_agg(v) as b from t group by i order by i
) as foo
) as bar
) as foobar;
This better get added to the docs. I tried to merge the new tsp function
into the existing docs, but given all this we probably need to split it
out into its own page.
On 5/19/2013 7:57 PM, Stephen Woodbridge wrote:
> OK, I just push a new function for tsp:
>
> select * from pgr_tsp('{{0,1,2,3},{1,0,3,2},{2,3,0,4},{3,2,4,0}}', 2);
> seq | id
> -----+----
> 0 | 2
> 1 | 0
> 2 | 1
> 3 | 3
> (4 rows)
>
> The above is just one simple way to define a matrix[4][4]
>
> i/j 0, 1, 2, 3
> 0: {0, 1, 2, 3},
> 1: {1, 0, 3, 2},
> 2: {2, 3, 0, 4},
> 3: {3, 2, 4, 0}
>
> So the result is a loop from 2-0-1-3-2
>
> edge: cost
> 2-0 : 2
> 0-1 : 1
> 1-3 : 2
> 3-2 : 4
>
> for a total cost of 2+1+2+4 = 9
>
> I'm looking into how to create an aggregate to assemble recordss into an
> array.
>
> But this is a start.
>
> -Steve
>
> On 5/19/2013 12:25 PM, Stephen Woodbridge wrote:
>> OK, so both you an Daniel are looking at the problem from some higher
>> level than I am dealing with. So we will have to build some layers to
>> bridge the gap between that and the low level code that I have to deal
>> with.
>>
>> The solver takes as arguments:
>>
>> num - the size of the matrix
>> matrix - a num*num array of float8
>>
>> and returns an array of num indices which it the optimal order.
>>
>> This will be very close to the first API I create. At this level it
>> needs to be this simple. At a higher level some one can map ids to array
>> indexes and map them back again.
>>
>> Regarding, null cell values or negative cell values, I guess I can set
>> them to infinity. I'm not going to try and modify the algorithm to
>> eliminate arbitrary rows.
>>
>> Postgresql supports an an array type and multi-dimensional arrays. Most
>> people do not use them, but it is a convenient type for passing the data
>> to this algorithm.
>>
>> If I can get this to work, then we can look at layering something
>> smarter on top of that.
>>
>> The bottom line is if your data can not be put into a distance matrix
>> then you do not have a problem that can be solved by TSP. Now we just
>> need to make it easier to put the data into a distance matrix.
>>
>> -Steve
>>
>> On 5/19/2013 11:39 AM, Dave Potts wrote:
>>> Hi,
>>>
>>>
>>> Is there any sort of time tablethisn idea?
>>>
>>> I must admit, I have a need for this type of thing and with out looking
>>> at the existing code its difficult to comment.
>>>
>>> Due to the nature of the data that I am working with every node has
>>> its set of data, so I prefer a solution that uses a generic sql
>>> expression as a parmeter i.e. something like
>>>
>>> select target,cost,reverse_cost, etc where source =XXXXX
>>>
>>> Where XXXXX is a supply argument that gets provided invoked when data is
>>> need.
>>>
>>> Dave.
>>>
>>> On 19/05/13 15:58, Daniel Kastl wrote:
>>>>
>>>>
>>>> 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.
>>>>
>>>>
>>>> Well start and end is just "id1" and "id2".
>>>> You could actually also have two costs there, one for each direction
>>>> (like cost and reverse_cost).
>>>>
>>>>
>>>> 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.
>>>>
>>>>
>>>> I know I said "matrix", but actually I didn't think about matrix ;-)
>>>> I thought about pairs of id's with cost(s). So it wouldn't be an
>>>> [m][m] matrix but more like a table with m*m/2 records (if there is a
>>>> cost for each direction for each combination).
>>>> I don't know how it should be later internally for the algorithm, but
>>>> I would say, that a query (table) always has a fix number of columns
>>>> and a variable number of rows.
>>>>
>>>> In the end this would look like a graph, where all nodes are connected
>>>> with all nodes.
>>>>
>>>>
>>>> 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.
>>>>
>>>>
>>>> Exactly ;-)
>>>>
>>>>
>>>> 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
>>>>
>>>>
>>>> If you always have pairs A <-> B then you won't have a diagonal set.
>>>> In case there is no way in one direction (maybe even in both
>>>> directions), then this could be -1 for example?
>>>> Then it would be same as negative cost for Dijkstra or Astar and it
>>>> won't be taken into account.
>>>>
>>>> Daniel
>>>>
>>>> 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>
>>>> <mailto: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>
>>>> <mailto: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
>>>> <mailto:pgrouting-dev at lists.osgeo.org>
>>>> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>>>>
>>>>
>>>> _______________________________________________
>>>> 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
>>>>
>>>>
>>>>
>>>>
>>>> --
>>>> 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
>>>
>>>
>>>
>>> _______________________________________________
>>> pgrouting-dev mailing list
>>> pgrouting-dev at lists.osgeo.org
>>> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>>>
>>
>> _______________________________________________
>> pgrouting-dev mailing list
>> pgrouting-dev at lists.osgeo.org
>> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>
> _______________________________________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
More information about the pgrouting-dev
mailing list