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