[pgrouting-dev] New TSP API
Daniel Kastl
daniel at georepublic.de
Sun May 19 20:33:28 PDT 2013
Hi Stvee,
Really cool! Thanks!
I will think about how to make the docs more readable.
Daniel
On Mon, May 20, 2013 at 11:17 AM, Stephen Woodbridge <
woodbri at swoodbridge.com> wrote:
> 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<pgrouting-dev at lists.osgeo.org>
>>>>> >
>>>>> <mailto:pgrouting-dev at lists.**osgeo.org<pgrouting-dev at lists.osgeo.org>
>>>>> <mailto:pgrouting-dev at lists.**osgeo.org<pgrouting-dev at lists.osgeo.org>
>>>>> >>
>>>>> http://lists.osgeo.org/__**mailman/listinfo/pgrouting-dev<http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev>
>>>>>
>>>>> <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@**georepublic.de<daniel.kastl at georepublic.de>
>>>>> >
>>>>> <mailto:daniel.kastl@**georepublic.de<daniel.kastl at georepublic.de>
>>>>> <mailto:daniel.kastl@**georepublic.de<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<pgrouting-dev at lists.osgeo.org>
>>>>> >
>>>>> http://lists.osgeo.org/**mailman/listinfo/pgrouting-dev<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<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@**
>>>>> georepublic.de <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<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<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<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<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<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>
>
--
Georepublic UG & Georepublic Japan
eMail: daniel.kastl at georepublic.de
Web: http://georepublic.de
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20130520/752b54d7/attachment-0001.html>
More information about the pgrouting-dev
mailing list