graph_v2.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 #include <stdio.h>
00024 #include <string.h>
00025 #include <sys/types.h>
00026 #include <sys/stat.h>
00027 #include <unistd.h>
00028 #include <stdlib.h>
00029 #include <errno.h>
00030 
00031 
00032 #include "type.h"
00033 #include "tree.h"
00034 #include "graph.h"
00035 #include "graph_v2.h"
00036 #include "helpers.h"
00037 
00038 
00039 /* Template expansion
00040  */
00041 #include "v2-defs.h"
00042 #include "sp-template.c"
00043 #include "nodemgmt-template.c"
00044 #include "edgemgmt-template.c"
00045 #include "misc-template.c"
00046 
00047 
00048 /* algorithms for TREE state
00049  */
00050 #define DGL_DEFINE_TREE_PROCS 1
00051 #include "v2-defs.h"
00052 #include "sp-template.c"
00053 #include "span-template.c"
00054 #undef DGL_DEFINE_TREE_PROCS
00055 
00056 
00057 /* algorithms for FLAT state
00058 */
00059 #define DGL_DEFINE_FLAT_PROCS 1
00060 #include "v2-defs.h"
00061 #include "sp-template.c"
00062 #include "span-template.c"
00063 #undef DGL_DEFINE_FLAT_PROCS
00064 
00065 
00066 
00067 int dgl_dijkstra_V2     (
00068                                                 dglGraph_s *            pgraph ,
00069                                                 dglSPReport_s **        ppReport ,
00070                                                 dglInt32_t *                    pDistance ,
00071                                                 dglInt32_t                      nStart ,
00072                                                 dglInt32_t                      nDestination ,
00073                                                 dglSPClip_fn            fnClip,
00074                                                 void *                          pvClipArg,
00075                                                 dglSPCache_s *  pCache
00076                                         )
00077 {
00078         if ( pgraph->Flags & DGL_GS_FLAT ) {
00079                 return dgl_dijkstra_V2_FLAT(pgraph,ppReport,pDistance,nStart,nDestination,fnClip,pvClipArg,pCache);
00080         }
00081         else {
00082                 return dgl_dijkstra_V2_TREE(pgraph,ppReport,pDistance,nStart,nDestination,fnClip,pvClipArg,pCache);
00083         }
00084 }
00085 
00086 
00087 int dgl_depthfirst_spanning_V2(
00088                                                 dglGraph_s * pgraphIn ,
00089                                                 dglGraph_s * pgraphOut ,
00090                                                 dglInt32_t nVertex ,
00091                                                 void * pvVisited ,
00092                                                 dglSpanClip_fn  fnClip ,
00093                                                 void *                          pvClipArg
00094                                                 )
00095 {
00096         if ( pgraphIn->Flags & DGL_GS_FLAT ) {
00097                 return dgl_span_depthfirst_spanning_V2_FLAT(pgraphIn,pgraphOut,nVertex,pvVisited,fnClip,pvClipArg);
00098         }
00099         else {
00100                 return dgl_span_depthfirst_spanning_V2_TREE(pgraphIn,pgraphOut,nVertex,pvVisited,fnClip,pvClipArg);
00101         }
00102 }
00103 
00104 int dgl_minimum_spanning_V2(
00105                                                 dglGraph_s * pgraphIn ,
00106                         dglGraph_s * pgraphOut ,
00107                                                 dglInt32_t nVertex ,
00108                                                 dglSpanClip_fn  fnClip ,
00109                                                 void *                          pvClipArg
00110                                                 )
00111 {
00112         if ( pgraphIn->Flags & DGL_GS_FLAT ) {
00113                 return dgl_span_minimum_spanning_V2_FLAT(pgraphIn,pgraphOut,nVertex,fnClip,pvClipArg);
00114         }
00115         else {
00116                 return dgl_span_minimum_spanning_V2_TREE(pgraphIn,pgraphOut,nVertex,fnClip,pvClipArg);
00117         }
00118 }
00119 
00120 
00121 int dgl_initialize_V2( dglGraph_s * pgraph )
00122 {
00123         if ( pgraph->pNodeTree == NULL ) pgraph->pNodeTree = avl_create( dglTreeNode2Compare, NULL, dglTreeGetAllocator() );
00124         if ( pgraph->pNodeTree == NULL ) {
00125                 pgraph->iErrno = DGL_ERR_MemoryExhausted;
00126                 return -pgraph->iErrno;
00127         }
00128         if ( pgraph->pEdgeTree == NULL ) pgraph->pEdgeTree = avl_create( dglTreeEdgeCompare, NULL, dglTreeGetAllocator() );
00129         if ( pgraph->pEdgeTree == NULL ) {
00130                 pgraph->iErrno = DGL_ERR_MemoryExhausted;
00131                 return -pgraph->iErrno;
00132         }
00133         return 0;
00134 }
00135 
00136 int dgl_release_V2( dglGraph_s * pgraph )
00137 {
00138         pgraph->iErrno = 0;
00139 
00140         if ( pgraph->pNodeTree ) avl_destroy( pgraph->pNodeTree, dglTreeNodeCancel );
00141         if ( pgraph->pEdgeTree ) avl_destroy( pgraph->pEdgeTree, dglTreeEdgeCancel );
00142         if ( pgraph->pNodeBuffer ) free( pgraph->pNodeBuffer );
00143         if ( pgraph->pEdgeBuffer ) free( pgraph->pEdgeBuffer );
00144         if ( pgraph->edgePrioritizer.pvAVL ) avl_destroy( pgraph->edgePrioritizer.pvAVL, dglTreeEdgePri32Cancel );
00145         if ( pgraph->nodePrioritizer.pvAVL ) avl_destroy( pgraph->nodePrioritizer.pvAVL, dglTreeNodePri32Cancel );
00146 
00147         return 0;
00148 }
00149 
00150 
00151 int dgl_write_V2( dglGraph_s * pgraph , int fd )
00152 {
00153         long nret , cnt , tot;  
00154 
00155         pgraph->iErrno = 0;
00156 
00157         if ( write( fd , & pgraph->Version , 1 ) != 1 )
00158         {
00159                 pgraph->iErrno = DGL_ERR_Write;
00160                 return -pgraph->iErrno;
00161         }
00162 
00163         if ( write( fd , & pgraph->Endian , 1 ) != 1 )
00164         {
00165                 pgraph->iErrno = DGL_ERR_Write;
00166                 return -pgraph->iErrno;
00167         }
00168 
00169         if ( write( fd , & pgraph->NodeAttrSize  , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00170         {
00171                 pgraph->iErrno = DGL_ERR_Write;
00172                 return -pgraph->iErrno;
00173         }
00174 
00175         if ( write( fd , & pgraph->EdgeAttrSize  , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00176         {
00177                 pgraph->iErrno = DGL_ERR_Write;
00178                 return -pgraph->iErrno;
00179         }
00180 
00181         for ( cnt = 0 ; cnt < 16 ; cnt ++ )
00182         {
00183                 if ( write( fd , & pgraph->aOpaqueSet[ cnt ] , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00184                 {
00185                         pgraph->iErrno = DGL_ERR_Write;
00186                         return -pgraph->iErrno;
00187                 }
00188         }
00189 
00190         if ( write( fd , & pgraph->nnCost , sizeof( dglInt64_t ) ) != sizeof( dglInt64_t ) )
00191         {
00192                 pgraph->iErrno = DGL_ERR_Write;
00193                 return -pgraph->iErrno;
00194         }
00195 
00196         if ( write( fd , & pgraph->cNode , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00197         {
00198                 pgraph->iErrno = DGL_ERR_Write;
00199                 return -pgraph->iErrno;
00200         }
00201 
00202         if ( write( fd , & pgraph->cHead , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00203         {
00204                 pgraph->iErrno = DGL_ERR_Write;
00205                 return -pgraph->iErrno;
00206         }
00207 
00208         if ( write( fd , & pgraph->cTail , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00209         {
00210                 pgraph->iErrno = DGL_ERR_Write;
00211                 return -pgraph->iErrno;
00212         }
00213 
00214         if ( write( fd , & pgraph->cAlone , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00215         {
00216                 pgraph->iErrno = DGL_ERR_Write;
00217                 return -pgraph->iErrno;
00218         }
00219 
00220         if ( write( fd , & pgraph->cEdge , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00221         {
00222                 pgraph->iErrno = DGL_ERR_Write;
00223                 return -pgraph->iErrno;
00224         }
00225 
00226         if ( write( fd , & pgraph->iNodeBuffer , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00227         {
00228                 pgraph->iErrno = DGL_ERR_Write;
00229                 return -pgraph->iErrno;
00230         }
00231 
00232         if ( write( fd , & pgraph->iEdgeBuffer , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00233         {
00234                 pgraph->iErrno = DGL_ERR_Write;
00235                 return -pgraph->iErrno;
00236         }
00237 
00238         for( tot = 0 , cnt = pgraph->iNodeBuffer ; tot < cnt ; tot += nret )
00239         {
00240                 if ( (nret = write( fd , & pgraph->pNodeBuffer[ tot ] , cnt - tot )) <= 0 )
00241                 {
00242                         pgraph->iErrno = DGL_ERR_Write;
00243                         return -pgraph->iErrno;
00244                 }
00245         }
00246 
00247         for( tot = 0 , cnt = pgraph->iEdgeBuffer ; tot < cnt ; tot += nret )
00248         {
00249                 if ( (nret = write( fd , & pgraph->pEdgeBuffer[ tot ] , cnt - tot )) <= 0 )
00250                 {
00251                         pgraph->iErrno = DGL_ERR_Write;
00252                         return -pgraph->iErrno;
00253                 }
00254         }
00255 
00256         return 0;
00257 }
00258 
00259 
00260 int dgl_read_V2( dglGraph_s * pgraph , int fd , int version )
00261 {
00262         long            nret , cnt , tot;       
00263         dglByte_t       Endian;
00264         dglInt32_t      NodeAttrSize , EdgeAttrSize;
00265         int                     i, cn, fSwap;
00266         dglInt32_t *    pn;
00267 
00268         if ( read( fd , & Endian , 1 ) != 1 )
00269         {
00270                 pgraph->iErrno = DGL_ERR_Read;
00271                 return -pgraph->iErrno;
00272         }
00273 
00274         fSwap = 0;
00275 #ifdef DGL_ENDIAN_BIG
00276         if ( Endian == DGL_ENDIAN_LITTLE ) fSwap = 1;
00277 #else
00278         if ( Endian == DGL_ENDIAN_BIG    ) fSwap = 1;
00279 #endif
00280 
00281         if ( read( fd , & NodeAttrSize , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00282         {
00283                 pgraph->iErrno = DGL_ERR_Read;
00284                 return -pgraph->iErrno;
00285         }
00286         if ( fSwap ) dgl_swapInt32Bytes( & NodeAttrSize );
00287 
00288         if ( read( fd , & EdgeAttrSize , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00289         {
00290                 pgraph->iErrno = DGL_ERR_Read;
00291                 return -pgraph->iErrno;
00292         }
00293         if ( fSwap ) dgl_swapInt32Bytes( & EdgeAttrSize );
00294 
00295         if ( (nret = dglInitialize( pgraph, version, NodeAttrSize, EdgeAttrSize, NULL )) < 0 )
00296         {
00297                 return nret;
00298         }
00299 
00300         for ( cnt = 0 ; cnt < 16 ; cnt ++ )
00301         {
00302                 if ( (nret=read( fd , & pgraph->aOpaqueSet[ cnt ] , sizeof( dglInt32_t ) )) != sizeof( dglInt32_t ) )
00303                 {
00304                         pgraph->iErrno = DGL_ERR_Read;
00305                         return -pgraph->iErrno;
00306                 }
00307                 if ( fSwap ) dgl_swapInt32Bytes( & pgraph->aOpaqueSet[ cnt ] );
00308         }
00309 
00310         if ( read( fd , & pgraph->nnCost , sizeof( dglInt64_t ) ) != sizeof( dglInt64_t ) )
00311         {
00312                 pgraph->iErrno = DGL_ERR_Read;
00313                 return -pgraph->iErrno;
00314         }
00315         if ( fSwap ) dgl_swapInt64Bytes( & pgraph->nnCost );
00316 
00317         if ( read( fd , & pgraph->cNode , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00318         {
00319                 pgraph->iErrno = DGL_ERR_Read;
00320                 return -pgraph->iErrno;
00321         }
00322         if ( fSwap ) dgl_swapInt32Bytes( & pgraph->cNode );
00323 
00324         if ( read( fd , & pgraph->cHead , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00325         {
00326                 pgraph->iErrno = DGL_ERR_Read;
00327                 return -pgraph->iErrno;
00328         }
00329         if ( fSwap ) dgl_swapInt32Bytes( & pgraph->cHead );
00330 
00331         if ( read( fd , & pgraph->cTail , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00332         {
00333                 pgraph->iErrno = DGL_ERR_Read;
00334                 return -pgraph->iErrno;
00335         }
00336         if ( fSwap ) dgl_swapInt32Bytes( & pgraph->cTail );
00337 
00338         if ( read( fd , & pgraph->cAlone , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00339         {
00340                 pgraph->iErrno = DGL_ERR_Read;
00341                 return -pgraph->iErrno;
00342         }
00343         if ( fSwap ) dgl_swapInt32Bytes( & pgraph->cAlone );
00344 
00345         if ( read( fd , & pgraph->cEdge , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00346         {
00347                 pgraph->iErrno = DGL_ERR_Read;
00348                 return -pgraph->iErrno;
00349         }
00350         if ( fSwap ) dgl_swapInt32Bytes( & pgraph->cEdge );
00351 
00352         if ( read( fd , & pgraph->iNodeBuffer , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00353         {
00354                 pgraph->iErrno = DGL_ERR_Read;
00355                 return -pgraph->iErrno;
00356         }
00357         if ( fSwap ) dgl_swapInt32Bytes( & pgraph->iNodeBuffer );
00358 
00359         if ( read( fd , & pgraph->iEdgeBuffer , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00360         {
00361                 pgraph->iErrno = DGL_ERR_Read;
00362                 return -pgraph->iErrno;
00363         }
00364         if ( fSwap ) dgl_swapInt32Bytes( & pgraph->iEdgeBuffer );
00365 
00366         if ( (pgraph->pNodeBuffer = malloc( pgraph->iNodeBuffer )) == NULL )
00367         {
00368                 pgraph->iErrno = DGL_ERR_MemoryExhausted;
00369                 return -pgraph->iErrno;
00370         }
00371 
00372         if ( (pgraph->pEdgeBuffer = malloc( pgraph->iEdgeBuffer )) == NULL )
00373         {
00374                 free( pgraph->pNodeBuffer );
00375                 pgraph->iErrno = DGL_ERR_MemoryExhausted;
00376                 return -pgraph->iErrno;
00377         }
00378 
00379         for( tot = 0 , cnt = pgraph->iNodeBuffer ; tot < cnt ; tot += nret )
00380         {
00381                 if ( (nret = read( fd , & pgraph->pNodeBuffer[ tot ] , cnt - tot )) <= 0 )
00382                 {
00383                         free( pgraph->pNodeBuffer );
00384                         free( pgraph->pEdgeBuffer );
00385                         pgraph->iErrno = DGL_ERR_Read;
00386                         return -pgraph->iErrno;
00387                 }
00388         }
00389         if ( fSwap ) {
00390                 pn = (dglInt32_t*) pgraph->pNodeBuffer;
00391                 cn = pgraph->iNodeBuffer / sizeof(dglInt32_t);
00392                 for ( i = 0 ; i < cn ; i ++ ) {
00393                         dgl_swapInt32Bytes( & pn[i] );
00394                 }
00395         }
00396 
00397         for( tot = 0 , cnt = pgraph->iEdgeBuffer ; tot < cnt ; tot += nret )
00398         {
00399                 if ( (nret = read( fd , & pgraph->pEdgeBuffer[ tot ] , cnt - tot )) <= 0 )
00400                 {
00401                         free( pgraph->pNodeBuffer );
00402                         free( pgraph->pEdgeBuffer );
00403                         pgraph->iErrno = DGL_ERR_Read;
00404                         return -pgraph->iErrno;
00405                 }
00406         }
00407         if ( fSwap ) {
00408                 pn = (dglInt32_t*) pgraph->pEdgeBuffer;
00409                 cn = pgraph->iEdgeBuffer / sizeof(dglInt32_t);
00410                 for ( i = 0 ; i < cn ; i ++ ) {
00411                         dgl_swapInt32Bytes( & pn[i] );
00412                 }
00413         }
00414 
00415         pgraph->Flags |= 0x1; /* flat-state */
00416         return 0;
00417 }

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