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