Here is an interesting way deal with this problem:
create or replace function pgr_makeDistanceMatrix(sqlin text, OUT dmatrix double precision, OUT ids integer)
as
$body$
declare
sql text;
r record;
begin
dmatrix := array::double precision;
ids := array::integer;
sql := 'with nodes as (' || sqlin || ')
select i, array_agg(dist) as arow from (
select a.id as i, b.id as j, st_distance(st_makepoint(a.x, a.y), st_makepoint(b.x, b.y)) as dist
from nodes a, nodes b
order by a.id, b.id
) as foo group by i order by i';
for r in execute sql loop
dmatrix := array_cat(dmatrix, array[r.arow]);
ids := ids || array[r.i];
end loop;
end;
$body$
language plpgsql stable cost 10;
with dm as (
select * from pgr_makeDistanceMatrix(
'select source_id as id, x, y
from tsp_00
where source_id in (1,7,16,3,5)')
),
ids as (
select (row_number() over (order by id asc))-1 as rnum, id
from (
select unnest(ids) as id
from dm
) foo
)
select a.seq, b.rnum, b.id, d.dmatrix[a.seq+1][b.rnum+1] as dist
from pgr_tsp(
(select dmatrix from dm),
(select rnum from ids where id=7)::integer
) a,
ids b,
dm d
where a.id=b.rnum;
i; j; id; cost
0; 3; 7; 6
1; 0; 1; 2.23606797749979
2; 1; 3; 3
3; 2; 5; 4.47213595499958
4; 4; 16; 0 <<-- this line seems to be bad see below
Since it took me all afternoon and evening to figure this out I will leave that as an exercise for the reader, but feel free to ask questions.
I think the whole second query can be wrapped in a stored procedure where it takes sql string the gets dropped into the dm CTE and returns the results.
I think there is a bug in my logic somewhere because I always seem to get back one row there the seq=rnum and the cost is zero so this not is not linked to the path.
But my brain is too fried to make sense of this anymore tonight.
Thoughts,
-Steve
On 6/28/2013 10:17 AM, Stephen Woodbridge wrote:
Hi All,
I'm trying to understand how the old TSP code was supposed to work, as
it is not making any sense to me. So the signature is:
select * from pgr_tsp(sql text, ids text, start_id integer, end_id
integer);
sql - sql that selects some number of point that have id, x, and y, ie:
'select id, x, y from table'
ids - is a comma separated list of ids, :ie: '3,27,44,6'
start_id - must be one of the ids in the ids list
end_id - [optional] will be the end of the path if passed in, otherwise
assumes a loop. must be in ids
Currently 'sql' can select an arbitrary list of nodes greater than the
list of ids. This does not make any sense to me and the code behaves
badly in this case. For example if you select 100 points in the sql and
only have 5 in the ids list what does this mean? Why is the ids list
separate from the sql?
Currently the code only works cleanly if the the sql returns exactly the
list of ids. ie:
select * from pgr_tsp(
'select id, x, y from mytable where id in (3,27,44,6)',
'3,27,44,6',
3, -1);
This seems redundant and messy at best.
Can anyone clear up what was supposed to happen in the old version?
I'm temped to just through out the old code and rewrite this as a
wrapper that computes a distance matrix and calls the matrix function,
or something like that.
Thoughts, use cases?
-Steve
_______________________________________________
Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users