<div dir="ltr">Hi Stvee,<div><br></div><div>Really cool! Thanks!</div><div>I will think about how to make the docs more readable.</div><div><br></div><div>Daniel<br><div class="gmail_extra"><br><br><div class="gmail_quote">
On Mon, May 20, 2013 at 11:17 AM, Stephen Woodbridge <span dir="ltr"><<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
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.<br>
<br>
-- DROP FUNCTION array_array_agg(float[][], float[]);<br>
CREATE OR REPLACE FUNCTION array_array_agg(float[][], float[])<br>
RETURNS float[][] AS<br>
$BODY$<br>
SELECT array_cat($1, ARRAY[$2]);<br>
$BODY$ LANGUAGE sql;<br>
<br>
DROP AGGREGATE IF EXISTS array_agg2(float[]);<br>
CREATE AGGREGATE array_agg2(float[])<br>
(<br>
sfunc = array_array_agg,<br>
stype = float[][],<br>
initcond = '{}'<br>
);<br>
<br>
<br>
drop table if exists t;<br>
create table t (<br>
i integer,<br>
j integer,<br>
v float<br>
);<br>
<br>
insert into t values<br>
(0,0,0),<br>
(0,1,1),<br>
(0,2,2),<br>
(0,3,3),<br>
(1,0,1),<br>
(1,1,0),<br>
(1,2,3),<br>
(1,3,2),<br>
(2,0,2),<br>
(2,1,3),<br>
(2,2,0),<br>
(2,3,4),<br>
(3,0,3),<br>
(3,1,2),<br>
(3,2,4),<br>
(3,3,0);<br>
<br>
select array_agg2(foo.b) from (<br>
select i, array_agg(v) as b from t group by i order by i<br>
) as foo;<br>
<br>
<br>
select (tsp).* from (<br>
select pgr_tsp(matrix::double precision[], 2) as tsp from (<br>
select array_agg2(b) as matrix from (<br>
select i, array_agg(v) as b from t group by i order by i<br>
) as foo<br>
) as bar<br>
) as foobar;<br>
<br>
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.<div class="HOEnZb"><div class="h5"><br>
<br>
On 5/19/2013 7:57 PM, Stephen Woodbridge wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
OK, I just push a new function for tsp:<br>
<br>
select * from pgr_tsp('{{0,1,2,3},{1,0,3,2},<u></u>{2,3,0,4},{3,2,4,0}}', 2);<br>
seq | id<br>
-----+----<br>
0 | 2<br>
1 | 0<br>
2 | 1<br>
3 | 3<br>
(4 rows)<br>
<br>
The above is just one simple way to define a matrix[4][4]<br>
<br>
i/j 0, 1, 2, 3<br>
0: {0, 1, 2, 3},<br>
1: {1, 0, 3, 2},<br>
2: {2, 3, 0, 4},<br>
3: {3, 2, 4, 0}<br>
<br>
So the result is a loop from 2-0-1-3-2<br>
<br>
edge: cost<br>
2-0 : 2<br>
0-1 : 1<br>
1-3 : 2<br>
3-2 : 4<br>
<br>
for a total cost of 2+1+2+4 = 9<br>
<br>
I'm looking into how to create an aggregate to assemble recordss into an<br>
array.<br>
<br>
But this is a start.<br>
<br>
-Steve<br>
<br>
On 5/19/2013 12:25 PM, Stephen Woodbridge wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
OK, so both you an Daniel are looking at the problem from some higher<br>
level than I am dealing with. So we will have to build some layers to<br>
bridge the gap between that and the low level code that I have to deal<br>
with.<br>
<br>
The solver takes as arguments:<br>
<br>
num - the size of the matrix<br>
matrix - a num*num array of float8<br>
<br>
and returns an array of num indices which it the optimal order.<br>
<br>
This will be very close to the first API I create. At this level it<br>
needs to be this simple. At a higher level some one can map ids to array<br>
indexes and map them back again.<br>
<br>
Regarding, null cell values or negative cell values, I guess I can set<br>
them to infinity. I'm not going to try and modify the algorithm to<br>
eliminate arbitrary rows.<br>
<br>
Postgresql supports an an array type and multi-dimensional arrays. Most<br>
people do not use them, but it is a convenient type for passing the data<br>
to this algorithm.<br>
<br>
If I can get this to work, then we can look at layering something<br>
smarter on top of that.<br>
<br>
The bottom line is if your data can not be put into a distance matrix<br>
then you do not have a problem that can be solved by TSP. Now we just<br>
need to make it easier to put the data into a distance matrix.<br>
<br>
-Steve<br>
<br>
On 5/19/2013 11:39 AM, Dave Potts wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Hi,<br>
<br>
<br>
Is there any sort of time tablethisn idea?<br>
<br>
I must admit, I have a need for this type of thing and with out looking<br>
at the existing code its difficult to comment.<br>
<br>
Due to the nature of the data that I am working with every node has<br>
its set of data, so I prefer a solution that uses a generic sql<br>
expression as a parmeter i.e. something like<br>
<br>
select target,cost,reverse_cost, etc where source =XXXXX<br>
<br>
Where XXXXX is a supply argument that gets provided invoked when data is<br>
need.<br>
<br>
Dave.<br>
<br>
On 19/05/13 15:58, Daniel Kastl wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
<br>
SELECT * FROM pgr_tsp( 'SELECT id, start, end, cost FROM<br>
distances,<br>
origin int [, destination int])<br>
<br>
<br>
I can do this, so each record is one cell. What are "start" and<br>
"end"? are these vertex ids or are they indices? Does the use KNOW<br>
that they need to also have a row for (end,start) as well as<br>
(start,end)? These things are less obvious and there for have more<br>
room for errors.<br>
<br>
<br>
Well start and end is just "id1" and "id2".<br>
You could actually also have two costs there, one for each direction<br>
(like cost and reverse_cost).<br>
<br>
<br>
I suppose we could write an aggregate function that takes your<br>
query and returns matrix[][]. But we still need to define how to<br>
deal with null values in the matrix.<br>
<br>
<br>
I know I said "matrix", but actually I didn't think about matrix ;-)<br>
I thought about pairs of id's with cost(s). So it wouldn't be an<br>
[m][m] matrix but more like a table with m*m/2 records (if there is a<br>
cost for each direction for each combination).<br>
I don't know how it should be later internally for the algorithm, but<br>
I would say, that a query (table) always has a fix number of columns<br>
and a variable number of rows.<br>
<br>
In the end this would look like a graph, where all nodes are connected<br>
with all nodes.<br>
<br>
<br>
select pgr_makematrix(i, j, cost) from<br>
(select start as i, end as j, cost from distances) as foo;<br>
<br>
Then this could be passed as the SQL to the TSP. We need to keep<br>
each function simple and make them chainable or we limit the<br>
usefulness of them.<br>
<br>
<br>
Exactly ;-)<br>
<br>
<br>
Any thoughts on how to deal with NULLs in the matrix?<br>
<br>
We could have some default rules like?<br>
1. if the null is on a diagonal set it to zero<br>
2. if the cell(i,j) is null and cell(j,i) is not use cell(j,i)<br>
3. otherwise report an error<br>
<br>
<br>
If you always have pairs A <-> B then you won't have a diagonal set.<br>
In case there is no way in one direction (maybe even in both<br>
directions), then this could be -1 for example?<br>
Then it would be same as negative cost for Dijkstra or Astar and it<br>
won't be taken into account.<br>
<br>
Daniel<br>
<br>
Thoughts?<br>
<br>
-Steve<br>
<br>
<br>
... which would return the matrix in an optimized order.<br>
I think it would be nice to be able to set origin and<br>
destination point.<br>
But destination could be optional.<br>
<br>
Daniel<br>
<br>
<br>
<br>
<br>
<br>
<br>
<br>
I'm not interested in computing the distance matrix<br>
because I will<br>
not be able to do it "right" for any given use case and it<br>
limits<br>
how people can use the function.<br>
<br>
Thoughts?<br>
<br>
-Steve<br>
______________________________<u></u>___________________<br>
pgrouting-dev mailing list<br>
<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a><br>
<mailto:<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.<u></u>osgeo.org</a>><br>
<mailto:<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.<u></u>osgeo.org</a><br>
<mailto:<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.<u></u>osgeo.org</a>>><br>
<a href="http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/__<u></u>mailman/listinfo/pgrouting-dev</a><br>
<br>
<<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/<u></u>mailman/listinfo/pgrouting-dev</a><u></u>><br>
<br>
<br>
<br>
<br>
--<br>
Georepublic UG & Georepublic Japan<br>
eMail: <a href="mailto:daniel.kastl@georepublic.de" target="_blank">daniel.kastl@georepublic.de</a><br>
<mailto:<a href="mailto:daniel.kastl@georepublic.de" target="_blank">daniel.kastl@<u></u>georepublic.de</a>><br>
<mailto:<a href="mailto:daniel.kastl@georepublic.de" target="_blank">daniel.kastl@<u></u>georepublic.de</a><br>
<mailto:<a href="mailto:daniel.kastl@georepublic.de" target="_blank">daniel.kastl@<u></u>georepublic.de</a>>><br>
Web: <a href="http://georepublic.de" target="_blank">http://georepublic.de</a> <<a href="http://georepublic.de/" target="_blank">http://georepublic.de/</a>><br>
<br>
<br>
<br>
______________________________<u></u>_________________<br>
pgrouting-dev mailing list<br>
<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a><br>
<mailto:<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.<u></u>osgeo.org</a>><br>
<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/<u></u>mailman/listinfo/pgrouting-dev</a><br>
<br>
<br>
______________________________<u></u>_________________<br>
pgrouting-dev mailing list<br>
<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a><br>
<mailto:<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.<u></u>osgeo.org</a>><br>
<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/<u></u>mailman/listinfo/pgrouting-dev</a><br>
<br>
<br>
<br>
<br>
--<br>
Georepublic UG & Georepublic Japan<br>
eMail: <a href="mailto:daniel.kastl@georepublic.de" target="_blank">daniel.kastl@georepublic.de</a> <mailto:<a href="mailto:daniel.kastl@georepublic.de" target="_blank">daniel.kastl@<u></u>georepublic.de</a>><br>
Web: <a href="http://georepublic.de" target="_blank">http://georepublic.de</a> <<a href="http://georepublic.de/" target="_blank">http://georepublic.de/</a>><br>
<br>
<br>
______________________________<u></u>_________________<br>
pgrouting-dev mailing list<br>
<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a><br>
<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/<u></u>mailman/listinfo/pgrouting-dev</a><br>
</blockquote>
<br>
<br>
<br>
______________________________<u></u>_________________<br>
pgrouting-dev mailing list<br>
<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a><br>
<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/<u></u>mailman/listinfo/pgrouting-dev</a><br>
<br>
</blockquote>
<br>
______________________________<u></u>_________________<br>
pgrouting-dev mailing list<br>
<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a><br>
<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/<u></u>mailman/listinfo/pgrouting-dev</a><br>
</blockquote>
<br>
______________________________<u></u>_________________<br>
pgrouting-dev mailing list<br>
<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a><br>
<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/<u></u>mailman/listinfo/pgrouting-dev</a><br>
</blockquote>
<br>
______________________________<u></u>_________________<br>
pgrouting-dev mailing list<br>
<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a><br>
<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/<u></u>mailman/listinfo/pgrouting-dev</a><br>
</div></div></blockquote></div><br><br clear="all"><div><br></div>-- <br><span style="font-family:arial,sans-serif;font-size:13px;border-collapse:collapse">Georepublic UG & Georepublic Japan<br>eMail: <a href="mailto:daniel.kastl@georepublic.de" style="color:rgb(66,99,171)" target="_blank">daniel.kastl@georepublic.de</a><br>
Web: <a href="http://georepublic.de/" style="color:rgb(66,99,171)" target="_blank">http://georepublic.de</a></span>
</div></div></div>