GRASS Programmer's Manual 6.4.1(2011)
|
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., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. 00017 */ 00018 00019 /* 00020 * best view with tabstop=4 00021 */ 00022 00023 00024 /* 00025 * Add edge can be performed on TREE state graph. If the state is FLAT 00026 * return BadOnFlatGraph error. 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 if ( DGL_T_NODEITEM_OutEdgesetPTR(pTailNodeItem) == NULL ) 00137 { 00138 pEdgeset = DGL_EDGESET_ALLOC( 0 , pgraph->EdgeAttrSize ); 00139 if ( pEdgeset == NULL ) { 00140 pgraph->iErrno = DGL_ERR_MemoryExhausted; 00141 return -pgraph->iErrno; 00142 } 00143 DGL_EDGESET_EDGECOUNT(pEdgeset) = 0; 00144 DGL_T_NODEITEM_Set_OutEdgesetPTR(pTailNodeItem,pEdgeset); 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 if ( DGL_T_NODEITEM_InEdgesetPTR(pHeadNodeItem) == NULL ) 00172 { 00173 pinEdgeset = DGL_EDGESET_ALLOC( 0 , pgraph->EdgeAttrSize ); 00174 if ( pinEdgeset == NULL ) { 00175 pgraph->iErrno = DGL_ERR_MemoryExhausted; 00176 return -pgraph->iErrno; 00177 } 00178 DGL_EDGESET_EDGECOUNT(pinEdgeset) = 0; 00179 DGL_T_NODEITEM_Set_InEdgesetPTR(pHeadNodeItem,pinEdgeset); 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 * Set the edge-tree 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 * assign edge id 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 printf( "add edge: node %ld(%ld,%ld) -> %ld(%ld,%ld)\n", 00232 DGL_NODE_ID(pHead), DGL_EDGESET_EDGECOUNT(pEdgeset),0, 00233 DGL_NODE_ID(pTail), 0,DGL_EDGESET_EDGECOUNT(pinEdgeset)); 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; /* will be an offset after flattening */ 00248 DGL_EDGE_TAILNODE_OFFSET(pEdge) = nTail; /* will be an offset after flattening */ 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 * If requested add a cost-weighted entry into the edge prioritizer 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 /* prioritizer sync 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; /* top of table */ 00351 register dglInt32_t pos; /* current position to compare */ 00352 register dglInt32_t bot; /* bottom of table */ 00353 register dglInt32_t *pref; 00354 register int cwords; /* size of a edge in words of 32 bit */ 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 /*bot = pgraph->iEdgeBuffer / DGL_EDGE_SIZEOF(pgraph->EdgeAttrSize); */ 00363 bot = pgraph->cEdge; 00364 top = 0; 00365 pos = 0; 00366 pref = (dglInt32_t *) pgraph->pEdgeBuffer; 00367 00368 /* perform a binary search 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 }