On 15/06/13 14:28, Stephen Woodbridge wrote:
Nice Idea, but one of the problems I have is that I am VERY lazy!
When I create a source/target/cost table I only tend to populate it with existing routes, so if I have path at cost of 42 betweens nodes 2 and 3
I will create an entry like
2 3 42
I have no desire to create an entry for journey between nodes 5 6 that does not exist or having to provide a value for journey between myself and myself eg a journey from node 2 to node 2, I think the suggested solution would require me to create entries like
2 2 0
5 6 0 etc
So I had a crack at writing a function based on Steves original screenplay. I think it needs a lot more work, when I create the temporary tables, I get a diagnostic from psql saying that its created a table. There must be a better way of doing it
Its invoked as
select mktsparray(' select source,target ,cost from edge_table2');
-- Make a distance matrix for the traveling salesman problem
--
-- Input is an sql string that provides source, target and the cost
-- of getting between them
--
--
CREATE or REPLACE FUNCTION mktsparray(tag_name text) RETURNS float
LANGUAGE plpgsql
AS $$
DECLARE
ret_array float ;
array_size integer;
tsp_details record;
BEGIN
ret_array := null;
-- create a copy of the source
EXECUTE 'DROP TABLE IF EXISTS tsp_src';
EXECUTE 'DROP TABLE IF EXISTS tsp_map';
create temporary table tsp_src ( id serial not null,source integer not null,
target integer not null, cost float not null);
-- create a tsp node to matrix lookup table
create temporary table tsp_map ( id serial not null primary key, nid integer);
EXECUTE 'insert into tsp_src (source, target, cost)'|| tag_name;
insert into tsp_map (nid) select nid from (select distinct source as nid from edge_table2 union select distinct target as nid from edge_table2) as foo;
-- should generate a matrix count(*) X count(*) of tsp_map
select count(*) INTO array_size from tsp_map;
-- by default populate the return results with zero, so any unknown
-- routes will not be listed
ret_array :=array_fill(0,ARRAY [ array_size,array_size]);
-- Loop trough the input looking for any listed routes
FOR tsp_details IN EXECUTE
'select c.nid as src ,b.nid as tar,a.cost as cos
from tsp_src a, tsp_map b, tsp_map c
where a.target= b.nid and a.source= c.nid and a.cost > 0
group by b.id,c.id,a.cost' LOOP
ret_array[tsp_details.src][tsp_details.tar]:=tsp_details.cos;
END LOOP;
return ret_array;
END
$$;
Dave,
I thought a lot about this problem before coming up with the matrix. The problem really boils down to how do you define your data that you want to fetch with "select * from xyz", ie: your inputs and what you need to solve TSP, ie: your outputs. In this case a symmetrix NxN matrix that is fully populated.
One idea I had was to structure xyz something like:
node_a, node_b, cost
but then you have to count the distinct nodes, and create a map to indices and a reverse map as you as you mention. But this is all pretty trivial to do in SQL.
create temporary table xyz_map (
id serial not null primary key,
nid integer
);
insert into xyz_map values (nid) select nid from (
select distinct node_a as nid from xyz
union
select distinct node_b as nid from xyz
) as foo;
select array_agg(row) as matrix from (
select a.id, array_agg(cost) as row
from xyz a, xyz_map b, xyz_map c
where a.node_a=b.nid and a.node_b=c.nid
group by a.id
order by c.id
) foo order by foo.id;
I have not tested this, but I think it is close to what you would work. I would then do some checking of matrix to make sure it is symmetric and filled out.
-Steve
On 6/15/2013 1:37 AM, Dave Potts wrote:
On 14/06/13 14:19, Daniel Kastl wrote:
I can try and have a play, my problem being that I am more a C/java
programmer than an sql programmer. I prefer to deal with standard sql
constructs rather that data base specfic stuff.
I can see why you got for the matrix solution, if avoid all those
node/hash lookup problems.
If coding an select * from xyz solution , you have to deal with the case
that a node may be any number in the range 1-32^2 and that has to be
mapped on to an array of given size by using some type of hashing
function and a reverse lookup has to be done on the return.
The store procedure has its attractions because its version neutral, it
will work as well on linix box as well as a Windoz box.
I see what I can come up with.
DAve.
//
On Fri, Jun 14, 2013 at 10:07 PM, Stephen Woodbridge
<woodbri@swoodbridge.com <mailto:woodbri@swoodbridge.com>> wrote:
Hi Dave,
I'm not totally opposed to this, but I would like to discuss how
you plan to structure the data and what your query would look like.
There is another possibility that I like better and that would be
to write stored procedure that takes you sql query and returns a
matrix.
matrix pgr_matrix(sql text)
Then you can do something like:
select * from pgr_tsp(pgr_matrix('select * from matrix_table'), 27);
This idea I really like, because we might also be able to use it then
for Razequl's VRP solver.
Daniel
--
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
