| 1 | -- |
|---|
| 2 | -- Copyright (c) 2005 Sylvain Pasche, |
|---|
| 3 | -- 2006-2007 Anton A. Patrushev, Orkney, Inc. |
|---|
| 4 | -- |
|---|
| 5 | -- This program is free software; you can redistribute it and/or modify |
|---|
| 6 | -- it under the terms of the GNU General Public License as published by |
|---|
| 7 | -- the Free Software Foundation; either version 2 of the License, or |
|---|
| 8 | -- (at your option) any later version. |
|---|
| 9 | -- |
|---|
| 10 | -- This program is distributed in the hope that it will be useful, |
|---|
| 11 | -- but WITHOUT ANY WARRANTY; without even the implied warranty of |
|---|
| 12 | -- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
|---|
| 13 | -- GNU General Public License for more details. |
|---|
| 14 | -- |
|---|
| 15 | -- You should have received a copy of the GNU General Public License |
|---|
| 16 | -- along with this program; if not, write to the Free Software |
|---|
| 17 | -- Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. |
|---|
| 18 | |
|---|
| 19 | |
|---|
| 20 | -- BEGIN; |
|---|
| 21 | |
|---|
| 22 | ----------------------------------------------------- |
|---|
| 23 | -- Returns TSP solution as a set of vertex ids |
|---|
| 24 | -- |
|---|
| 25 | -- Last changes: 14.02.2008 |
|---|
| 26 | ----------------------------------------------------- |
|---|
| 27 | CREATE OR REPLACE FUNCTION tsp_ids(geom_table varchar, |
|---|
| 28 | ids varchar, source integer) |
|---|
| 29 | RETURNS SETOF integer AS |
|---|
| 30 | $$ |
|---|
| 31 | DECLARE |
|---|
| 32 | r record; |
|---|
| 33 | path_result record; |
|---|
| 34 | v_id integer; |
|---|
| 35 | prev integer; |
|---|
| 36 | |
|---|
| 37 | BEGIN |
|---|
| 38 | prev := -1; |
|---|
| 39 | FOR path_result IN EXECUTE 'SELECT vertex_id FROM tsp(''select distinct source::integer as source_id, x(startpoint(the_geom)), y(startpoint(the_geom)) from ' || |
|---|
| 40 | quote_ident(geom_table) || ' where source in (' || |
|---|
| 41 | ids || ') UNION select distinct target as source_id, x(endpoint(the_geom)), y(endpoint(the_geom)) from tsp_test where target in ('||ids||')'', '''|| ids ||''', '|| source ||')' LOOP |
|---|
| 42 | |
|---|
| 43 | v_id = path_result.vertex_id; |
|---|
| 44 | RETURN NEXT v_id; |
|---|
| 45 | END LOOP; |
|---|
| 46 | |
|---|
| 47 | RETURN; |
|---|
| 48 | END; |
|---|
| 49 | $$ |
|---|
| 50 | LANGUAGE 'plpgsql' VOLATILE STRICT; |
|---|
| 51 | |
|---|
| 52 | |
|---|
| 53 | ------------------------------------------------------ |
|---|
| 54 | -- Returns TSP solution as a set of vertices connected |
|---|
| 55 | -- with A* paths |
|---|
| 56 | -- |
|---|
| 57 | -- Last changes: 14.02.2008 |
|---|
| 58 | ------------------------------------------------------ |
|---|
| 59 | CREATE OR REPLACE FUNCTION tsp_astar( |
|---|
| 60 | geom_table varchar,ids varchar, source integer, delta double precision) |
|---|
| 61 | RETURNS SETOF GEOMS AS |
|---|
| 62 | $$ |
|---|
| 63 | DECLARE |
|---|
| 64 | r record; |
|---|
| 65 | path_result record; |
|---|
| 66 | v_id integer; |
|---|
| 67 | prev integer; |
|---|
| 68 | geom geoms; |
|---|
| 69 | |
|---|
| 70 | id integer; |
|---|
| 71 | BEGIN |
|---|
| 72 | |
|---|
| 73 | id :=0; |
|---|
| 74 | prev := source; |
|---|
| 75 | FOR path_result IN EXECUTE 'SELECT vertex_id FROM tsp(''select distinct source::integer as source_id, x1::double precision as x, y1::double precision as y from ' || |
|---|
| 76 | quote_ident(geom_table) || ' where source in (' || |
|---|
| 77 | ids || ') UNION select distinct target as source_id, x(endpoint(the_geom)), y(endpoint(the_geom)) from tsp_test where target in ('||ids||')'', '''|| ids ||''', '|| source ||')' LOOP |
|---|
| 78 | |
|---|
| 79 | v_id = path_result.vertex_id; |
|---|
| 80 | |
|---|
| 81 | FOR r IN EXECUTE 'SELECT gid, the_geom FROM astar_sp_delta( ''' || |
|---|
| 82 | quote_ident(geom_table) ||''', '|| v_id ||', '|| |
|---|
| 83 | prev ||','||delta||')' LOOP |
|---|
| 84 | geom.gid := r.gid; |
|---|
| 85 | geom.the_geom := r.the_geom; |
|---|
| 86 | id := id+1; |
|---|
| 87 | geom.id := id; |
|---|
| 88 | RETURN NEXT geom; |
|---|
| 89 | END LOOP; |
|---|
| 90 | |
|---|
| 91 | prev = v_id; |
|---|
| 92 | END LOOP; |
|---|
| 93 | RETURN; |
|---|
| 94 | END; |
|---|
| 95 | $$ |
|---|
| 96 | LANGUAGE 'plpgsql' VOLATILE STRICT; |
|---|
| 97 | |
|---|
| 98 | ------------------------------------------------------ |
|---|
| 99 | -- Returns TSP solution as a set of vertices connected |
|---|
| 100 | -- with A* paths. |
|---|
| 101 | -- For directed graphs. |
|---|
| 102 | -- |
|---|
| 103 | -- Last changes: 14.02.2008 |
|---|
| 104 | ------------------------------------------------------ |
|---|
| 105 | CREATE OR REPLACE FUNCTION tsp_astar_directed( |
|---|
| 106 | geom_table varchar,ids varchar, source integer, delta float8, dir boolean, rc boolean) |
|---|
| 107 | RETURNS SETOF GEOMS AS |
|---|
| 108 | $$ |
|---|
| 109 | DECLARE |
|---|
| 110 | r record; |
|---|
| 111 | path_result record; |
|---|
| 112 | v_id integer; |
|---|
| 113 | prev integer; |
|---|
| 114 | geom geoms; |
|---|
| 115 | |
|---|
| 116 | query text; |
|---|
| 117 | |
|---|
| 118 | id integer; |
|---|
| 119 | BEGIN |
|---|
| 120 | |
|---|
| 121 | id :=0; |
|---|
| 122 | prev := source; |
|---|
| 123 | query := 'SELECT vertex_id FROM tsp(''select distinct source::integer '|| |
|---|
| 124 | 'as source_id, x1::double precision as x, y1::double precision as y '; |
|---|
| 125 | |
|---|
| 126 | IF rc THEN query := query || ' , reverse_cost '; |
|---|
| 127 | END IF; |
|---|
| 128 | |
|---|
| 129 | query := query || 'from ' || quote_ident(geom_table) || ' where source in (' || |
|---|
| 130 | ids || ') UNION select distinct target as source_id, x1::double precision as x, y1::double precision as y '; |
|---|
| 131 | |
|---|
| 132 | IF rc THEN query := query || ' , reverse_cost '; |
|---|
| 133 | END IF; |
|---|
| 134 | |
|---|
| 135 | query := query || 'from tsp_test where target in ('||ids||')'', '''|| ids ||''', '|| source ||')'; |
|---|
| 136 | |
|---|
| 137 | FOR path_result IN EXECUTE query |
|---|
| 138 | LOOP |
|---|
| 139 | |
|---|
| 140 | v_id = path_result.vertex_id; |
|---|
| 141 | |
|---|
| 142 | FOR r IN EXECUTE 'SELECT gid, the_geom FROM astar_sp_delta_directed( ''' || |
|---|
| 143 | quote_ident(geom_table) ||''', '|| v_id ||', '|| |
|---|
| 144 | prev ||','||delta||', '''||text(dir)||''', '''||text(rc)||''')' LOOP |
|---|
| 145 | geom.gid := r.gid; |
|---|
| 146 | geom.the_geom := r.the_geom; |
|---|
| 147 | id := id+1; |
|---|
| 148 | geom.id := id; |
|---|
| 149 | RETURN NEXT geom; |
|---|
| 150 | END LOOP; |
|---|
| 151 | |
|---|
| 152 | prev = v_id; |
|---|
| 153 | END LOOP; |
|---|
| 154 | RETURN; |
|---|
| 155 | END; |
|---|
| 156 | $$ |
|---|
| 157 | LANGUAGE 'plpgsql' VOLATILE STRICT; |
|---|
| 158 | |
|---|
| 159 | |
|---|
| 160 | ------------------------------------------------------ |
|---|
| 161 | -- Returns TSP solution as a set of vertices connected |
|---|
| 162 | -- with Dijkstra paths. |
|---|
| 163 | ------------------------------------------------------ |
|---|
| 164 | CREATE OR REPLACE FUNCTION tsp_dijkstra( |
|---|
| 165 | geom_table varchar,ids varchar, source integer) |
|---|
| 166 | RETURNS SETOF GEOMS AS |
|---|
| 167 | $$ |
|---|
| 168 | DECLARE |
|---|
| 169 | r record; |
|---|
| 170 | path_result record; |
|---|
| 171 | v_id integer; |
|---|
| 172 | prev integer; |
|---|
| 173 | geom geoms; |
|---|
| 174 | |
|---|
| 175 | id integer; |
|---|
| 176 | BEGIN |
|---|
| 177 | |
|---|
| 178 | id :=0; |
|---|
| 179 | prev := source; |
|---|
| 180 | FOR path_result IN EXECUTE 'SELECT vertex_id FROM tsp(''select distinct source::integer as source_id, x(startpoint(the_geom)), y(startpoint(the_geom)) from ' || |
|---|
| 181 | quote_ident(geom_table) || ' where source in (' || |
|---|
| 182 | ids || ') UNION select distinct target as source_id, x(endpoint(the_geom)), y(endpoint(the_geom)) from tsp_test where target in ('||ids||')'', '''|| ids ||''', '|| source ||')' LOOP |
|---|
| 183 | |
|---|
| 184 | v_id = path_result.vertex_id; |
|---|
| 185 | |
|---|
| 186 | |
|---|
| 187 | FOR r IN EXECUTE 'SELECT gid, the_geom FROM dijkstra_sp_delta( ''' || |
|---|
| 188 | quote_ident(geom_table) ||''', '|| v_id ||', '|| |
|---|
| 189 | prev ||',0.03)' LOOP |
|---|
| 190 | geom.gid := r.gid; |
|---|
| 191 | geom.the_geom := r.the_geom; |
|---|
| 192 | id := id+1; |
|---|
| 193 | geom.id := id; |
|---|
| 194 | RETURN NEXT geom; |
|---|
| 195 | END LOOP; |
|---|
| 196 | |
|---|
| 197 | prev = v_id; |
|---|
| 198 | END LOOP; |
|---|
| 199 | RETURN; |
|---|
| 200 | END; |
|---|
| 201 | $$ |
|---|
| 202 | LANGUAGE 'plpgsql' VOLATILE STRICT; |
|---|
| 203 | |
|---|
| 204 | ------------------------------------------------------ |
|---|
| 205 | -- Returns TSP solution as a set of vertices connected |
|---|
| 206 | -- with Dijkstra paths. |
|---|
| 207 | -- For directed graphs. |
|---|
| 208 | -- |
|---|
| 209 | -- Last changes: 14.02.2008 |
|---|
| 210 | ------------------------------------------------------ |
|---|
| 211 | CREATE OR REPLACE FUNCTION tsp_dijkstra_directed( |
|---|
| 212 | geom_table varchar,ids varchar, source integer, delta float8, dir boolean, rc boolean) |
|---|
| 213 | RETURNS SETOF GEOMS AS |
|---|
| 214 | $$ |
|---|
| 215 | DECLARE |
|---|
| 216 | r record; |
|---|
| 217 | path_result record; |
|---|
| 218 | v_id integer; |
|---|
| 219 | prev integer; |
|---|
| 220 | geom geoms; |
|---|
| 221 | |
|---|
| 222 | query text; |
|---|
| 223 | |
|---|
| 224 | id integer; |
|---|
| 225 | BEGIN |
|---|
| 226 | |
|---|
| 227 | id :=0; |
|---|
| 228 | prev := source; |
|---|
| 229 | |
|---|
| 230 | query := 'SELECT vertex_id FROM tsp(''select distinct source::integer as source_id, '|| |
|---|
| 231 | 'x(startpoint(the_geom)), y(startpoint(the_geom))'; |
|---|
| 232 | |
|---|
| 233 | IF rc THEN query := query || ' , reverse_cost '; |
|---|
| 234 | END IF; |
|---|
| 235 | |
|---|
| 236 | query := query || ' from ' || quote_ident(geom_table) || ' where source in (' || |
|---|
| 237 | ids || ') UNION select distinct target as source_id, x(endpoint(the_geom)), y(endpoint(the_geom))'; |
|---|
| 238 | |
|---|
| 239 | IF rc THEN query := query || ' , reverse_cost '; |
|---|
| 240 | END IF; |
|---|
| 241 | |
|---|
| 242 | query := query || 'from tsp_test where target in ('||ids||')'', '''|| ids ||''', '|| source ||')'; |
|---|
| 243 | |
|---|
| 244 | FOR path_result IN EXECUTE query |
|---|
| 245 | LOOP |
|---|
| 246 | |
|---|
| 247 | v_id = path_result.vertex_id; |
|---|
| 248 | |
|---|
| 249 | |
|---|
| 250 | FOR r IN EXECUTE 'SELECT gid, the_geom FROM dijkstra_sp_delta_directed( ''' || |
|---|
| 251 | quote_ident(geom_table) ||''', '|| v_id ||', '|| |
|---|
| 252 | prev ||','||delta||', '''||text(dir)||''', '''||text(rc)||''')' LOOP |
|---|
| 253 | geom.gid := r.gid; |
|---|
| 254 | geom.the_geom := r.the_geom; |
|---|
| 255 | id := id+1; |
|---|
| 256 | geom.id := id; |
|---|
| 257 | RETURN NEXT geom; |
|---|
| 258 | END LOOP; |
|---|
| 259 | |
|---|
| 260 | prev = v_id; |
|---|
| 261 | END LOOP; |
|---|
| 262 | RETURN; |
|---|
| 263 | END; |
|---|
| 264 | $$ |
|---|
| 265 | LANGUAGE 'plpgsql' VOLATILE STRICT; |
|---|
| 266 | |
|---|
| 267 | -- COMMIT; |
|---|
