GRASS GIS 8 Programmer's Manual  8.4.0dev(2024)-6da4f45b8e
timetables.c
Go to the documentation of this file.
1 /*!
2  \file vector/neta/timetables.c
3 
4  \brief Network Analysis library - timetables
5 
6  Shortest path using timetables.
7 
8  (C) 2009-2010 by Daniel Bundala, and the GRASS Development Team
9 
10  This program is free software under the GNU General Public License
11  (>=v2). Read the file COPYING that comes with GRASS for details.
12 
13  \author Daniel Bundala (Google Summer of Code 2009)
14  */
15 
16 #include <stdio.h>
17 #include <stdlib.h>
18 #include <grass/gis.h>
19 #include <grass/vector.h>
20 #include <grass/dbmi.h>
21 #include <grass/glocale.h>
22 #include <grass/dgl/graph.h>
23 #include <grass/neta.h>
24 
25 /*!
26  \brief Get number of distinct elements
27 
28  \param driver DB driver
29  \param sql SQl string
30  \param[out] list of lengths
31  \param[out] list of ids
32 
33  \return number of distinct elements
34  \return -1 on failure
35  */
36 int NetA_init_distinct(dbDriver *driver, dbString *sql, int **lengths,
37  int **ids)
38 {
39  int count, last, cur, result, index, more;
40  dbCursor cursor;
41  dbTable *table;
42  dbColumn *column;
43  dbValue *value;
44 
45  if (db_open_select_cursor(driver, sql, &cursor, DB_SEQUENTIAL) != DB_OK) {
46  G_warning(_("Unable to open select cursor: %s"), db_get_string(sql));
47  return -1;
48  }
49  /*TODO: check column types */
50 
51  count = last = 0;
52  /*count number of distinct routes */
53  table = db_get_cursor_table(&cursor);
54  column = db_get_table_column(table, 0);
55  while (db_fetch(&cursor, DB_NEXT, &more) == DB_OK && more) {
56  value = db_get_column_value(column);
57  cur = db_get_value_int(value);
58  if (count == 0 || cur != last) {
59  last = cur;
60  count++;
61  }
62  }
63  result = count;
64  db_close_cursor(&cursor);
65 
66  *lengths = (int *)G_calloc(count, sizeof(int));
67  *ids = (int *)G_calloc(count, sizeof(int));
68  if (!*lengths || !*ids) {
69  G_warning(_("Out of memory"));
70  return -1;
71  }
73  count = index = 0;
74  /*calculate the lengths of the routes */
75  table = db_get_cursor_table(&cursor);
76  column = db_get_table_column(table, 0);
77  while (db_fetch(&cursor, DB_NEXT, &more) == DB_OK && more) {
78  value = db_get_column_value(column);
79  cur = db_get_value_int(value);
80  if (count != 0 && cur != last)
81  index++;
82  if (count == 0 || cur != last)
83  (*ids)[index] = cur;
84  (*lengths)[index]++;
85  last = cur;
86  count++;
87  }
88  return result;
89 }
90 
91 static int cmp_int(const void *a, const void *b)
92 {
93  return *(int *)a - *(int *)b;
94 }
95 
96 /*!
97  \brief Initialises timetable from a database
98 
99  \param In pointer to Map_info structure
100  \param route_layer layer number of routes
101  \param walk_layer layer number of walkers
102  \param route_id id of route
103  \param times list of timestamps
104  \param to_stop ?
105  \param walk_length walk length as string
106  \param timetable pointer to neta_timetable
107  \param route_ids list of route ids
108  \param stop_ids list of stop ids
109 
110  \return 0 on success
111  \return non-zero value on failure
112  */
113 int NetA_init_timetable_from_db(struct Map_info *In, int route_layer,
114  int walk_layer, char *route_id, char *times,
115  char *to_stop, char *walk_length,
116  neta_timetable *timetable, int **route_ids,
117  int **stop_ids)
118 {
119  int more, i, stop, route, time, *stop_pnt, stop1, stop2;
120  dbString sql;
121  dbCursor cursor;
122  dbTable *table;
123  dbColumn *column1, *column2, *column3;
124  dbValue *value;
125  char buf[2000];
126 
127  dbDriver *driver;
128  struct field_info *Fi;
129 
130  Fi = Vect_get_field(In, route_layer);
132  if (driver == NULL)
133  G_fatal_error(_("Unable to open database <%s> by driver <%s>"),
134  Fi->database, Fi->driver);
135 
136  db_init_string(&sql);
137  sprintf(buf, "select %s from %s order by %s", route_id, Fi->table,
138  route_id);
139  db_set_string(&sql, buf);
140  timetable->routes =
141  NetA_init_distinct(driver, &sql, &(timetable->route_length), route_ids);
142  if (timetable->routes < 0)
143  return 1;
144 
145  sprintf(buf, "select %s from %s order by %s", Fi->key, Fi->table, Fi->key);
146  db_set_string(&sql, buf);
147  timetable->stops =
148  NetA_init_distinct(driver, &sql, &(timetable->stop_length), stop_ids);
149  if (timetable->stops < 0)
150  return 1;
151 
152  timetable->route_stops = (int **)G_calloc(timetable->routes, sizeof(int *));
153  timetable->route_times = (int **)G_calloc(timetable->routes, sizeof(int *));
154  timetable->stop_routes = (int **)G_calloc(timetable->stops, sizeof(int *));
155  timetable->stop_times = (int **)G_calloc(timetable->stops, sizeof(int *));
156  timetable->walk_length = (int *)G_calloc(timetable->stops, sizeof(int));
157  timetable->walk_stops = (int **)G_calloc(timetable->stops, sizeof(int *));
158  timetable->walk_times = (int **)G_calloc(timetable->stops, sizeof(int *));
159  if (!timetable->route_stops || !timetable->route_times ||
160  !timetable->stop_routes || !timetable->stop_times ||
161  !timetable->walk_length) {
162  G_warning(_("Out of memory"));
163  return 2;
164  }
165 
166  for (i = 0; i < timetable->routes; i++) {
167  timetable->route_stops[i] =
168  (int *)G_calloc(timetable->route_length[i], sizeof(int));
169  timetable->route_times[i] =
170  (int *)G_calloc(timetable->route_length[i], sizeof(int));
171  if (!timetable->route_stops[i] || !timetable->route_times[i]) {
172  G_warning(_("Out of memory"));
173  return 2;
174  }
175 
176  timetable->route_length[i] = 0;
177  }
178 
179  for (i = 0; i < timetable->stops; i++) {
180  timetable->stop_routes[i] =
181  (int *)G_calloc(timetable->stop_length[i], sizeof(int));
182  timetable->stop_times[i] =
183  (int *)G_calloc(timetable->stop_length[i], sizeof(int));
184  if (!timetable->stop_routes[i] || !timetable->stop_times[i]) {
185  G_warning(_("Out of memory"));
186  return 2;
187  }
188  timetable->walk_length[i] = 0;
189  timetable->stop_length[i] = 0;
190  }
191 
192  sprintf(buf, "select %s, %s, %s from %s order by %s", Fi->key, route_id,
193  times, Fi->table, times);
194  db_set_string(&sql, buf);
195 
196  if (db_open_select_cursor(driver, &sql, &cursor, DB_SEQUENTIAL) != DB_OK) {
197  G_warning(_("Unable to open select cursor: %s"), db_get_string(&sql));
198  return 1;
199  }
200 
201  table = db_get_cursor_table(&cursor);
202  column1 = db_get_table_column(table, 0);
203  column2 = db_get_table_column(table, 1);
204  column3 = db_get_table_column(table, 2);
205  while (db_fetch(&cursor, DB_NEXT, &more) == DB_OK && more) {
206  value = db_get_column_value(column1);
207  stop = db_get_value_int(value);
208  value = db_get_column_value(column2);
209  route = db_get_value_int(value);
210  value = db_get_column_value(column3);
211  time = db_get_value_int(value);
212  stop = (int *)bsearch(&stop, *stop_ids, timetable->stops, sizeof(int),
213  cmp_int) -
214  (*stop_ids);
215  route = (int *)bsearch(&route, *route_ids, timetable->routes,
216  sizeof(int), cmp_int) -
217  (*route_ids);
218 
219  timetable->stop_routes[stop][timetable->stop_length[stop]] = route;
220  timetable->stop_times[stop][timetable->stop_length[stop]++] = time;
221 
222  timetable->route_stops[route][timetable->route_length[route]] = stop;
223  timetable->route_times[route][timetable->route_length[route]++] = time;
224  }
225  db_close_cursor(&cursor);
226 
227  if (walk_layer != -1) {
228 
229  Fi = Vect_get_field(In, walk_layer);
230  sprintf(buf, "select %s, %s, %s from %s", Fi->key, to_stop, walk_length,
231  Fi->table);
232  db_set_string(&sql, buf);
233 
234  if (db_open_select_cursor(driver, &sql, &cursor, DB_SEQUENTIAL) !=
235  DB_OK) {
236  G_warning(_("Unable to open select cursor: %s"),
237  db_get_string(&sql));
238  return 1;
239  }
240 
241  table = db_get_cursor_table(&cursor);
242  column1 = db_get_table_column(table, 0);
243  column2 = db_get_table_column(table, 1);
244  while (db_fetch(&cursor, DB_NEXT, &more) == DB_OK && more) {
245  value = db_get_column_value(column2);
246  stop = db_get_value_int(value);
247  stop_pnt = (int *)bsearch(&stop, *stop_ids, timetable->stops,
248  sizeof(int), cmp_int);
249  if (stop_pnt) {
250  value = db_get_column_value(column1);
251  stop = db_get_value_int(value);
252  stop_pnt = (int *)bsearch(&stop, *stop_ids, timetable->stops,
253  sizeof(int), cmp_int);
254  if (stop_pnt) {
255  stop = stop_pnt - (*stop_ids);
256  timetable->walk_length[stop]++;
257  }
258  }
259  }
260  db_close_cursor(&cursor);
261 
262  for (i = 0; i < timetable->stops; i++) {
263  timetable->walk_stops[i] =
264  (int *)G_calloc(timetable->walk_length[i], sizeof(int));
265  timetable->walk_times[i] =
266  (int *)G_calloc(timetable->walk_length[i], sizeof(int));
267  if (!timetable->walk_stops[i] || !timetable->walk_times[i]) {
268  G_warning(_("Out of memory"));
269  return 2;
270  }
271  timetable->walk_length[i] = 0;
272  }
273 
274  if (db_open_select_cursor(driver, &sql, &cursor, DB_SEQUENTIAL) !=
275  DB_OK) {
276  G_warning(_("Unable to open select cursor: %s"),
277  db_get_string(&sql));
278  return 1;
279  }
280 
281  table = db_get_cursor_table(&cursor);
282  column1 = db_get_table_column(table, 0);
283  column2 = db_get_table_column(table, 1);
284  column3 = db_get_table_column(table, 2);
285  while (db_fetch(&cursor, DB_NEXT, &more) == DB_OK && more) {
286  value = db_get_column_value(column2);
287  stop = db_get_value_int(value);
288  stop_pnt = (int *)bsearch(&stop, *stop_ids, timetable->stops,
289  sizeof(int), cmp_int);
290  if (stop_pnt) {
291  stop2 = stop_pnt - (*stop_ids);
292  value = db_get_column_value(column1);
293  stop = db_get_value_int(value);
294  stop_pnt = (int *)bsearch(&stop, *stop_ids, timetable->stops,
295  sizeof(int), cmp_int);
296  if (stop_pnt) {
297  stop1 = stop_pnt - (*stop_ids);
298  value = db_get_column_value(column3);
299  time = db_get_value_int(value);
300  timetable
301  ->walk_stops[stop1][timetable->walk_length[stop1]] =
302  stop2;
303  timetable
304  ->walk_times[stop1][timetable->walk_length[stop1]++] =
305  time;
306  }
307  }
308  }
309  db_close_cursor(&cursor);
310  }
312 
313  return 0;
314 }
315 
316 typedef struct {
317  int v;
318  int conns;
319 } neta_heap_data;
320 
321 static neta_heap_data *new_heap_data(int conns, int v)
322 {
323  neta_heap_data *d = (neta_heap_data *)G_calloc(1, sizeof(neta_heap_data));
324  d->v = v;
325  d->conns = conns;
326  return d;
327 }
328 
329 /*!
330  \brief Update Dijkstra structures
331 
332  \param olc_conns old connection
333  \param new_conns new connection
334  \param to old 'to' node
335  \param new_dst new 'to' node
336  \param v ?
337  \param route id of route
338  \param rows ? (unused)
339  \param update ?
340  \param[out] result pointer to neta_timetable_result structure
341  \param heap ?
342  */
343 void NetA_update_dijkstra(int old_conns, int new_conns, int to, int new_dst,
344  int v, int route, int rows UNUSED, int update,
345  neta_timetable_result *result, dglHeap_s *heap)
346 {
347  if (result->dst[new_conns][to] == -1 ||
348  result->dst[new_conns][to] > new_dst) {
349  result->dst[new_conns][to] = new_dst;
350  result->prev_stop[new_conns][to] = v;
351  result->prev_route[new_conns][to] = route;
352  result->prev_conn[new_conns][to] = old_conns;
353  if (update) {
354  dglHeapData_u heap_data;
355 
356  heap_data.pv = (void *)new_heap_data(new_conns, to);
357  dglHeapInsertMin(heap, new_dst, ' ', heap_data);
358  }
359  }
360 }
361 
362 /*!
363  \brief Computes the earliest arrival time.
364 
365  Computes the earliest arrival time to to_stop from from_stop
366  starting at start_time, or -1 if no path exists
367 
368  \param timetable pointer to neta_timetable structure
369  \param from_stop 'from' node
370  \param to_stop 'to' stop
371  \param start_time start timestamp
372  \param min_change ?
373  \param max_changes ?
374  \param walking_change ?
375  \param[out] result pointer to neta_timetable_result
376 
377  \return ?
378  \return -1 on error
379  */
380 int NetA_timetable_shortest_path(neta_timetable *timetable, int from_stop,
381  int to_stop, int start_time, int min_change,
382  int max_changes, int walking_change,
383  neta_timetable_result *result)
384 {
385  int i, j;
386  dglHeap_s heap;
387 
388  int opt_conns, rows = 1;
389 
390  if (max_changes != -1)
391  rows = max_changes + 2;
392 
393  result->rows = rows;
394  result->dst = (int **)G_calloc(rows, sizeof(int *));
395  result->prev_stop = (int **)G_calloc(rows, sizeof(int *));
396  result->prev_route = (int **)G_calloc(rows, sizeof(int *));
397  result->prev_conn = (int **)G_calloc(rows, sizeof(int *));
398 
399  if (!result->dst || !result->prev_stop || !result->prev_route ||
400  !result->prev_conn) {
401  G_warning(_("Out of memory"));
402  return -1;
403  }
404 
405  for (i = 0; i < rows; i++) {
406  result->dst[i] = (int *)G_calloc(timetable->stops, sizeof(int));
407  result->prev_stop[i] = (int *)G_calloc(timetable->stops, sizeof(int));
408  result->prev_route[i] = (int *)G_calloc(timetable->stops, sizeof(int));
409  result->prev_conn[i] = (int *)G_calloc(timetable->stops, sizeof(int));
410  if (!result->dst[i] || !result->prev_stop[i] ||
411  !result->prev_route[i] || !result->prev_conn[i]) {
412  G_warning(_("Out of memory"));
413  return -1;
414  }
415  }
416 
417  if (from_stop == to_stop) {
418  result->dst[0][to_stop] = start_time;
419  result->prev_route[0][to_stop] = result->prev_stop[0][to_stop] = -1;
420  result->routes = 0;
421  return start_time;
422  }
423 
424  result->routes = -1;
425  if (walking_change > 1)
426  walking_change = 1;
427  if (walking_change < 0 || max_changes == -1)
428  walking_change = 0;
429  dglHeapInit(&heap);
430 
431  for (i = 0; i < rows; i++)
432  for (j = 0; j < timetable->stops; j++)
433  result->dst[i][j] = result->prev_stop[i][j] =
434  result->prev_route[i][j] = -1;
435 
436  result->dst[0][from_stop] = start_time - min_change;
437  result->prev_stop[0][from_stop] = result->prev_route[0][from_stop] = -1;
438  dglHeapData_u heap_data;
439 
440  heap_data.pv = (void *)new_heap_data(0, from_stop);
441  dglHeapInsertMin(&heap, start_time - min_change, ' ', heap_data);
442 
443  while (1) {
444  dglInt32_t v, dist, conns;
445  dglHeapNode_s heap_node;
446  int new_conns, walk_conns, update;
447 
448  if (!dglHeapExtractMin(&heap, &heap_node))
449  break;
450  v = ((neta_heap_data *)(heap_node.value.pv))->v;
451  conns = ((neta_heap_data *)(heap_node.value.pv))->conns;
452  dist = heap_node.key;
453 
454  if (dist > result->dst[conns][v])
455  continue;
456  if (v == to_stop)
457  break;
458  new_conns = (max_changes == -1) ? 0 : (conns + 1);
459  walk_conns = conns + walking_change;
460 
461  /*walking */
462  if (walk_conns < rows) {
463  /* update = (max_changes == -1 || walk_conns <=
464  * max_changes); */
465  update = 1;
466  for (i = 0; i < timetable->walk_length[v]; i++) {
467  int to = timetable->walk_stops[v][i];
468  int new_dst = dist + timetable->walk_times[v][i];
469 
470  NetA_update_dijkstra(conns, walk_conns, to, new_dst, v, -2,
471  rows, update, result, &heap);
472  }
473  }
474 
475  if (new_conns >= rows)
476  continue;
477  /*process all routes arriving after dist+min_change */
478  for (i = 0; i < timetable->stop_length[v]; i++)
479  if (timetable->stop_times[v][i] >= dist + min_change) {
480  int route = timetable->stop_routes[v][i];
481 
482  /*find the index of v on the route */
483  for (j = 0; j < timetable->route_length[route]; j++)
484  if (timetable->route_stops[route][j] == v)
485  break;
486  j++;
487  for (; j < timetable->route_length[route]; j++) {
488  int to = timetable->route_stops[route][j];
489 
490  NetA_update_dijkstra(conns, new_conns, to,
491  timetable->route_times[route][j], v,
492  route, rows, 1, result, &heap);
493  }
494  }
495  }
496  dglHeapFree(&heap, NULL);
497  opt_conns = -1;
498  for (i = 0; i < rows; i++)
499  if (result->dst[i][to_stop] != -1 &&
500  (opt_conns == -1 ||
501  result->dst[opt_conns][to_stop] > result->dst[i][to_stop]))
502  opt_conns = i;
503  result->routes = opt_conns;
504 
505  if (opt_conns != -1)
506  return result->dst[opt_conns][to_stop];
507  return -1;
508 }
509 
510 /*!
511  \brief Get time
512 
513  Get time when route "route" arrives at stop "stop" or -1.
514 
515  \param timetable pointer to neta_timetable structure
516  \param stop 'stop' node id
517  \param route route id
518 
519  \return time
520  \return -1 if not found
521  */
523  int route)
524 {
525  int i;
526 
527  for (i = 0; i < timetable->route_length[route]; i++)
528  if (timetable->route_stops[route][i] == stop)
529  return timetable->route_times[route][i];
530  return -1;
531 }
532 
533 /*!
534  \brief Free neta_timetable_result structure
535 
536  \param result pointer to neta_timetable_result structure
537  */
539 {
540  int i;
541 
542  for (i = 0; i < result->rows; i++) {
543  G_free(result->dst[i]);
544  G_free(result->prev_stop[i]);
545  G_free(result->prev_route[i]);
546  }
547  G_free(result->dst);
548  G_free(result->prev_stop);
549  G_free(result->prev_route);
550 }
#define NULL
Definition: ccmath.h:32
#define DB_SEQUENTIAL
Definition: dbmi.h:123
#define DB_OK
Definition: dbmi.h:71
#define DB_NEXT
Definition: dbmi.h:114
dbValue * db_get_column_value(dbColumn *)
Returns column value for given column structure.
dbColumn * db_get_table_column(dbTable *, int)
Returns column structure for given table and column number.
dbDriver * db_start_driver_open_database(const char *, const char *)
Open driver/database connection.
Definition: db.c:28
dbTable * db_get_cursor_table(dbCursor *)
Get table allocated by cursor.
Definition: cursor.c:67
int db_close_database_shutdown_driver(dbDriver *)
Close driver/database connection.
Definition: db.c:61
int db_set_string(dbString *, const char *)
Inserts string to dbString (enlarge string)
Definition: string.c:41
int db_get_value_int(dbValue *)
Get integer value.
Definition: value.c:38
void db_init_string(dbString *)
Initialize dbString.
Definition: string.c:25
int db_close_cursor(dbCursor *)
Close cursor.
Definition: c_close_cur.c:27
int db_open_select_cursor(dbDriver *, dbString *, dbCursor *, int)
Open select cursor.
Definition: c_openselect.c:37
char * db_get_string(const dbString *)
Get string.
Definition: string.c:140
int db_fetch(dbCursor *, int, int *)
Fetch data from open cursor.
Definition: c_fetch.c:28
void G_free(void *)
Free allocated memory.
Definition: gis/alloc.c:150
#define G_calloc(m, n)
Definition: defs/gis.h:95
void void void void G_fatal_error(const char *,...) __attribute__((format(printf
void G_warning(const char *,...) __attribute__((format(printf
struct field_info * Vect_get_field(struct Map_info *, int)
Get information about link to database (by layer number)
Definition: field.c:515
const struct driver * driver
Definition: driver/init.c:25
#define UNUSED
A macro for an attribute, if attached to a variable, indicating that the variable is not used.
Definition: gis.h:47
#define _(str)
Definition: glocale.h:10
void dglHeapInit(dglHeap_s *pheap)
Definition: heap.c:27
int dglHeapInsertMin(dglHeap_s *pheap, long key, unsigned char flags, dglHeapData_u value)
Definition: heap.c:50
void dglHeapFree(dglHeap_s *pheap, dglHeapCancelItem_fn pfnCancelItem)
Definition: heap.c:35
int dglHeapExtractMin(dglHeap_s *pheap, dglHeapNode_s *pnoderet)
Definition: heap.c:76
int count
double b
Definition: r_raster.c:39
Vector map info.
Definition: dig_structs.h:1243
long key
Definition: heap.h:35
dglHeapData_u value
Definition: heap.h:36
Definition: heap.h:41
Definition: driver.h:21
Layer (old: field) information.
Definition: dig_structs.h:131
char * table
Name of DB table.
Definition: dig_structs.h:151
char * driver
Name of DB driver ('sqlite', 'dbf', ...)
Definition: dig_structs.h:143
char * database
Definition: dig_structs.h:147
char * key
Name of key column (usually 'cat')
Definition: dig_structs.h:155
int ** route_times
Definition: defs/neta.h:59
int * route_length
Definition: defs/neta.h:56
int ** walk_times
Definition: defs/neta.h:70
int ** stop_times
Definition: defs/neta.h:65
int ** walk_stops
Definition: defs/neta.h:69
int ** stop_routes
Definition: defs/neta.h:63
int * stop_length
Definition: defs/neta.h:62
int * walk_length
Definition: defs/neta.h:67
int ** route_stops
Definition: defs/neta.h:58
int NetA_init_timetable_from_db(struct Map_info *In, int route_layer, int walk_layer, char *route_id, char *times, char *to_stop, char *walk_length, neta_timetable *timetable, int **route_ids, int **stop_ids)
Initialises timetable from a database.
Definition: timetables.c:113
int NetA_init_distinct(dbDriver *driver, dbString *sql, int **lengths, int **ids)
Get number of distinct elements.
Definition: timetables.c:36
void NetA_timetable_result_release(neta_timetable_result *result)
Free neta_timetable_result structure.
Definition: timetables.c:538
int NetA_timetable_get_route_time(neta_timetable *timetable, int stop, int route)
Get time.
Definition: timetables.c:522
int NetA_timetable_shortest_path(neta_timetable *timetable, int from_stop, int to_stop, int start_time, int min_change, int max_changes, int walking_change, neta_timetable_result *result)
Computes the earliest arrival time.
Definition: timetables.c:380
void NetA_update_dijkstra(int old_conns, int new_conns, int to, int new_dst, int v, int route, int rows UNUSED, int update, neta_timetable_result *result, dglHeap_s *heap)
Update Dijkstra structures.
Definition: timetables.c:343
long dglInt32_t
Definition: type.h:36
void * pv
Definition: heap.h:26