GRASS Programmer's Manual  6.4.3(2013)-r
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Macros Pages
path.c
Go to the documentation of this file.
1 
16 #include <stdio.h>
17 #include <stdlib.h>
18 #include <grass/gis.h>
19 #include <grass/Vect.h>
20 #include <grass/glocale.h>
21 #include <grass/dgl/graph.h>
22 #include <grass/neta.h>
23 
39 int NetA_distance_from_points(dglGraph_s * graph, struct ilist *from,
40  int *dst, dglInt32_t ** prev)
41 {
42  int i, nnodes;
43  dglHeap_s heap;
44 
45  nnodes = dglGet_NodeCount(graph);
47 
48  for (i = 1; i <= nnodes; i++) {
49  dst[i] = -1;
50  prev[i] = NULL;
51  }
52 
53  dglHeapInit(&heap);
54 
55  for (i = 0; i < from->n_values; i++) {
56  int v = from->value[i];
57 
58  if (dst[v] == 0)
59  continue; /*ingore duplicates */
60  dst[v] = 0;
61  dglHeapData_u heap_data;
62 
63  heap_data.ul = v;
64  dglHeapInsertMin(&heap, 0, ' ', heap_data);
65  }
66  while (1) {
67  dglInt32_t v, dist;
68  dglHeapNode_s heap_node;
69  dglHeapData_u heap_data;
70 
71  if (!dglHeapExtractMin(&heap, &heap_node))
72  break;
73  v = heap_node.value.ul;
74  dist = heap_node.key;
75  if (dst[v] < dist)
76  continue;
77 
78  dglInt32_t *edge;
79 
80  dglEdgeset_T_Initialize(&et, graph,
82  dglGetNode(graph, v)));
83  for (edge = dglEdgeset_T_First(&et); edge;
84  edge = dglEdgeset_T_Next(&et)) {
85  dglInt32_t *to = dglEdgeGet_Tail(graph, edge);
86  dglInt32_t to_id = dglNodeGet_Id(graph, to);
87  dglInt32_t d = dglEdgeGet_Cost(graph, edge);
88 
89  if (dst[to_id] == -1 || dst[to_id] > dist + d) {
90  dst[to_id] = dist + d;
91  prev[to_id] = edge;
92  heap_data.ul = to_id;
93  dglHeapInsertMin(&heap, dist + d, ' ', heap_data);
94  }
95  }
96 
98  }
99 
100  dglHeapFree(&heap, NULL);
101 
102  return 0;
103 }
104 
121 int NetA_find_path(dglGraph_s * graph, int from, int to, int *edges,
122  struct ilist *list)
123 {
124  dglInt32_t **prev, *queue;
126  char *vis;
127  int begin, end, cur, nnodes;
128 
129  nnodes = dglGet_NodeCount(graph);
130  prev = (dglInt32_t **) G_calloc(nnodes + 1, sizeof(dglInt32_t *));
131  queue = (dglInt32_t *) G_calloc(nnodes + 1, sizeof(dglInt32_t));
132  vis = (char *)G_calloc(nnodes + 1, sizeof(char));
133  if (!prev || !queue || !vis) {
134  G_fatal_error(_("Out of memory"));
135  return -1;
136  }
137  Vect_reset_list(list);
138 
139  begin = 0;
140  end = 1;
141  vis[from] = 'y';
142  queue[0] = from;
143  prev[from] = NULL;
144  while (begin != end) {
145  dglInt32_t vertex = queue[begin++];
146 
147  if (vertex == to)
148  break;
149  dglInt32_t *edge, *node = dglGetNode(graph, vertex);
150 
151  dglEdgeset_T_Initialize(&et, graph,
152  dglNodeGet_OutEdgeset(graph, node));
153  for (edge = dglEdgeset_T_First(&et); edge;
154  edge = dglEdgeset_T_Next(&et)) {
155  dglInt32_t id = abs(dglEdgeGet_Id(graph, edge));
156  dglInt32_t to =
157  dglNodeGet_Id(graph, dglEdgeGet_Tail(graph, edge));
158  if (edges[id] && !vis[to]) {
159  vis[to] = 'y';
160  prev[to] = edge;
161  queue[end++] = to;
162  }
163  }
165  }
166  G_free(queue);
167  if (!vis[to]) {
168  G_free(prev);
169  G_free(vis);
170  return -1;
171  }
172 
173  cur = to;
174  while (prev[cur] != NULL) {
175  Vect_list_append(list, abs(dglEdgeGet_Id(graph, prev[cur])));
176  cur = dglNodeGet_Id(graph, dglEdgeGet_Head(graph, prev[cur]));
177  }
178 
179  G_free(prev);
180  G_free(vis);
181  return list->n_values;
182 }