00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023 int DGL_ADD_NODE_FUNC(
00024 dglGraph_s * pgraph,
00025 dglInt32_t nId,
00026 void * pvNodeAttr,
00027 dglInt32_t nFlags
00028 )
00029 {
00030 DGL_T_NODEITEM_TYPE * pNodeItem;
00031 dglInt32_t * pnode;
00032
00033 if ( pgraph->Flags & DGL_GS_FLAT )
00034 {
00035 pgraph->iErrno = DGL_ERR_BadOnFlatGraph;
00036 return -pgraph->iErrno;
00037 }
00038
00039 if ( (pNodeItem = DGL_T_NODEITEM_Add( pgraph->pNodeTree , nId )) == NULL )
00040 {
00041 pgraph->iErrno = DGL_ERR_MemoryExhausted;
00042 return -pgraph->iErrno;
00043 }
00044
00045 if ( DGL_T_NODEITEM_NodePTR(pNodeItem) == NULL )
00046 {
00047 if ( (pnode = DGL_NODE_ALLOC( pgraph->NodeAttrSize )) == NULL ) {
00048 pgraph->iErrno = DGL_ERR_MemoryExhausted;
00049 return -pgraph->iErrno;
00050 }
00051 memset( pnode, 0, DGL_NODE_SIZEOF(pgraph->NodeAttrSize) );
00052 DGL_NODE_ID(pnode) = nId;
00053 DGL_NODE_STATUS(pnode) = DGL_NS_ALONE;
00054 DGL_T_NODEITEM_Set_NodePTR(pNodeItem,pnode);
00055 pgraph->cNode ++;
00056 pgraph->cAlone ++;
00057 }
00058 else
00059 {
00060
00061 pgraph->iErrno = DGL_ERR_NodeAlreadyExist;
00062 return -pgraph->iErrno;
00063 }
00064 return 0;
00065 }
00066
00067 #if !defined(_DGL_V1)
00068
00069
00070
00071 int DGL_DEL_NODE_OUTEDGE_FUNC(dglGraph_s * pgraph, dglInt32_t nNode, dglInt32_t nEdge)
00072 {
00073 DGL_T_NODEITEM_TYPE * pNodeItem , findNodeItem;
00074 dglInt32_t * pnEdgeset, * pnEdge, * pnNode;
00075 dglEdgesetTraverser_s t;
00076
00077 findNodeItem.nKey = nNode;
00078
00079 if ( (pNodeItem = avl_find( pgraph->pNodeTree, &findNodeItem )) != NULL) {
00080 pnNode = DGL_T_NODEITEM_NodePTR(pNodeItem);
00081 if ( DGL_NODE_STATUS(pnNode) == DGL_NS_ALONE ) {
00082 return 0;
00083 }
00084 if ( (pnEdgeset = DGL_T_NODEITEM_OutEdgesetPTR(pNodeItem)) != NULL ) {
00085 if ( DGL_EDGESET_T_INITIALIZE_FUNC(pgraph,&t,pnEdgeset) >= 0 ) {
00086 for (
00087 pnEdge = DGL_EDGESET_T_FIRST_FUNC(&t) ;
00088 pnEdge ;
00089 pnEdge = DGL_EDGESET_T_NEXT_FUNC(&t)
00090 )
00091 {
00092 if (DGL_EDGE_ID(pnEdge) == nEdge)
00093 {
00094 register dglInt32_t * pnSet;
00095 register int i1, i2, c;
00096
00097 c = pnEdgeset[0];
00098
00099 if ((pnSet = malloc(sizeof(dglInt32_t) * (c + 1))) == NULL) {
00100 pgraph->iErrno = DGL_ERR_MemoryExhausted;
00101 return -pgraph->iErrno;
00102 }
00103
00104 for(i1 = 0, i2 = 0 ; i2 < c ; i2++) {
00105 if (pnEdgeset[1 + i2] != nEdge) {
00106 pnSet[1 + i1++] = pnEdgeset[1 + i2];
00107 }
00108 }
00109 pnSet[0] = i1;
00110
00111 free(pnEdgeset);
00112 DGL_T_NODEITEM_Set_OutEdgesetPTR(pNodeItem,pnSet);
00113 break;
00114 }
00115 }
00116 }
00117 }
00118 {
00119 dglInt32_t *pIn, *pOut, *pNode;
00120 pOut = DGL_T_NODEITEM_OutEdgesetPTR(pNodeItem);
00121 pIn = DGL_T_NODEITEM_InEdgesetPTR(pNodeItem);
00122 pNode = DGL_T_NODEITEM_NodePTR(pNodeItem);
00123 if (
00124 (pOut == NULL || DGL_EDGESET_EDGECOUNT(pOut) == 0) &&
00125 (pIn == NULL || DGL_EDGESET_EDGECOUNT(pIn) == 0)
00126 )
00127 {
00128 if (DGL_NODE_STATUS(pNode) & DGL_NS_HEAD) pgraph->cHead--;
00129 if (DGL_NODE_STATUS(pNode) & DGL_NS_TAIL) pgraph->cTail--;
00130 DGL_NODE_STATUS(pNode) = DGL_NS_ALONE; pgraph->cAlone++;
00131 }
00132 }
00133 }
00134 return 0;
00135 }
00136
00137 int DGL_DEL_NODE_INEDGE_FUNC(dglGraph_s * pgraph, dglInt32_t nNode, dglInt32_t nEdge)
00138 {
00139 DGL_T_NODEITEM_TYPE * pNodeItem , findNodeItem;
00140 dglInt32_t * pnEdgeset, * pnEdge, * pnNode;
00141 dglEdgesetTraverser_s t;
00142
00143 findNodeItem.nKey = nNode;
00144
00145 if ( (pNodeItem = avl_find( pgraph->pNodeTree, &findNodeItem )) != NULL) {
00146 pnNode = DGL_T_NODEITEM_NodePTR(pNodeItem);
00147 if ( DGL_NODE_STATUS(pnNode) == DGL_NS_ALONE ) {
00148 return 0;
00149 }
00150 if ( (pnEdgeset = DGL_T_NODEITEM_InEdgesetPTR(pNodeItem)) != NULL ) {
00151 if ( DGL_EDGESET_T_INITIALIZE_FUNC(pgraph,&t,pnEdgeset) >= 0 ) {
00152 for (
00153 pnEdge = DGL_EDGESET_T_FIRST_FUNC(&t) ;
00154 pnEdge ;
00155 pnEdge = DGL_EDGESET_T_NEXT_FUNC(&t)
00156 )
00157 {
00158 if (DGL_EDGE_ID(pnEdge) == nEdge)
00159 {
00160 register dglInt32_t * pnSet;
00161 register int i1, i2, c;
00162
00163 c = pnEdgeset[0];
00164
00165 if ((pnSet = malloc(sizeof(dglInt32_t) * (c + 1))) == NULL) {
00166 pgraph->iErrno = DGL_ERR_MemoryExhausted;
00167 return -pgraph->iErrno;
00168 }
00169
00170 for(i1 = 0, i2 = 0 ; i2 < c ; i2++) {
00171 if (pnEdgeset[1 + i2] != nEdge) {
00172 pnSet[1 + i1++] = pnEdgeset[1 + i2];
00173 }
00174 }
00175 pnSet[0] = i1;
00176
00177 free(pnEdgeset);
00178 DGL_T_NODEITEM_Set_InEdgesetPTR(pNodeItem,pnSet);
00179 break;
00180 }
00181 }
00182 }
00183 }
00184 {
00185 dglInt32_t *pIn, *pOut, *pNode;
00186 pOut = DGL_T_NODEITEM_OutEdgesetPTR(pNodeItem);
00187 pIn = DGL_T_NODEITEM_InEdgesetPTR(pNodeItem);
00188 pNode = DGL_T_NODEITEM_NodePTR(pNodeItem);
00189 if (
00190 (pOut == NULL || DGL_EDGESET_EDGECOUNT(pOut) == 0) &&
00191 (pIn == NULL || DGL_EDGESET_EDGECOUNT(pIn) == 0)
00192 )
00193 {
00194 if (DGL_NODE_STATUS(pNode) & DGL_NS_HEAD) pgraph->cHead--;
00195 if (DGL_NODE_STATUS(pNode) & DGL_NS_TAIL) pgraph->cTail--;
00196 DGL_NODE_STATUS(pNode) = DGL_NS_ALONE; pgraph->cAlone++;
00197 }
00198 }
00199 }
00200 return 0;
00201 }
00202 #endif
00203
00204 int DGL_DEL_NODE_FUNC( dglGraph_s * pgraph, dglInt32_t nNodeId )
00205 {
00206 #if defined(_DGL_V1)
00207 pgraph->iErrno = DGL_ERR_NotSupported;
00208 return -pgraph->iErrno;
00209 #else
00210 DGL_T_NODEITEM_TYPE * pNodeItem, findNodeItem;
00211 dglInt32_t * pEdgeset;
00212 dglInt32_t * pnode;
00213 dglInt32_t * pEdge;
00214 dglEdgesetTraverser_s trav;
00215
00216 dglTreeEdge_s * pEdgeItem;
00217
00218 if ( pgraph->Flags & DGL_GS_FLAT )
00219 {
00220 pgraph->iErrno = DGL_ERR_BadOnFlatGraph;
00221 return -pgraph->iErrno;
00222 }
00223
00224 if ( pgraph->pNodeTree == NULL ) {
00225 pgraph->iErrno = DGL_ERR_UnexpectedNullPointer;
00226 return -pgraph->iErrno;
00227 }
00228
00229 findNodeItem.nKey = nNodeId;
00230 if ( (pNodeItem = avl_find( pgraph->pNodeTree, &findNodeItem )) == NULL) {
00231 pgraph->iErrno = DGL_ERR_NodeNotFound;
00232 return -pgraph->iErrno;
00233 }
00234
00235 pnode = DGL_T_NODEITEM_NodePTR(pNodeItem);
00236
00237 if ( DGL_NODE_STATUS(pnode) & DGL_NS_ALONE ) goto node_is_alone;
00238
00239 pEdgeset = DGL_T_NODEITEM_OutEdgesetPTR(pNodeItem);
00240
00241 if ( DGL_EDGESET_T_INITIALIZE_FUNC(pgraph,&trav,pEdgeset) < 0 ) return -pgraph->iErrno;
00242 for (
00243 pEdge = DGL_EDGESET_T_FIRST_FUNC(&trav) ;
00244 pEdge ;
00245 pEdge = DGL_EDGESET_T_NEXT_FUNC(&trav)
00246 )
00247 {
00248 if ( DGL_EDGE_TAILNODE_OFFSET(pEdge) != DGL_NODE_ID(pnode) ) {
00249 if ( DGL_DEL_NODE_INEDGE_FUNC(pgraph, DGL_EDGE_TAILNODE_OFFSET(pEdge), DGL_EDGE_ID(pEdge)) < 0 ) {
00250 return -pgraph->iErrno;
00251 }
00252 }
00253 if ( (pEdgeItem = trav.pvCurrentItem) != NULL ) {
00254
00255
00256 if (pgraph->nOptions & DGL_GO_EdgePrioritize_COST) {
00257 if ( dgl_edge_prioritizer_del(pgraph,DGL_EDGE_ID(pEdge),DGL_EDGE_COST(pEdge)) < 0) {
00258 return -pgraph->iErrno;
00259 }
00260 }
00261
00262
00263 pgraph->cEdge--;
00264 pgraph->nnCost -= (dglInt64_t)DGL_EDGE_COST(pEdge);
00265
00266 avl_delete(pgraph->pEdgeTree, pEdgeItem);
00267 dglTreeEdgeCancel(pEdgeItem,NULL);
00268 }
00269 }
00270 DGL_EDGESET_T_RELEASE_FUNC(&trav);
00271
00272 pEdgeset = DGL_T_NODEITEM_InEdgesetPTR(pNodeItem);
00273
00274 if ( DGL_EDGESET_T_INITIALIZE_FUNC(pgraph,&trav,pEdgeset) < 0 ) return -pgraph->iErrno;
00275 for (
00276 pEdge = DGL_EDGESET_T_FIRST_FUNC(&trav) ;
00277 pEdge ;
00278 pEdge = DGL_EDGESET_T_NEXT_FUNC(&trav)
00279 )
00280 {
00281 if ( DGL_EDGE_HEADNODE_OFFSET(pEdge) != DGL_NODE_ID(pnode) ) {
00282 if ( DGL_DEL_NODE_OUTEDGE_FUNC(pgraph, DGL_EDGE_HEADNODE_OFFSET(pEdge), DGL_EDGE_ID(pEdge)) < 0 ) {
00283 return -pgraph->iErrno;
00284 }
00285 }
00286 if ( (pEdgeItem = trav.pvCurrentItem) != NULL ) {
00287
00288
00289 if (pgraph->nOptions & DGL_GO_EdgePrioritize_COST) {
00290 if ( dgl_edge_prioritizer_del(pgraph,DGL_EDGE_ID(pEdge),DGL_EDGE_COST(pEdge)) < 0) {
00291 return -pgraph->iErrno;
00292 }
00293 }
00294
00295
00296 pgraph->cEdge--;
00297 pgraph->nnCost -= (dglInt64_t)DGL_EDGE_COST(pEdge);
00298
00299 avl_delete(pgraph->pEdgeTree, pEdgeItem);
00300 dglTreeEdgeCancel(pEdgeItem,NULL);
00301 }
00302 }
00303 DGL_EDGESET_T_RELEASE_FUNC(&trav);
00304
00305 if ( DGL_NODE_STATUS(pnode) & DGL_NS_HEAD ) pgraph->cHead--;
00306 if ( DGL_NODE_STATUS(pnode) & DGL_NS_TAIL ) pgraph->cTail--;
00307
00308 node_is_alone:
00309 if ( DGL_NODE_STATUS(pnode) & DGL_NS_ALONE ) pgraph->cAlone--;
00310 pgraph->cNode--;
00311
00312 avl_delete( pgraph->pNodeTree, pNodeItem );
00313 DGL_T_NODEITEM_Cancel(pNodeItem, NULL);
00314
00315 return 0;
00316 #endif
00317 }
00318
00319 dglInt32_t * DGL_GET_NODE_FUNC( dglGraph_s * pgraph , dglInt32_t nodeid )
00320 {
00321 register dglInt32_t top;
00322 register dglInt32_t pos;
00323 register dglInt32_t bot;
00324 register dglInt32_t * pref;
00325 register int cwords;
00326 register dglTreeNode_s * ptreenode;
00327 dglTreeNode_s findnode;
00328 dglInt32_t id;
00329
00330 pgraph->iErrno = 0;
00331 if ( pgraph->Flags & DGL_GS_FLAT ) {
00332 cwords = DGL_NODE_WSIZE(pgraph->NodeAttrSize);
00333
00334 bot = pgraph->cNode;
00335 top = 0;
00336 pos = 0;
00337 pref = (dglInt32_t*)pgraph->pNodeBuffer;
00338
00339
00340
00341 while( top != bot ) {
00342 pos = top + (bot - top) / 2;
00343 id = DGL_NODE_ID(& pref[pos * cwords]);
00344 if ( id == nodeid ) {
00345 break;
00346 }
00347 else if ( nodeid < id ) {
00348 bot = pos;
00349 }
00350 else if ( nodeid > id ) {
00351 top = pos + 1;
00352 }
00353 }
00354 if ( top == bot ) {
00355 return NULL;
00356 }
00357 return & pref[ pos * cwords ];
00358 }
00359 else {
00360 findnode.nKey = nodeid;
00361 ptreenode = avl_find( pgraph->pNodeTree , &findnode );
00362 if ( ptreenode && ptreenode->pv ) {
00363 return ptreenode->pv;
00364 }
00365 return NULL;
00366 }
00367 }
00368
00369
00370
00371
00372
00373 dglInt32_t * DGL_GET_NODE_OUTEDGESET_FUNC( dglGraph_s * pgraph , dglInt32_t * pnode )
00374 {
00375 DGL_T_NODEITEM_TYPE * ptreenode, findnode;
00376 dglInt32_t * pEdgeset;
00377
00378 pgraph->iErrno = 0;
00379
00380 if ( pnode == NULL ) {
00381 pgraph->iErrno = DGL_ERR_UnexpectedNullPointer;
00382 return NULL;
00383 }
00384
00385 if ( DGL_NODE_STATUS(pnode) & DGL_NS_ALONE) {
00386 pgraph->iErrno = DGL_ERR_NodeIsAComponent;
00387 return NULL;
00388 }
00389
00390 if ( pgraph->Flags & DGL_GS_FLAT ) {
00391 pEdgeset = DGL_EDGEBUFFER_SHIFT(pgraph, DGL_NODE_EDGESET_OFFSET(pnode));
00392 return pEdgeset;
00393 }
00394 else {
00395 findnode.nKey = DGL_NODE_ID(pnode);
00396 ptreenode = avl_find( pgraph->pNodeTree , &findnode );
00397 if ( ptreenode && DGL_T_NODEITEM_OutEdgesetPTR(ptreenode) ) {
00398 return DGL_T_NODEITEM_OutEdgesetPTR(ptreenode);
00399 }
00400 return NULL;
00401 }
00402 }
00403
00404 dglInt32_t * DGL_GET_NODE_INEDGESET_FUNC( dglGraph_s * pgraph , dglInt32_t * pnode )
00405 {
00406 #if defined(_DGL_V1)
00407 pgraph->iErrno = DGL_ERR_NotSupported;
00408 return NULL;
00409 #endif
00410
00411 #if defined(_DGL_V2)
00412 DGL_T_NODEITEM_TYPE * ptreenode, findnode;
00413 dglInt32_t * pEdgeset;
00414
00415 pgraph->iErrno = 0;
00416
00417 if ( pnode == NULL ) {
00418 pgraph->iErrno = DGL_ERR_UnexpectedNullPointer;
00419 return NULL;
00420 }
00421
00422 if ( DGL_NODE_STATUS(pnode) & DGL_NS_ALONE) {
00423 pgraph->iErrno = DGL_ERR_NodeIsAComponent;
00424 return NULL;
00425 }
00426
00427 if ( pgraph->Flags & DGL_GS_FLAT ) {
00428 pEdgeset = DGL_EDGEBUFFER_SHIFT(pgraph, DGL_NODE_EDGESET_OFFSET(pnode));
00429 pEdgeset += DGL_EDGESET_WSIZE(DGL_EDGESET_EDGECOUNT(pEdgeset), pgraph->EdgeAttrSize);
00430 return pEdgeset;
00431 }
00432 else {
00433 findnode.nKey = DGL_NODE_ID(pnode);
00434 ptreenode = avl_find( pgraph->pNodeTree , &findnode );
00435 if ( ptreenode && DGL_T_NODEITEM_InEdgesetPTR(ptreenode) ) {
00436 return DGL_T_NODEITEM_InEdgesetPTR(ptreenode);
00437 }
00438 return NULL;
00439 }
00440 #endif
00441 }
00442