GRASS GIS 8 Programmer's Manual  8.4.0dev(2024)-6c790bf5c0
vector/neta/path.c
Go to the documentation of this file.
1 /*!
2  \file vector/neta/path.c
3 
4  \brief Network Analysis library - shortest path
5 
6  Shortest paths from a set of nodes.
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  \author Markus Metz
15  */
16 
17 #include <stdio.h>
18 #include <stdlib.h>
19 #include <grass/gis.h>
20 #include <grass/vector.h>
21 #include <grass/glocale.h>
22 #include <grass/dgl/graph.h>
23 #include <grass/neta.h>
24 
25 /*!
26  \brief Computes shortest paths to every node from nodes in "from".
27 
28  Array "dst" contains the cost of the path or -1 if the node is not
29  reachable. Prev contains edges from predecessor along the shortest
30  path.
31 
32  \param graph input graph
33  \param from list of 'from' positions
34  \param[out] dst array of costs to reach nodes
35  \param[out] prev array of edges from predecessor along the shortest path
36 
37  \return 0 on success
38  \return -1 on failure
39  */
40 int NetA_distance_from_points(dglGraph_s *graph, struct ilist *from, int *dst,
41  dglInt32_t **prev)
42 {
43  int i, nnodes;
44  dglHeap_s heap;
45  int have_node_costs;
46  dglInt32_t ncost;
47 
48  nnodes = dglGet_NodeCount(graph);
50 
51  /* initialize costs and edge list */
52  for (i = 1; i <= nnodes; i++) {
53  dst[i] = -1;
54  prev[i] = NULL;
55  }
56 
57  ncost = 0;
58  have_node_costs = dglGet_NodeAttrSize(graph);
59 
60  dglHeapInit(&heap);
61 
62  for (i = 0; i < from->n_values; i++) {
63  int v = from->value[i];
64 
65  if (dst[v] == 0)
66  continue; /* ignore duplicates */
67  dst[v] = 0; /* make sure all from nodes are processed first */
68  dglHeapData_u heap_data;
69 
70  heap_data.ul = v;
71  dglHeapInsertMin(&heap, 0, ' ', heap_data);
72  }
73  while (1) {
74  dglInt32_t v, dist;
75  dglHeapNode_s heap_node;
76  dglHeapData_u heap_data;
77  dglInt32_t *edge;
78  dglInt32_t *node;
79 
80  if (!dglHeapExtractMin(&heap, &heap_node))
81  break;
82  v = heap_node.value.ul;
83  dist = heap_node.key;
84  if (dst[v] < dist)
85  continue;
86 
87  node = dglGetNode(graph, v);
88 
89  if (have_node_costs && prev[v]) {
90  memcpy(&ncost, dglNodeGet_Attr(graph, node), sizeof(ncost));
91  if (ncost > 0)
92  dist += ncost;
93  /* do not go through closed nodes */
94  if (ncost < 0)
95  continue;
96  }
97 
98  dglEdgeset_T_Initialize(&et, graph, dglNodeGet_OutEdgeset(graph, node));
99 
100  for (edge = dglEdgeset_T_First(&et); edge;
101  edge = dglEdgeset_T_Next(&et)) {
102  dglInt32_t *to = dglEdgeGet_Tail(graph, edge);
103  dglInt32_t to_id = dglNodeGet_Id(graph, to);
104  dglInt32_t d = dglEdgeGet_Cost(graph, edge);
105 
106  if (dst[to_id] < 0 || dst[to_id] > dist + d) {
107  dst[to_id] = dist + d;
108  prev[to_id] = edge;
109  heap_data.ul = to_id;
110  dglHeapInsertMin(&heap, dist + d, ' ', heap_data);
111  }
112  }
113 
115  }
116 
117  dglHeapFree(&heap, NULL);
118 
119  return 0;
120 }
121 
122 /*!
123  \brief Computes shortest paths from every node to nodes in "to".
124 
125  Array "dst" contains the cost of the path or -1 if the node is not
126  reachable. Nxt contains edges from successor along the shortest
127  path. This method does reverse search starting with "to" nodes and
128  going backward.
129 
130  \param graph input graph
131  \param to list of 'to' positions
132  \param[out] dst array of costs to reach nodes
133  \param[out] nxt array of edges from successor along the shortest path
134 
135  \return 0 on success
136  \return -1 on failure
137  */
138 int NetA_distance_to_points(dglGraph_s *graph, struct ilist *to, int *dst,
139  dglInt32_t **nxt)
140 {
141  int i, nnodes;
142  dglHeap_s heap;
144  int have_node_costs;
145  dglInt32_t ncost;
146 
147  nnodes = dglGet_NodeCount(graph);
148 
149  /* initialize costs and edge list */
150  for (i = 1; i <= nnodes; i++) {
151  dst[i] = -1;
152  nxt[i] = NULL;
153  }
154 
155  if (graph->Version < 2) {
156  G_warning("Directed graph must be version 2 or 3 for "
157  "NetA_distance_to_points()");
158  return -1;
159  }
160 
161  ncost = 0;
162  have_node_costs = dglGet_NodeAttrSize(graph);
163 
164  dglHeapInit(&heap);
165 
166  for (i = 0; i < to->n_values; i++) {
167  int v = to->value[i];
168 
169  if (dst[v] == 0)
170  continue; /* ignore duplicates */
171  dst[v] = 0; /* make sure all to nodes are processed first */
172  dglHeapData_u heap_data;
173 
174  heap_data.ul = v;
175  dglHeapInsertMin(&heap, 0, ' ', heap_data);
176  }
177  while (1) {
178  dglInt32_t v, dist;
179  dglHeapNode_s heap_node;
180  dglHeapData_u heap_data;
181  dglInt32_t *edge;
182  dglInt32_t *node;
183 
184  if (!dglHeapExtractMin(&heap, &heap_node))
185  break;
186  v = heap_node.value.ul;
187  dist = heap_node.key;
188  if (dst[v] < dist)
189  continue;
190 
191  node = dglGetNode(graph, v);
192 
193  if (have_node_costs && nxt[v]) {
194  memcpy(&ncost, dglNodeGet_Attr(graph, node), sizeof(ncost));
195  if (ncost > 0)
196  dist += ncost;
197  /* do not go through closed nodes */
198  if (ncost < 0)
199  continue;
200  }
201 
202  dglEdgeset_T_Initialize(&et, graph, dglNodeGet_InEdgeset(graph, node));
203 
204  for (edge = dglEdgeset_T_First(&et); edge;
205  edge = dglEdgeset_T_Next(&et)) {
206  dglInt32_t *from = dglEdgeGet_Head(graph, edge);
207  dglInt32_t from_id = dglNodeGet_Id(graph, from);
208  dglInt32_t d = dglEdgeGet_Cost(graph, edge);
209 
210  if (dst[from_id] < 0 || dst[from_id] > dist + d) {
211  dst[from_id] = dist + d;
212  nxt[from_id] = edge;
213  heap_data.ul = from_id;
214  dglHeapInsertMin(&heap, dist + d, ' ', heap_data);
215  }
216  }
217 
219  }
220 
221  dglHeapFree(&heap, NULL);
222 
223  return 0;
224 }
225 
226 /*!
227  \brief Find a path (minimum number of edges) from 'from' to 'to'
228  using only edges flagged as valid in 'edges'. Edge costs are not
229  considered. Closed nodes are not traversed.
230 
231  Precisely, edge with id I is used if edges[abs(i)] == 1. List
232  stores the indices of lines on the path. The method returns the
233  number of edges or -1 if no path exists.
234 
235  \param graph input graph
236  \param from 'from' position
237  \param to 'to' position
238  \param edges array of edges indicating whether an edge should be used
239  \param[out] list list of edges
240 
241  \return number of edges
242  \return -1 on failure
243  */
244 int NetA_find_path(dglGraph_s *graph, int from, int to, int *edges,
245  struct ilist *list)
246 {
247  dglInt32_t **prev, *queue;
249  char *vis;
250  int begin, end, cur, nnodes;
251  int have_node_costs;
252  dglInt32_t ncost;
253 
254  nnodes = dglGet_NodeCount(graph);
255  prev = (dglInt32_t **)G_calloc(nnodes + 1, sizeof(dglInt32_t *));
256  queue = (dglInt32_t *)G_calloc(nnodes + 1, sizeof(dglInt32_t));
257  vis = (char *)G_calloc(nnodes + 1, sizeof(char));
258  if (!prev || !queue || !vis) {
259  G_fatal_error(_("Out of memory"));
260  return -1;
261  }
263 
264  ncost = 0;
265  have_node_costs = dglGet_NodeAttrSize(graph);
266 
267  begin = 0;
268  end = 1;
269  vis[from] = 'y';
270  queue[0] = from;
271  prev[from] = NULL;
272  while (begin != end) {
273  dglInt32_t vertex = queue[begin++];
274  dglInt32_t *edge = NULL, *node;
275 
276  if (vertex == to)
277  break;
278 
279  /* do not go through closed nodes */
280  if (have_node_costs && prev[vertex]) {
281  memcpy(&ncost, dglNodeGet_Attr(graph, dglEdgeGet_Tail(graph, edge)),
282  sizeof(ncost));
283  if (ncost < 0)
284  continue;
285  }
286 
287  node = dglGetNode(graph, vertex);
288 
289  dglEdgeset_T_Initialize(&et, graph, dglNodeGet_OutEdgeset(graph, node));
290  for (edge = dglEdgeset_T_First(&et); edge;
291  edge = dglEdgeset_T_Next(&et)) {
292  dglInt32_t edge_id = labs(dglEdgeGet_Id(graph, edge));
293  dglInt32_t node_id =
294  dglNodeGet_Id(graph, dglEdgeGet_Tail(graph, edge));
295  if (edges[edge_id] && !vis[node_id]) {
296  vis[node_id] = 'y';
297  prev[node_id] = edge;
298  queue[end++] = node_id;
299  }
300  }
302  }
303  G_free(queue);
304  if (!vis[to]) {
305  G_free(prev);
306  G_free(vis);
307  return -1;
308  }
309 
310  cur = to;
311  while (prev[cur] != NULL) {
312  Vect_list_append(list, labs(dglEdgeGet_Id(graph, prev[cur])));
313  cur = dglNodeGet_Id(graph, dglEdgeGet_Head(graph, prev[cur]));
314  }
315 
316  G_free(prev);
317  G_free(vis);
318  return list->n_values;
319 }
#define NULL
Definition: ccmath.h:32
Definition: queue.h:43
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
int Vect_list_append(struct ilist *, int)
Append new item to the end of list if not yet present.
int Vect_reset_list(struct ilist *)
Reset ilist structure.
#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
dglByte_t Version
Definition: graph.h:140
long key
Definition: heap.h:35
dglHeapData_u value
Definition: heap.h:36
Definition: heap.h:41
List of integers.
Definition: gis.h:706
int n_values
Number of values in the list.
Definition: gis.h:714
int * value
Array of values.
Definition: gis.h:710
Definition: manage.h:4
Definition: path.h:10
long dglInt32_t
Definition: type.h:36
unsigned long ul
Definition: heap.h:30
int dglGet_NodeAttrSize(dglGraph_s *pgraph)
dglInt32_t * dglNodeGet_OutEdgeset(dglGraph_s *pGraph, dglInt32_t *pnNode)
int dglEdgeset_T_Initialize(dglEdgesetTraverser_s *pT, dglGraph_s *pGraph, dglInt32_t *pnEdgeset)
dglInt32_t dglEdgeGet_Id(dglGraph_s *pGraph, dglInt32_t *pnEdge)
dglInt32_t * dglEdgeset_T_Next(dglEdgesetTraverser_s *pT)
dglInt32_t * dglEdgeGet_Tail(dglGraph_s *pGraph, dglInt32_t *pnEdge)
dglInt32_t * dglEdgeGet_Head(dglGraph_s *pGraph, dglInt32_t *pnEdge)
dglInt32_t * dglNodeGet_Attr(dglGraph_s *pGraph, dglInt32_t *pnNode)
int dglGet_NodeCount(dglGraph_s *pgraph)
void dglEdgeset_T_Release(dglEdgesetTraverser_s *pT UNUSED)
dglInt32_t * dglNodeGet_InEdgeset(dglGraph_s *pGraph, dglInt32_t *pnNode)
dglInt32_t dglEdgeGet_Cost(dglGraph_s *pGraph, dglInt32_t *pnEdge)
dglInt32_t * dglEdgeset_T_First(dglEdgesetTraverser_s *pT)
dglInt32_t dglNodeGet_Id(dglGraph_s *pGraph, dglInt32_t *pnNode)
dglInt32_t * dglGetNode(dglGraph_s *pGraph, dglInt32_t nNodeId)
int NetA_find_path(dglGraph_s *graph, int from, int to, int *edges, struct ilist *list)
Find a path (minimum number of edges) from 'from' to 'to' using only edges flagged as valid in 'edges...
int NetA_distance_to_points(dglGraph_s *graph, struct ilist *to, int *dst, dglInt32_t **nxt)
Computes shortest paths from every node to nodes in "to".
int NetA_distance_from_points(dglGraph_s *graph, struct ilist *from, int *dst, dglInt32_t **prev)
Computes shortest paths to every node from nodes in "from".