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