GRASS Programmer's Manual
6.4.2(2012)
|
00001 /* LIBDGL -- a Directed Graph Library implementation 00002 * Copyright (C) 2002 Roberto Micarelli 00003 * 00004 * This program is free software; you can redistribute it and/or modify 00005 * it under the terms of the GNU General Public License as published by 00006 * the Free Software Foundation; either version 2 of the License, or 00007 * (at your option) any later version. 00008 * 00009 * This program is distributed in the hope that it will be useful, 00010 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00011 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00012 * GNU General Public License for more details. 00013 * 00014 * You should have received a copy of the GNU General Public License 00015 * along with this program; if not, write to the Free Software 00016 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA 00017 */ 00018 00019 /* 00020 * best view with tabstop=4 00021 */ 00022 00023 00024 /* 00025 * SHORTEST PATH CACHE 00026 * 00027 * components: 00028 * - start node id 00029 * - visited network: a node is marked as visited when its departing 00030 * edges have been added to the cache 00031 * - predist network: node distances from start node 00032 * - NodeHeap: holds unvisited nodes, the next node extracted is the 00033 * unvisited node closest to SP start 00034 * 00035 * not all nodes in the predist network have been visited, SP from start 00036 * is known only for visited nodes 00037 * unvisited nodes can be reached, but not necessarily on the shortest 00038 * possible path 00039 * important for DGL_SP_CACHE_DISTANCE_FUNC and DGL_SP_CACHE_REPORT_FUNC 00040 */ 00041 00042 #if !defined(DGL_DEFINE_TREE_PROCS) && !defined(DGL_DEFINE_FLAT_PROCS) 00043 00044 int DGL_SP_CACHE_INITIALIZE_FUNC(dglGraph_s * pgraph, dglSPCache_s * pCache, 00045 dglInt32_t nStart) 00046 { 00047 pCache->nStartNode = nStart; 00048 pCache->pvVisited = NULL; 00049 pCache->pvPredist = NULL; 00050 dglHeapInit(&pCache->NodeHeap); 00051 if ((pCache->pvVisited = 00052 avl_create(dglTreeTouchI32Compare, NULL, 00053 dglTreeGetAllocator())) == NULL) 00054 return -1; 00055 if ((pCache->pvPredist = 00056 avl_create(dglTreePredistCompare, NULL, 00057 dglTreeGetAllocator())) == NULL) 00058 return -1; 00059 return 0; 00060 } 00061 00062 void DGL_SP_CACHE_RELEASE_FUNC(dglGraph_s * pgraph, dglSPCache_s * pCache) 00063 { 00064 if (pCache->pvVisited) 00065 avl_destroy(pCache->pvVisited, dglTreeTouchI32Cancel); 00066 if (pCache->pvPredist) 00067 avl_destroy(pCache->pvPredist, dglTreePredistCancel); 00068 dglHeapFree(&pCache->NodeHeap, NULL); 00069 } 00070 00071 00072 static int DGL_SP_CACHE_DISTANCE_FUNC(dglGraph_s * pgraph, 00073 dglSPCache_s * pCache, 00074 dglInt32_t * pnDistance, 00075 dglInt32_t nStart, 00076 dglInt32_t nDestination) 00077 { 00078 dglTreeTouchI32_s VisitedItem; 00079 dglTreePredist_s *pPredistItem, PredistItem; 00080 00081 if (pCache->nStartNode != nStart) { 00082 pgraph->iErrno = DGL_ERR_HeadNodeNotFound; 00083 return -pgraph->iErrno; 00084 } 00085 00086 VisitedItem.nKey = nDestination; 00087 if (avl_find(pCache->pvVisited, &VisitedItem) == NULL) { 00088 pgraph->iErrno = DGL_ERR_TailNodeNotFound; 00089 return -pgraph->iErrno; 00090 } 00091 00092 PredistItem.nKey = nDestination; 00093 if ((pPredistItem = avl_find(pCache->pvPredist, &PredistItem)) == NULL) { 00094 pgraph->iErrno = DGL_ERR_UnexpectedNullPointer; 00095 return -pgraph->iErrno; 00096 } 00097 00098 if (pnDistance) 00099 *pnDistance = pPredistItem->nDistance; 00100 return 0; 00101 } 00102 00103 static dglSPReport_s *DGL_SP_CACHE_REPORT_FUNC(dglGraph_s * pgraph, 00104 dglSPCache_s * pCache, 00105 dglInt32_t nStart, 00106 dglInt32_t nDestination) 00107 { 00108 dglTreeTouchI32_s VisitedItem; 00109 dglTreePredist_s *pPredistItem, PredistItem; 00110 dglInt32_t *pEdge; 00111 dglInt32_t *pDestination; 00112 dglSPArc_s arc; 00113 long i, istack = 0; 00114 unsigned char *pstack = NULL; 00115 unsigned char *ppop; 00116 dglSPReport_s *pReport = NULL; 00117 00118 if (pCache->nStartNode != nStart) { 00119 pgraph->iErrno = DGL_ERR_HeadNodeNotFound; 00120 return NULL; 00121 } 00122 00123 VisitedItem.nKey = nDestination; 00124 if (avl_find(pCache->pvVisited, &VisitedItem) == NULL) { 00125 pgraph->iErrno = DGL_ERR_TailNodeNotFound; 00126 return NULL; 00127 } 00128 00129 PredistItem.nKey = nDestination; 00130 if (avl_find(pCache->pvPredist, &PredistItem) == NULL) { 00131 pgraph->iErrno = DGL_ERR_UnexpectedNullPointer; 00132 return NULL; 00133 } 00134 00135 for (PredistItem.nKey = nDestination, 00136 pPredistItem = avl_find(pCache->pvPredist, &PredistItem); 00137 pPredistItem; 00138 PredistItem.nKey = pPredistItem->nFrom, 00139 pPredistItem = avl_find(pCache->pvPredist, &PredistItem) 00140 ) { 00141 if (pPredistItem->nFrom < 0) { 00142 pgraph->iErrno = DGL_ERR_BadEdge; 00143 goto spr_error; 00144 } 00145 00146 pEdge = (dglInt32_t *) pPredistItem->pnEdge; 00147 00148 if (pPredistItem->bFlags == 0) { 00149 if (pgraph->Flags & DGL_GS_FLAT) { 00150 pDestination = 00151 DGL_NODEBUFFER_SHIFT(pgraph, 00152 DGL_EDGE_TAILNODE_OFFSET(pEdge)); 00153 } 00154 else { 00155 pDestination = 00156 DGL_GET_NODE_FUNC(pgraph, 00157 DGL_EDGE_TAILNODE_OFFSET(pEdge)); 00158 } 00159 } 00160 else { 00161 if (pgraph->Flags & DGL_GS_FLAT) { 00162 pDestination = 00163 DGL_NODEBUFFER_SHIFT(pgraph, 00164 DGL_EDGE_HEADNODE_OFFSET(pEdge)); 00165 } 00166 else { 00167 pDestination = 00168 DGL_GET_NODE_FUNC(pgraph, 00169 DGL_EDGE_HEADNODE_OFFSET(pEdge)); 00170 } 00171 } 00172 00173 if ((arc.pnEdge = DGL_EDGE_ALLOC(pgraph->EdgeAttrSize)) == NULL) 00174 goto spr_error; 00175 arc.nFrom = pPredistItem->nFrom; 00176 arc.nTo = DGL_NODE_ID(pDestination); 00177 arc.nDistance = pPredistItem->nDistance; 00178 memcpy(arc.pnEdge, pEdge, DGL_EDGE_SIZEOF(pgraph->EdgeAttrSize)); 00179 DGL_EDGE_COST(arc.pnEdge) = pPredistItem->nCost; 00180 00181 if ((pstack = 00182 dgl_mempush(pstack, &istack, sizeof(dglSPArc_s), 00183 &arc)) == NULL) { 00184 pgraph->iErrno = DGL_ERR_MemoryExhausted; 00185 goto spr_error; 00186 } 00187 00188 if (arc.nFrom == nStart) 00189 break; 00190 } 00191 00192 if (pPredistItem == NULL) { 00193 pgraph->iErrno = DGL_ERR_UnexpectedNullPointer; 00194 goto spr_error; 00195 } 00196 00197 if ((pReport = malloc(sizeof(dglSPReport_s))) == NULL) { 00198 pgraph->iErrno = DGL_ERR_MemoryExhausted; 00199 goto spr_error; 00200 } 00201 memset(pReport, 0, sizeof(dglSPReport_s)); 00202 00203 pReport->cArc = istack; 00204 00205 if ((pReport->pArc = malloc(sizeof(dglSPArc_s) * pReport->cArc)) == NULL) { 00206 pgraph->iErrno = DGL_ERR_MemoryExhausted; 00207 goto spr_error; 00208 } 00209 00210 pReport->nDistance = 0; 00211 00212 for (i = 0; 00213 (ppop = dgl_mempop(pstack, &istack, sizeof(dglSPArc_s))) != NULL; 00214 i++) { 00215 memcpy(&pReport->pArc[i], ppop, sizeof(dglSPArc_s)); 00216 pReport->nDistance += DGL_EDGE_COST(pReport->pArc[i].pnEdge); 00217 } 00218 00219 pReport->nStartNode = nStart; 00220 pReport->nDestinationNode = nDestination; 00221 00222 if (pstack) 00223 free(pstack); 00224 00225 return pReport; 00226 00227 spr_error: 00228 if (pstack) 00229 free(pstack); 00230 if (pReport) 00231 dglFreeSPReport(pgraph, pReport); 00232 00233 return NULL; 00234 } 00235 #endif 00236 00237 #if defined(DGL_DEFINE_TREE_PROCS) || defined(DGL_DEFINE_FLAT_PROCS) 00238 00239 #define __EDGELOOP_BODY_1(f) \ 00240 if ( (f) == 0 ) { \ 00241 pDestination = _DGL_EDGE_TAILNODE(pgraph, pEdge); \ 00242 } \ 00243 else { \ 00244 pDestination = _DGL_EDGE_HEADNODE(pgraph, pEdge); \ 00245 } \ 00246 if ( !(DGL_NODE_STATUS(pDestination) & DGL_NS_TAIL) && pgraph->Version < 3) { \ 00247 pgraph->iErrno = DGL_ERR_BadEdge; \ 00248 goto sp_error; \ 00249 } \ 00250 clipOutput.nEdgeCost = DGL_EDGE_COST(pEdge); \ 00251 if ( fnClip ) { \ 00252 clipInput.pnPrevEdge = NULL; \ 00253 clipInput.pnNodeFrom = pStart; \ 00254 clipInput.pnEdge = pEdge; \ 00255 clipInput.pnNodeTo = pDestination; \ 00256 clipInput.nFromDistance = 0; \ 00257 if ( fnClip( pgraph , & clipInput , & clipOutput , pvClipArg ) ) continue; \ 00258 } \ 00259 pPredistItem = dglTreePredistAdd( pCache->pvPredist, DGL_NODE_ID(pDestination) ); \ 00260 if ( pPredistItem == NULL ) goto sp_error; \ 00261 pPredistItem->nFrom = nStart; \ 00262 pPredistItem->pnEdge = pEdge; \ 00263 pPredistItem->nCost = clipOutput.nEdgeCost; \ 00264 pPredistItem->nDistance = clipOutput.nEdgeCost; \ 00265 pPredistItem->bFlags = (f); \ 00266 heapvalue.pv = pEdge; \ 00267 if ( dglHeapInsertMin( & pCache->NodeHeap, pPredistItem->nDistance , f , heapvalue ) < 0 ) { \ 00268 pgraph->iErrno = DGL_ERR_HeapError; \ 00269 goto sp_error; \ 00270 } 00271 00272 #define __EDGELOOP_BODY_2(f) \ 00273 if ( (f) == 0 ) { \ 00274 pDestination = _DGL_EDGE_TAILNODE(pgraph, pEdge); \ 00275 } \ 00276 else if ( pgraph->Version == 3 ) { \ 00277 pDestination = _DGL_EDGE_HEADNODE(pgraph, pEdge); \ 00278 } \ 00279 if ( !(DGL_NODE_STATUS(pDestination) & DGL_NS_TAIL) && pgraph->Version < 3) { \ 00280 pgraph->iErrno = DGL_ERR_BadEdge; \ 00281 goto sp_error; \ 00282 } \ 00283 clipOutput.nEdgeCost = DGL_EDGE_COST(pEdge); \ 00284 if ( fnClip ) { \ 00285 clipInput.pnPrevEdge = pEdge_prev; \ 00286 clipInput.pnNodeFrom = pStart; \ 00287 clipInput.pnEdge = pEdge; \ 00288 clipInput.pnNodeTo = pDestination; \ 00289 clipInput.nFromDistance = fromDist; \ 00290 if ( fnClip( pgraph , & clipInput , & clipOutput , pvClipArg ) ) continue; \ 00291 } \ 00292 findPredist.nKey = DGL_NODE_ID(pDestination); \ 00293 if ( (pPredistItem = avl_find( pCache->pvPredist, &findPredist)) == NULL ) { \ 00294 if ( (pPredistItem = dglTreePredistAdd( pCache->pvPredist, DGL_NODE_ID(pDestination) )) == NULL ) { \ 00295 pgraph->iErrno = DGL_ERR_MemoryExhausted; \ 00296 goto sp_error; \ 00297 } \ 00298 } \ 00299 else { \ 00300 if ( pPredistItem->nDistance <= fromDist + clipOutput.nEdgeCost ) { \ 00301 continue; \ 00302 } \ 00303 } \ 00304 pPredistItem->nFrom = DGL_NODE_ID(pStart); \ 00305 pPredistItem->pnEdge = pEdge; \ 00306 pPredistItem->nCost = clipOutput.nEdgeCost; \ 00307 pPredistItem->nDistance = fromDist + clipOutput.nEdgeCost; \ 00308 pPredistItem->bFlags = (f); \ 00309 heapvalue.pv = pEdge; \ 00310 if ( dglHeapInsertMin( & pCache->NodeHeap, pPredistItem->nDistance , f , heapvalue ) < 0 ) { \ 00311 pgraph->iErrno = DGL_ERR_HeapError; \ 00312 goto sp_error; \ 00313 } 00314 00315 /* 00316 * Dijkstra Shortest Path 00317 */ 00318 int DGL_SP_DIJKSTRA_FUNC(dglGraph_s * pgraph, 00319 dglSPReport_s ** ppReport, 00320 dglInt32_t * pDistance, 00321 dglInt32_t nStart, 00322 dglInt32_t nDestination, 00323 dglSPClip_fn fnClip, 00324 void *pvClipArg, dglSPCache_s * pCache) 00325 { 00326 dglInt32_t *pStart; /* pointer to the start node (pgraph->pNodeBuffer) */ 00327 register dglInt32_t *pDestination; /* temporary destination pointer */ 00328 register dglInt32_t *pEdgeset; /* pointer to the edge (pgraph->pEdgeBuffer) */ 00329 register dglInt32_t *pEdge; /* pointer to the to-edges in edge */ 00330 register dglInt32_t *pEdge_prev; /* pointer to the previous edge in path */ 00331 int nRet; 00332 dglEdgesetTraverser_s laT; 00333 00334 dglSPCache_s spCache; 00335 int new_cache = 0; 00336 00337 /* 00338 * shortest path distance temporary min heap 00339 */ 00340 dglHeapData_u heapvalue; 00341 dglHeapNode_s heapnode; 00342 00343 /* 00344 * shortest path visited network 00345 */ 00346 dglTreeTouchI32_s *pVisitedItem, findVisited; 00347 00348 /* 00349 * shortest path predecessor and distance network 00350 */ 00351 dglTreePredist_s *pPredistItem, findPredist; 00352 00353 /* 00354 * args to clip() 00355 */ 00356 dglSPClipInput_s clipInput; 00357 dglSPClipOutput_s clipOutput; 00358 00359 00360 /* 00361 * Initialize the cache: initialize the heap and create temporary networks - 00362 * The use of a predist network for predecessor and distance has two important results: 00363 * 1) allows us not having to reset the whole graph status at each call; 00364 * 2) use of a stack memory area for temporary (and otherwise possibly thread-conflicting) states. 00365 * If a cache pointer was supplied, do not initialize it but try to get SP immediately. 00366 */ 00367 if (pCache == NULL) { 00368 pCache = &spCache; 00369 DGL_SP_CACHE_INITIALIZE_FUNC(pgraph, pCache, nStart); 00370 new_cache = 1; 00371 } 00372 else { 00373 if (ppReport) { 00374 if ((*ppReport = 00375 DGL_SP_CACHE_REPORT_FUNC(pgraph, pCache, nStart, 00376 nDestination)) != NULL) { 00377 return 1; 00378 } 00379 } 00380 else { 00381 if (DGL_SP_CACHE_DISTANCE_FUNC 00382 (pgraph, pCache, pDistance, nStart, nDestination) >= 0) { 00383 return 2; 00384 } 00385 } 00386 if (pgraph->iErrno == DGL_ERR_HeadNodeNotFound) { 00387 DGL_SP_CACHE_RELEASE_FUNC(pgraph, pCache); 00388 DGL_SP_CACHE_INITIALIZE_FUNC(pgraph, pCache, nStart); 00389 new_cache = 1; 00390 } 00391 else if (pgraph->iErrno != DGL_ERR_TailNodeNotFound) { 00392 goto sp_error; 00393 } 00394 } 00395 00396 /* 00397 * reset error status after using the cache 00398 */ 00399 pgraph->iErrno = 0; 00400 00401 if ((pStart = DGL_GET_NODE_FUNC(pgraph, nStart)) == NULL) { 00402 pgraph->iErrno = DGL_ERR_HeadNodeNotFound; 00403 goto sp_error; 00404 } 00405 00406 if ((pDestination = DGL_GET_NODE_FUNC(pgraph, nDestination)) == NULL) { 00407 pgraph->iErrno = DGL_ERR_TailNodeNotFound; 00408 goto sp_error; 00409 } 00410 00411 if ((DGL_NODE_STATUS(pStart) & DGL_NS_ALONE) || 00412 (DGL_NODE_STATUS(pDestination) & DGL_NS_ALONE)) { 00413 goto sp_error; 00414 } 00415 00416 if (!(DGL_NODE_STATUS(pStart) & DGL_NS_HEAD) && pgraph->Version < 3) { 00417 goto sp_error; 00418 } 00419 00420 if (!(DGL_NODE_STATUS(pDestination) & DGL_NS_TAIL) && pgraph->Version < 3) { 00421 goto sp_error; 00422 } 00423 00424 /* if we do not need a new cache, we just continue with the unvisited 00425 * nodes in the cache */ 00426 if (new_cache) { 00427 /* 00428 * now we inspect all edges departing from the start node 00429 * - at each loop 'pedge' points to the edge in the edge buffer 00430 * - we invoke the caller's clip() and eventually skip the edge (clip() != 0) 00431 * - we insert a item in the predist network to set actual predecessor and distance 00432 * (there is no precedecessor at this stage) and actual distance from the starting node 00433 * (at this stage it equals the edge's cost) 00434 * - we insert a item in the node min-heap (sorted on node distance), storing the offset of the 00435 * edge in the edge buffer. 00436 * In the case of undirected graph (version 3) we inspect input edges as well. 00437 */ 00438 pEdgeset = _DGL_OUTEDGESET(pgraph, pStart); 00439 if (DGL_EDGESET_T_INITIALIZE_FUNC(pgraph, &laT, pEdgeset) < 0) { 00440 goto sp_error; 00441 } 00442 for (pEdge = DGL_EDGESET_T_FIRST_FUNC(&laT); 00443 pEdge; pEdge = DGL_EDGESET_T_NEXT_FUNC(&laT) 00444 ) { 00445 __EDGELOOP_BODY_1(0); 00446 } 00447 DGL_EDGESET_T_RELEASE_FUNC(&laT); 00448 00449 if (pgraph->Version == 3) { 00450 pEdgeset = _DGL_INEDGESET(pgraph, pStart); 00451 if (DGL_EDGESET_T_INITIALIZE_FUNC(pgraph, &laT, pEdgeset) < 0) { 00452 goto sp_error; 00453 } 00454 for (pEdge = DGL_EDGESET_T_FIRST_FUNC(&laT); 00455 pEdge; pEdge = DGL_EDGESET_T_NEXT_FUNC(&laT) 00456 ) { 00457 if (DGL_EDGE_STATUS(pEdge) & DGL_ES_DIRECTED) 00458 continue; 00459 __EDGELOOP_BODY_1(1); 00460 } 00461 DGL_EDGESET_T_RELEASE_FUNC(&laT); 00462 } 00463 } 00464 00465 /* 00466 * Now we begin extracting nodes from the min-heap. Each node extracted is 00467 * the one that is actually closest to the SP start. 00468 */ 00469 while (dglHeapExtractMin(&pCache->NodeHeap, &heapnode) == 1) { 00470 dglInt32_t fromDist; 00471 00472 /* 00473 * recover the stored edge pointer 00474 */ 00475 pEdge = heapnode.value.pv; 00476 00477 /* 00478 * the new relative head is the tail of the edge 00479 * or the head of the edge if the traversal was reversed (undirected edge) 00480 */ 00481 if (heapnode.flags == 0) { 00482 pStart = _DGL_EDGE_TAILNODE(pgraph, pEdge); /* continue from previous tail */ 00483 } 00484 else { 00485 pStart = _DGL_EDGE_HEADNODE(pgraph, pEdge); /* reversed head/tail */ 00486 } 00487 00488 /* 00489 * We do not want to explore twice the same node as a relative starting point, 00490 * that's the meaning of 'visited'. We mark actual start node as 'visited' by 00491 * inserting it into the visited-network. If we find actual node in the network 00492 * we just give up and continue looping. Otherwise we add actual node to the network. 00493 */ 00494 findVisited.nKey = DGL_NODE_ID(pStart); 00495 if ((pVisitedItem = 00496 avl_find(pCache->pvVisited, &findVisited)) == NULL) { 00497 if (dglTreeTouchI32Add(pCache->pvVisited, DGL_NODE_ID(pStart)) == 00498 NULL) { 00499 pgraph->iErrno = DGL_ERR_MemoryExhausted; 00500 goto sp_error; 00501 } 00502 } 00503 00504 /* 00505 * Give up with visited nodes now 00506 */ 00507 if (pVisitedItem) { 00508 if (DGL_NODE_ID(pStart) == nDestination) { 00509 /* should not happen but does not harm 00510 * this case should have been handled above */ 00511 goto destination_found; 00512 } 00513 else 00514 continue; 00515 } 00516 00517 /* 00518 * If the node is not marked as having departing edges, then we are into a 00519 * blind alley. Just give up this direction and continue looping. 00520 * This only applies to v1 and v2 (digraphs) 00521 */ 00522 if (!(DGL_NODE_STATUS(pStart) & DGL_NS_HEAD) && pgraph->Version < 3) { 00523 if (DGL_NODE_ID(pStart) == nDestination) { 00524 goto destination_found; 00525 } 00526 else 00527 continue; 00528 } 00529 00530 /* 00531 * save actual edge for later clip() 00532 */ 00533 pEdge_prev = pEdge; 00534 00535 /* 00536 * Recover the head node distance from the predist network 00537 */ 00538 findPredist.nKey = DGL_NODE_ID(pStart); 00539 if ((pPredistItem = 00540 avl_find(pCache->pvPredist, &findPredist)) == NULL) { 00541 pgraph->iErrno = DGL_ERR_UnexpectedNullPointer; 00542 goto sp_error; 00543 } 00544 00545 fromDist = pPredistItem->nDistance; 00546 00547 /* 00548 * Loop on departing edges: 00549 * Scan the edgeset and loads pedge at each iteration with next-edge. 00550 * iWay == DGL_EDGESET_T_WAY_OUT then pedge is a out arc (departing from node) else ot is a in arc. 00551 * V1 has no in-degree support so iWay is always OUT, V2/3 have in-degree support. 00552 * 00553 * This loop needs to be done also when destination is found, otherwise 00554 * the node is marked as visited but its departing edges are not added to the cache 00555 * --> loose end, we might need these edges later on 00556 */ 00557 pEdgeset = _DGL_OUTEDGESET(pgraph, pStart); 00558 if (DGL_EDGESET_T_INITIALIZE_FUNC(pgraph, &laT, pEdgeset) < 0) { 00559 goto sp_error; 00560 } 00561 for (pEdge = DGL_EDGESET_T_FIRST_FUNC(&laT); 00562 pEdge; pEdge = DGL_EDGESET_T_NEXT_FUNC(&laT) 00563 ) { 00564 __EDGELOOP_BODY_2(0); 00565 } 00566 DGL_EDGESET_T_RELEASE_FUNC(&laT); 00567 00568 if (pgraph->Version == 3) { 00569 pEdgeset = _DGL_INEDGESET(pgraph, pStart); 00570 if (DGL_EDGESET_T_INITIALIZE_FUNC(pgraph, &laT, pEdgeset) < 0) { 00571 goto sp_error; 00572 } 00573 for (pEdge = DGL_EDGESET_T_FIRST_FUNC(&laT); 00574 pEdge; pEdge = DGL_EDGESET_T_NEXT_FUNC(&laT) 00575 ) { 00576 if (DGL_EDGE_STATUS(pEdge) & DGL_ES_DIRECTED) 00577 continue; 00578 __EDGELOOP_BODY_2(1); 00579 } 00580 DGL_EDGESET_T_RELEASE_FUNC(&laT); 00581 } 00582 00583 /* 00584 * Dijkstra algorithm ends when the destination node is extracted from 00585 * the min distance heap, that means: no other path exist in the network giving 00586 * a shortest output. 00587 * If this happens we jump to the epilogue in order to build a path report and return. 00588 */ 00589 if (DGL_NODE_ID(pStart) == nDestination) { 00590 goto destination_found; 00591 } 00592 } 00593 00594 sp_error: 00595 if (pCache == &spCache) { 00596 DGL_SP_CACHE_RELEASE_FUNC(pgraph, pCache); 00597 } 00598 return -pgraph->iErrno; /* == 0 path not found */ 00599 00600 destination_found: /* path found - build a shortest path report or report the distance only */ 00601 00602 if (ppReport) { 00603 *ppReport = 00604 DGL_SP_CACHE_REPORT_FUNC(pgraph, pCache, nStart, nDestination); 00605 if (*ppReport == NULL) { 00606 nRet = -pgraph->iErrno; 00607 } 00608 else { 00609 nRet = 1; 00610 } 00611 } 00612 else { 00613 if (DGL_SP_CACHE_DISTANCE_FUNC 00614 (pgraph, pCache, pDistance, nStart, nDestination) < 0) { 00615 nRet = -pgraph->iErrno; 00616 } 00617 else { 00618 nRet = 2; 00619 } 00620 } 00621 if (pCache == &spCache) { 00622 DGL_SP_CACHE_RELEASE_FUNC(pgraph, pCache); 00623 } 00624 return nRet; 00625 } 00626 00627 #endif