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

[Dave Potts]

On 15/06/13 14:28, Stephen Woodbridge wrote:
Hi Steve,

I have had another at this problem,  I managed to write some code to 
generate a matrix, small problem, since your mapping node values so fits 
in to the size values of the matrix, you also have to perform the same 
mapping on the start node and return value as well.

Dave.
> 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
>>
>
> _______________________________________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev