span-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  * Build the depth-first spanning tree of 'pgraphIn' into 'pgraphOut'
00025  * - pgraphOut must have been previously initialized by the caller and is returned in TREE state
00026  * - I prefer using a iterative approach with a stack for 'waiting edges' instead of recursion: it's
00027  *   cheaper to stack 8 bytes for each edge than the whole function stack
00028  * - The visited network is passed by the caller because this function can be used for two purposes:
00029  *   1. generate a single spanning tree (dglDepthSpanning)
00030  *   2. part of a loop for generating connected-components of the graph (dglDepthComponents)
00031  */
00032 int DGL_SPAN_DEPTHFIRST_SPANNING_FUNC(
00033                                                 dglGraph_s * pgraphIn ,
00034                                                 dglGraph_s * pgraphOut ,
00035                                                 dglInt32_t nVertex ,
00036                                                 void * pvVisited ,
00037                                                 dglSpanClip_fn  fnClip ,
00038                                                 void *                          pvClipArg
00039                                                 )
00040 {
00041         struct _stackItem {
00042                 dglInt32_t * pnHead;
00043                 dglInt32_t * pnEdge;
00044                 int iWay;
00045         };
00046 
00047         struct _stackItem stackItem;
00048         struct _stackItem * pStackItem;
00049 
00050         dglInt32_t *    pHead;
00051         dglInt32_t *    pTail;
00052         dglInt32_t *    pEdgeset;
00053         dglInt32_t *    pEdge;
00054         long                    istack = 0;
00055         unsigned char * pstack = NULL;
00056         int                             nret;
00057         dglSpanClipInput_s      clipInput;
00058         dglTreeNode_s findVisited;
00059         dglEdgesetTraverser_s laT;
00060 
00061 
00062         if ( (pHead = dglGetNode( pgraphIn, nVertex )) == NULL ) {
00063                 pgraphIn->iErrno = DGL_ERR_HeadNodeNotFound; goto dfs_error;
00064         }
00065 
00066         /*
00067          * the simplest case is when vertex node is alone or has no outgoing edges, the result
00068          * of the spanning is a graph having only one node
00069          */
00070         if ( DGL_NODE_STATUS(pHead) & DGL_NS_ALONE ||
00071                  (!(DGL_NODE_STATUS(pHead) & DGL_NS_HEAD) && DGL_NODE_STATUS(pHead) & DGL_NS_TAIL) ) {
00072                 nret = DGL_ADD_NODE_FUNC(
00073                                         pgraphOut,
00074                                         DGL_NODE_ID(pHead),
00075                                         DGL_NODE_ATTR_PTR(pHead),
00076                                         0
00077                                 );
00078                 if ( nret < 0 ) {
00079                         goto dfs_error;
00080                 }
00081                 return 0;
00082         }
00083 
00084         if ( (DGL_NODE_STATUS(pHead) & DGL_NS_HEAD) || pgraphIn->Version == 3) {
00085 
00086                 pEdgeset = _DGL_OUTEDGESET(pgraphIn, pHead);
00087 
00088                 if ( DGL_EDGESET_T_INITIALIZE_FUNC(pgraphIn,&laT,pEdgeset) < 0 ) {
00089                         goto dfs_error;
00090                 }
00091                 for (
00092                         pEdge = DGL_EDGESET_T_FIRST_FUNC(&laT) ;
00093                         pEdge ;
00094                         pEdge = DGL_EDGESET_T_NEXT_FUNC(&laT)
00095                         )
00096                 {
00097                         stackItem.pnHead = pHead;
00098                         stackItem.pnEdge = pEdge;
00099                         stackItem.iWay = 0;
00100                         if ( (pstack = dgl_mempush( pstack , & istack , sizeof(stackItem) , &stackItem )) == NULL ) {
00101                                 pgraphIn->iErrno = DGL_ERR_MemoryExhausted; goto dfs_error;
00102                         }
00103                 }
00104                 DGL_EDGESET_T_RELEASE_FUNC(&laT);
00105 
00106                 if ( pgraphIn->Version == 3 ) {
00107                         pEdgeset = _DGL_INEDGESET(pgraphIn, pHead);
00108 
00109                         if ( DGL_EDGESET_T_INITIALIZE_FUNC(pgraphIn,&laT,pEdgeset) < 0 ) {
00110                                 goto dfs_error;
00111                         }
00112                         for (
00113                                 pEdge = DGL_EDGESET_T_FIRST_FUNC(&laT) ;
00114                                 pEdge ;
00115                                 pEdge = DGL_EDGESET_T_NEXT_FUNC(&laT)
00116                                 )
00117                         {
00118                                 if (DGL_EDGE_STATUS(pEdge) & DGL_ES_DIRECTED) continue;
00119                                 stackItem.pnHead = pHead;
00120                                 stackItem.pnEdge = pEdge;
00121                                 stackItem.iWay = 1;
00122                                 if ( (pstack = dgl_mempush( pstack , & istack , sizeof(stackItem) , &stackItem )) == NULL ) {
00123                                         pgraphIn->iErrno = DGL_ERR_MemoryExhausted; goto dfs_error;
00124                                 }
00125                         }
00126                         DGL_EDGESET_T_RELEASE_FUNC(&laT);
00127                 }
00128 
00129                 if ( dglTreeNodeAdd(pvVisited , DGL_NODE_ID(pHead)) == NULL ) {
00130                         pgraphIn->iErrno = DGL_ERR_MemoryExhausted; goto dfs_error;
00131                 }
00132         }
00133 
00134         while( (pStackItem = (struct _stackItem *)dgl_mempop( pstack , & istack , sizeof(stackItem) )) != NULL )
00135         {
00136                 pHead  = pStackItem->pnHead;
00137                 pEdge  = pStackItem->pnEdge;
00138 
00139                 if ( pStackItem->iWay == 0 )
00140                         pTail = _DGL_EDGE_TAILNODE(pgraphIn, pEdge);
00141                 else
00142                         pTail = _DGL_EDGE_HEADNODE(pgraphIn, pEdge);
00143 
00144                 findVisited.nKey = DGL_NODE_ID(pTail);
00145                 if ( avl_find( pvVisited , &findVisited) ) { /* already visited */
00146                         continue;
00147                 }
00148 
00149                 if ( fnClip ) {
00150                         clipInput.pnNodeFrom = pHead;
00151                         clipInput.pnEdge     = pEdge;
00152                         clipInput.pnNodeTo   = pTail;
00153                         if ( fnClip( pgraphIn, pgraphOut, & clipInput, NULL, pvClipArg ) ) continue;
00154                 }
00155 
00156                 if ( dglTreeNodeAdd(pvVisited , DGL_NODE_ID(pTail)) == NULL ) {
00157                         pgraphIn->iErrno = DGL_ERR_MemoryExhausted; goto dfs_error;
00158                 }
00159 
00160                 /* add this edge */
00161                 nret = DGL_ADD_EDGE_FUNC( pgraphOut,
00162                                         DGL_NODE_ID(pHead),
00163                                         DGL_NODE_ID(pTail),
00164                                         DGL_EDGE_COST(pEdge),
00165                                         DGL_EDGE_ID(pEdge),
00166                                         DGL_NODE_ATTR_PTR(pHead),
00167                                         DGL_NODE_ATTR_PTR(pTail),
00168                                         DGL_EDGE_ATTR_PTR(pEdge),
00169                                         0 );
00170 
00171                 if ( nret < 0 ) {
00172                         goto dfs_error;
00173                 }
00174 
00175                 if ( (DGL_NODE_STATUS(pHead) & DGL_NS_HEAD) || pgraphIn->Version == 3 ) {
00176 
00177                         pEdgeset = _DGL_OUTEDGESET(pgraphIn, pTail);
00178                         if ( DGL_EDGESET_T_INITIALIZE_FUNC(pgraphIn,&laT,pEdgeset) < 0 ) {
00179                                 goto dfs_error;
00180                         }
00181                         for (
00182                                 pEdge = DGL_EDGESET_T_FIRST_FUNC(&laT) ;
00183                                 pEdge ;
00184                                 pEdge = DGL_EDGESET_T_NEXT_FUNC(&laT)
00185                                 )
00186                         {
00187                                 stackItem.pnHead = pTail;
00188                                 stackItem.pnEdge = pEdge;
00189                                 stackItem.iWay = 0;
00190                                 if ( (pstack = dgl_mempush( pstack , & istack , sizeof(stackItem) , &stackItem )) == NULL ) {
00191                                         pgraphIn->iErrno = DGL_ERR_MemoryExhausted; goto dfs_error;
00192                                 }
00193                         }
00194                         DGL_EDGESET_T_RELEASE_FUNC(&laT);
00195 
00196                         if ( pgraphIn->Version == 3 ) {
00197                                 pEdgeset = _DGL_INEDGESET(pgraphIn, pTail);
00198                                 if ( DGL_EDGESET_T_INITIALIZE_FUNC(pgraphIn,&laT,pEdgeset) < 0 ) {
00199                                         goto dfs_error;
00200                                 }
00201                                 for (
00202                                         pEdge = DGL_EDGESET_T_FIRST_FUNC(&laT) ;
00203                                         pEdge ;
00204                                         pEdge = DGL_EDGESET_T_NEXT_FUNC(&laT)
00205                                         )
00206                                 {
00207                                         if (DGL_EDGE_STATUS(pEdge) & DGL_ES_DIRECTED) continue;
00208                                         stackItem.pnHead = pTail;
00209                                         stackItem.pnEdge = pEdge;
00210                                         stackItem.iWay = 1;
00211                                         if ( (pstack = dgl_mempush( pstack , & istack , sizeof(stackItem) , &stackItem )) == NULL ) {
00212                                                 pgraphIn->iErrno = DGL_ERR_MemoryExhausted; goto dfs_error;
00213                                         }
00214                                 }
00215                                 DGL_EDGESET_T_RELEASE_FUNC(&laT);
00216                         }
00217                 }
00218         }
00219 
00220         if ( pstack ) free( pstack );
00221         return 0;
00222 
00223 dfs_error:
00224         if ( pstack ) free( pstack );
00225         return -pgraphIn->iErrno;
00226 }
00227 
00228 /*
00229  * Use a edge prioritized, tree growing scheme (aka Prim algorithm) in order to
00230  * be appliable to both undirected graphs (minimum spanning tree - MST) and
00231  * digraphs (minimum arborescense tree - MAT)
00232  * The vertex argument is ignored in MST (when algorithm is applied to a
00233  * version 3 undirected graph).
00234  */
00235 int DGL_SPAN_MINIMUM_SPANNING_FUNC(
00236                                                 dglGraph_s *    pgraphIn ,
00237                                                 dglGraph_s *    pgraphOut ,
00238                                                 dglInt32_t              nVertex ,
00239                                                 dglSpanClip_fn  fnClip ,
00240                                                 void *                          pvClipArg
00241                                                 )
00242 {
00243         dglInt32_t * pHead, * pTail , * pEdgeset , * pEdge;
00244         dglHeap_s FrontEdgeHeap;
00245         dglHeapData_u HeapData;
00246         dglHeapNode_s HeapItem;
00247         dglTreeNode_s * pPredistItem, findItem;
00248         dglEdgesetTraverser_s laT;
00249         int nret;
00250 
00251         dglHeapInit( & FrontEdgeHeap );
00252 
00253         if ( pgraphIn->Version == 3 ) { /* undirected: pick up the first node */
00254                 dglNodeTraverser_s pT;
00255                 DGL_NODE_T_INITIALIZE_FUNC( pgraphIn, &pT );
00256                 pHead = DGL_NODE_T_FIRST_FUNC( &pT );
00257                 DGL_NODE_T_RELEASE_FUNC( &pT );
00258         }
00259         else { /* directed: pick up the arborescense origin */
00260                 pHead = DGL_GET_NODE_FUNC( pgraphIn, nVertex );
00261         }
00262 
00263         if ( pHead == NULL ) {
00264                 pgraphIn->iErrno = DGL_ERR_HeadNodeNotFound;
00265                 goto mst_error;
00266         }
00267 
00268         if ( DGL_NODE_STATUS(pHead) & DGL_NS_HEAD || DGL_NODE_STATUS(pHead) & DGL_NS_ALONE ) {
00269 
00270                 if      (
00271                         (DGL_NODE_STATUS(pHead) & DGL_NS_HEAD) ||
00272                         (DGL_NODE_STATUS(pHead) & DGL_NS_ALONE) ||
00273                         pgraphIn->Version == 3
00274                         )
00275                 {
00276                         if ( DGL_ADD_NODE_FUNC(pgraphOut, DGL_NODE_ID(pHead), DGL_NODE_ATTR_PTR(pHead), 0) < 0 ) {
00277                                 goto mst_error;
00278                         }
00279 
00280                         if ( DGL_NODE_STATUS(pHead) & DGL_NS_ALONE ) {
00281                                 dglHeapFree( &FrontEdgeHeap , NULL );
00282                                 return 0;
00283                         }
00284 
00285                         pEdgeset = _DGL_OUTEDGESET(pgraphIn, pHead);
00286                         if ( DGL_EDGESET_T_INITIALIZE_FUNC(pgraphIn,&laT,pEdgeset) < 0 ) {
00287                                 goto mst_error;
00288                         }
00289                         for (
00290                                 pEdge = DGL_EDGESET_T_FIRST_FUNC(&laT) ;
00291                                 pEdge ;
00292                                 pEdge = DGL_EDGESET_T_NEXT_FUNC(&laT)
00293                                 )
00294                         {
00295                                 HeapData.pv = pEdge;
00296                                 if ( dglHeapInsertMin( &FrontEdgeHeap, DGL_EDGE_COST(pEdge), 0, HeapData ) < 0 ) {
00297                                         pgraphIn->iErrno = DGL_ERR_HeapError;
00298                                         goto mst_error;
00299                                 }
00300                         }
00301                         DGL_EDGESET_T_RELEASE_FUNC(&laT);
00302                         if ( pgraphIn->Version == 3 ) {
00303                                 pEdgeset = _DGL_INEDGESET(pgraphIn, pHead);
00304                                 if ( DGL_EDGESET_T_INITIALIZE_FUNC(pgraphIn,&laT,pEdgeset) < 0 ) {
00305                                         goto mst_error;
00306                                 }
00307                                 for (
00308                                         pEdge = DGL_EDGESET_T_FIRST_FUNC(&laT) ;
00309                                         pEdge ;
00310                                         pEdge = DGL_EDGESET_T_NEXT_FUNC(&laT)
00311                                         )
00312                                 {
00313                                         if (DGL_EDGE_STATUS(pEdge) & DGL_ES_DIRECTED) continue;
00314                                         HeapData.pv = pEdge;
00315                                         if ( dglHeapInsertMin( &FrontEdgeHeap, DGL_EDGE_COST(pEdge), 1, HeapData ) < 0 ) {
00316                                                 pgraphIn->iErrno = DGL_ERR_HeapError;
00317                                                 goto mst_error;
00318                                         }
00319                                 }
00320                                 DGL_EDGESET_T_RELEASE_FUNC(&laT);
00321                         }
00322                 }
00323         }
00324         else {
00325                 pgraphIn->iErrno = DGL_ERR_BadEdge;
00326                 goto mst_error;
00327         }
00328 
00329         while ( dglHeapExtractMin( &FrontEdgeHeap , &HeapItem ) == 1 ) {
00330                 pEdge = HeapItem.value.pv;
00331 
00332                 if ( HeapItem.flags == 0 ) {
00333                         if ( (pHead = _DGL_EDGE_HEADNODE( pgraphIn, pEdge )) == NULL ) {
00334                                 pgraphIn->iErrno = DGL_ERR_UnexpectedNullPointer;
00335                                 goto mst_error;
00336                         }
00337                         if ( (pTail   = _DGL_EDGE_TAILNODE( pgraphIn, pEdge )) == NULL ) {
00338                                 pgraphIn->iErrno = DGL_ERR_UnexpectedNullPointer;
00339                                 goto mst_error;
00340                         }
00341                 }
00342                 else if (pgraphIn->Version == 3) {
00343                         if ( (pTail = _DGL_EDGE_HEADNODE( pgraphIn, pEdge )) == NULL ) {
00344                                 pgraphIn->iErrno = DGL_ERR_UnexpectedNullPointer;
00345                                 goto mst_error;
00346                         }
00347                         if ( (pHead   = _DGL_EDGE_TAILNODE( pgraphIn, pEdge )) == NULL ) {
00348                                 pgraphIn->iErrno = DGL_ERR_UnexpectedNullPointer;
00349                                 goto mst_error;
00350                         }
00351                 }
00352                 else continue;
00353 
00354                 findItem.nKey = DGL_NODE_ID( pTail );
00355 
00356                 if ( (pPredistItem = avl_find(pgraphOut->pNodeTree, &findItem)) != NULL ) {
00357                         continue;
00358                 }
00359 
00360                 nret = DGL_ADD_EDGE_FUNC (pgraphOut,
00361                                 DGL_NODE_ID(pHead),
00362                                 DGL_NODE_ID(pTail),
00363                                 DGL_EDGE_COST(pEdge),
00364                                 DGL_EDGE_ID(pEdge),
00365                                 DGL_NODE_ATTR_PTR(pHead),
00366                                 DGL_NODE_ATTR_PTR(pTail),
00367                                 DGL_EDGE_ATTR_PTR(pEdge),
00368                                 0 );
00369 
00370                 if ( nret < 0 ) {
00371                         goto mst_error;
00372                 }
00373 
00374                 pHead = pTail;
00375 
00376                 if ( (DGL_NODE_STATUS(pHead) & DGL_NS_HEAD) || pgraphIn->Version == 3 ) {
00377                         pEdgeset = _DGL_OUTEDGESET(pgraphIn, pHead);
00378                         if ( DGL_EDGESET_T_INITIALIZE_FUNC(pgraphIn,&laT,pEdgeset) < 0 ) {
00379                                 goto mst_error;
00380                         }
00381                         for (
00382                                 pEdge = DGL_EDGESET_T_FIRST_FUNC(&laT) ;
00383                                 pEdge ;
00384                                 pEdge = DGL_EDGESET_T_NEXT_FUNC(&laT)
00385                                 )
00386                         {
00387                                 HeapData.pv = pEdge;
00388                                 if ( dglHeapInsertMin( &FrontEdgeHeap, DGL_EDGE_COST(pEdge), 0, HeapData ) < 0 ) {
00389                                         pgraphIn->iErrno = DGL_ERR_HeapError;
00390                                         goto mst_error;
00391                                 }
00392                         }
00393                         if ( pgraphIn->Version == 3 ) {
00394                                 DGL_EDGESET_T_RELEASE_FUNC(&laT);
00395                                 pEdgeset = _DGL_OUTEDGESET(pgraphIn, pHead);
00396                                 if ( DGL_EDGESET_T_INITIALIZE_FUNC(pgraphIn,&laT,pEdgeset) < 0 ) {
00397                                         goto mst_error;
00398                                 }
00399                                 for (
00400                                         pEdge = DGL_EDGESET_T_FIRST_FUNC(&laT) ;
00401                                         pEdge ;
00402                                         pEdge = DGL_EDGESET_T_NEXT_FUNC(&laT)
00403                                         )
00404                                 {
00405                                         if (DGL_EDGE_STATUS(pEdge) & DGL_ES_DIRECTED) continue;
00406                                         HeapData.pv = pEdge;
00407                                         if ( dglHeapInsertMin( &FrontEdgeHeap, DGL_EDGE_COST(pEdge), 1, HeapData ) < 0 ) {
00408                                                 pgraphIn->iErrno = DGL_ERR_HeapError;
00409                                                 goto mst_error;
00410                                         }
00411                                 }
00412                                 DGL_EDGESET_T_RELEASE_FUNC(&laT);
00413                         }
00414                 }
00415         }
00416         dglHeapFree( &FrontEdgeHeap , NULL );
00417         return 0;
00418 
00419 mst_error:
00420         dglHeapFree( &FrontEdgeHeap , NULL );
00421         return -pgraphIn->iErrno;
00422 }

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