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,
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
00064
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
00074
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
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,
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
00149
00150 version = atoi(pszVersion);
00151
00152
00153
00154
00155 printf("graph initialize...");
00156 fflush(stdout);
00157 dglInitialize(&graph,
00158 version, sizeof(xyz),
00159 sizeof(direction),
00160 opaqueset
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
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 }