GRASS GIS 8 Programmer's Manual  8.5.0dev(2024)-c7e1de7dfd
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 
46  dglSPCache_s *pCache, dglInt32_t nStart)
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 
62 {
63  if (pCache->pvVisited)
65  if (pCache->pvPredist)
67  dglHeapFree(&pCache->NodeHeap, NULL);
68 }
69 
70 static int DGL_SP_CACHE_DISTANCE_FUNC(dglGraph_s *pgraph, dglSPCache_s *pCache,
71  dglInt32_t *pnDistance, dglInt32_t nStart,
72  dglInt32_t nDestination)
73 {
74  dglTreeTouchI32_s VisitedItem;
75  dglTreePredist_s *pPredistItem, PredistItem;
76 
77  if (pCache->nStartNode != nStart) {
79  return -pgraph->iErrno;
80  }
81 
82  VisitedItem.nKey = nDestination;
83  if (avl_find(pCache->pvVisited, &VisitedItem) == NULL) {
85  return -pgraph->iErrno;
86  }
87 
88  PredistItem.nKey = nDestination;
89  if ((pPredistItem = avl_find(pCache->pvPredist, &PredistItem)) == NULL) {
91  return -pgraph->iErrno;
92  }
93 
94  if (pnDistance)
95  *pnDistance = pPredistItem->nDistance;
96  return 0;
97 }
98 
100  dglSPCache_s *pCache,
101  dglInt32_t nStart,
102  dglInt32_t nDestination)
103 {
104  dglTreeTouchI32_s VisitedItem;
105  dglTreePredist_s *pPredistItem, PredistItem;
106  dglInt32_t *pEdge;
107  dglInt32_t *pDestination;
108  dglSPArc_s arc;
109  long i, istack = 0;
110  unsigned char *pstack = NULL;
111  unsigned char *ppop;
112  dglSPReport_s *pReport = NULL;
113 
114  if (pCache->nStartNode != nStart) {
116  return NULL;
117  }
118 
119  VisitedItem.nKey = nDestination;
120  if (avl_find(pCache->pvVisited, &VisitedItem) == NULL) {
122  return NULL;
123  }
124 
125  PredistItem.nKey = nDestination;
126  if (avl_find(pCache->pvPredist, &PredistItem) == NULL) {
128  return NULL;
129  }
130 
131  for (PredistItem.nKey = nDestination,
132  pPredistItem = avl_find(pCache->pvPredist, &PredistItem);
133  pPredistItem; PredistItem.nKey = pPredistItem->nFrom,
134  pPredistItem = avl_find(pCache->pvPredist, &PredistItem)) {
135  if (pPredistItem->nFrom < 0) {
136  pgraph->iErrno = DGL_ERR_BadEdge;
137  goto spr_error;
138  }
139 
140  pEdge = (dglInt32_t *)pPredistItem->pnEdge;
141 
142  if (pPredistItem->bFlags == 0) {
143  if (pgraph->Flags & DGL_GS_FLAT) {
144  pDestination = DGL_NODEBUFFER_SHIFT(
145  pgraph, DGL_EDGE_TAILNODE_OFFSET(pEdge));
146  }
147  else {
148  pDestination =
150  }
151  }
152  else {
153  if (pgraph->Flags & DGL_GS_FLAT) {
154  pDestination = DGL_NODEBUFFER_SHIFT(
155  pgraph, DGL_EDGE_HEADNODE_OFFSET(pEdge));
156  }
157  else {
158  pDestination =
160  }
161  }
162 
163  if ((arc.pnEdge = DGL_EDGE_ALLOC(pgraph->EdgeAttrSize)) == NULL)
164  goto spr_error;
165  arc.nFrom = pPredistItem->nFrom;
166  arc.nTo = DGL_NODE_ID(pDestination);
167  arc.nDistance = pPredistItem->nDistance;
168  memcpy(arc.pnEdge, pEdge, DGL_EDGE_SIZEOF(pgraph->EdgeAttrSize));
169  DGL_EDGE_COST(arc.pnEdge) = pPredistItem->nCost;
170 
171  if ((pstack = dgl_mempush(pstack, &istack, sizeof(dglSPArc_s), &arc)) ==
172  NULL) {
174  goto spr_error;
175  }
176 
177  if (arc.nFrom == nStart)
178  break;
179  }
180 
181  if (pPredistItem == NULL) {
183  goto spr_error;
184  }
185 
186  if ((pReport = malloc(sizeof(dglSPReport_s))) == NULL) {
188  goto spr_error;
189  }
190  memset(pReport, 0, sizeof(dglSPReport_s));
191 
192  pReport->cArc = istack;
193 
194  if ((pReport->pArc = malloc(sizeof(dglSPArc_s) * pReport->cArc)) == NULL) {
196  goto spr_error;
197  }
198 
199  pReport->nDistance = 0;
200 
201  for (i = 0;
202  (ppop = dgl_mempop(pstack, &istack, sizeof(dglSPArc_s))) != NULL;
203  i++) {
204  memcpy(&pReport->pArc[i], ppop, sizeof(dglSPArc_s));
205  pReport->nDistance += DGL_EDGE_COST(pReport->pArc[i].pnEdge);
206  }
207 
208  pReport->nStartNode = nStart;
209  pReport->nDestinationNode = nDestination;
210 
211  if (pstack)
212  free(pstack);
213 
214  return pReport;
215 
216 spr_error:
217  if (pstack)
218  free(pstack);
219  if (pReport)
220  dglFreeSPReport(pgraph, pReport);
221 
222  return NULL;
223 }
224 #endif
225 
226 #if defined(DGL_DEFINE_TREE_PROCS) || defined(DGL_DEFINE_FLAT_PROCS)
227 
228 #define __EDGELOOP_BODY_1(f) \
229  if ((f) == 0) { \
230  pDestination = _DGL_EDGE_TAILNODE(pgraph, pEdge); \
231  } \
232  else { \
233  pDestination = _DGL_EDGE_HEADNODE(pgraph, pEdge); \
234  } \
235  if (!(DGL_NODE_STATUS(pDestination) & DGL_NS_TAIL) && \
236  pgraph->Version < 3) { \
237  pgraph->iErrno = DGL_ERR_BadEdge; \
238  goto sp_error; \
239  } \
240  clipOutput.nEdgeCost = DGL_EDGE_COST(pEdge); \
241  if (fnClip) { \
242  clipInput.pnPrevEdge = NULL; \
243  clipInput.pnNodeFrom = pStart; \
244  clipInput.pnEdge = pEdge; \
245  clipInput.pnNodeTo = pDestination; \
246  clipInput.nFromDistance = 0; \
247  if (fnClip(pgraph, &clipInput, &clipOutput, pvClipArg)) \
248  continue; \
249  } \
250  findPredist.nKey = DGL_NODE_ID(pDestination); \
251  if ((pPredistItem = avl_find(pCache->pvPredist, &findPredist)) == NULL) { \
252  if ((pPredistItem = dglTreePredistAdd( \
253  pCache->pvPredist, DGL_NODE_ID(pDestination))) == NULL) { \
254  pgraph->iErrno = DGL_ERR_MemoryExhausted; \
255  goto sp_error; \
256  } \
257  } \
258  else { \
259  if (pPredistItem->nDistance <= clipOutput.nEdgeCost) { \
260  continue; \
261  } \
262  } \
263  pPredistItem->nFrom = nStart; \
264  pPredistItem->pnEdge = pEdge; \
265  pPredistItem->nCost = clipOutput.nEdgeCost; \
266  pPredistItem->nDistance = clipOutput.nEdgeCost; \
267  pPredistItem->bFlags = (f); \
268  heapvalue.pv = pEdge; \
269  if (dglHeapInsertMin(&pCache->NodeHeap, pPredistItem->nDistance, f, \
270  heapvalue) < 0) { \
271  pgraph->iErrno = DGL_ERR_HeapError; \
272  goto sp_error; \
273  }
274 
275 #define __EDGELOOP_BODY_2(f) \
276  if ((f) == 0) { \
277  pDestination = _DGL_EDGE_TAILNODE(pgraph, pEdge); \
278  } \
279  else if (pgraph->Version == 3) { \
280  pDestination = _DGL_EDGE_HEADNODE(pgraph, pEdge); \
281  } \
282  if (!(DGL_NODE_STATUS(pDestination) & DGL_NS_TAIL) && \
283  pgraph->Version < 3) { \
284  pgraph->iErrno = DGL_ERR_BadEdge; \
285  goto sp_error; \
286  } \
287  clipOutput.nEdgeCost = DGL_EDGE_COST(pEdge); \
288  if (fnClip) { \
289  clipInput.pnPrevEdge = pEdge_prev; \
290  clipInput.pnNodeFrom = pStart; \
291  clipInput.pnEdge = pEdge; \
292  clipInput.pnNodeTo = pDestination; \
293  clipInput.nFromDistance = fromDist; \
294  if (fnClip(pgraph, &clipInput, &clipOutput, pvClipArg)) \
295  continue; \
296  } \
297  findPredist.nKey = DGL_NODE_ID(pDestination); \
298  if ((pPredistItem = avl_find(pCache->pvPredist, &findPredist)) == NULL) { \
299  if ((pPredistItem = dglTreePredistAdd( \
300  pCache->pvPredist, DGL_NODE_ID(pDestination))) == NULL) { \
301  pgraph->iErrno = DGL_ERR_MemoryExhausted; \
302  goto sp_error; \
303  } \
304  } \
305  else { \
306  if (pPredistItem->nDistance <= fromDist + clipOutput.nEdgeCost) { \
307  continue; \
308  } \
309  } \
310  pPredistItem->nFrom = DGL_NODE_ID(pStart); \
311  pPredistItem->pnEdge = pEdge; \
312  pPredistItem->nCost = clipOutput.nEdgeCost; \
313  pPredistItem->nDistance = fromDist + clipOutput.nEdgeCost; \
314  pPredistItem->bFlags = (f); \
315  heapvalue.pv = pEdge; \
316  if (dglHeapInsertMin(&pCache->NodeHeap, pPredistItem->nDistance, f, \
317  heapvalue) < 0) { \
318  pgraph->iErrno = DGL_ERR_HeapError; \
319  goto sp_error; \
320  }
321 
322 /*
323  * Dijkstra Shortest Path
324  */
325 int DGL_SP_DIJKSTRA_FUNC(dglGraph_s *pgraph, dglSPReport_s **ppReport,
326  dglInt32_t *pDistance, dglInt32_t nStart,
327  dglInt32_t nDestination, dglSPClip_fn fnClip,
328  void *pvClipArg, dglSPCache_s *pCache)
329 {
330  dglInt32_t *pStart; /* pointer to the start node (pgraph->pNodeBuffer) */
331  register dglInt32_t *pDestination; /* temporary destination pointer */
332  register dglInt32_t
333  *pEdgeset; /* pointer to the edge (pgraph->pEdgeBuffer) */
334  register dglInt32_t *pEdge; /* pointer to the to-edges in edge */
335  register dglInt32_t *pEdge_prev; /* pointer to the previous edge in path */
336  int nRet;
338 
339  dglSPCache_s spCache;
340  int new_cache = 0;
341 
342  /*
343  * shortest path distance temporary min heap
344  */
345  dglHeapData_u heapvalue;
346  dglHeapNode_s heapnode;
347 
348  /*
349  * shortest path visited network
350  */
351  dglTreeTouchI32_s *pVisitedItem, findVisited;
352 
353  /*
354  * shortest path predecessor and distance network
355  */
356  dglTreePredist_s *pPredistItem, findPredist;
357 
358  /*
359  * args to clip()
360  */
361  dglSPClipInput_s clipInput;
362  dglSPClipOutput_s clipOutput;
363 
364  /*
365  * Initialize the cache: initialize the heap and create temporary networks -
366  * The use of a predist network for predecessor and distance has two
367  * important results: 1) allows us not having to reset the whole graph
368  * status at each call; 2) use of a stack memory area for temporary (and
369  * otherwise possibly thread-conflicting) states. If a cache pointer was
370  * supplied, do not initialize it but try to get SP immediately.
371  */
372  if (pCache == NULL) {
373  pCache = &spCache;
374  DGL_SP_CACHE_INITIALIZE_FUNC(pgraph, pCache, nStart);
375  new_cache = 1;
376  }
377  else {
378  if (ppReport) {
379  if ((*ppReport = DGL_SP_CACHE_REPORT_FUNC(pgraph, pCache, nStart,
380  nDestination)) != NULL) {
381  return 1;
382  }
383  }
384  else {
385  if (DGL_SP_CACHE_DISTANCE_FUNC(pgraph, pCache, pDistance, nStart,
386  nDestination) >= 0) {
387  return 2;
388  }
389  }
390  if (pgraph->iErrno == DGL_ERR_HeadNodeNotFound) {
391  DGL_SP_CACHE_RELEASE_FUNC(pgraph, pCache);
392  DGL_SP_CACHE_INITIALIZE_FUNC(pgraph, pCache, nStart);
393  new_cache = 1;
394  }
395  else if (pgraph->iErrno != DGL_ERR_TailNodeNotFound) {
396  goto sp_error;
397  }
398  }
399 
400  /*
401  * reset error status after using the cache
402  */
403  pgraph->iErrno = 0;
404 
405  if ((pStart = DGL_GET_NODE_FUNC(pgraph, nStart)) == NULL) {
407  goto sp_error;
408  }
409 
410  if ((pDestination = DGL_GET_NODE_FUNC(pgraph, nDestination)) == NULL) {
412  goto sp_error;
413  }
414 
415  if ((DGL_NODE_STATUS(pStart) & DGL_NS_ALONE) ||
416  (DGL_NODE_STATUS(pDestination) & DGL_NS_ALONE)) {
417  goto sp_error;
418  }
419 
420  if (!(DGL_NODE_STATUS(pStart) & DGL_NS_HEAD) && pgraph->Version < 3) {
421  goto sp_error;
422  }
423 
424  if (!(DGL_NODE_STATUS(pDestination) & DGL_NS_TAIL) && pgraph->Version < 3) {
425  goto sp_error;
426  }
427 
428  /* if we do not need a new cache, we just continue with the unvisited
429  * nodes in the cache */
430  if (new_cache) {
431  /*
432  * now we inspect all edges departing from the start node
433  * - at each loop 'pedge' points to the edge in the edge buffer
434  * - we invoke the caller's clip() and eventually skip the edge (clip()
435  * != 0)
436  * - we insert a item in the predist network to set actual predecessor
437  * and distance (there is no precedecessor at this stage) and actual
438  * distance from the starting node (at this stage it equals the edge's
439  * cost)
440  * - we insert a item in the node min-heap (sorted on node distance),
441  * storing the offset of the edge in the edge buffer. In the case of
442  * undirected graph (version 3) we inspect input edges as well.
443  */
444  pEdgeset = _DGL_OUTEDGESET(pgraph, pStart);
445  if (DGL_EDGESET_T_INITIALIZE_FUNC(pgraph, &laT, pEdgeset) < 0) {
446  goto sp_error;
447  }
448  for (pEdge = DGL_EDGESET_T_FIRST_FUNC(&laT); pEdge;
449  pEdge = DGL_EDGESET_T_NEXT_FUNC(&laT)) {
450  __EDGELOOP_BODY_1(0);
451  }
453 
454  if (pgraph->Version == 3) {
455  pEdgeset = _DGL_INEDGESET(pgraph, pStart);
456  if (DGL_EDGESET_T_INITIALIZE_FUNC(pgraph, &laT, pEdgeset) < 0) {
457  goto sp_error;
458  }
459  for (pEdge = DGL_EDGESET_T_FIRST_FUNC(&laT); pEdge;
460  pEdge = DGL_EDGESET_T_NEXT_FUNC(&laT)) {
461  if (DGL_EDGE_STATUS(pEdge) & DGL_ES_DIRECTED)
462  continue;
463  __EDGELOOP_BODY_1(1);
464  }
466  }
467  }
468 
469  /*
470  * Now we begin extracting nodes from the min-heap. Each node extracted is
471  * the one that is actually closest to the SP start.
472  */
473  while (dglHeapExtractMin(&pCache->NodeHeap, &heapnode) == 1) {
474  dglInt32_t fromDist;
475 
476  /*
477  * recover the stored edge pointer
478  */
479  pEdge = heapnode.value.pv;
480 
481  /*
482  * the new relative head is the tail of the edge
483  * or the head of the edge if the traversal was reversed (undirected
484  * edge)
485  */
486  if (heapnode.flags == 0) {
487  pStart = _DGL_EDGE_TAILNODE(
488  pgraph, pEdge); /* continue from previous tail */
489  }
490  else {
491  pStart = _DGL_EDGE_HEADNODE(pgraph, pEdge); /* reversed head/tail */
492  }
493 
494  /*
495  * We do not want to explore twice the same node as a relative starting
496  * point, that's the meaning of 'visited'. We mark actual start node as
497  * 'visited' by inserting it into the visited-network. If we find actual
498  * node in the network we just give up and continue looping. Otherwise
499  * we add actual node to the network.
500  */
501  findVisited.nKey = DGL_NODE_ID(pStart);
502  if ((pVisitedItem = avl_find(pCache->pvVisited, &findVisited)) ==
503  NULL) {
504  if (dglTreeTouchI32Add(pCache->pvVisited, DGL_NODE_ID(pStart)) ==
505  NULL) {
507  goto sp_error;
508  }
509  }
510 
511  /*
512  * Give up with visited nodes now
513  */
514  if (pVisitedItem) {
515  if (DGL_NODE_ID(pStart) == nDestination) {
516  /* should not happen but does not harm
517  * this case should have been handled above */
518  goto destination_found;
519  }
520  else
521  continue;
522  }
523 
524  /*
525  * If the node is not marked as having departing edges, then we are into
526  * a blind alley. Just give up this direction and continue looping. This
527  * only applies to v1 and v2 (digraphs)
528  */
529  if (!(DGL_NODE_STATUS(pStart) & DGL_NS_HEAD) && pgraph->Version < 3) {
530  if (DGL_NODE_ID(pStart) == nDestination) {
531  goto destination_found;
532  }
533  else
534  continue;
535  }
536 
537  /*
538  * save actual edge for later clip()
539  */
540  pEdge_prev = pEdge;
541 
542  /*
543  * Recover the head node distance from the predist network
544  */
545  findPredist.nKey = DGL_NODE_ID(pStart);
546  if ((pPredistItem = avl_find(pCache->pvPredist, &findPredist)) ==
547  NULL) {
549  goto sp_error;
550  }
551 
552  fromDist = pPredistItem->nDistance;
553 
554  /*
555  * Loop on departing edges:
556  * Scan the edgeset and loads pedge at each iteration with next-edge.
557  * iWay == DGL_EDGESET_T_WAY_OUT then pedge is a out arc (departing from
558  * node) else ot is a in arc. V1 has no in-degree support so iWay is
559  * always OUT, V2/3 have in-degree support.
560  *
561  * This loop needs to be done also when destination is found, otherwise
562  * the node is marked as visited but its departing edges are not added
563  * to the cache
564  * --> loose end, we might need these edges later on
565  */
566  pEdgeset = _DGL_OUTEDGESET(pgraph, pStart);
567  if (DGL_EDGESET_T_INITIALIZE_FUNC(pgraph, &laT, pEdgeset) < 0) {
568  goto sp_error;
569  }
570  for (pEdge = DGL_EDGESET_T_FIRST_FUNC(&laT); pEdge;
571  pEdge = DGL_EDGESET_T_NEXT_FUNC(&laT)) {
572  __EDGELOOP_BODY_2(0);
573  }
575 
576  if (pgraph->Version == 3) {
577  pEdgeset = _DGL_INEDGESET(pgraph, pStart);
578  if (DGL_EDGESET_T_INITIALIZE_FUNC(pgraph, &laT, pEdgeset) < 0) {
579  goto sp_error;
580  }
581  for (pEdge = DGL_EDGESET_T_FIRST_FUNC(&laT); pEdge;
582  pEdge = DGL_EDGESET_T_NEXT_FUNC(&laT)) {
583  if (DGL_EDGE_STATUS(pEdge) & DGL_ES_DIRECTED)
584  continue;
585  __EDGELOOP_BODY_2(1);
586  }
588  }
589 
590  /*
591  * Dijkstra algorithm ends when the destination node is extracted from
592  * the min distance heap, that means: no other path exist in the network
593  * giving a shortest output. If this happens we jump to the epilogue in
594  * order to build a path report and return.
595  */
596  if (DGL_NODE_ID(pStart) == nDestination) {
597  goto destination_found;
598  }
599  }
600 
601 sp_error:
602  if (pCache == &spCache) {
603  DGL_SP_CACHE_RELEASE_FUNC(pgraph, pCache);
604  }
605  return -pgraph->iErrno; /* == 0 path not found */
606 
607 destination_found: /* path found - build a shortest path report or report the
608  distance only */
609 
610  if (ppReport) {
611  *ppReport =
612  DGL_SP_CACHE_REPORT_FUNC(pgraph, pCache, nStart, nDestination);
613  if (*ppReport == NULL) {
614  nRet = -pgraph->iErrno;
615  }
616  else {
617  nRet = 1;
618  }
619  }
620  else {
621  if (DGL_SP_CACHE_DISTANCE_FUNC(pgraph, pCache, pDistance, nStart,
622  nDestination) < 0) {
623  nRet = -pgraph->iErrno;
624  }
625  else {
626  nRet = 2;
627  }
628  }
629  if (pCache == &spCache) {
630  DGL_SP_CACHE_RELEASE_FUNC(pgraph, pCache);
631  }
632  return nRet;
633 }
634 
635 #endif
#define NULL
Definition: ccmath.h:32
#define UNUSED
A macro for an attribute, if attached to a variable, indicating that the variable is not used.
Definition: gis.h:47
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 DGL_EDGESET_T_RELEASE_FUNC(dglEdgesetTraverser_s *pT UNUSED)
dglInt32_t * DGL_EDGESET_T_FIRST_FUNC(dglEdgesetTraverser_s *pT)
int DGL_EDGESET_T_INITIALIZE_FUNC(dglGraph_s *pGraph, dglEdgesetTraverser_s *pT, dglInt32_t *pnEdgeset)
dglInt32_t * DGL_EDGESET_T_NEXT_FUNC(dglEdgesetTraverser_s *pT)
dglInt32_t * DGL_GET_NODE_FUNC(dglGraph_s *pgraph, dglInt32_t nodeid)
void DGL_SP_CACHE_RELEASE_FUNC(dglGraph_s *pgraph UNUSED, dglSPCache_s *pCache)
Definition: sp-template.c:61
int DGL_SP_CACHE_INITIALIZE_FUNC(dglGraph_s *pgraph UNUSED, dglSPCache_s *pCache, dglInt32_t nStart)
Definition: sp-template.c:45
void * malloc(YYSIZE_T)
void free(void *)
if(!(yy_init))
Definition: sqlp.yy.c:775
dglInt32_t EdgeAttrSize
Definition: graph.h:143
int iErrno
Definition: graph.h:138
dglByte_t Version
Definition: graph.h:140
dglInt32_t Flags
Definition: graph.h:153
unsigned char flags
Definition: heap.h:37
dglHeapData_u value
Definition: heap.h:36
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
dglInt32_t nDistance
Definition: graph.h:205
dglInt32_t cArc
Definition: graph.h:206
dglSPArc_s * pArc
Definition: graph.h:207
dglInt32_t nStartNode
Definition: graph.h:203
dglInt32_t nDestinationNode
Definition: graph.h:204
dglByte_t bFlags
Definition: tree.h:122
dglInt32_t nKey
Definition: tree.h:117
dglInt32_t nDistance
Definition: tree.h:119
dglInt32_t nCost
Definition: tree.h:120
dglInt32_t nFrom
Definition: tree.h:118
dglInt32_t * pnEdge
Definition: tree.h:121
dglInt32_t nKey
Definition: tree.h:104
void * pvPredist
Definition: graph.h:217
void * pvVisited
Definition: graph.h:216
dglHeap_s NodeHeap
Definition: graph.h:215
dglInt32_t nStartNode
Definition: graph.h:214
int dglTreePredistCompare(const void *pvPredistA, const void *pvPredistB, void *pvParam UNUSED)
Definition: tree.c:257
void dglTreeTouchI32Cancel(void *pvTouchI32, void *pvParam UNUSED)
Definition: tree.c:202
void * dglTreeGetAllocator(void)
Definition: tree.c:406
dglTreeTouchI32_s * dglTreeTouchI32Add(void *pavl, dglInt32_t nKey)
Definition: tree.c:220
void dglTreePredistCancel(void *pvPredist, void *pvParam UNUSED)
Definition: tree.c:252
int dglTreeTouchI32Compare(const void *pvTouchI32A, const void *pvTouchI32B, void *pvParam UNUSED)
Definition: tree.c:207
#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
void * pv
Definition: heap.h:26
#define DGL_SP_CACHE_REPORT_FUNC
Definition: v1-defs.h:86
#define DGL_NODE_STATUS
Definition: v1-defs.h:126
#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_EDGE_STATUS(p)
Definition: v1-defs.h:136
#define DGL_SP_CACHE_DISTANCE_FUNC
Definition: v1-defs.h:87
#define DGL_EDGE_HEADNODE_OFFSET
Definition: v1-defs.h:140
#define DGL_EDGE_COST
Definition: v1-defs.h:137
#define DGL_NODEBUFFER_SHIFT
Definition: v1-defs.h:157
void dglFreeSPReport(dglGraph_s *pgraph UNUSED, dglSPReport_s *pSPReport)