[pgrouting-dev] Having problems under standing the distance matrix of TSP in respect to route network pgroute version 2

[Stephen Woodbridge]

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 at swoodbridge.com <mailto:woodbri at 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 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
>