GRASS Programmer's Manual
6.4.2(2012)
|
00001 00016 #include <stdio.h> 00017 #include <stdlib.h> 00018 #include <grass/gis.h> 00019 #include <grass/Vect.h> 00020 #include <grass/dbmi.h> 00021 #include <grass/glocale.h> 00022 #include <grass/dgl/graph.h> 00023 #include <grass/neta.h> 00024 00036 int NetA_init_distinct(dbDriver * driver, dbString * sql, int **lengths, 00037 int **ids) 00038 { 00039 int count, last, cur, result, index, more; 00040 dbCursor cursor; 00041 dbTable *table; 00042 dbColumn *column; 00043 dbValue *value; 00044 00045 if (db_open_select_cursor(driver, sql, &cursor, DB_SEQUENTIAL) != DB_OK) { 00046 G_warning(_("Unable to open select cursor: %s"), db_get_string(sql)); 00047 return -1; 00048 } 00049 /*TODO: check column types */ 00050 00051 count = last = 0; 00052 /*count number of distinct routes */ 00053 table = db_get_cursor_table(&cursor); 00054 column = db_get_table_column(table, 0); 00055 while (db_fetch(&cursor, DB_NEXT, &more) == DB_OK && more) { 00056 value = db_get_column_value(column); 00057 cur = db_get_value_int(value); 00058 if (count == 0 || cur != last) { 00059 last = cur; 00060 count++; 00061 } 00062 } 00063 result = count; 00064 db_close_cursor(&cursor); 00065 00066 *lengths = (int *)G_calloc(count, sizeof(int)); 00067 *ids = (int *)G_calloc(count, sizeof(int)); 00068 if (!*lengths || !*ids) { 00069 G_warning(_("Out of memory")); 00070 return -1; 00071 } 00072 db_open_select_cursor(driver, sql, &cursor, DB_SEQUENTIAL); 00073 count = index = 0; 00074 /*calculate the lengths of the routes */ 00075 table = db_get_cursor_table(&cursor); 00076 column = db_get_table_column(table, 0); 00077 while (db_fetch(&cursor, DB_NEXT, &more) == DB_OK && more) { 00078 value = db_get_column_value(column); 00079 cur = db_get_value_int(value); 00080 if (count != 0 && cur != last) 00081 index++; 00082 if (count == 0 || cur != last) 00083 (*ids)[index] = cur; 00084 (*lengths)[index]++; 00085 last = cur; 00086 count++; 00087 } 00088 return result; 00089 } 00090 00091 static int cmp_int(const void *a, const void *b) 00092 { 00093 return *(int *)a - *(int *)b; 00094 } 00095 00113 int NetA_init_timetable_from_db(struct Map_info *In, int route_layer, 00114 int walk_layer, char *route_id, char *times, 00115 char *to_stop, char *walk_length, 00116 neta_timetable * timetable, int **route_ids, 00117 int **stop_ids) 00118 { 00119 int more, i, stop, route, time, *stop_pnt, stop1, stop2; 00120 dbString sql; 00121 dbCursor cursor; 00122 dbTable *table; 00123 dbColumn *column1, *column2, *column3; 00124 dbValue *value; 00125 char buf[2000]; 00126 00127 dbDriver *driver; 00128 struct field_info *Fi; 00129 00130 Fi = Vect_get_field(In, route_layer); 00131 driver = db_start_driver_open_database(Fi->driver, Fi->database); 00132 if (driver == NULL) 00133 G_fatal_error(_("Unable to open database <%s> by driver <%s>"), 00134 Fi->database, Fi->driver); 00135 00136 00137 db_init_string(&sql); 00138 sprintf(buf, "select %s from %s order by %s", route_id, Fi->table, 00139 route_id); 00140 db_set_string(&sql, buf); 00141 timetable->routes = 00142 NetA_init_distinct(driver, &sql, &(timetable->route_length), 00143 route_ids); 00144 if (timetable->routes < 0) 00145 return 1; 00146 00147 sprintf(buf, "select %s from %s order by %s", Fi->key, Fi->table, 00148 Fi->key); 00149 db_set_string(&sql, buf); 00150 timetable->stops = 00151 NetA_init_distinct(driver, &sql, &(timetable->stop_length), stop_ids); 00152 if (timetable->stops < 0) 00153 return 1; 00154 00155 timetable->route_stops = 00156 (int **)G_calloc(timetable->routes, sizeof(int *)); 00157 timetable->route_times = 00158 (int **)G_calloc(timetable->routes, sizeof(int *)); 00159 timetable->stop_routes = 00160 (int **)G_calloc(timetable->stops, sizeof(int *)); 00161 timetable->stop_times = (int **)G_calloc(timetable->stops, sizeof(int *)); 00162 timetable->walk_length = (int *)G_calloc(timetable->stops, sizeof(int)); 00163 timetable->walk_stops = (int **)G_calloc(timetable->stops, sizeof(int *)); 00164 timetable->walk_times = (int **)G_calloc(timetable->stops, sizeof(int *)); 00165 if (!timetable->route_stops || !timetable->route_times || 00166 !timetable->stop_routes || !timetable->stop_times || 00167 !timetable->walk_length) { 00168 G_warning(_("Out of memory")); 00169 return 2; 00170 } 00171 00172 for (i = 0; i < timetable->routes; i++) { 00173 timetable->route_stops[i] = 00174 (int *)G_calloc(timetable->route_length[i], sizeof(int)); 00175 timetable->route_times[i] = 00176 (int *)G_calloc(timetable->route_length[i], sizeof(int)); 00177 if (!timetable->route_stops[i] || !timetable->route_times[i]) { 00178 G_warning(_("Out of memory")); 00179 return 2; 00180 } 00181 00182 timetable->route_length[i] = 0; 00183 } 00184 00185 for (i = 0; i < timetable->stops; i++) { 00186 timetable->stop_routes[i] = 00187 (int *)G_calloc(timetable->stop_length[i], sizeof(int)); 00188 timetable->stop_times[i] = 00189 (int *)G_calloc(timetable->stop_length[i], sizeof(int)); 00190 if (!timetable->stop_routes[i] || !timetable->stop_times[i]) { 00191 G_warning(_("Out of memory")); 00192 return 2; 00193 } 00194 timetable->walk_length[i] = 0; 00195 timetable->stop_length[i] = 0; 00196 } 00197 00198 sprintf(buf, "select %s, %s, %s from %s order by %s", Fi->key, route_id, 00199 times, Fi->table, times); 00200 db_set_string(&sql, buf); 00201 00202 if (db_open_select_cursor(driver, &sql, &cursor, DB_SEQUENTIAL) != DB_OK) { 00203 G_warning(_("Unable to open select cursor: %s"), db_get_string(&sql)); 00204 return 1; 00205 } 00206 00207 00208 table = db_get_cursor_table(&cursor); 00209 column1 = db_get_table_column(table, 0); 00210 column2 = db_get_table_column(table, 1); 00211 column3 = db_get_table_column(table, 2); 00212 while (db_fetch(&cursor, DB_NEXT, &more) == DB_OK && more) { 00213 value = db_get_column_value(column1); 00214 stop = db_get_value_int(value); 00215 value = db_get_column_value(column2); 00216 route = db_get_value_int(value); 00217 value = db_get_column_value(column3); 00218 time = db_get_value_int(value); 00219 stop = 00220 (int *)bsearch(&stop, *stop_ids, timetable->stops, sizeof(int), 00221 cmp_int) - (*stop_ids); 00222 route = 00223 (int *)bsearch(&route, *route_ids, timetable->routes, sizeof(int), 00224 cmp_int) - (*route_ids); 00225 00226 timetable->stop_routes[stop][timetable->stop_length[stop]] = route; 00227 timetable->stop_times[stop][timetable->stop_length[stop]++] = time; 00228 00229 timetable->route_stops[route][timetable->route_length[route]] = stop; 00230 timetable->route_times[route][timetable->route_length[route]++] = 00231 time; 00232 } 00233 db_close_cursor(&cursor); 00234 00235 if (walk_layer != -1) { 00236 00237 Fi = Vect_get_field(In, walk_layer); 00238 sprintf(buf, "select %s, %s, %s from %s", Fi->key, to_stop, 00239 walk_length, Fi->table); 00240 db_set_string(&sql, buf); 00241 00242 if (db_open_select_cursor(driver, &sql, &cursor, DB_SEQUENTIAL) != 00243 DB_OK) { 00244 G_warning(_("Unable to open select cursor: %s"), 00245 db_get_string(&sql)); 00246 return 1; 00247 } 00248 00249 table = db_get_cursor_table(&cursor); 00250 column1 = db_get_table_column(table, 0); 00251 column2 = db_get_table_column(table, 1); 00252 while (db_fetch(&cursor, DB_NEXT, &more) == DB_OK && more) { 00253 value = db_get_column_value(column2); 00254 stop = db_get_value_int(value); 00255 stop_pnt = 00256 (int *)bsearch(&stop, *stop_ids, timetable->stops, 00257 sizeof(int), cmp_int); 00258 if (stop_pnt) { 00259 value = db_get_column_value(column1); 00260 stop = db_get_value_int(value); 00261 stop_pnt = 00262 (int *)bsearch(&stop, *stop_ids, timetable->stops, 00263 sizeof(int), cmp_int); 00264 if (stop_pnt) { 00265 stop = stop_pnt - (*stop_ids); 00266 timetable->walk_length[stop]++; 00267 } 00268 } 00269 } 00270 db_close_cursor(&cursor); 00271 00272 for (i = 0; i < timetable->stops; i++) { 00273 timetable->walk_stops[i] = 00274 (int *)G_calloc(timetable->walk_length[i], sizeof(int)); 00275 timetable->walk_times[i] = 00276 (int *)G_calloc(timetable->walk_length[i], sizeof(int)); 00277 if (!timetable->walk_stops[i] || !timetable->walk_times[i]) { 00278 G_warning(_("Out of memory")); 00279 return 2; 00280 } 00281 timetable->walk_length[i] = 0; 00282 } 00283 00284 if (db_open_select_cursor(driver, &sql, &cursor, DB_SEQUENTIAL) != 00285 DB_OK) { 00286 G_warning(_("Unable to open select cursor: %s"), 00287 db_get_string(&sql)); 00288 return 1; 00289 } 00290 00291 table = db_get_cursor_table(&cursor); 00292 column1 = db_get_table_column(table, 0); 00293 column2 = db_get_table_column(table, 1); 00294 column3 = db_get_table_column(table, 2); 00295 while (db_fetch(&cursor, DB_NEXT, &more) == DB_OK && more) { 00296 value = db_get_column_value(column2); 00297 stop = db_get_value_int(value); 00298 stop_pnt = 00299 (int *)bsearch(&stop, *stop_ids, timetable->stops, 00300 sizeof(int), cmp_int); 00301 if (stop_pnt) { 00302 stop2 = stop_pnt - (*stop_ids); 00303 value = db_get_column_value(column1); 00304 stop = db_get_value_int(value); 00305 stop_pnt = 00306 (int *)bsearch(&stop, *stop_ids, timetable->stops, 00307 sizeof(int), cmp_int); 00308 if (stop_pnt) { 00309 stop1 = stop_pnt - (*stop_ids); 00310 value = db_get_column_value(column3); 00311 time = db_get_value_int(value); 00312 timetable->walk_stops[stop1][timetable-> 00313 walk_length[stop1]] = stop2; 00314 timetable->walk_times[stop1][timetable-> 00315 walk_length[stop1]++] = time; 00316 } 00317 } 00318 } 00319 db_close_cursor(&cursor); 00320 } 00321 db_close_database_shutdown_driver(driver); 00322 00323 return 0; 00324 } 00325 00326 typedef struct 00327 { 00328 int v; 00329 int conns; 00330 } neta_heap_data; 00331 00332 static neta_heap_data *new_heap_data(int conns, int v) 00333 { 00334 neta_heap_data *d = 00335 (neta_heap_data *) G_calloc(1, sizeof(neta_heap_data)); 00336 d->v = v; 00337 d->conns = conns; 00338 return d; 00339 } 00340 00355 void NetA_update_dijkstra(int old_conns, int new_conns, int to, int new_dst, 00356 int v, int route, int rows, int update, 00357 neta_timetable_result * result, dglHeap_s * heap) 00358 { 00359 if (result->dst[new_conns][to] == -1 || 00360 result->dst[new_conns][to] > new_dst) { 00361 result->dst[new_conns][to] = new_dst; 00362 result->prev_stop[new_conns][to] = v; 00363 result->prev_route[new_conns][to] = route; 00364 result->prev_conn[new_conns][to] = old_conns; 00365 if (update) { 00366 dglHeapData_u heap_data; 00367 00368 heap_data.pv = (void *)new_heap_data(new_conns, to); 00369 dglHeapInsertMin(heap, new_dst, ' ', heap_data); 00370 } 00371 } 00372 } 00373 00392 int NetA_timetable_shortest_path(neta_timetable * timetable, int from_stop, 00393 int to_stop, int start_time, int min_change, 00394 int max_changes, int walking_change, 00395 neta_timetable_result * result) 00396 { 00397 int i, j; 00398 dglHeap_s heap; 00399 00400 int opt_conns, rows = 1; 00401 00402 if (max_changes != -1) 00403 rows = max_changes + 2; 00404 00405 result->rows = rows; 00406 result->dst = (int **)G_calloc(rows, sizeof(int *)); 00407 result->prev_stop = (int **)G_calloc(rows, sizeof(int *)); 00408 result->prev_route = (int **)G_calloc(rows, sizeof(int *)); 00409 result->prev_conn = (int **)G_calloc(rows, sizeof(int *)); 00410 00411 if (!result->dst || !result->prev_stop || !result->prev_route || 00412 !result->prev_conn) { 00413 G_warning(_("Out of memory")); 00414 return -1; 00415 } 00416 00417 for (i = 0; i < rows; i++) { 00418 result->dst[i] = (int *)G_calloc(timetable->stops, sizeof(int)); 00419 result->prev_stop[i] = (int *)G_calloc(timetable->stops, sizeof(int)); 00420 result->prev_route[i] = 00421 (int *)G_calloc(timetable->stops, sizeof(int)); 00422 result->prev_conn[i] = (int *)G_calloc(timetable->stops, sizeof(int)); 00423 if (!result->dst[i] || !result->prev_stop[i] || !result->prev_route[i] 00424 || !result->prev_conn[i]) { 00425 G_warning(_("Out of memory")); 00426 return -1; 00427 } 00428 } 00429 00430 if (from_stop == to_stop) { 00431 result->dst[0][to_stop] = start_time; 00432 result->prev_route[0][to_stop] = result->prev_stop[0][to_stop] = -1; 00433 result->routes = 0; 00434 return start_time; 00435 } 00436 00437 result->routes = -1; 00438 if (walking_change > 1) 00439 walking_change = 1; 00440 if (walking_change < 0 || max_changes == -1) 00441 walking_change = 0; 00442 dglHeapInit(&heap); 00443 00444 for (i = 0; i < rows; i++) 00445 for (j = 0; j < timetable->stops; j++) 00446 result->dst[i][j] = result->prev_stop[i][j] = 00447 result->prev_route[i][j] = -1; 00448 00449 result->dst[0][from_stop] = start_time - min_change; 00450 result->prev_stop[0][from_stop] = result->prev_route[0][from_stop] = -1; 00451 dglHeapData_u heap_data; 00452 00453 heap_data.pv = (void *)new_heap_data(0, from_stop); 00454 dglHeapInsertMin(&heap, start_time - min_change, ' ', heap_data); 00455 00456 while (1) { 00457 dglInt32_t v, dist, conns; 00458 dglHeapNode_s heap_node; 00459 int new_conns, walk_conns, update; 00460 00461 if (!dglHeapExtractMin(&heap, &heap_node)) 00462 break; 00463 v = ((neta_heap_data *) (heap_node.value.pv))->v; 00464 conns = ((neta_heap_data *) (heap_node.value.pv))->conns; 00465 dist = heap_node.key; 00466 00467 if (dist > result->dst[conns][v]) 00468 continue; 00469 if (v == to_stop) 00470 break; 00471 new_conns = (max_changes == -1) ? 0 : (conns + 1); 00472 walk_conns = conns + walking_change; 00473 00474 /*walking */ 00475 if (walk_conns < rows) { 00476 /* update = (max_changes == -1 || walk_conns <= max_changes); */ 00477 update = 1; 00478 for (i = 0; i < timetable->walk_length[v]; i++) { 00479 int to = timetable->walk_stops[v][i]; 00480 int new_dst = dist + timetable->walk_times[v][i]; 00481 00482 NetA_update_dijkstra(conns, walk_conns, to, new_dst, v, -2, 00483 rows, update, result, &heap); 00484 } 00485 } 00486 00487 if (new_conns >= rows) 00488 continue; 00489 /*process all routes arriving after dist+min_change */ 00490 for (i = 0; i < timetable->stop_length[v]; i++) 00491 if (timetable->stop_times[v][i] >= dist + min_change) { 00492 int route = timetable->stop_routes[v][i]; 00493 00494 /*find the index of v on the route */ 00495 for (j = 0; j < timetable->route_length[route]; j++) 00496 if (timetable->route_stops[route][j] == v) 00497 break; 00498 j++; 00499 for (; j < timetable->route_length[route]; j++) { 00500 int to = timetable->route_stops[route][j]; 00501 00502 NetA_update_dijkstra(conns, new_conns, to, 00503 timetable->route_times[route][j], v, 00504 route, rows, 1, result, &heap); 00505 } 00506 } 00507 } 00508 dglHeapFree(&heap, NULL); 00509 opt_conns = -1; 00510 for (i = 0; i < rows; i++) 00511 if (result->dst[i][to_stop] != -1 && 00512 (opt_conns == -1 || 00513 result->dst[opt_conns][to_stop] > result->dst[i][to_stop])) 00514 opt_conns = i; 00515 result->routes = opt_conns; 00516 00517 if (opt_conns != -1) 00518 return result->dst[opt_conns][to_stop]; 00519 return -1; 00520 } 00521 00534 int NetA_timetable_get_route_time(neta_timetable * timetable, int stop, 00535 int route) 00536 { 00537 int i; 00538 00539 for (i = 0; i < timetable->route_length[route]; i++) 00540 if (timetable->route_stops[route][i] == stop) 00541 return timetable->route_times[route][i]; 00542 return -1; 00543 } 00544 00550 void NetA_timetable_result_release(neta_timetable_result * result) 00551 { 00552 int i; 00553 00554 for (i = 0; i < result->rows; i++) { 00555 G_free(result->dst[i]); 00556 G_free(result->prev_stop[i]); 00557 G_free(result->prev_route[i]); 00558 } 00559 G_free(result->dst); 00560 G_free(result->prev_stop); 00561 G_free(result->prev_route); 00562 }