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 (
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         if ( DGL_T_NODEITEM_OutEdgesetPTR(pTailNodeItem) == NULL )
00145         {
00146                 pEdgeset = DGL_EDGESET_ALLOC( 0 , pgraph->EdgeAttrSize );
00147                 if ( pEdgeset == NULL ) {
00148                         pgraph->iErrno = DGL_ERR_MemoryExhausted;
00149                         return -pgraph->iErrno;
00150                 }
00151                 DGL_EDGESET_EDGECOUNT(pEdgeset) = 0;
00152                 DGL_T_NODEITEM_Set_OutEdgesetPTR(pTailNodeItem,pEdgeset);
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         if ( DGL_T_NODEITEM_InEdgesetPTR(pHeadNodeItem) == NULL )
00182         {
00183                 pinEdgeset = DGL_EDGESET_ALLOC( 0 , pgraph->EdgeAttrSize );
00184                 if ( pinEdgeset == NULL ) {
00185                         pgraph->iErrno = DGL_ERR_MemoryExhausted;
00186                         return -pgraph->iErrno;
00187                 }
00188                 DGL_EDGESET_EDGECOUNT(pinEdgeset) = 0;
00189                 DGL_T_NODEITEM_Set_InEdgesetPTR(pHeadNodeItem,pinEdgeset);
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          * Set the edge-tree
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          * assign edge id
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 printf( "add edge: node %ld(%ld,%ld) -> %ld(%ld,%ld)\n",
00244                                 DGL_NODE_ID(pHead), DGL_EDGESET_EDGECOUNT(pEdgeset),0,
00245                                 DGL_NODE_ID(pTail), 0,DGL_EDGESET_EDGECOUNT(pinEdgeset));
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;                /* will be an offset after flattening */
00258         DGL_EDGE_TAILNODE_OFFSET(pEdge) = nTail;                /* will be an offset after flattening */
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          * If requested add a cost-weighted entry into the edge prioritizer
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         /* prioritizer sync
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;    /* top of table */
00356         register dglInt32_t             pos;    /* current position to compare */
00357         register dglInt32_t             bot;    /* bottom of table */
00358         register dglInt32_t *   pref;
00359         register int                    cwords; /* size of a edge in words of 32 bit */
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                 /*bot    = pgraph->iEdgeBuffer / DGL_EDGE_SIZEOF(pgraph->EdgeAttrSize);*/
00368                 bot    = pgraph->cEdge;
00369                 top    = 0;
00370                 pos    = 0;
00371                 pref   = (dglInt32_t*)pgraph->pEdgeBuffer;
00372 
00373                 /* perform a binary search
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 

Generated on Sun Apr 6 17:32:44 2008 for GRASS by  doxygen 1.5.5