GRASS Programmer's Manual 6.4.1(2011)
|
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 }