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