GRASS Programmer's Manual  6.4.2(2012)
timetables.c
Go to the documentation of this file.
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 }
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines