graph_v1.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_v1.h"
00036 #include "helpers.h"
00037 
00038 
00039 /* Template expansion
00040  */
00041 #include "v1-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 "v1-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 "v1-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_V1     (
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_V1_FLAT(pgraph,ppReport,pDistance,nStart,nDestination,fnClip,pvClipArg,pCache);
00080         }
00081         else {
00082                 return dgl_dijkstra_V1_TREE(pgraph,ppReport,pDistance,nStart,nDestination,fnClip,pvClipArg,pCache);
00083         }
00084 }
00085 
00086 
00087 int dgl_depthfirst_spanning_V1(
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_V1_FLAT(pgraphIn,pgraphOut,nVertex,pvVisited,fnClip,pvClipArg);
00098         }
00099         else {
00100                 return dgl_span_depthfirst_spanning_V1_TREE(pgraphIn,pgraphOut,nVertex,pvVisited,fnClip,pvClipArg);
00101         }
00102 }
00103 
00104 int dgl_minimum_spanning_V1(
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_V1_FLAT(pgraphIn,pgraphOut,nVertex,fnClip,pvClipArg);
00114         }
00115         else {
00116                 return dgl_span_minimum_spanning_V1_TREE(pgraphIn,pgraphOut,nVertex,fnClip,pvClipArg);
00117         }
00118 }
00119 
00120 
00121 int dgl_initialize_V1( dglGraph_s * pgraph )
00122 {
00123         if ( pgraph->pNodeTree == NULL ) pgraph->pNodeTree = avl_create( dglTreeNodeCompare, NULL, dglTreeGetAllocator() );
00124         if ( pgraph->pNodeTree == NULL ) {
00125                 pgraph->iErrno = DGL_ERR_MemoryExhausted;
00126                 return -pgraph->iErrno;
00127         }
00128         pgraph->pEdgeTree = NULL;
00129         return 0;
00130 }
00131 
00132 int dgl_release_V1( dglGraph_s * pgraph )
00133 {
00134         pgraph->iErrno = 0;
00135 
00136         if ( pgraph->pNodeTree ) avl_destroy( pgraph->pNodeTree, dglTreeNodeCancel );
00137         if ( pgraph->pEdgeTree ) avl_destroy( pgraph->pEdgeTree, dglTreeEdgeCancel );
00138         if ( pgraph->pNodeBuffer ) free( pgraph->pNodeBuffer );
00139         if ( pgraph->pEdgeBuffer ) free( pgraph->pEdgeBuffer );
00140         if ( pgraph->edgePrioritizer.pvAVL ) avl_destroy( pgraph->edgePrioritizer.pvAVL, dglTreeEdgePri32Cancel );
00141         if ( pgraph->nodePrioritizer.pvAVL ) avl_destroy( pgraph->nodePrioritizer.pvAVL, dglTreeNodePri32Cancel );
00142 
00143         return 0;
00144 }
00145 
00146 
00147 int dgl_write_V1( dglGraph_s * pgraph , int fd )
00148 {
00149         long nret , cnt , tot;  
00150 
00151         pgraph->iErrno = 0;
00152 
00153         if ( write( fd , & pgraph->Version , 1 ) != 1 )
00154         {
00155                 pgraph->iErrno = DGL_ERR_Write;
00156                 return -pgraph->iErrno;
00157         }
00158 
00159         if ( write( fd , & pgraph->Endian , 1 ) != 1 )
00160         {
00161                 pgraph->iErrno = DGL_ERR_Write;
00162                 return -pgraph->iErrno;
00163         }
00164 
00165         if ( write( fd , & pgraph->NodeAttrSize  , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00166         {
00167                 pgraph->iErrno = DGL_ERR_Write;
00168                 return -pgraph->iErrno;
00169         }
00170 
00171         if ( write( fd , & pgraph->EdgeAttrSize  , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00172         {
00173                 pgraph->iErrno = DGL_ERR_Write;
00174                 return -pgraph->iErrno;
00175         }
00176 
00177         for ( cnt = 0 ; cnt < 16 ; cnt ++ )
00178         {
00179                 if ( write( fd , & pgraph->aOpaqueSet[ cnt ] , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00180                 {
00181                         pgraph->iErrno = DGL_ERR_Write;
00182                         return -pgraph->iErrno;
00183                 }
00184         }
00185 
00186         if ( write( fd , & pgraph->nnCost , sizeof( dglInt64_t ) ) != sizeof( dglInt64_t ) )
00187         {
00188                 pgraph->iErrno = DGL_ERR_Write;
00189                 return -pgraph->iErrno;
00190         }
00191 
00192         if ( write( fd , & pgraph->cNode , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00193         {
00194                 pgraph->iErrno = DGL_ERR_Write;
00195                 return -pgraph->iErrno;
00196         }
00197 
00198         if ( write( fd , & pgraph->cHead , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00199         {
00200                 pgraph->iErrno = DGL_ERR_Write;
00201                 return -pgraph->iErrno;
00202         }
00203 
00204         if ( write( fd , & pgraph->cTail , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00205         {
00206                 pgraph->iErrno = DGL_ERR_Write;
00207                 return -pgraph->iErrno;
00208         }
00209 
00210         if ( write( fd , & pgraph->cAlone , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00211         {
00212                 pgraph->iErrno = DGL_ERR_Write;
00213                 return -pgraph->iErrno;
00214         }
00215 
00216         if ( write( fd , & pgraph->cEdge , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00217         {
00218                 pgraph->iErrno = DGL_ERR_Write;
00219                 return -pgraph->iErrno;
00220         }
00221 
00222         if ( write( fd , & pgraph->iNodeBuffer , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00223         {
00224                 pgraph->iErrno = DGL_ERR_Write;
00225                 return -pgraph->iErrno;
00226         }
00227 
00228         if ( write( fd , & pgraph->iEdgeBuffer , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00229         {
00230                 pgraph->iErrno = DGL_ERR_Write;
00231                 return -pgraph->iErrno;
00232         }
00233 
00234         for( tot = 0 , cnt = pgraph->iNodeBuffer ; tot < cnt ; tot += nret )
00235         {
00236                 if ( (nret = write( fd , & pgraph->pNodeBuffer[ tot ] , cnt - tot )) <= 0 )
00237                 {
00238                         pgraph->iErrno = DGL_ERR_Write;
00239                         return -pgraph->iErrno;
00240                 }
00241         }
00242 
00243         for( tot = 0 , cnt = pgraph->iEdgeBuffer ; tot < cnt ; tot += nret )
00244         {
00245                 if ( (nret = write( fd , & pgraph->pEdgeBuffer[ tot ] , cnt - tot )) <= 0 )
00246                 {
00247                         pgraph->iErrno = DGL_ERR_Write;
00248                         return -pgraph->iErrno;
00249                 }
00250         }
00251 
00252         return 0;
00253 }
00254 
00255 
00256 int dgl_read_V1( dglGraph_s * pgraph , int fd )
00257 {
00258         long            nret , cnt , tot;       
00259         dglByte_t       Endian;
00260         dglInt32_t      NodeAttrSize , EdgeAttrSize;
00261         int                     i, cn, fSwap;
00262         dglInt32_t *    pn;
00263 
00264         if ( read( fd , & Endian , 1 ) != 1 )
00265         {
00266                 pgraph->iErrno = DGL_ERR_Read;
00267                 return -pgraph->iErrno;
00268         }
00269 
00270         fSwap = 0;
00271 #ifdef DGL_ENDIAN_BIG
00272         if ( Endian == DGL_ENDIAN_LITTLE ) fSwap = 1;
00273 #else
00274         if ( Endian == DGL_ENDIAN_BIG    ) fSwap = 1;
00275 #endif
00276 
00277         if ( read( fd , & NodeAttrSize , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00278         {
00279                 pgraph->iErrno = DGL_ERR_Read;
00280                 return -pgraph->iErrno;
00281         }
00282         if ( fSwap ) dgl_swapInt32Bytes( & NodeAttrSize );
00283 
00284         if ( read( fd , & EdgeAttrSize , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00285         {
00286                 pgraph->iErrno = DGL_ERR_Read;
00287                 return -pgraph->iErrno;
00288         }
00289         if ( fSwap ) dgl_swapInt32Bytes( & EdgeAttrSize );
00290 
00291         if ( (nret = dglInitialize( pgraph, 1, NodeAttrSize, EdgeAttrSize, NULL )) < 0 )
00292         {
00293                 return nret;
00294         }
00295 
00296         for ( cnt = 0 ; cnt < 16 ; cnt ++ )
00297         {
00298                 if ( (nret=read( fd , & pgraph->aOpaqueSet[ cnt ] , sizeof( dglInt32_t ) )) != sizeof( dglInt32_t ) )
00299                 {
00300                         pgraph->iErrno = DGL_ERR_Read;
00301                         return -pgraph->iErrno;
00302                 }
00303                 if ( fSwap ) dgl_swapInt32Bytes( & pgraph->aOpaqueSet[ cnt ] );
00304         }
00305 
00306         if ( read( fd , & pgraph->nnCost , sizeof( dglInt64_t ) ) != sizeof( dglInt64_t ) )
00307         {
00308                 pgraph->iErrno = DGL_ERR_Read;
00309                 return -pgraph->iErrno;
00310         }
00311         if ( fSwap ) dgl_swapInt64Bytes( & pgraph->nnCost );
00312 
00313         if ( read( fd , & pgraph->cNode , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00314         {
00315                 pgraph->iErrno = DGL_ERR_Read;
00316                 return -pgraph->iErrno;
00317         }
00318         if ( fSwap ) dgl_swapInt32Bytes( & pgraph->cNode );
00319 
00320         if ( read( fd , & pgraph->cHead , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00321         {
00322                 pgraph->iErrno = DGL_ERR_Read;
00323                 return -pgraph->iErrno;
00324         }
00325         if ( fSwap ) dgl_swapInt32Bytes( & pgraph->cHead );
00326 
00327         if ( read( fd , & pgraph->cTail , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00328         {
00329                 pgraph->iErrno = DGL_ERR_Read;
00330                 return -pgraph->iErrno;
00331         }
00332         if ( fSwap ) dgl_swapInt32Bytes( & pgraph->cTail );
00333 
00334         if ( read( fd , & pgraph->cAlone , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00335         {
00336                 pgraph->iErrno = DGL_ERR_Read;
00337                 return -pgraph->iErrno;
00338         }
00339         if ( fSwap ) dgl_swapInt32Bytes( & pgraph->cAlone );
00340 
00341         if ( read( fd , & pgraph->cEdge , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00342         {
00343                 pgraph->iErrno = DGL_ERR_Read;
00344                 return -pgraph->iErrno;
00345         }
00346         if ( fSwap ) dgl_swapInt32Bytes( & pgraph->cEdge );
00347 
00348         if ( read( fd , & pgraph->iNodeBuffer , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00349         {
00350                 pgraph->iErrno = DGL_ERR_Read;
00351                 return -pgraph->iErrno;
00352         }
00353         if ( fSwap ) dgl_swapInt32Bytes( & pgraph->iNodeBuffer );
00354 
00355         if ( read( fd , & pgraph->iEdgeBuffer , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00356         {
00357                 pgraph->iErrno = DGL_ERR_Read;
00358                 return -pgraph->iErrno;
00359         }
00360         if ( fSwap ) dgl_swapInt32Bytes( & pgraph->iEdgeBuffer );
00361 
00362         if ( (pgraph->pNodeBuffer = malloc( pgraph->iNodeBuffer )) == NULL )
00363         {
00364                 pgraph->iErrno = DGL_ERR_MemoryExhausted;
00365                 return -pgraph->iErrno;
00366         }
00367 
00368         if ( (pgraph->pEdgeBuffer = malloc( pgraph->iEdgeBuffer )) == NULL )
00369         {
00370                 free( pgraph->pNodeBuffer );
00371                 pgraph->iErrno = DGL_ERR_MemoryExhausted;
00372                 return -pgraph->iErrno;
00373         }
00374 
00375         for( tot = 0 , cnt = pgraph->iNodeBuffer ; tot < cnt ; tot += nret )
00376         {
00377                 if ( (nret = read( fd , & pgraph->pNodeBuffer[ tot ] , cnt - tot )) <= 0 )
00378                 {
00379                         free( pgraph->pNodeBuffer );
00380                         free( pgraph->pEdgeBuffer );
00381                         pgraph->iErrno = DGL_ERR_Read;
00382                         return -pgraph->iErrno;
00383                 }
00384         }
00385         if ( fSwap ) {
00386                 pn = (dglInt32_t*) pgraph->pNodeBuffer;
00387                 cn = pgraph->iNodeBuffer / sizeof(dglInt32_t);
00388                 for ( i = 0 ; i < cn ; i ++ ) {
00389                         dgl_swapInt32Bytes( & pn[i] );
00390                 }
00391         }
00392 
00393         for( tot = 0 , cnt = pgraph->iEdgeBuffer ; tot < cnt ; tot += nret )
00394         {
00395                 if ( (nret = read( fd , & pgraph->pEdgeBuffer[ tot ] , cnt - tot )) <= 0 )
00396                 {
00397                         free( pgraph->pNodeBuffer );
00398                         free( pgraph->pEdgeBuffer );
00399                         pgraph->iErrno = DGL_ERR_Read;
00400                         return -pgraph->iErrno;
00401                 }
00402         }
00403         if ( fSwap ) {
00404                 pn = (dglInt32_t*) pgraph->pEdgeBuffer;
00405                 cn = pgraph->iEdgeBuffer / sizeof(dglInt32_t);
00406                 for ( i = 0 ; i < cn ; i ++ ) {
00407                         dgl_swapInt32Bytes( & pn[i] );
00408                 }
00409         }
00410 
00411         pgraph->Flags |= 0x1; /* flat-state */
00412         return 0;
00413 }

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