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 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 /* node already exists */ 00053 pgraph->iErrno = DGL_ERR_NodeAlreadyExist; 00054 return -pgraph->iErrno; 00055 } 00056 return 0; 00057 } 00058 00059 #if !defined(_DGL_V1) 00060 /* 00061 * Delete the link from the node's out-edgeset 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 { /* check alone status */ 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 { /* check alone status */ 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 /* prioritizer sync 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 /* prioritizer sync 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; /* top of table */ 00319 register dglInt32_t pos; /* current position to compare */ 00320 register dglInt32_t bot; /* bottom of table */ 00321 register dglInt32_t *pref; 00322 register int cwords; /* size of a node in words of 32 bit */ 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 /*bot = pgraph->iNodeBuffer / DGL_NODE_SIZEOF(pgraph->NodeAttrSize); */ 00331 bot = pgraph->cNode; 00332 top = 0; 00333 pos = 0; 00334 pref = (dglInt32_t *) pgraph->pNodeBuffer; 00335 00336 /* perform a binary search 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 * if graph is FLAT retrieve the edge area from the pEdgeBuffer 00368 * if graph is TREE retrieve the node from the pNodeTree avl and return pv field 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 }