00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027 #if !defined(DGL_DEFINE_TREE_PROCS) && !defined(DGL_DEFINE_FLAT_PROCS)
00028
00029 int DGL_SP_CACHE_INITIALIZE_FUNC(dglGraph_s * pgraph, dglSPCache_s * pCache,
00030 dglInt32_t nStart)
00031 {
00032 pCache->nStartNode = nStart;
00033 pCache->pvVisited = NULL;
00034 pCache->pvPredist = NULL;
00035 dglHeapInit(&pCache->NodeHeap);
00036 if ((pCache->pvVisited =
00037 avl_create(dglTreeTouchI32Compare, NULL,
00038 dglTreeGetAllocator())) == NULL)
00039 return -1;
00040 if ((pCache->pvPredist =
00041 avl_create(dglTreePredistCompare, NULL,
00042 dglTreeGetAllocator())) == NULL)
00043 return -1;
00044 return 0;
00045 }
00046
00047 void DGL_SP_CACHE_RELEASE_FUNC(dglGraph_s * pgraph, dglSPCache_s * pCache)
00048 {
00049 if (pCache->pvVisited)
00050 avl_destroy(pCache->pvVisited, dglTreeTouchI32Cancel);
00051 if (pCache->pvPredist)
00052 avl_destroy(pCache->pvPredist, dglTreePredistCancel);
00053 dglHeapFree(&pCache->NodeHeap, NULL);
00054 }
00055
00056
00057 static int DGL_SP_CACHE_DISTANCE_FUNC(dglGraph_s * pgraph,
00058 dglSPCache_s * pCache,
00059 dglInt32_t * pnDistance,
00060 dglInt32_t nStart,
00061 dglInt32_t nDestination)
00062 {
00063 dglTreeTouchI32_s *pVisitedItem, VisitedItem;
00064 dglTreePredist_s *pPredistItem, PredistItem;
00065
00066 if (pCache->nStartNode != nStart) {
00067 pgraph->iErrno = DGL_ERR_HeadNodeNotFound;
00068 return -pgraph->iErrno;
00069 }
00070
00071 VisitedItem.nKey = nDestination;
00072 if ((pVisitedItem = avl_find(pCache->pvPredist, &VisitedItem)) == NULL) {
00073 pgraph->iErrno = DGL_ERR_TailNodeNotFound;
00074 return -pgraph->iErrno;
00075 }
00076
00077 PredistItem.nKey = nDestination;
00078 if ((pPredistItem = avl_find(pCache->pvPredist, &PredistItem)) == NULL) {
00079 pgraph->iErrno = DGL_ERR_UnexpectedNullPointer;
00080 return -pgraph->iErrno;
00081 }
00082
00083 if (pnDistance)
00084 *pnDistance = pPredistItem->nDistance;
00085 return 0;
00086 }
00087
00088 static dglSPReport_s *DGL_SP_CACHE_REPORT_FUNC(dglGraph_s * pgraph,
00089 dglSPCache_s * pCache,
00090 dglInt32_t nStart,
00091 dglInt32_t nDestination)
00092 {
00093 dglTreeTouchI32_s VisitedItem;
00094 dglTreePredist_s *pPredistItem, PredistItem;
00095 dglInt32_t *pEdge;
00096 dglInt32_t *pDestination;
00097 dglSPArc_s arc;
00098 long i, istack = 0;
00099 unsigned char *pstack = NULL;
00100 unsigned char *ppop;
00101 dglSPReport_s *pReport = NULL;
00102
00103 if (pCache->nStartNode != nStart) {
00104 pgraph->iErrno = DGL_ERR_HeadNodeNotFound;
00105 return NULL;
00106 }
00107
00108 VisitedItem.nKey = nDestination;
00109
00110 if (avl_find(pCache->pvVisited, &VisitedItem) == NULL) {
00111 pgraph->iErrno = DGL_ERR_TailNodeNotFound;
00112 return NULL;
00113 }
00114
00115 for (PredistItem.nKey = nDestination,
00116 pPredistItem = avl_find(pCache->pvPredist, &PredistItem);
00117 pPredistItem;
00118 PredistItem.nKey = pPredistItem->nFrom,
00119 pPredistItem = avl_find(pCache->pvPredist, &PredistItem)
00120 ) {
00121 if (pPredistItem->nFrom < 0) {
00122 pgraph->iErrno = DGL_ERR_BadEdge;
00123 goto spr_error;
00124 }
00125
00126 pEdge = (dglInt32_t *) pPredistItem->pnEdge;
00127
00128 if (pPredistItem->bFlags == 0) {
00129 if (pgraph->Flags & DGL_GS_FLAT) {
00130 pDestination =
00131 DGL_NODEBUFFER_SHIFT(pgraph,
00132 DGL_EDGE_TAILNODE_OFFSET(pEdge));
00133 }
00134 else {
00135 pDestination =
00136 DGL_GET_NODE_FUNC(pgraph,
00137 DGL_EDGE_TAILNODE_OFFSET(pEdge));
00138 }
00139 }
00140 else {
00141 if (pgraph->Flags & DGL_GS_FLAT) {
00142 pDestination =
00143 DGL_NODEBUFFER_SHIFT(pgraph,
00144 DGL_EDGE_HEADNODE_OFFSET(pEdge));
00145 }
00146 else {
00147 pDestination =
00148 DGL_GET_NODE_FUNC(pgraph,
00149 DGL_EDGE_HEADNODE_OFFSET(pEdge));
00150 }
00151 }
00152
00153 if ((arc.pnEdge = DGL_EDGE_ALLOC(pgraph->EdgeAttrSize)) == NULL)
00154 goto spr_error;
00155 arc.nFrom = pPredistItem->nFrom;
00156 arc.nTo = DGL_NODE_ID(pDestination);
00157 arc.nDistance = pPredistItem->nDistance;
00158 memcpy(arc.pnEdge, pEdge, DGL_EDGE_SIZEOF(pgraph->EdgeAttrSize));
00159 DGL_EDGE_COST(arc.pnEdge) = pPredistItem->nCost;
00160
00161 if ((pstack =
00162 dgl_mempush(pstack, &istack, sizeof(dglSPArc_s),
00163 &arc)) == NULL) {
00164 pgraph->iErrno = DGL_ERR_MemoryExhausted;
00165 goto spr_error;
00166 }
00167
00168 if (arc.nFrom == nStart)
00169 break;
00170 }
00171
00172 if (pPredistItem == NULL) {
00173 pgraph->iErrno = DGL_ERR_UnexpectedNullPointer;
00174 goto spr_error;
00175 }
00176
00177 if ((pReport = malloc(sizeof(dglSPReport_s))) == NULL) {
00178 pgraph->iErrno = DGL_ERR_MemoryExhausted;
00179 goto spr_error;
00180 }
00181 memset(pReport, 0, sizeof(dglSPReport_s));
00182
00183 pReport->cArc = istack;
00184
00185 if ((pReport->pArc = malloc(sizeof(dglSPArc_s) * pReport->cArc)) == NULL) {
00186 pgraph->iErrno = DGL_ERR_MemoryExhausted;
00187 goto spr_error;
00188 }
00189
00190 pReport->nDistance = 0;
00191
00192 for (i = 0;
00193 (ppop = dgl_mempop(pstack, &istack, sizeof(dglSPArc_s))) != NULL;
00194 i++) {
00195 memcpy(&pReport->pArc[i], ppop, sizeof(dglSPArc_s));
00196 pReport->nDistance += DGL_EDGE_COST(pReport->pArc[i].pnEdge);
00197 }
00198
00199 pReport->nStartNode = nStart;
00200 pReport->nDestinationNode = nDestination;
00201
00202 if (pstack)
00203 free(pstack);
00204
00205 return pReport;
00206
00207 spr_error:
00208 if (pstack)
00209 free(pstack);
00210 if (pReport)
00211 dglFreeSPReport(pgraph, pReport);
00212
00213 return NULL;
00214 }
00215 #endif
00216
00217 #if defined(DGL_DEFINE_TREE_PROCS) || defined(DGL_DEFINE_FLAT_PROCS)
00218
00219 #define __EDGELOOP_BODY_1(f) \
00220 if ( (f) == 0 ) { \
00221 pDestination = _DGL_EDGE_TAILNODE(pgraph, pEdge); \
00222 } \
00223 else { \
00224 pDestination = _DGL_EDGE_HEADNODE(pgraph, pEdge); \
00225 } \
00226 if ( !(DGL_NODE_STATUS(pDestination) & DGL_NS_TAIL) && pgraph->Version < 3) { \
00227 pgraph->iErrno = DGL_ERR_BadEdge; \
00228 goto sp_error; \
00229 } \
00230 clipOutput.nEdgeCost = DGL_EDGE_COST(pEdge); \
00231 if ( fnClip ) { \
00232 clipInput.pnPrevEdge = NULL; \
00233 clipInput.pnNodeFrom = pStart; \
00234 clipInput.pnEdge = pEdge; \
00235 clipInput.pnNodeTo = pDestination; \
00236 clipInput.nFromDistance = 0; \
00237 if ( fnClip( pgraph , & clipInput , & clipOutput , pvClipArg ) ) continue; \
00238 } \
00239 pPredistItem = dglTreePredistAdd( pCache->pvPredist, DGL_NODE_ID(pDestination) ); \
00240 if ( pPredistItem == NULL ) goto sp_error; \
00241 pPredistItem->nFrom = nStart; \
00242 pPredistItem->pnEdge = pEdge; \
00243 pPredistItem->nCost = clipOutput.nEdgeCost; \
00244 pPredistItem->nDistance = clipOutput.nEdgeCost; \
00245 pPredistItem->bFlags = (f); \
00246 heapvalue.pv = pEdge; \
00247 if ( dglHeapInsertMin( & pCache->NodeHeap, pPredistItem->nDistance , f , heapvalue ) < 0 ) { \
00248 pgraph->iErrno = DGL_ERR_HeapError; \
00249 goto sp_error; \
00250 }
00251
00252 #define __EDGELOOP_BODY_2(f) \
00253 if ( (f) == 0 ) { \
00254 pDestination = _DGL_EDGE_TAILNODE(pgraph, pEdge); \
00255 } \
00256 else if ( pgraph->Version == 3 ) { \
00257 pDestination = _DGL_EDGE_HEADNODE(pgraph, pEdge); \
00258 } \
00259 if ( !(DGL_NODE_STATUS(pDestination) & DGL_NS_TAIL) && pgraph->Version < 3) { \
00260 pgraph->iErrno = DGL_ERR_BadEdge; \
00261 goto sp_error; \
00262 } \
00263 clipOutput.nEdgeCost = DGL_EDGE_COST(pEdge); \
00264 if ( fnClip ) { \
00265 clipInput.pnPrevEdge = pEdge_prev; \
00266 clipInput.pnNodeFrom = pStart; \
00267 clipInput.pnEdge = pEdge; \
00268 clipInput.pnNodeTo = pDestination; \
00269 clipInput.nFromDistance = fromDist; \
00270 if ( fnClip( pgraph , & clipInput , & clipOutput , pvClipArg ) ) continue; \
00271 } \
00272 findPredist.nKey = DGL_NODE_ID(pDestination); \
00273 if ( (pPredistItem = avl_find( pCache->pvPredist, &findPredist)) == NULL ) { \
00274 if ( (pPredistItem = dglTreePredistAdd( pCache->pvPredist, DGL_NODE_ID(pDestination) )) == NULL ) { \
00275 pgraph->iErrno = DGL_ERR_MemoryExhausted; \
00276 goto sp_error; \
00277 } \
00278 } \
00279 else { \
00280 if ( pPredistItem->nDistance <= fromDist + clipOutput.nEdgeCost ) { \
00281 continue; \
00282 } \
00283 } \
00284 pPredistItem->nFrom = DGL_NODE_ID(pStart); \
00285 pPredistItem->pnEdge = pEdge; \
00286 pPredistItem->nCost = clipOutput.nEdgeCost; \
00287 pPredistItem->nDistance = fromDist + clipOutput.nEdgeCost; \
00288 pPredistItem->bFlags = (f); \
00289 heapvalue.pv = pEdge; \
00290 if ( dglHeapInsertMin( & pCache->NodeHeap, pPredistItem->nDistance , f , heapvalue ) < 0 ) { \
00291 pgraph->iErrno = DGL_ERR_HeapError; \
00292 goto sp_error; \
00293 }
00294
00295
00296
00297
00298 int DGL_SP_DIJKSTRA_FUNC(dglGraph_s * pgraph,
00299 dglSPReport_s ** ppReport,
00300 dglInt32_t * pDistance,
00301 dglInt32_t nStart,
00302 dglInt32_t nDestination,
00303 dglSPClip_fn fnClip,
00304 void *pvClipArg, dglSPCache_s * pCache)
00305 {
00306 dglInt32_t *pStart;
00307 register dglInt32_t *pDestination;
00308 register dglInt32_t *pEdgeset;
00309 register dglInt32_t *pEdge;
00310 register dglInt32_t *pEdge_prev;
00311 int nRet;
00312 dglEdgesetTraverser_s laT;
00313
00314 dglSPCache_s spCache;
00315
00316
00317
00318
00319 dglHeapData_u heapvalue;
00320 dglHeapNode_s heapnode;
00321
00322
00323
00324
00325 dglTreeTouchI32_s *pVisitedItem, findVisited;
00326
00327
00328
00329
00330 dglTreePredist_s *pPredistItem, findPredist;
00331
00332
00333
00334
00335 dglSPClipInput_s clipInput;
00336 dglSPClipOutput_s clipOutput;
00337
00338
00339
00340
00341
00342
00343
00344
00345
00346 if (pCache == NULL) {
00347 pCache = &spCache;
00348 DGL_SP_CACHE_INITIALIZE_FUNC(pgraph, pCache, nStart);
00349 }
00350 else {
00351 if (ppReport) {
00352 if ((*ppReport =
00353 DGL_SP_CACHE_REPORT_FUNC(pgraph, pCache, nStart,
00354 nDestination)) != NULL) {
00355 return 1;
00356 }
00357 }
00358 else {
00359 if (DGL_SP_CACHE_DISTANCE_FUNC
00360 (pgraph, pCache, pDistance, nStart, nDestination) >= 0) {
00361 return 2;
00362 }
00363 }
00364 if (pgraph->iErrno == DGL_ERR_HeadNodeNotFound) {
00365 DGL_SP_CACHE_RELEASE_FUNC(pgraph, pCache);
00366 DGL_SP_CACHE_INITIALIZE_FUNC(pgraph, pCache, nStart);
00367 }
00368 else if (pgraph->iErrno != DGL_ERR_TailNodeNotFound) {
00369 goto sp_error;
00370 }
00371 }
00372
00373
00374
00375
00376 pgraph->iErrno = 0;
00377
00378 if ((pStart = DGL_GET_NODE_FUNC(pgraph, nStart)) == NULL) {
00379 pgraph->iErrno = DGL_ERR_HeadNodeNotFound;
00380 goto sp_error;
00381 }
00382
00383 if ((pDestination = DGL_GET_NODE_FUNC(pgraph, nDestination)) == NULL) {
00384 pgraph->iErrno = DGL_ERR_TailNodeNotFound;
00385 goto sp_error;
00386 }
00387
00388 if ((DGL_NODE_STATUS(pStart) & DGL_NS_ALONE) ||
00389 (DGL_NODE_STATUS(pDestination) & DGL_NS_ALONE)) {
00390 goto sp_error;
00391 }
00392
00393 if (!(DGL_NODE_STATUS(pStart) & DGL_NS_HEAD) && pgraph->Version < 3) {
00394 goto sp_error;
00395 }
00396
00397 if (!(DGL_NODE_STATUS(pDestination) & DGL_NS_TAIL) && pgraph->Version < 3) {
00398 goto sp_error;
00399 }
00400
00401
00402
00403
00404
00405
00406
00407
00408
00409
00410
00411
00412 pEdgeset = _DGL_OUTEDGESET(pgraph, pStart);
00413 if (DGL_EDGESET_T_INITIALIZE_FUNC(pgraph, &laT, pEdgeset) < 0) {
00414 goto sp_error;
00415 }
00416 for (pEdge = DGL_EDGESET_T_FIRST_FUNC(&laT);
00417 pEdge; pEdge = DGL_EDGESET_T_NEXT_FUNC(&laT)
00418 ) {
00419 __EDGELOOP_BODY_1(0);
00420 }
00421 DGL_EDGESET_T_RELEASE_FUNC(&laT);
00422
00423 if (pgraph->Version == 3) {
00424 pEdgeset = _DGL_INEDGESET(pgraph, pStart);
00425 if (DGL_EDGESET_T_INITIALIZE_FUNC(pgraph, &laT, pEdgeset) < 0) {
00426 goto sp_error;
00427 }
00428 for (pEdge = DGL_EDGESET_T_FIRST_FUNC(&laT);
00429 pEdge; pEdge = DGL_EDGESET_T_NEXT_FUNC(&laT)
00430 ) {
00431 if (DGL_EDGE_STATUS(pEdge) & DGL_ES_DIRECTED)
00432 continue;
00433 __EDGELOOP_BODY_1(1);
00434 }
00435 DGL_EDGESET_T_RELEASE_FUNC(&laT);
00436 }
00437
00438
00439
00440
00441
00442
00443 while (dglHeapExtractMin(&pCache->NodeHeap, &heapnode) == 1) {
00444 dglInt32_t fromDist;
00445
00446
00447
00448
00449 pEdge = heapnode.value.pv;
00450
00451
00452
00453
00454
00455 if (heapnode.flags == 0) {
00456 pStart = _DGL_EDGE_TAILNODE(pgraph, pEdge);
00457 }
00458 else {
00459 pStart = _DGL_EDGE_HEADNODE(pgraph, pEdge);
00460 }
00461
00462
00463
00464
00465
00466
00467
00468
00469 findVisited.nKey = DGL_NODE_ID(pStart);
00470 if ((pVisitedItem =
00471 avl_find(pCache->pvVisited, &findVisited)) == NULL) {
00472 if (dglTreeTouchI32Add(pCache->pvVisited, DGL_NODE_ID(pStart)) ==
00473 NULL) {
00474 pgraph->iErrno = DGL_ERR_MemoryExhausted;
00475 goto sp_error;
00476 }
00477 }
00478
00479
00480
00481
00482
00483
00484
00485 if (DGL_NODE_ID(pStart) == nDestination) {
00486 goto destination_found;
00487 }
00488
00489
00490
00491
00492 if (pVisitedItem) {
00493 continue;
00494 }
00495
00496
00497
00498
00499
00500
00501 if (!(DGL_NODE_STATUS(pStart) & DGL_NS_HEAD) && pgraph->Version < 3)
00502 continue;
00503
00504
00505
00506
00507 pEdge_prev = pEdge;
00508
00509
00510
00511
00512 findPredist.nKey = DGL_NODE_ID(pStart);
00513 if ((pPredistItem =
00514 avl_find(pCache->pvPredist, &findPredist)) == NULL) {
00515 pgraph->iErrno = DGL_ERR_UnexpectedNullPointer;
00516 goto sp_error;
00517 }
00518
00519 fromDist = pPredistItem->nDistance;
00520
00521
00522
00523
00524
00525
00526
00527 pEdgeset = _DGL_OUTEDGESET(pgraph, pStart);
00528 if (DGL_EDGESET_T_INITIALIZE_FUNC(pgraph, &laT, pEdgeset) < 0) {
00529 goto sp_error;
00530 }
00531 for (pEdge = DGL_EDGESET_T_FIRST_FUNC(&laT);
00532 pEdge; pEdge = DGL_EDGESET_T_NEXT_FUNC(&laT)
00533 ) {
00534 __EDGELOOP_BODY_2(0);
00535 }
00536 DGL_EDGESET_T_RELEASE_FUNC(&laT);
00537
00538 if (pgraph->Version == 3) {
00539 pEdgeset = _DGL_INEDGESET(pgraph, pStart);
00540 if (DGL_EDGESET_T_INITIALIZE_FUNC(pgraph, &laT, pEdgeset) < 0) {
00541 goto sp_error;
00542 }
00543 for (pEdge = DGL_EDGESET_T_FIRST_FUNC(&laT);
00544 pEdge; pEdge = DGL_EDGESET_T_NEXT_FUNC(&laT)
00545 ) {
00546 if (DGL_EDGE_STATUS(pEdge) & DGL_ES_DIRECTED)
00547 continue;
00548 __EDGELOOP_BODY_2(1);
00549 }
00550 DGL_EDGESET_T_RELEASE_FUNC(&laT);
00551 }
00552 }
00553
00554 sp_error:
00555 if (pCache == &spCache) {
00556 DGL_SP_CACHE_RELEASE_FUNC(pgraph, pCache);
00557 }
00558 return -pgraph->iErrno;
00559
00560 destination_found:
00561
00562 if (ppReport) {
00563 *ppReport =
00564 DGL_SP_CACHE_REPORT_FUNC(pgraph, pCache, nStart, nDestination);
00565 if (*ppReport == NULL) {
00566 nRet = -pgraph->iErrno;
00567 }
00568 else {
00569 nRet = 1;
00570 }
00571 }
00572 else {
00573 if (DGL_SP_CACHE_DISTANCE_FUNC
00574 (pgraph, pCache, pDistance, nStart, nDestination) < 0) {
00575 nRet = -pgraph->iErrno;
00576 }
00577 else {
00578 nRet = 2;
00579 }
00580 }
00581 if (pCache == &spCache) {
00582 DGL_SP_CACHE_RELEASE_FUNC(pgraph, pCache);
00583 }
00584 return nRet;
00585 }
00586
00587 #endif