GRASS Programmer's Manual
6.4.2(2012)
|
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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA 00017 */ 00018 00019 /* 00020 * best view with tabstop=4 00021 */ 00022 00023 /* 00024 * Edge Traversing 00025 */ 00026 int DGL_EDGE_T_INITIALIZE_FUNC( dglGraph_s * pGraph , dglEdgeTraverser_s * pT , dglEdgePrioritizer_s * pEP ) { 00027 #if defined(_DGL_V1) 00028 pGraph->iErrno = DGL_ERR_NotSupported; 00029 return -pGraph->iErrno; 00030 #else 00031 if ( pGraph->Flags & DGL_GS_FLAT ) { 00032 if ( pEP && pEP->pvAVL ) { 00033 if ( (pT->pvAVLT = malloc( sizeof(struct avl_traverser) )) == NULL ) { 00034 pGraph->iErrno = DGL_ERR_MemoryExhausted; 00035 return -pGraph->iErrno; 00036 } 00037 avl_t_init( pT->pvAVLT , pEP->pvAVL ); 00038 pT->pnEdge = NULL; 00039 pT->pEdgePrioritizer = pEP; 00040 } 00041 else { 00042 pT->pvAVLT = NULL; 00043 pT->pnEdge = NULL; 00044 pT->pEdgePrioritizer = NULL; 00045 } 00046 } 00047 else { 00048 if ( (pT->pvAVLT = malloc( sizeof(struct avl_traverser) )) == NULL ) { 00049 pGraph->iErrno = DGL_ERR_MemoryExhausted; 00050 return -pGraph->iErrno; 00051 } 00052 if ( pEP && pEP->pvAVL ) { 00053 avl_t_init( pT->pvAVLT , pEP->pvAVL ); 00054 pT->pnEdge = NULL; 00055 pT->pEdgePrioritizer = pEP; 00056 } 00057 else { 00058 avl_t_init( pT->pvAVLT , pGraph->pEdgeTree ); 00059 pT->pnEdge = NULL; 00060 pT->pEdgePrioritizer = NULL; 00061 } 00062 } 00063 pT->pGraph = pGraph; 00064 return 0; 00065 #endif 00066 } 00067 00068 void DGL_EDGE_T_RELEASE_FUNC( dglEdgeTraverser_s * pT ) { 00069 #if defined(_DGL_V1) 00070 pT->pGraph->iErrno = DGL_ERR_NotSupported; 00071 #else 00072 if ( pT->pvAVLT ) free( pT->pvAVLT ); 00073 pT->pvAVLT = NULL; 00074 pT->pnEdge = NULL; 00075 pT->pEdgePrioritizer = NULL; 00076 #endif 00077 } 00078 00079 dglInt32_t * DGL_EDGE_T_FIRST_FUNC( dglEdgeTraverser_s * pT ) { 00080 #if defined(_DGL_V1) 00081 pT->pGraph->iErrno = DGL_ERR_NotSupported; 00082 return NULL; 00083 #else 00084 dglGraph_s * pG = pT->pGraph; 00085 00086 pT->pnEdge = NULL; 00087 if ( pT->pvAVLT && pT->pEdgePrioritizer ) { 00088 dglEdgePrioritizer_s * pPri = pT->pEdgePrioritizer; 00089 dglTreeEdgePri32_s * pItem; 00090 00091 pItem = avl_t_first( pT->pvAVLT, pPri->pvAVL ); 00092 if ( pItem ) { 00093 /* 00094 printf("edge_t_first: cEdge=%ld\n", pItem->cnData); 00095 */ 00096 pPri->cEdge = pItem->cnData; 00097 pPri->iEdge = 0; 00098 if ( pPri->iEdge < pPri->cEdge ) { 00099 pT->pnEdge = DGL_GET_EDGE_FUNC(pG, pItem->pnData[pPri->iEdge]); 00100 pPri->iEdge++; 00101 } 00102 } 00103 pPri->pEdgePri32Item = pItem; 00104 } 00105 else if ( pT->pvAVLT ) { 00106 dglTreeEdge_s * pEdgeItem; 00107 00108 if ( (pEdgeItem = avl_t_first( pT->pvAVLT, pG->pEdgeTree )) == NULL ) { 00109 pT->pnEdge = NULL; 00110 } 00111 else { 00112 pT->pnEdge = pEdgeItem->pv; 00113 } 00114 } 00115 else { 00116 if ( pG->cEdge > 0 ) pT->pnEdge = (dglInt32_t*)pG->pEdgeBuffer; 00117 else pT->pnEdge = NULL; 00118 } 00119 return pT->pnEdge; 00120 #endif 00121 } 00122 00123 dglInt32_t * DGL_EDGE_T_NEXT_FUNC( dglEdgeTraverser_s * pT ) 00124 { 00125 #if defined(_DGL_V1) 00126 pT->pGraph->iErrno = DGL_ERR_NotSupported; 00127 return NULL; 00128 #else 00129 dglGraph_s * pG = pT->pGraph; 00130 00131 pT->pnEdge = NULL; 00132 00133 if ( pT->pvAVLT && pT->pEdgePrioritizer ) { 00134 dglEdgePrioritizer_s * pPri = pT->pEdgePrioritizer; 00135 dglTreeEdgePri32_s * pItem = pPri->pEdgePri32Item; 00136 00137 if (pItem && pPri->iEdge < pPri->cEdge) { 00138 pT->pnEdge = DGL_GET_EDGE_FUNC(pG, pItem->pnData[pPri->iEdge]); 00139 pPri->iEdge++; 00140 } 00141 else { 00142 if ( (pItem = avl_t_next(pT->pvAVLT)) != NULL ) { 00143 pPri->cEdge = pItem->cnData; 00144 pPri->iEdge = 0; 00145 if ( pPri->iEdge < pPri->cEdge ) { 00146 pT->pnEdge = DGL_GET_EDGE_FUNC(pG, pItem->pnData[pPri->iEdge]); 00147 pPri->iEdge++; 00148 } 00149 } 00150 pPri->pEdgePri32Item = pItem; 00151 } 00152 } 00153 else if ( pT->pvAVLT ) { 00154 dglTreeEdge_s * pItem; 00155 00156 if ( (pItem = avl_t_next( pT->pvAVLT )) != NULL ) { 00157 pT->pnEdge = pItem->pv; 00158 } 00159 } 00160 else { 00161 pT->pnEdge += DGL_NODE_WSIZE( pG->EdgeAttrSize); 00162 if (pT->pnEdge >= (dglInt32_t*)(pG->pEdgeBuffer + pG->iEdgeBuffer) ) { 00163 pT->pnEdge = NULL; 00164 } 00165 } 00166 return pT->pnEdge; 00167 #endif 00168 } 00169 00170 00171 /* 00172 * Node Traversing 00173 */ 00174 int DGL_NODE_T_INITIALIZE_FUNC( dglGraph_s * pGraph , dglNodeTraverser_s * pT ) { 00175 if ( pGraph->Flags & DGL_GS_FLAT ) { 00176 pT->pnNode = NULL; 00177 pT->pvAVLT = NULL; 00178 } 00179 else { 00180 if ( (pT->pvAVLT = malloc( sizeof(struct avl_traverser) )) == NULL ) { 00181 pGraph->iErrno = DGL_ERR_MemoryExhausted; 00182 return -pGraph->iErrno; 00183 } 00184 avl_t_init( pT->pvAVLT , pGraph->pNodeTree ); 00185 pT->pnNode = NULL; 00186 } 00187 pT->pGraph = pGraph; 00188 return 0; 00189 } 00190 00191 void DGL_NODE_T_RELEASE_FUNC( dglNodeTraverser_s * pT ) { 00192 if ( pT->pvAVLT ) free( pT->pvAVLT ); 00193 pT->pvAVLT = NULL; 00194 pT->pnNode = NULL; 00195 } 00196 00197 dglInt32_t * DGL_NODE_T_FIRST_FUNC( dglNodeTraverser_s * pT ) 00198 { 00199 DGL_T_NODEITEM_TYPE * pNodeItem; 00200 00201 if ( pT->pvAVLT ) { 00202 if ( (pNodeItem = avl_t_first( pT->pvAVLT, pT->pGraph->pNodeTree )) == NULL ) 00203 pT->pnNode = NULL; 00204 else 00205 pT->pnNode = DGL_T_NODEITEM_NodePTR(pNodeItem); 00206 } 00207 else { 00208 if ( pT->pGraph->cNode > 0 ) pT->pnNode = (dglInt32_t*)pT->pGraph->pNodeBuffer; 00209 else pT->pnNode = NULL; 00210 } 00211 return pT->pnNode; 00212 } 00213 00214 dglInt32_t * DGL_NODE_T_NEXT_FUNC( dglNodeTraverser_s * pT ) 00215 { 00216 DGL_T_NODEITEM_TYPE * pNodeItem; 00217 00218 if ( pT->pvAVLT ) { 00219 if ( (pNodeItem = avl_t_next( pT->pvAVLT )) == NULL ) 00220 pT->pnNode = NULL; 00221 else 00222 pT->pnNode = DGL_T_NODEITEM_NodePTR(pNodeItem); 00223 } 00224 else { 00225 pT->pnNode += DGL_NODE_WSIZE( pT->pGraph->NodeAttrSize ); 00226 if ( pT->pnNode >= (dglInt32_t*)(pT->pGraph->pNodeBuffer + pT->pGraph->iNodeBuffer) ) pT->pnNode = NULL; 00227 } 00228 return pT->pnNode; 00229 } 00230 00231 dglInt32_t * DGL_NODE_T_FIND_FUNC( dglNodeTraverser_s * pT , dglInt32_t nNodeId ) 00232 { 00233 DGL_T_NODEITEM_TYPE * pNodeItem , findItem; 00234 00235 if ( pT->pvAVLT ) { 00236 findItem.nKey = nNodeId; 00237 if ( (pNodeItem = avl_t_find( pT->pvAVLT , pT->pGraph->pNodeTree , &findItem )) == NULL ) 00238 pT->pnNode = NULL; 00239 else 00240 pT->pnNode = DGL_T_NODEITEM_NodePTR(pNodeItem); 00241 } 00242 else { 00243 pT->pnNode = DGL_GET_NODE_FUNC(pT->pGraph, nNodeId); 00244 } 00245 return pT->pnNode; 00246 } 00247 00248 00249 /* 00250 * Edgeset Traversing 00251 */ 00252 int DGL_EDGESET_T_INITIALIZE_FUNC( 00253 dglGraph_s * pGraph , 00254 dglEdgesetTraverser_s * pT , 00255 dglInt32_t * pnEdgeset 00256 ) 00257 { 00258 pT->pGraph = pGraph; 00259 pT->pnEdgeset = pnEdgeset; 00260 pT->cEdge = (pnEdgeset)?*pnEdgeset:0; 00261 pT->iEdge = 0; 00262 return 0; 00263 } 00264 00265 00266 void DGL_EDGESET_T_RELEASE_FUNC( dglEdgesetTraverser_s * pT ) 00267 { 00268 } 00269 00270 dglInt32_t * DGL_EDGESET_T_FIRST_FUNC( dglEdgesetTraverser_s * pT ) 00271 { 00272 #if defined(_DGL_V2) 00273 dglInt32_t * pnOffset; 00274 dglTreeEdge_s * pEdgeItem, EdgeItem; 00275 #endif 00276 00277 if ( pT->cEdge == 0 ) return NULL; 00278 pT->iEdge = 1; 00279 #if defined(_DGL_V1) 00280 return pT->pnEdgeset + 1; 00281 #endif 00282 #if defined(_DGL_V2) 00283 pnOffset = pT->pnEdgeset + 1; 00284 if ( pT->pGraph->Flags & DGL_GS_FLAT ) { 00285 pT->pvCurrentItem = NULL; 00286 return DGL_EDGEBUFFER_SHIFT(pT->pGraph, *pnOffset); 00287 } 00288 else { 00289 EdgeItem.nKey = *pnOffset; 00290 if ( (pEdgeItem = avl_find( pT->pGraph->pEdgeTree, &EdgeItem )) != NULL) { 00291 pT->pvCurrentItem = pEdgeItem; 00292 return pEdgeItem->pv; 00293 } 00294 } 00295 #endif 00296 return NULL; 00297 } 00298 00299 00300 dglInt32_t * DGL_EDGESET_T_NEXT_FUNC( dglEdgesetTraverser_s * pT ) 00301 { 00302 #if defined(_DGL_V2) 00303 dglInt32_t * pnOffset; 00304 dglTreeEdge_s * pEdgeItem, EdgeItem; 00305 #endif 00306 00307 if ( pT->cEdge > 0 && pT->iEdge < pT->cEdge ) { 00308 #if defined(_DGL_V1) 00309 return DGL_EDGESET_EDGE_PTR(pT->pnEdgeset, pT->iEdge++, pT->pGraph->EdgeAttrSize); 00310 #endif 00311 #if defined(_DGL_V2) 00312 pnOffset = pT->pnEdgeset + 1 + pT->iEdge++; 00313 if ( pT->pGraph->Flags & DGL_GS_FLAT ) { 00314 return DGL_EDGEBUFFER_SHIFT(pT->pGraph, *pnOffset); 00315 } 00316 else { 00317 EdgeItem.nKey = *pnOffset; 00318 if ( (pEdgeItem = avl_find( pT->pGraph->pEdgeTree, &EdgeItem )) != NULL) { 00319 pT->pvCurrentItem = pEdgeItem; 00320 return pEdgeItem->pv; 00321 } 00322 } 00323 #endif 00324 } 00325 return NULL; 00326 } 00327 00328 00329 /* 00330 * Flatten the graph 00331 */ 00332 int DGL_FLATTEN_FUNC( dglGraph_s * pgraph ) 00333 { 00334 register DGL_T_NODEITEM_TYPE * ptreenode; 00335 #if defined(_DGL_V2) 00336 register dglTreeEdge_s * ptreeEdge; 00337 int i; 00338 #endif 00339 register dglInt32_t * pEdge; 00340 register dglInt32_t * pnode; 00341 register dglInt32_t * pnodescan; 00342 dglInt32_t * pOutEdgeset; 00343 dglInt32_t * pInEdgeset; 00344 int cOutEdgeset; 00345 int cInEdgeset; 00346 00347 struct avl_traverser avlTraverser; 00348 00349 if ( pgraph->Flags & DGL_GS_FLAT ) 00350 { 00351 pgraph->iErrno = DGL_ERR_BadOnFlatGraph; 00352 return -pgraph->iErrno; 00353 } 00354 00355 pgraph->pNodeBuffer = NULL; /* should be already */ 00356 pgraph->iNodeBuffer = 0; 00357 pgraph->pEdgeBuffer = NULL; 00358 pgraph->iEdgeBuffer = 0; 00359 00360 00361 #if defined(_DGL_V2) 00362 /* 00363 printf("flatten: traversing edges\n"); 00364 */ 00365 avl_t_init( & avlTraverser, pgraph->pEdgeTree ); 00366 00367 for ( 00368 ptreeEdge = avl_t_first( & avlTraverser , pgraph->pEdgeTree ) ; 00369 ptreeEdge ; 00370 ptreeEdge = avl_t_next( & avlTraverser ) 00371 ) 00372 { 00373 pEdge = ptreeEdge->pv; 00374 00375 /* 00376 printf( "flatten: add edge %ld to edge buffer\n", DGL_EDGE_ID(pEdge) ); 00377 */ 00378 00379 pgraph->pEdgeBuffer = realloc( 00380 pgraph->pEdgeBuffer , 00381 pgraph->iEdgeBuffer + DGL_EDGE_SIZEOF(pgraph->EdgeAttrSize) 00382 ); 00383 00384 if ( pgraph->pEdgeBuffer == NULL ) { 00385 pgraph->iErrno = DGL_ERR_MemoryExhausted; 00386 return -pgraph->iErrno; 00387 } 00388 00389 memcpy( pgraph->pEdgeBuffer + pgraph->iEdgeBuffer, pEdge, DGL_EDGE_SIZEOF(pgraph->EdgeAttrSize) ); 00390 00391 pgraph->iEdgeBuffer += DGL_EDGE_SIZEOF(pgraph->EdgeAttrSize); 00392 } 00393 #endif 00394 00395 /* 00396 printf("flatten: traversing nodes\n"); 00397 */ 00398 avl_t_init( & avlTraverser, pgraph->pNodeTree ); 00399 00400 for ( 00401 ptreenode = avl_t_first( & avlTraverser , pgraph->pNodeTree ) ; 00402 ptreenode ; 00403 ptreenode = avl_t_next( & avlTraverser ) 00404 ) 00405 { 00406 pnode = DGL_T_NODEITEM_NodePTR(ptreenode); 00407 pOutEdgeset = DGL_T_NODEITEM_OutEdgesetPTR(ptreenode); 00408 pInEdgeset = DGL_T_NODEITEM_InEdgesetPTR(ptreenode); 00409 00410 if ( !(DGL_NODE_STATUS(pnode) & DGL_NS_ALONE) ) 00411 { 00412 cOutEdgeset = (pOutEdgeset) ? 00413 DGL_EDGESET_SIZEOF(DGL_EDGESET_EDGECOUNT(pOutEdgeset), pgraph->EdgeAttrSize) : 00414 sizeof(dglInt32_t); 00415 00416 #if !defined(_DGL_V1) 00417 cInEdgeset = (pInEdgeset) ? 00418 DGL_EDGESET_SIZEOF(DGL_EDGESET_EDGECOUNT(pInEdgeset), pgraph->EdgeAttrSize) : 00419 sizeof(dglInt32_t); 00420 #else 00421 cInEdgeset = 0; 00422 #endif 00423 00424 pgraph->pEdgeBuffer = realloc( pgraph->pEdgeBuffer , 00425 pgraph->iEdgeBuffer + cOutEdgeset + cInEdgeset ); 00426 00427 if ( pgraph->pEdgeBuffer == NULL ) 00428 { 00429 pgraph->iErrno = DGL_ERR_MemoryExhausted; 00430 return -pgraph->iErrno; 00431 } 00432 00433 { 00434 dglInt32_t nDummy = 0; 00435 00436 memcpy( pgraph->pEdgeBuffer + pgraph->iEdgeBuffer , (pOutEdgeset)?pOutEdgeset:&nDummy , cOutEdgeset ); 00437 #if !defined(_DGL_V1) 00438 memcpy( pgraph->pEdgeBuffer + pgraph->iEdgeBuffer + cOutEdgeset , (pInEdgeset)?pInEdgeset:&nDummy, cInEdgeset ); 00439 #endif 00440 } 00441 00442 DGL_NODE_EDGESET_OFFSET(pnode) = pgraph->iEdgeBuffer; 00443 00444 pgraph->iEdgeBuffer += cOutEdgeset + cInEdgeset; 00445 } 00446 00447 pgraph->pNodeBuffer = realloc(pgraph->pNodeBuffer, pgraph->iNodeBuffer + DGL_NODE_SIZEOF(pgraph->NodeAttrSize)); 00448 00449 if ( pgraph->pNodeBuffer == NULL ) 00450 { 00451 pgraph->iErrno = DGL_ERR_MemoryExhausted; 00452 return -pgraph->iErrno; 00453 } 00454 00455 memcpy( pgraph->pNodeBuffer + pgraph->iNodeBuffer , pnode , DGL_NODE_SIZEOF(pgraph->NodeAttrSize) ); 00456 pgraph->iNodeBuffer += DGL_NODE_SIZEOF(pgraph->NodeAttrSize); 00457 } 00458 00459 #if defined(_DGL_V2) 00460 if ( pgraph->pEdgeTree ) { 00461 avl_destroy( pgraph->pEdgeTree, dglTreeEdgeCancel ); 00462 pgraph->pEdgeTree = NULL; 00463 } 00464 #endif 00465 00466 if ( pgraph->pNodeTree ) { 00467 avl_destroy( pgraph->pNodeTree, dglTreeNodeCancel ); 00468 pgraph->pNodeTree = NULL; 00469 } 00470 00471 pgraph->Flags |= DGL_GS_FLAT; /* flattened */ 00472 00473 /* 00474 * convert node-id to node-offset 00475 */ 00476 DGL_FOREACH_NODE(pgraph, pnodescan) 00477 { 00478 if ( !(DGL_NODE_STATUS(pnodescan) & DGL_NS_ALONE) ) 00479 { 00480 pOutEdgeset = DGL_EDGEBUFFER_SHIFT(pgraph, DGL_NODE_EDGESET_OFFSET(pnodescan)); 00481 00482 #if defined(_DGL_V2) 00483 for( i = 0 ; i < pOutEdgeset[0] ; i ++ ) { 00484 /* 00485 printf("flatten: node %ld: scan out edge %ld/%ld - %ld\n", DGL_NODE_ID(pnodescan), i+1, pOutEdgeset[0], pOutEdgeset[i+1]); 00486 */ 00487 pEdge = DGL_GET_EDGE_FUNC(pgraph, pOutEdgeset[i+1]); 00488 if (pEdge == NULL) { 00489 pgraph->iErrno = DGL_ERR_UnexpectedNullPointer; 00490 return -pgraph->iErrno; 00491 } 00492 /* 00493 printf(" retrieved id %ld\n", DGL_EDGE_ID(pEdge) ); 00494 */ 00495 pOutEdgeset[i+1] = DGL_EDGEBUFFER_OFFSET(pgraph,pEdge); 00496 } 00497 00498 pInEdgeset = pOutEdgeset + pOutEdgeset[0] + 1; 00499 00500 for( i = 0 ; i < pInEdgeset[0] ; i ++ ) { 00501 /* 00502 printf("flatten: node %ld: scan in edge %ld/%ld - %ld\n", 00503 DGL_NODE_ID(pnodescan), i+1, pInEdgeset[0], pInEdgeset[i+1]); 00504 */ 00505 pEdge = DGL_GET_EDGE_FUNC(pgraph, pInEdgeset[i+1]); 00506 if (pEdge == NULL) { 00507 pgraph->iErrno = DGL_ERR_UnexpectedNullPointer; 00508 return -pgraph->iErrno; 00509 } 00510 /* 00511 printf(" retrieved id %ld\n", DGL_EDGE_ID(pEdge) ); 00512 */ 00513 pInEdgeset[i+1] = DGL_EDGEBUFFER_OFFSET(pgraph,pEdge); 00514 } 00515 #endif 00516 00517 #if defined(_DGL_V2) 00518 { 00519 int iEdge; 00520 DGL_FOREACH_EDGE(pgraph, pOutEdgeset, pEdge, iEdge) 00521 #else 00522 DGL_FOREACH_EDGE(pgraph, pOutEdgeset, pEdge) 00523 #endif 00524 { 00525 if ( (pnode = DGL_GET_NODE_FUNC( pgraph, DGL_EDGE_HEADNODE_OFFSET(pEdge))) == NULL ) 00526 { 00527 pgraph->iErrno = DGL_ERR_HeadNodeNotFound; 00528 return -pgraph->iErrno; 00529 } 00530 DGL_EDGE_HEADNODE_OFFSET(pEdge) = DGL_NODEBUFFER_OFFSET(pgraph, pnode); 00531 00532 if ( (pnode = DGL_GET_NODE_FUNC( pgraph , DGL_EDGE_TAILNODE_OFFSET(pEdge))) == NULL ) 00533 { 00534 pgraph->iErrno = DGL_ERR_TailNodeNotFound; 00535 return -pgraph->iErrno; 00536 } 00537 DGL_EDGE_TAILNODE_OFFSET(pEdge) = DGL_NODEBUFFER_OFFSET(pgraph, pnode); 00538 } 00539 #if defined(_DGL_V2) 00540 } 00541 #endif 00542 } 00543 } 00544 00545 return 0; 00546 } 00547 00548 00549 int DGL_UNFLATTEN_FUNC( dglGraph_s * pgraph ) 00550 { 00551 register dglInt32_t * pHead; 00552 register dglInt32_t * pTail; 00553 register dglInt32_t * pEdge; 00554 register dglInt32_t * pEdgeset; 00555 int nret; 00556 00557 if ( ! (pgraph->Flags & DGL_GS_FLAT) ) 00558 { 00559 pgraph->iErrno = DGL_ERR_BadOnTreeGraph; 00560 return -pgraph->iErrno; 00561 } 00562 00563 /* 00564 * unflag it now to avoid DGL_ADD_EDGE_FUNC() failure 00565 */ 00566 pgraph->Flags &= ~DGL_GS_FLAT; 00567 pgraph->cNode = 0; 00568 pgraph->cEdge = 0; 00569 pgraph->cHead = 0; 00570 pgraph->cTail = 0; 00571 pgraph->cAlone = 0; 00572 pgraph->nnCost = (dglInt64_t)0; 00573 00574 if ( pgraph->pNodeTree == NULL ) pgraph->pNodeTree = avl_create( DGL_T_NODEITEM_Compare, NULL, dglTreeGetAllocator() ); 00575 if ( pgraph->pNodeTree == NULL ) { 00576 pgraph->iErrno = DGL_ERR_MemoryExhausted; 00577 return -pgraph->iErrno; 00578 } 00579 #if defined(_DGL_V1) 00580 pgraph->pEdgeTree = NULL; 00581 #else 00582 if ( pgraph->pEdgeTree == NULL ) pgraph->pEdgeTree = avl_create( dglTreeEdgeCompare, NULL, dglTreeGetAllocator() ); 00583 if ( pgraph->pEdgeTree == NULL ) { 00584 pgraph->iErrno = DGL_ERR_MemoryExhausted; 00585 return -pgraph->iErrno; 00586 } 00587 #endif 00588 00589 DGL_FOREACH_NODE(pgraph,pHead) 00590 { 00591 if ( DGL_NODE_STATUS(pHead) & DGL_NS_HEAD ) 00592 { 00593 pEdgeset = DGL_EDGEBUFFER_SHIFT(pgraph, DGL_NODE_EDGESET_OFFSET(pHead)); 00594 00595 #if defined(_DGL_V2) 00596 { 00597 int iEdge; 00598 DGL_FOREACH_EDGE(pgraph, pEdgeset, pEdge, iEdge) 00599 #else 00600 DGL_FOREACH_EDGE(pgraph, pEdgeset, pEdge) 00601 #endif 00602 { 00603 pTail = DGL_NODEBUFFER_SHIFT(pgraph, DGL_EDGE_TAILNODE_OFFSET(pEdge)); 00604 00605 nret = DGL_ADD_EDGE_FUNC( pgraph, 00606 DGL_NODE_ID(pHead), 00607 DGL_NODE_ID(pTail), 00608 DGL_EDGE_COST(pEdge), 00609 DGL_EDGE_ID(pEdge), 00610 DGL_NODE_ATTR_PTR(pHead), 00611 DGL_NODE_ATTR_PTR(pTail), 00612 DGL_EDGE_ATTR_PTR(pEdge), 00613 0 ); 00614 00615 if ( nret < 0 ) { 00616 goto error; 00617 } 00618 } 00619 #if defined(_DGL_V2) 00620 } 00621 #endif 00622 } 00623 else if ( DGL_NODE_STATUS(pHead) & DGL_NS_ALONE ) { 00624 nret = DGL_ADD_NODE_FUNC( pgraph, 00625 DGL_NODE_ID(pHead), 00626 DGL_NODE_ATTR_PTR(pHead), 00627 0 ); 00628 if ( nret < 0 ) { 00629 goto error; 00630 } 00631 } 00632 } 00633 00634 /* move away flat-state data 00635 */ 00636 if ( pgraph->pNodeBuffer ) free( pgraph->pNodeBuffer ); 00637 if ( pgraph->pEdgeBuffer ) free( pgraph->pEdgeBuffer ); 00638 pgraph->pNodeBuffer = NULL; 00639 pgraph->pEdgeBuffer = NULL; 00640 return 0; 00641 00642 error: 00643 if ( pgraph->pNodeTree ) avl_destroy( pgraph->pNodeTree, dglTreeNodeCancel ); 00644 if ( pgraph->pEdgeTree ) avl_destroy( pgraph->pEdgeTree, dglTreeEdgeCancel ); 00645 pgraph->pNodeTree = NULL; 00646 pgraph->pEdgeTree = NULL; 00647 pgraph->Flags |= DGL_GS_FLAT; 00648 return nret; 00649 } 00650