cr_large_graph.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  * Source best viewed with tabstop=4
00021  */
00022 
00023 #include <stdio.h>
00024 #include <sys/types.h>
00025 #include <sys/stat.h>
00026 #include <unistd.h>
00027 #include <stdlib.h>
00028 #include <fcntl.h>
00029 #include <time.h>
00030 #include <errno.h>
00031 #include <math.h>
00032 
00033 #include "../type.h"
00034 #include "../graph.h"
00035 
00036 #include "opt.h"
00037 
00038 extern int errno;
00039 
00040 
00041 #define NROWS 600
00042 #define NCOLS 100
00043 #define FACTOR 10000
00044 #define BIDIRECTIONAL 1
00045 
00046 /*
00047 #define NROWS 600
00048 #define NCOLS 400
00049 #define FACTOR 10000
00050 #define BIDIRECTIONAL 1
00051 */
00052 
00053 
00054 static int _add_edge(   dglGraph_s * pgraph ,
00055                                                 dglInt32_t from , dglInt32_t to , dglInt32_t cost , dglInt32_t arc ,
00056                                                 char chDirection ,
00057                                                 int fLast )
00058 {
00059         int nret;
00060 
00061         dglInt32_t xyz_from[3] , xyz_to[3] , direction[2];
00062 
00063         if ( ! fLast ) {
00064                 /* setup node attributes with the x y coords in the grid by
00065                    reversing the calculation done the main loop */
00066                 xyz_from[0] = from % NCOLS;
00067                 xyz_from[1] = from / NCOLS;
00068                 xyz_from[2] = 0;
00069 
00070                 xyz_to[0] = to % NCOLS;
00071                 xyz_to[1] = to / NCOLS;
00072                 xyz_to[2] = 0;
00073 
00074                 /* chDirection says if the edge direction is 'u'=toward the top 'b'=the bot. 'l'=the left 'r'=the right
00075                    'o'=toward right-bottom 'O'=toward top-left * Account for this in the edge attributes */
00076                 direction[0] = (dglInt32_t)chDirection;
00077                 direction[1] = 0;
00078 
00079 
00080                 nret = dglAddEdgeX( pgraph , from , to , cost , arc , xyz_from , xyz_to , direction , 0 );
00081                 if ( nret < 0 ) {
00082                         fprintf( stderr, "dglAddEdge error: %s\n", dglStrerror( pgraph ) );
00083                         return 1;
00084                 }
00085         }
00086 
00087         if ( (arc % 1024) == 0 || fLast ) {
00088 #ifndef DGL_STATS
00089                 printf( "add arc %07ld - from %07ld - to %07ld - cost %07ld\r",
00090                                 arc , from , to , cost );
00091 #else
00092                 printf( "add arc %07ld - from %07ld - to %07ld - cost %07ld . Clock: tot %09ld nt %09ld o %09ld\r" ,
00093                                 arc , from , to , cost ,
00094                                 pgraph->clkAddEdge / pgraph->cAddEdge,
00095                                 pgraph->clkNodeTree / pgraph->cAddEdge,
00096                                 (pgraph->clkAddEdge - pgraph->clkNodeTree) / pgraph->cAddEdge
00097                                 );
00098 #endif
00099                 fflush( stdout );
00100         }
00101         return 0;
00102 }
00103 
00104 int main( int argc , char ** argv )
00105 {
00106         dglGraph_s      graph;
00107         int                             nret , fd;
00108         int                             version;
00109 
00110         int                             irow , icol , itrow , itcol;
00111         int                             irowsave , icolsave;
00112 
00113         dglInt32_t              from, to, arc, cost;
00114 
00115         /* node attributes */
00116         dglInt32_t              xyz[3];
00117 
00118         /* edge attributes */
00119         dglInt32_t              direction[2];
00120 
00121         dglInt32_t              opaqueset[ 16 ] = {
00122                 FACTOR, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
00123         };
00124 
00125         /* program options
00126          */
00127         char    *       pszFileout;
00128         Boolean         fInterlaced;
00129         char    *       pszVersion;
00130  
00131         GNO_BEGIN/* short   long                default     variable        help */
00132         GNO_OPTION( "g",        "graph",                NULL ,          & pszFileout ,  "Output Graph file" )
00133         GNO_SWITCH( "i",        "interlaced",   False ,         & fInterlaced , "Avoid node ids sorting at insertion - default False" )
00134         GNO_OPTION( "v",        "version",              "1" ,           & pszVersion ,  "Output Graph Version {1,2,3} - default 1" )
00135         GNO_END
00136  
00137 
00138         if ( GNO_PARSE( argc , argv ) < 0 )
00139         {
00140                 return 1;
00141         }
00142 
00143         if ( pszFileout == NULL )
00144         {
00145                 GNO_HELP( "Incomplete parameters" );
00146                 return 1;
00147         }
00148 
00149         /*
00150          * options parsed
00151          */
00152         version = atoi(pszVersion);
00153 
00154         /*
00155          * new API call
00156          */
00157         printf( "graph initialize..." ); fflush(stdout);
00158         dglInitialize (
00159                                         & graph ,                       /* graph context to initialize */
00160                                         version ,
00161                                         sizeof(xyz) ,           /* node attributes size */
00162                                         sizeof(direction) ,     /* edge attributes size */
00163                                         opaqueset                       /* opaque graph parameters */
00164                                         );
00165         printf( "done.\n" );
00166 
00167 #if 0
00168         dglSet_Options( & graph, DGL_GO_EdgePrioritize_COST );
00169 #endif
00170 
00171         from = 0;
00172         to = 0;
00173         arc = 0;
00174 
00175 
00176         printf( "add horizontal and vertical edges...\n" );
00177         for ( irow = 0 ; irow < NROWS ; irow ++ ) {
00178 
00179                 if ( fInterlaced == True ) {
00180                         irowsave = irow;
00181                         if ( irow % 2 ) irow = NROWS - irow;
00182                 }
00183 
00184                 for ( icol = 0 ; icol < NCOLS ; icol ++ ) {
00185 
00186                         if ( fInterlaced == True ) {
00187                                         icolsave = icol;
00188                                         if ( icol % 2 ) icol = NCOLS - icol;
00189                         }
00190 
00191                         itcol = icol + 1;
00192                         itrow = irow + 1;
00193 
00194                         if ( itcol < NCOLS ) {
00195                                 from = irow * NCOLS + icol;
00196                                 to = irow * NCOLS + itcol;
00197                                 cost = FACTOR;
00198                                 arc ++;
00199                                 if ( _add_edge( &graph, from , to , cost , arc , 'r' , 0 ) ) {
00200                                         return 1;
00201                                 }
00202 #ifdef BIDIRECTIONAL
00203                                 arc ++;
00204                                 if ( _add_edge( &graph, to , from , cost , arc , 'l' , 0 ) ) {
00205                                         return 1;
00206                                 }
00207 #endif
00208                         }
00209 
00210                         if ( itrow < NROWS ) {
00211                                 from = irow * NCOLS + icol;
00212                                 to = itrow * NCOLS + icol;
00213                                 cost = FACTOR;
00214                                 arc ++;
00215                                 if ( _add_edge( &graph, from , to , cost , arc , 'b' , 0 ) ) {
00216                                         return 1;
00217                                 }
00218 #ifdef BIDIRECTIONAL
00219                                 arc ++;
00220                                 if ( _add_edge( &graph, to , from , cost , arc , 't' , 0 ) ) {
00221                                         return 1;
00222                                 }
00223 #endif
00224                         }
00225 
00226                         if ( fInterlaced == True ) icol = icolsave;
00227                 }
00228 
00229                 if ( fInterlaced == True ) irow = irowsave;
00230         }
00231         _add_edge( &graph, to  , from , cost , arc , 'x' , 1 );
00232 
00233 
00234 #if 1
00235         printf( "\nadd oblique edges...\n" );
00236         for ( irow = 0 ; irow < NROWS ; irow ++ ) {
00237                 for ( icol = 0 ; icol < NCOLS ; icol ++ ) {
00238                         itcol = icol + 1;
00239                         itrow = irow + 1;
00240 
00241                         if ( itrow < NROWS && itcol < NCOLS ) {
00242                                 from = irow * NCOLS + icol;
00243                                 to = itrow * NCOLS + itcol;
00244                                 cost = (dglInt32_t)(sqrt(2.0) * (double)FACTOR);
00245                                 arc ++;
00246                                 if ( _add_edge( &graph, from , to , cost , arc , 'o' , 0 ) ) {
00247                                         return 1;
00248                                 }
00249 #ifdef BIDIRECTIONAL
00250                                 arc ++;
00251                                 if ( _add_edge( &graph, to  , from , cost , arc , 'O' , 0 ) ) {
00252                                         return 1;
00253                                 }
00254 #endif
00255                         }
00256                 }
00257         }
00258         _add_edge( &graph, to  , from , cost , arc , 'x' , 1 );
00259         printf( "\ndone.\n" );
00260 #endif
00261 
00262 
00263 #if 0
00264         {
00265                 dglEdgeTraverser_s t;
00266                 dglInt32_t * pEdge;
00267                 nret = dglEdge_T_Initialize(& graph, & t, dglGet_EdgePrioritizer(& graph));
00268                 /*nret = dglEdge_T_Initialize(& graph, & t, NULL);*/
00269                 if ( nret < 0 ) {
00270                         fprintf( stderr , "\ndglEdge_T_Initialize error: %s\n" , dglStrerror(& graph) );
00271                         return 1;
00272                 }
00273                 for( pEdge = dglEdge_T_First(& t); pEdge; pEdge = dglEdge_T_Next(& t) ) {
00274                         printf( "edge: id=%ld cost=%ld\n",
00275                                                 dglEdgeGet_Id(&graph, pEdge),
00276                                                 dglEdgeGet_Cost(&graph, pEdge) );
00277                 }
00278                 dglEdge_T_Release(& t);
00279         }
00280 #endif
00281 
00282 
00283         printf( "graph flattening..." ); fflush(stdout);
00284         nret = dglFlatten( & graph );
00285         if ( nret < 0 )
00286         {
00287                 fprintf( stderr , "\ndglFlatten error: %s\n" , dglStrerror( & graph ) );
00288                 return 1;
00289         }
00290         printf( "done.\n" );
00291 
00292 
00293         printf( "graph write..." ); fflush(stdout);
00294         if ( (fd = open( pszFileout , O_WRONLY | O_CREAT | O_TRUNC, 0666 )) < 0 )
00295         {
00296                 perror( "open" ); return 1;
00297         }
00298         nret = dglWrite( & graph , fd );
00299         if ( nret < 0 )
00300         {
00301                 fprintf( stderr , "\ndglWrite error: %s\n" , dglStrerror( & graph ) );
00302                 return 1;
00303         }
00304         close( fd );
00305         printf( "done.\n" );
00306 
00307 
00308         printf( "graph release..." ); fflush(stdout);
00309         dglRelease( & graph );
00310         printf( "program finished.\n" );
00311         return 0;
00312 }

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