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