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 int DGL_ADD_EDGE_FUNC(dglGraph_s * pgraph,
00029 dglInt32_t nHead,
00030 dglInt32_t nTail,
00031 dglInt32_t nCost,
00032 dglInt32_t nEdge,
00033 void *pvHeadAttr,
00034 void *pvTailAttr, void *pvEdgeAttr, dglInt32_t nFlags)
00035 {
00036 dglInt32_t *pHead;
00037 dglInt32_t *pTail;
00038 dglInt32_t *pEdgeset;
00039 dglInt32_t *pEdge;
00040 DGL_T_NODEITEM_TYPE *pHeadNodeItem;
00041 DGL_T_NODEITEM_TYPE *pTailNodeItem;
00042
00043 #if defined(_DGL_V2)
00044 dglInt32_t *pinEdgeset;
00045 dglTreeEdge_s *pEdgeItem;
00046 dglTreeEdge_s findEdge;
00047 #endif
00048
00049 if (pgraph->Flags & DGL_GS_FLAT) {
00050 pgraph->iErrno = DGL_ERR_BadOnFlatGraph;
00051 return -pgraph->iErrno;
00052 }
00053
00054 #ifdef DGL_STATS
00055 {
00056 clock_t clk = clock();
00057 #endif
00058
00059 if ((pHeadNodeItem =
00060 DGL_T_NODEITEM_Add(pgraph->pNodeTree, nHead)) == NULL ||
00061 (pTailNodeItem =
00062 DGL_T_NODEITEM_Add(pgraph->pNodeTree, nTail)) == NULL) {
00063 pgraph->iErrno = DGL_ERR_MemoryExhausted;
00064 return -pgraph->iErrno;
00065 }
00066
00067 #ifdef DGL_STATS
00068 pgraph->clkNodeTree += clock() - clk;
00069 pgraph->cNodeTree++;
00070 pgraph->cNodeTree++;
00071 }
00072 #endif
00073
00074 if (DGL_T_NODEITEM_NodePTR(pHeadNodeItem) == NULL) {
00075 if ((pHead = DGL_NODE_ALLOC(pgraph->NodeAttrSize)) == NULL) {
00076 pgraph->iErrno = DGL_ERR_MemoryExhausted;
00077 return -1;
00078 }
00079 DGL_NODE_STATUS(pHead) = 0;
00080 DGL_T_NODEITEM_Set_NodePTR(pHeadNodeItem, pHead);
00081 pgraph->cNode++;
00082 pgraph->cHead++;
00083 }
00084 else {
00085 pHead = DGL_T_NODEITEM_NodePTR(pHeadNodeItem);
00086 if (!(DGL_NODE_STATUS(pHead) & DGL_NS_HEAD))
00087 pgraph->cHead++;
00088 }
00089
00090 if (DGL_T_NODEITEM_NodePTR(pTailNodeItem) == NULL) {
00091 if ((pTail = DGL_NODE_ALLOC(pgraph->NodeAttrSize)) == NULL) {
00092 pgraph->iErrno = DGL_ERR_MemoryExhausted;
00093 return -pgraph->iErrno;
00094 }
00095 DGL_NODE_STATUS(pTail) = 0;
00096 DGL_T_NODEITEM_Set_NodePTR(pTailNodeItem, pTail);
00097 pgraph->cNode++;
00098 pgraph->cTail++;
00099 }
00100 else {
00101 pTail = DGL_T_NODEITEM_NodePTR(pTailNodeItem);
00102 if (!(DGL_NODE_STATUS(pTail) & DGL_NS_TAIL))
00103 pgraph->cTail++;
00104 }
00105
00106
00107 DGL_NODE_STATUS(pHead) |= DGL_NS_HEAD;
00108 DGL_NODE_STATUS(pTail) |= DGL_NS_TAIL;
00109
00110 if (DGL_NODE_STATUS(pHead) & DGL_NS_ALONE) {
00111 DGL_NODE_STATUS(pHead) &= ~DGL_NS_ALONE;
00112 pgraph->cAlone--;
00113 }
00114
00115 if (DGL_NODE_STATUS(pTail) & DGL_NS_ALONE) {
00116 DGL_NODE_STATUS(pTail) &= ~DGL_NS_ALONE;
00117 pgraph->cAlone--;
00118 }
00119
00120 DGL_NODE_ID(pHead) = nHead;
00121 DGL_NODE_ID(pTail) = nTail;
00122
00123 DGL_NODE_EDGESET_OFFSET(pHead) = -1;
00124 DGL_NODE_EDGESET_OFFSET(pTail) = -1;
00125
00126 if (pvHeadAttr && pgraph->NodeAttrSize) {
00127 memcpy(DGL_NODE_ATTR_PTR(pHead), pvHeadAttr, pgraph->NodeAttrSize);
00128 }
00129
00130 if (pvTailAttr && pgraph->NodeAttrSize) {
00131 memcpy(DGL_NODE_ATTR_PTR(pTail), pvTailAttr, pgraph->NodeAttrSize);
00132 }
00133
00134
00135
00136
00137
00138
00139
00140
00141
00142
00143
00144
00145
00146
00147
00148 if ((pEdgeset = DGL_T_NODEITEM_OutEdgesetPTR(pHeadNodeItem)) == NULL) {
00149 pEdgeset = DGL_EDGESET_ALLOC(1, pgraph->EdgeAttrSize);
00150 if (pEdgeset == NULL) {
00151 pgraph->iErrno = DGL_ERR_MemoryExhausted;
00152 return -pgraph->iErrno;
00153 }
00154 DGL_EDGESET_EDGECOUNT(pEdgeset) = 0;
00155 DGL_T_NODEITEM_Set_OutEdgesetPTR(pHeadNodeItem, pEdgeset);
00156 }
00157 else {
00158 pEdgeset = DGL_EDGESET_REALLOC(pEdgeset,
00159 DGL_EDGESET_EDGECOUNT(pEdgeset) + 1,
00160 pgraph->EdgeAttrSize);
00161
00162 if (pEdgeset == NULL) {
00163 pgraph->iErrno = DGL_ERR_MemoryExhausted;
00164 return -pgraph->iErrno;
00165 }
00166 DGL_T_NODEITEM_Set_OutEdgesetPTR(pHeadNodeItem, pEdgeset);
00167 }
00168
00169 #if defined(_DGL_V2)
00170
00171
00172
00173
00174
00175
00176
00177
00178
00179
00180
00181
00182
00183 if ((pinEdgeset = DGL_T_NODEITEM_InEdgesetPTR(pTailNodeItem)) == NULL) {
00184 pinEdgeset = DGL_EDGESET_ALLOC(1, pgraph->EdgeAttrSize);
00185 if (pinEdgeset == NULL) {
00186 pgraph->iErrno = DGL_ERR_MemoryExhausted;
00187 return -pgraph->iErrno;
00188 }
00189 DGL_EDGESET_EDGECOUNT(pinEdgeset) = 0;
00190 DGL_T_NODEITEM_Set_InEdgesetPTR(pTailNodeItem, pinEdgeset);
00191 }
00192 else {
00193 pinEdgeset = DGL_EDGESET_REALLOC(pinEdgeset,
00194 DGL_EDGESET_EDGECOUNT(pinEdgeset) +
00195 1, pgraph->EdgeAttrSize);
00196
00197 if (pinEdgeset == NULL) {
00198 pgraph->iErrno = DGL_ERR_MemoryExhausted;
00199 return -pgraph->iErrno;
00200 }
00201 DGL_T_NODEITEM_Set_InEdgesetPTR(pTailNodeItem, pinEdgeset);
00202 }
00203
00204
00205
00206
00207 findEdge.nKey = nEdge;
00208
00209 if ((pEdgeItem = dglTreeEdgeAdd(pgraph->pEdgeTree, nEdge)) == NULL) {
00210 pgraph->iErrno = DGL_ERR_MemoryExhausted;
00211 return -pgraph->iErrno;
00212 }
00213 if (pEdgeItem->pv) {
00214 pgraph->iErrno = DGL_ERR_EdgeAlreadyExist;
00215 return -pgraph->iErrno;
00216 }
00217 if ((pEdgeItem->pv = DGL_EDGE_ALLOC(pgraph->EdgeAttrSize)) == NULL) {
00218 pgraph->iErrno = DGL_ERR_MemoryExhausted;
00219 return -pgraph->iErrno;
00220 }
00221
00222
00223
00224
00225 pEdgeset[DGL_EDGESET_EDGECOUNT(pEdgeset) + 1] = nEdge;
00226 pinEdgeset[DGL_EDGESET_EDGECOUNT(pinEdgeset) + 1] = nEdge;
00227 ++DGL_EDGESET_EDGECOUNT(pEdgeset);
00228 ++DGL_EDGESET_EDGECOUNT(pinEdgeset);
00229
00230
00231
00232
00233
00234
00235
00236
00237 pEdge = pEdgeItem->pv;
00238 #endif
00239
00240 #if defined(_DGL_V1)
00241 pEdge =
00242 DGL_EDGESET_EDGE_PTR(pEdgeset, DGL_EDGESET_EDGECOUNT(pEdgeset),
00243 pgraph->EdgeAttrSize);
00244 DGL_EDGESET_EDGECOUNT(pEdgeset)++;
00245 #endif
00246
00247 DGL_EDGE_HEADNODE_OFFSET(pEdge) = nHead;
00248 DGL_EDGE_TAILNODE_OFFSET(pEdge) = nTail;
00249 DGL_EDGE_COST(pEdge) = nCost;
00250 DGL_EDGE_ID(pEdge) = nEdge;
00251
00252 #if !defined(_DGL_V1)
00253 if (nFlags & DGL_ES_DIRECTED)
00254 DGL_EDGE_STATUS(pEdge) = DGL_ES_DIRECTED;
00255 else
00256 DGL_EDGE_STATUS(pEdge) = 0;
00257 #endif
00258
00259 pgraph->cEdge++;
00260 pgraph->nnCost += (dglInt64_t) nCost;
00261
00262 if (pvEdgeAttr && pgraph->EdgeAttrSize) {
00263 memcpy(DGL_EDGE_ATTR_PTR(pEdge), pvEdgeAttr, pgraph->EdgeAttrSize);
00264 }
00265
00266
00267
00268
00269 #if !defined(_DGL_V1)
00270 if (pgraph->nOptions & DGL_GO_EdgePrioritize_COST) {
00271 if (dgl_edge_prioritizer_add
00272 (pgraph, DGL_EDGE_ID(pEdge), DGL_EDGE_COST(pEdge)) < 0) {
00273 return -pgraph->iErrno;
00274 }
00275 }
00276 #endif
00277
00278 if (nFlags & DGL_STRONGCONNECT) {
00279 return DGL_ADD_EDGE_FUNC(pgraph, nTail, nHead, nCost, nEdge,
00280 pvHeadAttr, pvTailAttr, pvEdgeAttr,
00281 nFlags & ~DGL_STRONGCONNECT);
00282 }
00283
00284 return 0;
00285 }
00286
00287 int DGL_DEL_EDGE_FUNC(dglGraph_s * pgraph, dglInt32_t nEdge)
00288 {
00289 #if defined(_DGL_V1)
00290 pgraph->iErrno = DGL_ERR_NotSupported;
00291 return -pgraph->iErrno;
00292 #else
00293 dglTreeEdge_s *pEdgeItem, findEdgeItem;
00294 dglInt32_t *pEdge;
00295
00296 if (pgraph->Flags & DGL_GS_FLAT) {
00297 pgraph->iErrno = DGL_ERR_BadOnFlatGraph;
00298 return -pgraph->iErrno;
00299 }
00300
00301 if (pgraph->pEdgeTree == NULL) {
00302 pgraph->iErrno = DGL_ERR_UnexpectedNullPointer;
00303 return -pgraph->iErrno;
00304 }
00305
00306 findEdgeItem.nKey = nEdge;
00307 if ((pEdgeItem = avl_find(pgraph->pEdgeTree, &findEdgeItem)) == NULL) {
00308 pgraph->iErrno = DGL_ERR_EdgeNotFound;
00309 return -pgraph->iErrno;
00310 }
00311
00312 pEdge = pEdgeItem->pv;
00313
00314 if (DGL_DEL_NODE_INEDGE_FUNC
00315 (pgraph, DGL_EDGE_TAILNODE_OFFSET(pEdge), DGL_EDGE_ID(pEdge)) < 0) {
00316 return -pgraph->iErrno;
00317 }
00318
00319 if (DGL_DEL_NODE_OUTEDGE_FUNC
00320 (pgraph, DGL_EDGE_HEADNODE_OFFSET(pEdge), DGL_EDGE_ID(pEdge)) < 0) {
00321 return -pgraph->iErrno;
00322 }
00323
00324
00325
00326
00327 if (pgraph->nOptions & DGL_GO_EdgePrioritize_COST) {
00328 if (dgl_edge_prioritizer_del
00329 (pgraph, DGL_EDGE_ID(pEdge), DGL_EDGE_COST(pEdge)) < 0) {
00330 return -pgraph->iErrno;
00331 }
00332 }
00333
00334
00335 pgraph->cEdge--;
00336 pgraph->nnCost -= (dglInt64_t) DGL_EDGE_COST(pEdge);
00337
00338 avl_delete(pgraph->pEdgeTree, pEdgeItem);
00339 dglTreeEdgeCancel(pEdgeItem, NULL);
00340 return 0;
00341 #endif
00342 }
00343
00344 dglInt32_t *DGL_GET_EDGE_FUNC(dglGraph_s * pgraph, dglInt32_t nEdge)
00345 {
00346 #if defined(_DGL_V1)
00347 pgraph->iErrno = DGL_ERR_NotSupported;
00348 return NULL;
00349 #else
00350 register dglInt32_t top;
00351 register dglInt32_t pos;
00352 register dglInt32_t bot;
00353 register dglInt32_t *pref;
00354 register int cwords;
00355 register dglTreeEdge_s *ptreeEdge;
00356 dglTreeEdge_s findEdge;
00357 dglInt32_t id;
00358
00359 pgraph->iErrno = 0;
00360 if (pgraph->Flags & DGL_GS_FLAT) {
00361 cwords = DGL_EDGE_WSIZE(pgraph->EdgeAttrSize);
00362
00363 bot = pgraph->cEdge;
00364 top = 0;
00365 pos = 0;
00366 pref = (dglInt32_t *) pgraph->pEdgeBuffer;
00367
00368
00369
00370 while (top != bot) {
00371 pos = top + (bot - top) / 2;
00372 id = DGL_EDGE_ID(&pref[pos * cwords]);
00373 if (id == nEdge) {
00374 break;
00375 }
00376 else if (nEdge < id) {
00377 bot = pos;
00378 }
00379 else if (nEdge > id) {
00380 top = pos + 1;
00381 }
00382 }
00383 if (top == bot) {
00384 return NULL;
00385 }
00386 return &pref[pos * cwords];
00387 }
00388 else {
00389 findEdge.nKey = nEdge;
00390 ptreeEdge = avl_find(pgraph->pEdgeTree, &findEdge);
00391 if (ptreeEdge && ptreeEdge->pv) {
00392 return ptreeEdge->pv;
00393 }
00394 return NULL;
00395 }
00396 #endif
00397 }