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(
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
00068
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) ) {
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
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
00230
00231
00232
00233
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 ) {
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 {
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 }