GRASS 8 Programmer's Manual 8.6.0dev(2026)-5a31d549cc
Loading...
Searching...
No Matches
sp-template.c
Go to the documentation of this file.
1/* LIBDGL -- a Directed Graph Library implementation
2 * Copyright (C) 2002 Roberto Micarelli
3 *
4 * This program is free software; you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License as published by
6 * the Free Software Foundation; either version 2 of the License, or
7 * (at your option) any later version.
8 *
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the Free Software
16 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
17 */
18
19/*
20 * best view with tabstop=4
21 */
22
23/*
24 * SHORTEST PATH CACHE
25 *
26 * components:
27 * - start node id
28 * - visited network: a node is marked as visited when its departing
29 * edges have been added to the cache
30 * - predist network: node distances from start node
31 * - NodeHeap: holds unvisited nodes, the next node extracted is the
32 * unvisited node closest to SP start
33 *
34 * not all nodes in the predist network have been visited, SP from start
35 * is known only for visited nodes
36 * unvisited nodes can be reached, but not necessarily on the shortest
37 * possible path
38 * important for DGL_SP_CACHE_DISTANCE_FUNC and DGL_SP_CACHE_REPORT_FUNC
39 */
40
41#if !defined(DGL_DEFINE_TREE_PROCS) && !defined(DGL_DEFINE_FLAT_PROCS)
42
43#include <grass/gis.h>
44
47{
48 pCache->nStartNode = nStart;
49 pCache->pvVisited = NULL;
50 pCache->pvPredist = NULL;
51 dglHeapInit(&pCache->NodeHeap);
54 return -1;
57 return -1;
58 return 0;
59}
60
63{
64 if (pCache->pvVisited)
66 if (pCache->pvPredist)
68 dglHeapFree(&pCache->NodeHeap, NULL);
69}
70
74{
77
78 if (pCache->nStartNode != nStart) {
80 return -pgraph->iErrno;
81 }
82
84 if (avl_find(pCache->pvVisited, &VisitedItem) == NULL) {
86 return -pgraph->iErrno;
87 }
88
90 if ((pPredistItem = avl_find(pCache->pvPredist, &PredistItem)) == NULL) {
92 return -pgraph->iErrno;
93 }
94
95 if (pnDistance)
96 *pnDistance = pPredistItem->nDistance;
97 return 0;
98}
99
104{
109 dglSPArc_s arc;
110 long i, istack = 0;
111 unsigned char *pstack = NULL;
112 unsigned char *ppop;
114
115 if (pCache->nStartNode != nStart) {
117 return NULL;
118 }
119
121 if (avl_find(pCache->pvVisited, &VisitedItem) == NULL) {
123 return NULL;
124 }
125
127 if (avl_find(pCache->pvPredist, &PredistItem) == NULL) {
129 return NULL;
130 }
131
132 for (PredistItem.nKey = nDestination,
133 pPredistItem = avl_find(pCache->pvPredist, &PredistItem);
135 pPredistItem = avl_find(pCache->pvPredist, &PredistItem)) {
136 if (pPredistItem->nFrom < 0) {
137 pgraph->iErrno = DGL_ERR_BadEdge;
138 goto spr_error;
139 }
140
141 pEdge = (dglInt32_t *)pPredistItem->pnEdge;
142
143 if (pPredistItem->bFlags == 0) {
144 if (pgraph->Flags & DGL_GS_FLAT) {
147 }
148 else {
151 }
152 }
153 else {
154 if (pgraph->Flags & DGL_GS_FLAT) {
157 }
158 else {
161 }
162 }
163
164 if ((arc.pnEdge = DGL_EDGE_ALLOC(pgraph->EdgeAttrSize)) == NULL)
165 goto spr_error;
166 arc.nFrom = pPredistItem->nFrom;
168 arc.nDistance = pPredistItem->nDistance;
169 memcpy(arc.pnEdge, pEdge, DGL_EDGE_SIZEOF(pgraph->EdgeAttrSize));
170 DGL_EDGE_COST(arc.pnEdge) = pPredistItem->nCost;
171
172 if ((pstack = dgl_mempush(pstack, &istack, sizeof(dglSPArc_s), &arc)) ==
173 NULL) {
175 goto spr_error;
176 }
177
178 if (arc.nFrom == nStart)
179 break;
180 }
181
182 if (pPredistItem == NULL) {
184 goto spr_error;
185 }
186
187 if ((pReport = malloc(sizeof(dglSPReport_s))) == NULL) {
189 goto spr_error;
190 }
191 memset(pReport, 0, sizeof(dglSPReport_s));
192
193 pReport->cArc = istack;
194
195 if ((pReport->pArc = malloc(sizeof(dglSPArc_s) * pReport->cArc)) == NULL) {
197 goto spr_error;
198 }
199
200 pReport->nDistance = 0;
201
202 for (i = 0;
203 (ppop = dgl_mempop(pstack, &istack, sizeof(dglSPArc_s))) != NULL;
204 i++) {
205 memcpy(&pReport->pArc[i], ppop, sizeof(dglSPArc_s));
206 pReport->nDistance += DGL_EDGE_COST(pReport->pArc[i].pnEdge);
207 }
208
209 pReport->nStartNode = nStart;
210 pReport->nDestinationNode = nDestination;
211
212 if (pstack)
213 free(pstack);
214
215 return pReport;
216
218 if (pstack)
219 free(pstack);
220 if (pReport)
222
223 return NULL;
224}
225#endif
226
227#if defined(DGL_DEFINE_TREE_PROCS) || defined(DGL_DEFINE_FLAT_PROCS)
228
229#define __EDGELOOP_BODY_1(f) \
230 if ((f) == 0) { \
231 pDestination = _DGL_EDGE_TAILNODE(pgraph, pEdge); \
232 } \
233 else { \
234 pDestination = _DGL_EDGE_HEADNODE(pgraph, pEdge); \
235 } \
236 if (!(DGL_NODE_STATUS(pDestination) & DGL_NS_TAIL) && \
237 pgraph->Version < 3) { \
238 pgraph->iErrno = DGL_ERR_BadEdge; \
239 goto sp_error; \
240 } \
241 clipOutput.nEdgeCost = DGL_EDGE_COST(pEdge); \
242 if (fnClip) { \
243 clipInput.pnPrevEdge = NULL; \
244 clipInput.pnNodeFrom = pStart; \
245 clipInput.pnEdge = pEdge; \
246 clipInput.pnNodeTo = pDestination; \
247 clipInput.nFromDistance = 0; \
248 if (fnClip(pgraph, &clipInput, &clipOutput, pvClipArg)) \
249 continue; \
250 } \
251 findPredist.nKey = DGL_NODE_ID(pDestination); \
252 if ((pPredistItem = avl_find(pCache->pvPredist, &findPredist)) == NULL) { \
253 if ((pPredistItem = dglTreePredistAdd( \
254 pCache->pvPredist, DGL_NODE_ID(pDestination))) == NULL) { \
255 pgraph->iErrno = DGL_ERR_MemoryExhausted; \
256 goto sp_error; \
257 } \
258 } \
259 else { \
260 if (pPredistItem->nDistance <= clipOutput.nEdgeCost) { \
261 continue; \
262 } \
263 } \
264 pPredistItem->nFrom = nStart; \
265 pPredistItem->pnEdge = pEdge; \
266 pPredistItem->nCost = clipOutput.nEdgeCost; \
267 pPredistItem->nDistance = clipOutput.nEdgeCost; \
268 pPredistItem->bFlags = (f); \
269 heapvalue.pv = pEdge; \
270 if (dglHeapInsertMin(&pCache->NodeHeap, pPredistItem->nDistance, f, \
271 heapvalue) < 0) { \
272 pgraph->iErrno = DGL_ERR_HeapError; \
273 goto sp_error; \
274 }
275
276#define __EDGELOOP_BODY_2(f) \
277 if ((f) == 0) { \
278 pDestination = _DGL_EDGE_TAILNODE(pgraph, pEdge); \
279 } \
280 else if (pgraph->Version == 3) { \
281 pDestination = _DGL_EDGE_HEADNODE(pgraph, pEdge); \
282 } \
283 if (!(DGL_NODE_STATUS(pDestination) & DGL_NS_TAIL) && \
284 pgraph->Version < 3) { \
285 pgraph->iErrno = DGL_ERR_BadEdge; \
286 goto sp_error; \
287 } \
288 clipOutput.nEdgeCost = DGL_EDGE_COST(pEdge); \
289 if (fnClip) { \
290 clipInput.pnPrevEdge = pEdge_prev; \
291 clipInput.pnNodeFrom = pStart; \
292 clipInput.pnEdge = pEdge; \
293 clipInput.pnNodeTo = pDestination; \
294 clipInput.nFromDistance = fromDist; \
295 if (fnClip(pgraph, &clipInput, &clipOutput, pvClipArg)) \
296 continue; \
297 } \
298 findPredist.nKey = DGL_NODE_ID(pDestination); \
299 if ((pPredistItem = avl_find(pCache->pvPredist, &findPredist)) == NULL) { \
300 if ((pPredistItem = dglTreePredistAdd( \
301 pCache->pvPredist, DGL_NODE_ID(pDestination))) == NULL) { \
302 pgraph->iErrno = DGL_ERR_MemoryExhausted; \
303 goto sp_error; \
304 } \
305 } \
306 else { \
307 if (pPredistItem->nDistance <= fromDist + clipOutput.nEdgeCost) { \
308 continue; \
309 } \
310 } \
311 pPredistItem->nFrom = DGL_NODE_ID(pStart); \
312 pPredistItem->pnEdge = pEdge; \
313 pPredistItem->nCost = clipOutput.nEdgeCost; \
314 pPredistItem->nDistance = fromDist + clipOutput.nEdgeCost; \
315 pPredistItem->bFlags = (f); \
316 heapvalue.pv = pEdge; \
317 if (dglHeapInsertMin(&pCache->NodeHeap, pPredistItem->nDistance, f, \
318 heapvalue) < 0) { \
319 pgraph->iErrno = DGL_ERR_HeapError; \
320 goto sp_error; \
321 }
322
323/*
324 * Dijkstra Shortest Path
325 */
330{
331 dglInt32_t *pStart; /* pointer to the start node (pgraph->pNodeBuffer) */
332 register dglInt32_t *pDestination; /* temporary destination pointer */
333 register dglInt32_t
334 *pEdgeset; /* pointer to the edge (pgraph->pEdgeBuffer) */
335 register dglInt32_t *pEdge; /* pointer to the to-edges in edge */
336 register dglInt32_t *pEdge_prev; /* pointer to the previous edge in path */
337 int nRet;
339
340 dglSPCache_s spCache;
341 int new_cache = 0;
342
343 /*
344 * shortest path distance temporary min heap
345 */
348
349 /*
350 * shortest path visited network
351 */
353
354 /*
355 * shortest path predecessor and distance network
356 */
358
359 /*
360 * args to clip()
361 */
364
365 /*
366 * Initialize the cache: initialize the heap and create temporary networks -
367 * The use of a predist network for predecessor and distance has two
368 * important results: 1) allows us not having to reset the whole graph
369 * status at each call; 2) use of a stack memory area for temporary (and
370 * otherwise possibly thread-conflicting) states. If a cache pointer was
371 * supplied, do not initialize it but try to get SP immediately.
372 */
373 if (pCache == NULL) {
374 pCache = &spCache;
376 new_cache = 1;
377 }
378 else {
379 if (ppReport) {
381 nDestination)) != NULL) {
382 return 1;
383 }
384 }
385 else {
387 nDestination) >= 0) {
388 return 2;
389 }
390 }
391 if (pgraph->iErrno == DGL_ERR_HeadNodeNotFound) {
394 new_cache = 1;
395 }
396 else if (pgraph->iErrno != DGL_ERR_TailNodeNotFound) {
397 goto sp_error;
398 }
399 }
400
401 /*
402 * reset error status after using the cache
403 */
404 pgraph->iErrno = 0;
405
408 goto sp_error;
409 }
410
413 goto sp_error;
414 }
415
418 goto sp_error;
419 }
420
421 if (!(DGL_NODE_STATUS(pStart) & DGL_NS_HEAD) && pgraph->Version < 3) {
422 goto sp_error;
423 }
424
425 if (!(DGL_NODE_STATUS(pDestination) & DGL_NS_TAIL) && pgraph->Version < 3) {
426 goto sp_error;
427 }
428
429 /* if we do not need a new cache, we just continue with the unvisited
430 * nodes in the cache */
431 if (new_cache) {
432 /*
433 * now we inspect all edges departing from the start node
434 * - at each loop 'pedge' points to the edge in the edge buffer
435 * - we invoke the caller's clip() and eventually skip the edge (clip()
436 * != 0)
437 * - we insert a item in the predist network to set actual predecessor
438 * and distance (there is no precedecessor at this stage) and actual
439 * distance from the starting node (at this stage it equals the edge's
440 * cost)
441 * - we insert a item in the node min-heap (sorted on node distance),
442 * storing the offset of the edge in the edge buffer. In the case of
443 * undirected graph (version 3) we inspect input edges as well.
444 */
447 goto sp_error;
448 }
452 }
454
455 if (pgraph->Version == 3) {
458 goto sp_error;
459 }
463 continue;
465 }
467 }
468 }
469
470 /*
471 * Now we begin extracting nodes from the min-heap. Each node extracted is
472 * the one that is actually closest to the SP start.
473 */
474 while (dglHeapExtractMin(&pCache->NodeHeap, &heapnode) == 1) {
476
477 /*
478 * recover the stored edge pointer
479 */
480 pEdge = heapnode.value.pv;
481
482 /*
483 * the new relative head is the tail of the edge
484 * or the head of the edge if the traversal was reversed (undirected
485 * edge)
486 */
487 if (heapnode.flags == 0) {
489 pgraph, pEdge); /* continue from previous tail */
490 }
491 else {
492 pStart = _DGL_EDGE_HEADNODE(pgraph, pEdge); /* reversed head/tail */
493 }
494
495 /*
496 * We do not want to explore twice the same node as a relative starting
497 * point, that's the meaning of 'visited'. We mark actual start node as
498 * 'visited' by inserting it into the visited-network. If we find actual
499 * node in the network we just give up and continue looping. Otherwise
500 * we add actual node to the network.
501 */
503 if ((pVisitedItem = avl_find(pCache->pvVisited, &findVisited)) ==
504 NULL) {
505 if (dglTreeTouchI32Add(pCache->pvVisited, DGL_NODE_ID(pStart)) ==
506 NULL) {
508 goto sp_error;
509 }
510 }
511
512 /*
513 * Give up with visited nodes now
514 */
515 if (pVisitedItem) {
517 /* should not happen but does not harm
518 * this case should have been handled above */
520 }
521 else
522 continue;
523 }
524
525 /*
526 * If the node is not marked as having departing edges, then we are into
527 * a blind alley. Just give up this direction and continue looping. This
528 * only applies to v1 and v2 (digraphs)
529 */
530 if (!(DGL_NODE_STATUS(pStart) & DGL_NS_HEAD) && pgraph->Version < 3) {
533 }
534 else
535 continue;
536 }
537
538 /*
539 * save actual edge for later clip()
540 */
542
543 /*
544 * Recover the head node distance from the predist network
545 */
547 if ((pPredistItem = avl_find(pCache->pvPredist, &findPredist)) ==
548 NULL) {
550 goto sp_error;
551 }
552
553 fromDist = pPredistItem->nDistance;
554
555 /*
556 * Loop on departing edges:
557 * Scan the edgeset and loads pedge at each iteration with next-edge.
558 * iWay == DGL_EDGESET_T_WAY_OUT then pedge is an out arc (departing
559 * from node) else it is an in arc. V1 has no in-degree support so iWay
560 * is always OUT, V2/3 have in-degree support.
561 *
562 * This loop needs to be done also when destination is found, otherwise
563 * the node is marked as visited but its departing edges are not added
564 * to the cache
565 * --> loose end, we might need these edges later on
566 */
569 goto sp_error;
570 }
574 }
576
577 if (pgraph->Version == 3) {
580 goto sp_error;
581 }
585 continue;
587 }
589 }
590
591 /*
592 * Dijkstra algorithm ends when the destination node is extracted from
593 * the min distance heap, that means: no other path exist in the network
594 * giving a shortest output. If this happens we jump to the epilogue in
595 * order to build a path report and return.
596 */
599 }
600 }
601
603 if (pCache == &spCache) {
605 }
606 return -pgraph->iErrno; /* == 0 path not found */
607
608destination_found: /* path found - build a shortest path report or report the
609 distance only */
610
611 if (ppReport) {
612 *ppReport =
614 if (*ppReport == NULL) {
615 nRet = -pgraph->iErrno;
616 }
617 else {
618 nRet = 1;
619 }
620 }
621 else {
623 nDestination) < 0) {
624 nRet = -pgraph->iErrno;
625 }
626 else {
627 nRet = 2;
628 }
629 }
630 if (pCache == &spCache) {
632 }
633 return nRet;
634}
635
636#endif
#define NULL
Definition ccmath.h:32
#define G_UNUSED
A macro for an attribute, if attached to a variable, indicating that the variable is not used.
Definition gis.h:46
int(* dglSPClip_fn)(dglGraph_s *, dglSPClipInput_s *, dglSPClipOutput_s *, void *)
Definition graph.h:179
#define DGL_NS_TAIL
Definition graph.h:60
#define DGL_NS_ALONE
Definition graph.h:61
#define DGL_ERR_MemoryExhausted
Definition graph.h:254
#define DGL_NS_HEAD
Definition graph.h:59
#define DGL_GS_FLAT
Definition graph.h:36
#define DGL_ERR_HeadNodeNotFound
Definition graph.h:261
#define DGL_ERR_UnexpectedNullPointer
Definition graph.h:268
#define DGL_ERR_BadEdge
Definition graph.h:263
#define DGL_ERR_TailNodeNotFound
Definition graph.h:262
#define DGL_ES_DIRECTED
Definition graph.h:66
void dglHeapInit(dglHeap_s *pheap)
Definition heap.c:27
void dglHeapFree(dglHeap_s *pheap, dglHeapCancelItem_fn pfnCancelItem)
Definition heap.c:35
int dglHeapExtractMin(dglHeap_s *pheap, dglHeapNode_s *pnoderet)
Definition heap.c:76
unsigned char * dgl_mempop(unsigned char *pstack, long *istack, long size)
Definition helpers.c:47
unsigned char * dgl_mempush(unsigned char *pstack, long *istack, long size, void *pv)
Definition helpers.c:34
void * malloc(unsigned)
void free(void *)
dglInt32_t nDistance
Definition graph.h:196
dglInt32_t nTo
Definition graph.h:194
dglInt32_t * pnEdge
Definition graph.h:195
dglInt32_t nFrom
Definition graph.h:193
void dglTreePredistCancel(void *pvPredist, void *pvParam)
Definition tree.c:252
int dglTreeTouchI32Compare(const void *pvTouchI32A, const void *pvTouchI32B, void *pvParam)
Definition tree.c:207
int dglTreePredistCompare(const void *pvPredistA, const void *pvPredistB, void *pvParam)
Definition tree.c:257
void * dglTreeGetAllocator(void)
Definition tree.c:406
dglTreeTouchI32_s * dglTreeTouchI32Add(void *pavl, dglInt32_t nKey)
Definition tree.c:220
void dglTreeTouchI32Cancel(void *pvTouchI32, void *pvParam)
Definition tree.c:202
#define avl_find
Definition tree.h:38
#define avl_create
Definition tree.h:31
#define avl_destroy
Definition tree.h:33
long dglInt32_t
Definition type.h:36
#define DGL_SP_CACHE_REPORT_FUNC
Definition v1-defs.h:86
#define DGL_EDGESET_T_FIRST_FUNC
Definition v1-defs.h:112
#define DGL_SP_CACHE_INITIALIZE_FUNC
Definition v1-defs.h:84
#define DGL_NODE_STATUS
Definition v1-defs.h:126
#define DGL_SP_CACHE_RELEASE_FUNC
Definition v1-defs.h:85
#define DGL_EDGE_SIZEOF
Definition v1-defs.h:134
#define DGL_NODE_ID
Definition v1-defs.h:127
#define DGL_EDGE_ALLOC
Definition v1-defs.h:133
#define DGL_EDGE_TAILNODE_OFFSET
Definition v1-defs.h:141
#define DGL_GET_NODE_FUNC
Definition v1-defs.h:92
#define DGL_EDGE_STATUS(p)
Definition v1-defs.h:136
#define DGL_EDGESET_T_RELEASE_FUNC
Definition v1-defs.h:111
#define DGL_EDGESET_T_INITIALIZE_FUNC
Definition v1-defs.h:110
#define DGL_SP_CACHE_DISTANCE_FUNC
Definition v1-defs.h:87
#define DGL_EDGE_HEADNODE_OFFSET
Definition v1-defs.h:140
#define DGL_EDGESET_T_NEXT_FUNC
Definition v1-defs.h:113
#define DGL_EDGE_COST
Definition v1-defs.h:137
#define DGL_NODEBUFFER_SHIFT
Definition v1-defs.h:157
void dglFreeSPReport(dglGraph_s *pgraph, dglSPReport_s *pSPReport)