Changeset 106
- Timestamp:
- 02/14/08 10:42:26 (9 months ago)
- Files:
-
- trunk/core/sql/routing_core_wrappers.sql (modified) (16 diffs)
- trunk/core/src/boost_wrapper.cpp (modified) (1 diff)
- trunk/core/src/shooting_star_boost_wrapper.cpp (modified) (5 diffs)
- trunk/core/src/shooting_star_search.hpp (modified) (2 diffs)
- trunk/extra/driving_distance/sql/routing_dd_wrappers.sql (modified) (1 diff)
- trunk/extra/tsp/sql/routing_tsp_wrappers.sql (modified) (4 diffs)
Legend:
- Unmodified
- Added
- Removed
- Modified
- Copied
- Moved
trunk/core/sql/routing_core_wrappers.sql
r105 r106 18 18 19 19 20 -- TODO: use spatial index when possible21 -- TODO: make variable names more consistent22 23 -- Geometry schema description:24 -- gid25 -- source26 -- target27 -- edge_id28 29 20 -- BEGIN; 30 21 … … 39 30 -- For each vertex in the vertices table, set a point geometry which is 40 31 -- the corresponding line start or line end point 32 -- 33 -- Last changes: 14.02.2008 41 34 ----------------------------------------------------------------------- 42 35 CREATE OR REPLACE FUNCTION add_vertices_geometry(geom_table varchar) … … 81 74 -- of a new point or an existing point. Tolerance is the minimal distance 82 75 -- between existing points and the new point to create a new point. 76 -- 77 -- Last changes: 14.02.2008 83 78 ----------------------------------------------------------------------- 84 79 CREATE OR REPLACE FUNCTION point_to_id(point geometry, … … 198 193 -- Update the cost column from the edges table, from the length of 199 194 -- all lines which belong to an edge. 200 ----------------------------------------------------------------------- 201 -- FIXME: directed or not ? 195 -- 196 -- Last changes: 14.02.2008 197 ----------------------------------------------------------------------- 202 198 CREATE OR REPLACE FUNCTION update_cost_from_distance(geom_table varchar) 203 199 RETURNS VOID AS … … 236 232 -- Compute the shortest path using edges table, and return 237 233 -- the result as a set of (gid integer, the_geom geometry) records. 234 -- 235 -- Last changes: 14.02.2008 238 236 ----------------------------------------------------------------------- 239 237 CREATE OR REPLACE FUNCTION dijkstra_sp( … … 277 275 -- Compute the shortest path using edges table, and return 278 276 -- the result as a set of (gid integer, the_geom geometry) records. 277 -- 278 -- Last changes: 14.02.2008 279 279 ----------------------------------------------------------------------- 280 280 CREATE OR REPLACE FUNCTION dijkstra_sp_directed( … … 326 326 -- the result as a set of (gid integer, the_geom geometry) records. 327 327 -- Also data clipping added to improve function performance. 328 -- 329 -- Last changes: 14.02.2008 328 330 ----------------------------------------------------------------------- 329 331 CREATE OR REPLACE FUNCTION astar_sp_delta( … … 373 375 -- the result as a set of (gid integer, the_geom geometry) records. 374 376 -- Also data clipping added to improve function performance. 377 -- 378 -- Last changes: 14.02.2008 375 379 ----------------------------------------------------------------------- 376 380 CREATE OR REPLACE FUNCTION astar_sp_delta_directed( … … 522 526 -- Also data clipping added to improve function performance. 523 527 -- Cost column name can be specified (last parameter) 528 -- 529 -- Last changes: 14.02.2008 524 530 ----------------------------------------------------------------------- 525 531 CREATE OR REPLACE FUNCTION astar_sp_delta_cc( … … 571 577 -- Also data clipping added to improve function performance. 572 578 -- Cost column name can be specified (last parameter) 579 -- 580 -- Last changes: 14.02.2008 573 581 ----------------------------------------------------------------------- 574 582 CREATE OR REPLACE FUNCTION astar_sp_delta_cc_directed( … … 711 719 -- the result as a set of (gid integer, the_geom geometry) records. 712 720 -- Also data clipping added to improve function performance. 721 -- 722 -- Last changes: 14.02.2008 713 723 ----------------------------------------------------------------------- 714 724 CREATE OR REPLACE FUNCTION dijkstra_sp_delta( … … 756 766 -- the result as a set of (gid integer, the_geom geometry) records. 757 767 -- Also data clipping added to improve function performance. 768 -- 769 -- Last changes: 14.02.2008 758 770 ----------------------------------------------------------------------- 759 771 CREATE OR REPLACE FUNCTION dijkstra_sp_delta_directed( … … 892 904 -- Also data clipping added to improve function performance 893 905 -- (specified by lower left and upper right box corners). 906 -- 907 -- Last changes: 14.02.2008 894 908 ----------------------------------------------------------------------- 895 909 CREATE OR REPLACE FUNCTION astar_sp_bbox( … … 945 959 -- Also data clipping added to improve function performance 946 960 -- (specified by lower left and upper right box corners). 961 -- 962 -- Last changes: 14.02.2008 947 963 ----------------------------------------------------------------------- 948 964 CREATE OR REPLACE FUNCTION astar_sp_bbox_directed( … … 1054 1070 -- the result as a set of (gid integer, the_geom geometry) records. 1055 1071 -- Also data clipping added to improve function performance. 1072 -- 1073 -- Last changes: 14.02.2008 1056 1074 ----------------------------------------------------------------------- 1057 1075 CREATE OR REPLACE FUNCTION astar_sp_directed( … … 1106 1124 -- Compute the shortest path using edges table, and return 1107 1125 -- the result as a set of (gid integer, the_geom geometry) records. 1126 -- 1127 -- Last changes: 14.02.2008 1108 1128 ----------------------------------------------------------------------- 1109 1129 CREATE OR REPLACE FUNCTION shootingstar_sp( trunk/core/src/boost_wrapper.cpp
r105 r106 189 189 return EXIT_SUCCESS; 190 190 } 191 192 #if 0193 194 // Testing function195 196 #define NUM_EDGES 100197 int main() {198 199 edge_t *e;200 201 e = (edge_t *)malloc(NUM_EDGES * sizeof(edge_t));202 if (!e)203 return -1;204 205 for (int i = 0; i < NUM_EDGES; i++)206 {207 e[i].id = i;208 e[i].source = i;209 e[i].target = (i + 1 > NUM_EDGES) ? 0 : i + 1;210 e[i].cost = 1;211 }212 213 char *err_msg = NULL;214 path_element_t *path;215 int ret;216 int path_count;217 218 int final_edges = NUM_EDGES - 1;219 220 ret = boost_dijkstra(e, NUM_EDGES, 0, final_edges, 1, 0, &path, &path_count, &err_msg);221 222 if (ret < 0)223 {224 printf("Error: %s\n", err_msg);225 226 } else {227 printf("Path is :\n");228 for (int i = 0; i < path_count; i++)229 {230 printf("Step %i vertex_id %i \n", i, path[i].vertex_id);231 printf(" edge_id %i \n", path[i].edge_id);232 printf(" cost %f \n", path[i].cost);233 }234 free(path);235 }236 printf("\n");237 free(e);238 }239 #endiftrunk/core/src/shooting_star_boost_wrapper.cpp
r92 r106 87 87 }; 88 88 89 89 // Heuristic function 90 90 template <class Graph, class CostType> 91 91 class distance_heuristic … … 112 112 113 113 114 // Adds an edge to the graph 115 // Also copies all attributes and adjacent edges 114 116 template <class G, class E> 115 117 static void … … 155 157 } 156 158 159 // Main Shooting* function. 160 // It renumbers vertices, fills the graph with edges, 161 // calculates a route and return a result. 157 162 int 158 163 boost_shooting_star(edge_shooting_star_t *edges_array, unsigned int count, … … 224 229 edges_array[j].t_x, edges_array[j].t_y, adjacent_edges); 225 230 231 // if the edge is not directed or if it is directed and has reverse cost 226 232 if (!directed || (directed && has_reverse_cost)) 227 233 { … … 313 319 try 314 320 { 321 //calling Shooting* search 315 322 shooting_star_search 316 323 (graph, source_edge, trunk/core/src/shooting_star_search.hpp
r105 r106 231 231 232 232 namespace detail { 233 233 234 // Shooting* visitor 235 // based on BFS visitor concept from BGL 234 236 template <class AStarHeuristic, class UniformCostVisitor, 235 237 class UpdatableQueue, class PredecessorMap, … … 423 425 typedef typename graph_traits<VertexAndEdgeListGraph>::edge_descriptor 424 426 Edge; 425 427 428 // Queue to store the list of edges to examine. 429 // I really hate this queue for what it does with the memory sometimes. 426 430 typedef mutable_queue<Edge, std::vector<Edge>, IndirectCmp, IndexMap> 427 431 MutableQueue; trunk/extra/driving_distance/sql/routing_dd_wrappers.sql
r105 r106 21 21 ---------------------------------------------------------- 22 22 -- Draws an alpha shape around given set of points. 23 -- 24 -- Last changes: 14.02.2008 23 25 ---------------------------------------------------------- 24 26 CREATE OR REPLACE FUNCTION points_as_polygon(query varchar) trunk/extra/tsp/sql/routing_tsp_wrappers.sql
r105 r106 22 22 ----------------------------------------------------- 23 23 -- Returns TSP solution as a set of vertex ids 24 -- 25 -- Last changes: 14.02.2008 24 26 ----------------------------------------------------- 25 27 CREATE OR REPLACE FUNCTION tsp_ids(geom_table varchar, … … 52 54 -- Returns TSP solution as a set of vertices connected 53 55 -- with A* paths 56 -- 57 -- Last changes: 14.02.2008 54 58 ------------------------------------------------------ 55 59 CREATE OR REPLACE FUNCTION tsp_astar( … … 96 100 -- with A* paths. 97 101 -- For directed graphs. 102 -- 103 -- Last changes: 14.02.2008 98 104 ------------------------------------------------------ 99 105 CREATE OR REPLACE FUNCTION tsp_astar_directed( … … 195 201 -- with Dijkstra paths. 196 202 -- For directed graphs. 203 -- 204 -- Last changes: 14.02.2008 197 205 ------------------------------------------------------ 198 206 CREATE OR REPLACE FUNCTION tsp_dijkstra_directed(
