GRASS Programmer's Manual  6.4.2(2012)
sp-template.c
Go to the documentation of this file.
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
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines