GRASS Programmer's Manual  6.4.2(2012)
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
cr_large_graph.c
Go to the documentation of this file.
1 /* LIBDGL -- a Directed Graph Library implementation
2  * Copyright (C) 2002 Roberto Micarelli
3  *
4  * This program is free software; you can redistribute it and/or modify
5  * it under the terms of the GNU General Public License as published by
6  * the Free Software Foundation; either version 2 of the License, or
7  * (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software
16  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
17  */
18 
19 /*
20  * Source best viewed with tabstop=4
21  */
22 
23 #include <stdio.h>
24 #include <sys/types.h>
25 #include <sys/stat.h>
26 #include <unistd.h>
27 #include <stdlib.h>
28 #include <fcntl.h>
29 #include <time.h>
30 #include <errno.h>
31 #include <math.h>
32 
33 #include "../type.h"
34 #include "../graph.h"
35 
36 #include "opt.h"
37 
38 extern int errno;
39 
40 
41 #define NROWS 600
42 #define NCOLS 100
43 #define FACTOR 10000
44 #define BIDIRECTIONAL 1
45 
46 /*
47  #define NROWS 600
48  #define NCOLS 400
49  #define FACTOR 10000
50  #define BIDIRECTIONAL 1
51  */
52 
53 
54 static int _add_edge(dglGraph_s * pgraph,
55  dglInt32_t from, dglInt32_t to, dglInt32_t cost,
56  dglInt32_t arc, char chDirection, int fLast)
57 {
58  int nret;
59 
60  dglInt32_t xyz_from[3], xyz_to[3], direction[2];
61 
62  if (!fLast) {
63  /* setup node attributes with the x y coords in the grid by
64  reversing the calculation done the main loop */
65  xyz_from[0] = from % NCOLS;
66  xyz_from[1] = from / NCOLS;
67  xyz_from[2] = 0;
68 
69  xyz_to[0] = to % NCOLS;
70  xyz_to[1] = to / NCOLS;
71  xyz_to[2] = 0;
72 
73  /* chDirection says if the edge direction is 'u'=toward the top 'b'=the bot. 'l'=the left 'r'=the right
74  'o'=toward right-bottom 'O'=toward top-left * Account for this in the edge attributes */
75  direction[0] = (dglInt32_t) chDirection;
76  direction[1] = 0;
77 
78 
79  nret =
80  dglAddEdgeX(pgraph, from, to, cost, arc, xyz_from, xyz_to,
81  direction, 0);
82  if (nret < 0) {
83  fprintf(stderr, "dglAddEdge error: %s\n", dglStrerror(pgraph));
84  return 1;
85  }
86  }
87 
88  if ((arc % 1024) == 0 || fLast) {
89 #ifndef DGL_STATS
90  printf("add arc %07ld - from %07ld - to %07ld - cost %07ld\r",
91  arc, from, to, cost);
92 #else
93  printf
94  ("add arc %07ld - from %07ld - to %07ld - cost %07ld . Clock: tot %09ld nt %09ld o %09ld\r",
95  arc, from, to, cost, pgraph->clkAddEdge / pgraph->cAddEdge,
96  pgraph->clkNodeTree / pgraph->cAddEdge,
97  (pgraph->clkAddEdge - pgraph->clkNodeTree) / pgraph->cAddEdge);
98 #endif
99  fflush(stdout);
100  }
101  return 0;
102 }
103 
104 int main(int argc, char **argv)
105 {
106  dglGraph_s graph;
107  int nret, fd;
108  int version;
109 
110  int irow, icol, itrow, itcol;
111  int irowsave, icolsave;
112 
113  dglInt32_t from, to, arc, cost;
114 
115  /* node attributes */
116  dglInt32_t xyz[3];
117 
118  /* edge attributes */
119  dglInt32_t direction[2];
120 
121  dglInt32_t opaqueset[16] = {
122  FACTOR, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
123  };
124 
125  /* program options
126  */
127  char *pszFileout;
128  Boolean fInterlaced;
129  char *pszVersion;
130 
131  GNO_BEGIN /* short long default variable help */
132  GNO_OPTION("g", "graph", NULL, &pszFileout, "Output Graph file")
133  GNO_SWITCH("i", "interlaced", False, &fInterlaced,
134  "Avoid node ids sorting at insertion - default False")
135  GNO_OPTION("v", "version", "1", &pszVersion,
136  "Output Graph Version {1,2,3} - default 1")
137  GNO_END if (GNO_PARSE(argc, argv) < 0)
138  {
139  return 1;
140  }
141 
142  if (pszFileout == NULL) {
143  GNO_HELP("Incomplete parameters");
144  return 1;
145  }
146 
147  /*
148  * options parsed
149  */
150  version = atoi(pszVersion);
151 
152  /*
153  * new API call
154  */
155  printf("graph initialize...");
156  fflush(stdout);
157  dglInitialize(&graph, /* graph context to initialize */
158  version, sizeof(xyz), /* node attributes size */
159  sizeof(direction), /* edge attributes size */
160  opaqueset /* opaque graph parameters */
161  );
162  printf("done.\n");
163 
164 #if 0
166 #endif
167 
168  from = 0;
169  to = 0;
170  arc = 0;
171 
172 
173  printf("add horizontal and vertical edges...\n");
174  for (irow = 0; irow < NROWS; irow++) {
175 
176  if (fInterlaced == True) {
177  irowsave = irow;
178  if (irow % 2)
179  irow = NROWS - irow;
180  }
181 
182  for (icol = 0; icol < NCOLS; icol++) {
183 
184  if (fInterlaced == True) {
185  icolsave = icol;
186  if (icol % 2)
187  icol = NCOLS - icol;
188  }
189 
190  itcol = icol + 1;
191  itrow = irow + 1;
192 
193  if (itcol < NCOLS) {
194  from = irow * NCOLS + icol;
195  to = irow * NCOLS + itcol;
196  cost = FACTOR;
197  arc++;
198  if (_add_edge(&graph, from, to, cost, arc, 'r', 0)) {
199  return 1;
200  }
201 #ifdef BIDIRECTIONAL
202  arc++;
203  if (_add_edge(&graph, to, from, cost, arc, 'l', 0)) {
204  return 1;
205  }
206 #endif
207  }
208 
209  if (itrow < NROWS) {
210  from = irow * NCOLS + icol;
211  to = itrow * NCOLS + icol;
212  cost = FACTOR;
213  arc++;
214  if (_add_edge(&graph, from, to, cost, arc, 'b', 0)) {
215  return 1;
216  }
217 #ifdef BIDIRECTIONAL
218  arc++;
219  if (_add_edge(&graph, to, from, cost, arc, 't', 0)) {
220  return 1;
221  }
222 #endif
223  }
224 
225  if (fInterlaced == True)
226  icol = icolsave;
227  }
228 
229  if (fInterlaced == True)
230  irow = irowsave;
231  }
232  _add_edge(&graph, to, from, cost, arc, 'x', 1);
233 
234 
235 #if 1
236  printf("\nadd oblique edges...\n");
237  for (irow = 0; irow < NROWS; irow++) {
238  for (icol = 0; icol < NCOLS; icol++) {
239  itcol = icol + 1;
240  itrow = irow + 1;
241 
242  if (itrow < NROWS && itcol < NCOLS) {
243  from = irow * NCOLS + icol;
244  to = itrow * NCOLS + itcol;
245  cost = (dglInt32_t) (sqrt(2.0) * (double)FACTOR);
246  arc++;
247  if (_add_edge(&graph, from, to, cost, arc, 'o', 0)) {
248  return 1;
249  }
250 #ifdef BIDIRECTIONAL
251  arc++;
252  if (_add_edge(&graph, to, from, cost, arc, 'O', 0)) {
253  return 1;
254  }
255 #endif
256  }
257  }
258  }
259  _add_edge(&graph, to, from, cost, arc, 'x', 1);
260  printf("\ndone.\n");
261 #endif
262 
263 
264 #if 0
265  {
267  dglInt32_t *pEdge;
268 
269  nret =
270  dglEdge_T_Initialize(&graph, &t, dglGet_EdgePrioritizer(&graph));
271  /*nret = dglEdge_T_Initialize(& graph, & t, NULL); */
272  if (nret < 0) {
273  fprintf(stderr, "\ndglEdge_T_Initialize error: %s\n",
274  dglStrerror(&graph));
275  return 1;
276  }
277  for (pEdge = dglEdge_T_First(&t); pEdge; pEdge = dglEdge_T_Next(&t)) {
278  printf("edge: id=%ld cost=%ld\n",
279  dglEdgeGet_Id(&graph, pEdge),
280  dglEdgeGet_Cost(&graph, pEdge));
281  }
282  dglEdge_T_Release(&t);
283  }
284 #endif
285 
286 
287  printf("graph flattening...");
288  fflush(stdout);
289  nret = dglFlatten(&graph);
290  if (nret < 0) {
291  fprintf(stderr, "\ndglFlatten error: %s\n", dglStrerror(&graph));
292  return 1;
293  }
294  printf("done.\n");
295 
296 
297  printf("graph write...");
298  fflush(stdout);
299  if ((fd = open(pszFileout, O_WRONLY | O_CREAT | O_TRUNC, 0666)) < 0) {
300  perror("open");
301  return 1;
302  }
303  nret = dglWrite(&graph, fd);
304  if (nret < 0) {
305  fprintf(stderr, "\ndglWrite error: %s\n", dglStrerror(&graph));
306  return 1;
307  }
308  close(fd);
309  printf("done.\n");
310 
311 
312  printf("graph release...");
313  fflush(stdout);
314  dglRelease(&graph);
315  printf("program finished.\n");
316  return 0;
317 }