GRASS Programmer's Manual 6.4.1(2011)
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,
00056                      dglInt32_t arc, char chDirection, int fLast)
00057 {
00058     int nret;
00059 
00060     dglInt32_t xyz_from[3], xyz_to[3], direction[2];
00061 
00062     if (!fLast) {
00063         /* setup node attributes with the x y coords in the grid by
00064            reversing the calculation done the main loop */
00065         xyz_from[0] = from % NCOLS;
00066         xyz_from[1] = from / NCOLS;
00067         xyz_from[2] = 0;
00068 
00069         xyz_to[0] = to % NCOLS;
00070         xyz_to[1] = to / NCOLS;
00071         xyz_to[2] = 0;
00072 
00073         /* chDirection says if the edge direction is 'u'=toward the top 'b'=the bot. 'l'=the left 'r'=the right
00074            'o'=toward right-bottom 'O'=toward top-left * Account for this in the edge attributes */
00075         direction[0] = (dglInt32_t) chDirection;
00076         direction[1] = 0;
00077 
00078 
00079         nret =
00080             dglAddEdgeX(pgraph, from, to, cost, arc, xyz_from, xyz_to,
00081                         direction, 0);
00082         if (nret < 0) {
00083             fprintf(stderr, "dglAddEdge error: %s\n", dglStrerror(pgraph));
00084             return 1;
00085         }
00086     }
00087 
00088     if ((arc % 1024) == 0 || fLast) {
00089 #ifndef DGL_STATS
00090         printf("add arc %07ld - from %07ld - to %07ld - cost %07ld\r",
00091                arc, from, to, cost);
00092 #else
00093         printf
00094             ("add arc %07ld - from %07ld - to %07ld - cost %07ld . Clock: tot %09ld nt %09ld o %09ld\r",
00095              arc, from, to, cost, pgraph->clkAddEdge / pgraph->cAddEdge,
00096              pgraph->clkNodeTree / pgraph->cAddEdge,
00097              (pgraph->clkAddEdge - pgraph->clkNodeTree) / pgraph->cAddEdge);
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,
00134                    "Avoid node ids sorting at insertion - default False")
00135         GNO_OPTION("v", "version", "1", &pszVersion,
00136                    "Output Graph Version {1,2,3} - default 1")
00137     GNO_END if (GNO_PARSE(argc, argv) < 0)
00138     {
00139         return 1;
00140     }
00141 
00142     if (pszFileout == NULL) {
00143         GNO_HELP("Incomplete parameters");
00144         return 1;
00145     }
00146 
00147     /*
00148      * options parsed
00149      */
00150     version = atoi(pszVersion);
00151 
00152     /*
00153      * new API call
00154      */
00155     printf("graph initialize...");
00156     fflush(stdout);
00157     dglInitialize(&graph,       /* graph context to initialize */
00158                   version, sizeof(xyz), /* node attributes size */
00159                   sizeof(direction),    /* edge attributes size */
00160                   opaqueset     /* opaque graph parameters */
00161         );
00162     printf("done.\n");
00163 
00164 #if 0
00165     dglSet_Options(&graph, DGL_GO_EdgePrioritize_COST);
00166 #endif
00167 
00168     from = 0;
00169     to = 0;
00170     arc = 0;
00171 
00172 
00173     printf("add horizontal and vertical edges...\n");
00174     for (irow = 0; irow < NROWS; irow++) {
00175 
00176         if (fInterlaced == True) {
00177             irowsave = irow;
00178             if (irow % 2)
00179                 irow = NROWS - irow;
00180         }
00181 
00182         for (icol = 0; icol < NCOLS; icol++) {
00183 
00184             if (fInterlaced == True) {
00185                 icolsave = icol;
00186                 if (icol % 2)
00187                     icol = NCOLS - icol;
00188             }
00189 
00190             itcol = icol + 1;
00191             itrow = irow + 1;
00192 
00193             if (itcol < NCOLS) {
00194                 from = irow * NCOLS + icol;
00195                 to = irow * NCOLS + itcol;
00196                 cost = FACTOR;
00197                 arc++;
00198                 if (_add_edge(&graph, from, to, cost, arc, 'r', 0)) {
00199                     return 1;
00200                 }
00201 #ifdef BIDIRECTIONAL
00202                 arc++;
00203                 if (_add_edge(&graph, to, from, cost, arc, 'l', 0)) {
00204                     return 1;
00205                 }
00206 #endif
00207             }
00208 
00209             if (itrow < NROWS) {
00210                 from = irow * NCOLS + icol;
00211                 to = itrow * NCOLS + icol;
00212                 cost = FACTOR;
00213                 arc++;
00214                 if (_add_edge(&graph, from, to, cost, arc, 'b', 0)) {
00215                     return 1;
00216                 }
00217 #ifdef BIDIRECTIONAL
00218                 arc++;
00219                 if (_add_edge(&graph, to, from, cost, arc, 't', 0)) {
00220                     return 1;
00221                 }
00222 #endif
00223             }
00224 
00225             if (fInterlaced == True)
00226                 icol = icolsave;
00227         }
00228 
00229         if (fInterlaced == True)
00230             irow = irowsave;
00231     }
00232     _add_edge(&graph, to, from, cost, arc, 'x', 1);
00233 
00234 
00235 #if 1
00236     printf("\nadd oblique edges...\n");
00237     for (irow = 0; irow < NROWS; irow++) {
00238         for (icol = 0; icol < NCOLS; icol++) {
00239             itcol = icol + 1;
00240             itrow = irow + 1;
00241 
00242             if (itrow < NROWS && itcol < NCOLS) {
00243                 from = irow * NCOLS + icol;
00244                 to = itrow * NCOLS + itcol;
00245                 cost = (dglInt32_t) (sqrt(2.0) * (double)FACTOR);
00246                 arc++;
00247                 if (_add_edge(&graph, from, to, cost, arc, 'o', 0)) {
00248                     return 1;
00249                 }
00250 #ifdef BIDIRECTIONAL
00251                 arc++;
00252                 if (_add_edge(&graph, to, from, cost, arc, 'O', 0)) {
00253                     return 1;
00254                 }
00255 #endif
00256             }
00257         }
00258     }
00259     _add_edge(&graph, to, from, cost, arc, 'x', 1);
00260     printf("\ndone.\n");
00261 #endif
00262 
00263 
00264 #if 0
00265     {
00266         dglEdgeTraverser_s t;
00267         dglInt32_t *pEdge;
00268 
00269         nret =
00270             dglEdge_T_Initialize(&graph, &t, dglGet_EdgePrioritizer(&graph));
00271         /*nret = dglEdge_T_Initialize(& graph, & t, NULL); */
00272         if (nret < 0) {
00273             fprintf(stderr, "\ndglEdge_T_Initialize error: %s\n",
00274                     dglStrerror(&graph));
00275             return 1;
00276         }
00277         for (pEdge = dglEdge_T_First(&t); pEdge; pEdge = dglEdge_T_Next(&t)) {
00278             printf("edge: id=%ld cost=%ld\n",
00279                    dglEdgeGet_Id(&graph, pEdge),
00280                    dglEdgeGet_Cost(&graph, pEdge));
00281         }
00282         dglEdge_T_Release(&t);
00283     }
00284 #endif
00285 
00286 
00287     printf("graph flattening...");
00288     fflush(stdout);
00289     nret = dglFlatten(&graph);
00290     if (nret < 0) {
00291         fprintf(stderr, "\ndglFlatten error: %s\n", dglStrerror(&graph));
00292         return 1;
00293     }
00294     printf("done.\n");
00295 
00296 
00297     printf("graph write...");
00298     fflush(stdout);
00299     if ((fd = open(pszFileout, O_WRONLY | O_CREAT | O_TRUNC, 0666)) < 0) {
00300         perror("open");
00301         return 1;
00302     }
00303     nret = dglWrite(&graph, fd);
00304     if (nret < 0) {
00305         fprintf(stderr, "\ndglWrite error: %s\n", dglStrerror(&graph));
00306         return 1;
00307     }
00308     close(fd);
00309     printf("done.\n");
00310 
00311 
00312     printf("graph release...");
00313     fflush(stdout);
00314     dglRelease(&graph);
00315     printf("program finished.\n");
00316     return 0;
00317 }
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Defines