edgemgmt-template.c

Go to the documentation of this file.
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 }

Generated on Sat Oct 24 03:25:19 2009 for GRASS Programmer's Manual by  doxygen 1.6.1