00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
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
00067
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)) {
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
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
00235
00236
00237
00238
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) {
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 {
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 }