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, 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  * Dijkstra Shortest Path 
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;                         /* pointer to the start node (pgraph->pNodeBuffer) */
00280         register dglInt32_t *           pDestination;           /* temporary destination pointer */
00281         register dglInt32_t *           pEdgeset;                       /* pointer to the edge (pgraph->pEdgeBuffer) */
00282         register dglInt32_t *           pEdge;                          /* pointer to the to-edges in edge  */
00283         register dglInt32_t *           pEdge_prev;                     /* pointer to the previous edge in path */
00284         int                                             nRet;
00285         dglEdgesetTraverser_s   laT;
00286 
00287         dglSPCache_s spCache;
00288 
00289         /*
00290          * shortest path distance temporary min heap
00291          */
00292         dglHeapData_u                           heapvalue;
00293         dglHeapNode_s                           heapnode;
00294 
00295         /*
00296          * shortest path visited network
00297          */
00298         dglTreeTouchI32_s *     pVisitedItem, findVisited;
00299 
00300         /*
00301          * shortest path predecessor and distance network
00302          */
00303         dglTreePredist_s *      pPredistItem, findPredist;
00304 
00305         /*
00306          * args to clip()
00307          */
00308         dglSPClipInput_s        clipInput;
00309         dglSPClipOutput_s       clipOutput;
00310 
00311 
00312         /*
00313          * Initialize the cache: initialize the heap and create temporary networks -
00314          * The use of a predist network for predecessor and distance has two important results:
00315          * 1) allows us not having to reset the whole graph status at each call;
00316          * 2) use of a stack memory area for temporary (and otherwise possibly thread-conflicting) states.
00317          * If a cache pointer was supplied, do not initialize it but try to get SP immediately.
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          * reset error status after using the cache
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          * now we inspect all edges departing from the start node
00375          * - at each loop 'pedge' points to the edge in the edge buffer
00376          * - we invoke the caller's clip() and eventually skip the edge (clip() != 0)
00377          * - we insert a item in the predist network to set actual predecessor and distance
00378          *   (there is no precedecessor at this stage) and actual distance from the starting node
00379          *   (at this stage it equals the edge's cost)
00380          * - we insert a item in the node min-heap (sorted on node distance), storing the offset of the
00381          *   edge in the edge buffer.
00382          * In the case of undirected graph (version 3) we inspect input edges as well.
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          * Now we begin extracting nodes from the min-heap. Each node extracted is
00418          * the one that is actually closest to the SP start.
00419          */
00420         while( dglHeapExtractMin( &pCache->NodeHeap , &heapnode) == 1 )
00421         {
00422                 dglInt32_t fromDist;
00423 
00424                 /*
00425                  * recover the stored edge pointer
00426                  */
00427                 pEdge                = heapnode.value.pv;
00428 
00429                 /*
00430                  * the new relative head is the tail of the edge
00431                  * or the head of the edge if the traversal was reversed (undirected edge)
00432                  */
00433                 if ( heapnode.flags == 0 ) {
00434                         pStart  = _DGL_EDGE_TAILNODE(pgraph, pEdge); /* continue from previous tail */
00435                 }
00436                 else {
00437                         pStart  = _DGL_EDGE_HEADNODE(pgraph, pEdge); /* reversed head/tail */
00438                 }
00439 
00440 
00441                 /*
00442                  * We do not want to explore twice the same node as a relative starting point,
00443                  * that's the meaning of 'visited'. We mark actual start node as 'visited' by
00444                  * inserting it into the visited-network. If we find actual node in the network
00445                  * we just give up and continue looping. Otherwise we add actual node to the network.
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                  * Dijkstra algorithm ends when the destination node is extracted from
00457                  * the min distance heap, that means: no other path exist in the network giving
00458                  * a shortest output.
00459                  * If this happens we jump to the epilogue in order to build a path report and return.
00460                  */
00461                 if ( DGL_NODE_ID(pStart) == nDestination )
00462                 {
00463                         goto destination_found;
00464                 }
00465 
00466                 /*
00467                  * Give up with visited nodes now
00468                  */
00469                 if ( pVisitedItem ) {
00470                         continue;
00471                 }
00472 
00473                 /*
00474                  * If the node is not marked as having departing edges, then we are into a
00475                  * blind alley. Just give up this direction and continue looping.
00476                  * This only applies to v1 and v2 (digraphs)
00477                  */
00478                 if ( !(DGL_NODE_STATUS(pStart) & DGL_NS_HEAD) && pgraph->Version < 3)  continue;
00479 
00480                 /*
00481                  * save actual edge for later clip()
00482                  */
00483                 pEdge_prev       = pEdge;
00484 
00485                 /*
00486                  * Recover the head node distance from the predist network
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                  * Loop on departing edges:
00498                  * Scan the edgeset and loads pedge at each iteration with next-edge.
00499                  * iWay == DGL_EDGESET_T_WAY_OUT then pedge is a out arc (departing from node) else ot is a in arc.
00500                  * V1 has no in-degree support so iWay is always OUT, V2/3 have in-degree support.
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; /* ==0 path not found */
00539 
00540 destination_found: /* path found - build a shortest path report or report the distance only */
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 

Generated on Sun Apr 6 17:32:44 2008 for GRASS by  doxygen 1.5.5