00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
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
00048
00049
00050
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
00065
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
00075
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
00116 dglInt32_t xyz[3];
00117
00118
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
00126
00127 char * pszFileout;
00128 Boolean fInterlaced;
00129 char * pszVersion;
00130
00131 GNO_BEGIN
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
00151
00152 version = atoi(pszVersion);
00153
00154
00155
00156
00157 printf( "graph initialize..." ); fflush(stdout);
00158 dglInitialize (
00159 & graph ,
00160 version ,
00161 sizeof(xyz) ,
00162 sizeof(direction) ,
00163 opaqueset
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
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 }