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., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
00017  */
00018 
00019 /*
00020  * best view with tabstop=4
00021  */
00022 
00023 
00024 /*
00025  * SHORTEST PATH CACHE
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  * Dijkstra Shortest Path 
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;         /* pointer to the start node (pgraph->pNodeBuffer) */
00307     register dglInt32_t *pDestination;  /* temporary destination pointer */
00308     register dglInt32_t *pEdgeset;      /* pointer to the edge (pgraph->pEdgeBuffer) */
00309     register dglInt32_t *pEdge; /* pointer to the to-edges in edge  */
00310     register dglInt32_t *pEdge_prev;    /* pointer to the previous edge in path */
00311     int nRet;
00312     dglEdgesetTraverser_s laT;
00313 
00314     dglSPCache_s spCache;
00315 
00316     /*
00317      * shortest path distance temporary min heap
00318      */
00319     dglHeapData_u heapvalue;
00320     dglHeapNode_s heapnode;
00321 
00322     /*
00323      * shortest path visited network
00324      */
00325     dglTreeTouchI32_s *pVisitedItem, findVisited;
00326 
00327     /*
00328      * shortest path predecessor and distance network
00329      */
00330     dglTreePredist_s *pPredistItem, findPredist;
00331 
00332     /*
00333      * args to clip()
00334      */
00335     dglSPClipInput_s clipInput;
00336     dglSPClipOutput_s clipOutput;
00337 
00338 
00339     /*
00340      * Initialize the cache: initialize the heap and create temporary networks -
00341      * The use of a predist network for predecessor and distance has two important results:
00342      * 1) allows us not having to reset the whole graph status at each call;
00343      * 2) use of a stack memory area for temporary (and otherwise possibly thread-conflicting) states.
00344      * If a cache pointer was supplied, do not initialize it but try to get SP immediately.
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          * reset visited status for existing cache: fix for BUG1
00373          */
00374         if (pCache->pvVisited) {
00375             avl_destroy(pCache->pvVisited, dglTreeTouchI32Cancel);
00376 
00377             if ((pCache->pvVisited =
00378                 avl_create(dglTreeTouchI32Compare, NULL,
00379                         dglTreeGetAllocator())) == NULL)
00380                 return -1;
00381         }
00382     }
00383 
00384     /*
00385      * reset error status after using the cache
00386      */
00387     pgraph->iErrno = 0;
00388 
00389     if ((pStart = DGL_GET_NODE_FUNC(pgraph, nStart)) == NULL) {
00390         pgraph->iErrno = DGL_ERR_HeadNodeNotFound;
00391         goto sp_error;
00392     }
00393 
00394     if ((pDestination = DGL_GET_NODE_FUNC(pgraph, nDestination)) == NULL) {
00395         pgraph->iErrno = DGL_ERR_TailNodeNotFound;
00396         goto sp_error;
00397     }
00398 
00399     if ((DGL_NODE_STATUS(pStart) & DGL_NS_ALONE) ||
00400         (DGL_NODE_STATUS(pDestination) & DGL_NS_ALONE)) {
00401         goto sp_error;
00402     }
00403 
00404     if (!(DGL_NODE_STATUS(pStart) & DGL_NS_HEAD) && pgraph->Version < 3) {
00405         goto sp_error;
00406     }
00407 
00408     if (!(DGL_NODE_STATUS(pDestination) & DGL_NS_TAIL) && pgraph->Version < 3) {
00409         goto sp_error;
00410     }
00411 
00412     /*
00413      * now we inspect all edges departing from the start node
00414      * - at each loop 'pedge' points to the edge in the edge buffer
00415      * - we invoke the caller's clip() and eventually skip the edge (clip() != 0)
00416      * - we insert a item in the predist network to set actual predecessor and distance
00417      *   (there is no precedecessor at this stage) and actual distance from the starting node
00418      *   (at this stage it equals the edge's cost)
00419      * - we insert a item in the node min-heap (sorted on node distance), storing the offset of the
00420      *   edge in the edge buffer.
00421      * In the case of undirected graph (version 3) we inspect input edges as well.
00422      */
00423     pEdgeset = _DGL_OUTEDGESET(pgraph, pStart);
00424     if (DGL_EDGESET_T_INITIALIZE_FUNC(pgraph, &laT, pEdgeset) < 0) {
00425         goto sp_error;
00426     }
00427     for (pEdge = DGL_EDGESET_T_FIRST_FUNC(&laT);
00428          pEdge; pEdge = DGL_EDGESET_T_NEXT_FUNC(&laT)
00429         ) {
00430         __EDGELOOP_BODY_1(0);
00431     }
00432     DGL_EDGESET_T_RELEASE_FUNC(&laT);
00433 
00434     if (pgraph->Version == 3) {
00435         pEdgeset = _DGL_INEDGESET(pgraph, pStart);
00436         if (DGL_EDGESET_T_INITIALIZE_FUNC(pgraph, &laT, pEdgeset) < 0) {
00437             goto sp_error;
00438         }
00439         for (pEdge = DGL_EDGESET_T_FIRST_FUNC(&laT);
00440              pEdge; pEdge = DGL_EDGESET_T_NEXT_FUNC(&laT)
00441             ) {
00442             if (DGL_EDGE_STATUS(pEdge) & DGL_ES_DIRECTED)
00443                 continue;
00444             __EDGELOOP_BODY_1(1);
00445         }
00446         DGL_EDGESET_T_RELEASE_FUNC(&laT);
00447     }
00448 
00449 
00450     /*
00451      * Now we begin extracting nodes from the min-heap. Each node extracted is
00452      * the one that is actually closest to the SP start.
00453      */
00454     while (dglHeapExtractMin(&pCache->NodeHeap, &heapnode) == 1) {
00455         dglInt32_t fromDist;
00456 
00457         /*
00458          * recover the stored edge pointer
00459          */
00460         pEdge = heapnode.value.pv;
00461 
00462         /*
00463          * the new relative head is the tail of the edge
00464          * or the head of the edge if the traversal was reversed (undirected edge)
00465          */
00466         if (heapnode.flags == 0) {
00467             pStart = _DGL_EDGE_TAILNODE(pgraph, pEdge); /* continue from previous tail */
00468         }
00469         else {
00470             pStart = _DGL_EDGE_HEADNODE(pgraph, pEdge); /* reversed head/tail */
00471         }
00472 
00473 
00474         /*
00475          * We do not want to explore twice the same node as a relative starting point,
00476          * that's the meaning of 'visited'. We mark actual start node as 'visited' by
00477          * inserting it into the visited-network. If we find actual node in the network
00478          * we just give up and continue looping. Otherwise we add actual node to the network.
00479          */
00480         findVisited.nKey = DGL_NODE_ID(pStart);
00481         if ((pVisitedItem =
00482              avl_find(pCache->pvVisited, &findVisited)) == NULL) {
00483             if (dglTreeTouchI32Add(pCache->pvVisited, DGL_NODE_ID(pStart)) ==
00484                 NULL) {
00485                 pgraph->iErrno = DGL_ERR_MemoryExhausted;
00486                 goto sp_error;
00487             }
00488         }
00489 
00490         /*
00491          * Dijkstra algorithm ends when the destination node is extracted from
00492          * the min distance heap, that means: no other path exist in the network giving
00493          * a shortest output.
00494          * If this happens we jump to the epilogue in order to build a path report and return.
00495          */
00496         if (DGL_NODE_ID(pStart) == nDestination) {
00497             goto destination_found;
00498         }
00499 
00500         /*
00501          * Give up with visited nodes now
00502          */
00503         if (pVisitedItem) {
00504             continue;
00505         }
00506 
00507         /*
00508          * If the node is not marked as having departing edges, then we are into a
00509          * blind alley. Just give up this direction and continue looping.
00510          * This only applies to v1 and v2 (digraphs)
00511          */
00512         if (!(DGL_NODE_STATUS(pStart) & DGL_NS_HEAD) && pgraph->Version < 3)
00513             continue;
00514 
00515         /*
00516          * save actual edge for later clip()
00517          */
00518         pEdge_prev = pEdge;
00519 
00520         /*
00521          * Recover the head node distance from the predist network
00522          */
00523         findPredist.nKey = DGL_NODE_ID(pStart);
00524         if ((pPredistItem =
00525              avl_find(pCache->pvPredist, &findPredist)) == NULL) {
00526             pgraph->iErrno = DGL_ERR_UnexpectedNullPointer;
00527             goto sp_error;
00528         }
00529 
00530         fromDist = pPredistItem->nDistance;
00531 
00532         /*
00533          * Loop on departing edges:
00534          * Scan the edgeset and loads pedge at each iteration with next-edge.
00535          * iWay == DGL_EDGESET_T_WAY_OUT then pedge is a out arc (departing from node) else ot is a in arc.
00536          * V1 has no in-degree support so iWay is always OUT, V2/3 have in-degree support.
00537          */
00538         pEdgeset = _DGL_OUTEDGESET(pgraph, pStart);
00539         if (DGL_EDGESET_T_INITIALIZE_FUNC(pgraph, &laT, pEdgeset) < 0) {
00540             goto sp_error;
00541         }
00542         for (pEdge = DGL_EDGESET_T_FIRST_FUNC(&laT);
00543              pEdge; pEdge = DGL_EDGESET_T_NEXT_FUNC(&laT)
00544             ) {
00545             __EDGELOOP_BODY_2(0);
00546         }
00547         DGL_EDGESET_T_RELEASE_FUNC(&laT);
00548 
00549         if (pgraph->Version == 3) {
00550             pEdgeset = _DGL_INEDGESET(pgraph, pStart);
00551             if (DGL_EDGESET_T_INITIALIZE_FUNC(pgraph, &laT, pEdgeset) < 0) {
00552                 goto sp_error;
00553             }
00554             for (pEdge = DGL_EDGESET_T_FIRST_FUNC(&laT);
00555                  pEdge; pEdge = DGL_EDGESET_T_NEXT_FUNC(&laT)
00556                 ) {
00557                 if (DGL_EDGE_STATUS(pEdge) & DGL_ES_DIRECTED)
00558                     continue;
00559                 __EDGELOOP_BODY_2(1);
00560             }
00561             DGL_EDGESET_T_RELEASE_FUNC(&laT);
00562         }
00563     }
00564 
00565   sp_error:
00566     if (pCache == &spCache) {
00567         DGL_SP_CACHE_RELEASE_FUNC(pgraph, pCache);
00568     }
00569     return -pgraph->iErrno;     /* ==0 path not found */
00570 
00571   destination_found:            /* path found - build a shortest path report or report the distance only */
00572 
00573     if (ppReport) {
00574         *ppReport =
00575             DGL_SP_CACHE_REPORT_FUNC(pgraph, pCache, nStart, nDestination);
00576         if (*ppReport == NULL) {
00577             nRet = -pgraph->iErrno;
00578         }
00579         else {
00580             nRet = 1;
00581         }
00582     }
00583     else {
00584         if (DGL_SP_CACHE_DISTANCE_FUNC
00585             (pgraph, pCache, pDistance, nStart, nDestination) < 0) {
00586             nRet = -pgraph->iErrno;
00587         }
00588         else {
00589             nRet = 2;
00590         }
00591     }
00592     if (pCache == &spCache) {
00593         DGL_SP_CACHE_RELEASE_FUNC(pgraph, pCache);
00594     }
00595     return nRet;
00596 }
00597 
00598 #endif
Generated on Tue Apr 6 13:28:10 2010 for GRASS Programmer's Manual by  doxygen 1.6.3