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@lists.osgeo.org
<mailto:pgrouting-dev@lists.osgeo.org>
<mailto: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>
--
Georepublic UG & Georepublic Japan
eMail: daniel.kastl@georepublic.de
<mailto:daniel.kastl@georepublic.de>
<mailto:daniel.kastl@georepublic.de
<mailto:daniel.kastl@georepublic.de>>
Web: http://georepublic.de/>
_______________________________________________
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
<mailto:pgrouting-dev@lists.osgeo.org>
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
_______________________________________________
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
<mailto:pgrouting-dev@lists.osgeo.org>
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
--
Georepublic UG & Georepublic Japan
eMail: daniel.kastl@georepublic.de <mailto:daniel.kastl@georepublic.de>
Web: http://georepublic.de/>
_______________________________________________
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
_______________________________________________
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev