GRASS Programmer's Manual 6.4.1(2011)
|
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 }