1/* $Id$Revision: */
2/* vim:set shiftwidth=4 ts=8: */
3
4/*************************************************************************
5 * Copyright (c) 2011 AT&T Intellectual Property
6 * All rights reserved. This program and the accompanying materials
7 * are made available under the terms of the Eclipse Public License v1.0
8 * which accompanies this distribution, and is available at
9 * http://www.eclipse.org/legal/epl-v10.html
10 *
11 * Contributors: See CVS logs. Details at http://www.graphviz.org/
12 *************************************************************************/
13
14/*
15 * Written by Emden Gansner
16 */
17
18#include "config.h"
19
20#include <stdio.h>
21#include <stdlib.h>
22#ifdef HAVE_UNISTD_H
23#include <unistd.h>
24#endif
25#include <string.h>
26#include <ctype.h>
27#include <getopt.h>
28#include "graph_generator.h"
29
30typedef enum { unknown, grid, circle, complete, completeb,
31 path, tree, torus, cylinder, mobius, randomg, randomt, ball,
32 sierpinski, hypercube, star, wheel, trimesh
33} GraphType;
34
35typedef struct {
36 int graphSize1;
37 int graphSize2;
38 int cnt;
39 int parm1;
40 int parm2;
41 int Verbose;
42 int isPartial;
43 int foldVal;
44 int directed;
45 FILE *outfile;
46 char* pfx;
47 char* name;
48} opts_t;
49
50static char *cmd;
51
52static FILE *openFile(char *name, char *mode)
53{
54 FILE *fp;
55 char *modestr;
56
57 fp = fopen(name, mode);
58 if (!fp) {
59 if (*mode == 'r')
60 modestr = "reading";
61 else
62 modestr = "writing";
63 fprintf(stderr, "%s: could not open file %s for %s\n",
64 cmd, name, modestr);
65 exit(1);
66 }
67 return fp;
68}
69
70static char *Usage = "Usage: %s [-dv?] [options]\n\
71 -c<n> : cycle \n\
72 -C<x,y> : cylinder \n\
73 -g[f]<h,w> : grid (folded if f is used)\n\
74 -G[f]<h,w> : partial grid (folded if f is used)\n\
75 -h<x> : hypercube \n\
76 -k<x> : complete \n\
77 -b<x,y> : complete bipartite\n\
78 -B<x,y> : ball\n\
79 -i<n> : generate <n> random\n\
80 -m<x> : triangular mesh\n\
81 -M<x,y> : x by y Moebius strip\n\
82 -n<prefix> : use <prefix> in node names (\"\")\n\
83 -N<name> : use <name> for the graph (\"\")\n\
84 -o<outfile> : put output in <outfile> (stdout)\n\
85 -p<x> : path \n\
86 -r<x>,<n> : random graph\n\
87 -R<n> : random rooted tree on <n> vertices\n\
88 -s<x> : star\n\
89 -S<x> : 2D sierpinski\n\
90 -S<x>,<d> : <d>D sierpinski (<d> = 2,3)\n\
91 -t<x> : binary tree \n\
92 -t<x>,<n> : n-ary tree \n\
93 -T<x,y> : torus \n\
94 -T<x,y,t1,t2> : twisted torus \n\
95 -w<x> : wheel\n\
96 -d : directed graph\n\
97 -v : verbose mode\n\
98 -? : print usage\n";
99
100static void usage(int v)
101{
102 fprintf(v ? stderr : stdout, Usage, cmd);
103 exit(v);
104}
105
106static void errexit(char opt)
107{
108 fprintf(stderr, "in flag -%c\n", opt);
109 usage(1);
110}
111
112/* readPos:
113 * Read and return a single int from s, guaranteed to be >= min.
114 * A pointer to the next available character from s is stored in e.
115 * Return -1 on error.
116 */
117static int readPos(char *s, char **e, int min)
118{
119 int d;
120
121 d = strtol(s, e, 10);
122 if (s == *e) {
123 fprintf(stderr, "ill-formed integer \"%s\" ", s);
124 return -1;
125 }
126 if (d < min) {
127 fprintf(stderr, "integer \"%s\" less than %d", s, min);
128 return -1;
129 }
130 return d;
131}
132
133/* readOne:
134 * Return non-zero on error.
135 */
136static int readOne(char *s, int* ip)
137{
138 int d;
139 char *next;
140
141 d = readPos(s, &next, 1);
142 if (d > 0) {
143 *ip = d;
144 return 0;
145 }
146 else return d;
147}
148
149/* setOne:
150 * Return non-zero on error.
151 */
152static int setOne(char *s, opts_t* opts)
153{
154 int d;
155 char *next;
156
157 d = readPos(s, &next, 1);
158 if (d > 0) {
159 opts->graphSize1 = d;
160 return 0;
161 }
162 else return d;
163}
164
165/* setTwo:
166 * Return non-zero on error.
167 */
168static int setTwo(char *s, opts_t* opts)
169{
170 int d;
171 char *next;
172
173 d = readPos(s, &next, 1);
174 if (d < 0)
175 return d;
176 opts->graphSize1 = d;
177
178 if (*next != ',') {
179 fprintf(stderr, "ill-formed int pair \"%s\" ", s);
180 return -1;
181 }
182
183 s = next + 1;
184 d = readPos(s, &next, 1);
185 if (d > 1) {
186 opts->graphSize2 = d;
187 return 0;
188 }
189 else return d;
190}
191
192/* setTwoTwoOpt:
193 * Read 2 numbers
194 * Read 2 more optional numbers
195 * Return non-zero on error.
196 */
197static int setTwoTwoOpt(char *s, opts_t* opts, int dflt)
198{
199 int d;
200 char *next;
201
202 d = readPos(s, &next, 1);
203 if (d < 0)
204 return d;
205 opts->graphSize1 = d;
206
207 if (*next != ',') {
208 fprintf(stderr, "ill-formed int pair \"%s\" ", s);
209 return -1;
210 }
211
212 s = next + 1;
213 d = readPos(s, &next, 1);
214 if (d < 1) {
215 return 0;
216 }
217 opts->graphSize2 = d;
218
219 if (*next != ',') {
220 opts->parm1 = opts->parm2 = dflt;
221 return 0;
222 }
223
224 s = next + 1;
225 d = readPos(s, &next, 1);
226 if (d < 0)
227 return d;
228 opts->parm1 = d;
229
230 if (*next != ',') {
231 opts->parm2 = dflt;
232 return 0;
233 }
234
235 s = next + 1;
236 d = readPos(s, &next, 1);
237 if (d < 0) {
238 return d;
239 }
240 opts->parm2 = d;
241 return 0;
242}
243
244/* setTwoOpt:
245 * Return non-zero on error.
246 */
247static int setTwoOpt(char *s, opts_t* opts, int dflt)
248{
249 int d;
250 char *next;
251
252 d = readPos(s, &next, 1);
253 if (d < 0)
254 return d;
255 opts->graphSize1 = d;
256
257 if (*next != ',') {
258 opts->graphSize2 = dflt;
259 return 0;
260 }
261
262 s = next + 1;
263 d = readPos(s, &next, 1);
264 if (d > 1) {
265 opts->graphSize2 = d;
266 return 0;
267 }
268 else return d;
269}
270
271static char* setFold(char *s, opts_t* opts)
272{
273 char *next;
274
275 if (*s == 'f') {
276 next = s+1;
277 opts->foldVal = 1;
278 }
279 else
280 next = s;
281
282 return next;
283}
284
285static char *optList = ":i:M:m:n:N:c:C:dg:G:h:k:b:B:o:p:r:R:s:S:X:t:T:vw:";
286
287static GraphType init(int argc, char *argv[], opts_t* opts)
288{
289 int c;
290 GraphType graphType = unknown;
291
292 cmd = argv[0];
293 opterr = 0;
294 while ((c = getopt(argc, argv, optList)) != -1) {
295 switch (c) {
296 case 'c':
297 graphType = circle;
298 if (setOne(optarg, opts))
299 errexit(c);
300 break;
301 case 'C':
302 graphType = cylinder;
303 if (setTwo(optarg, opts))
304 errexit(c);
305 break;
306 case 'M':
307 graphType = mobius;
308 if (setTwo(optarg, opts))
309 errexit(c);
310 break;
311 case 'd':
312 opts->directed = 1;
313 break;
314 case 'G':
315 opts->isPartial = 1;
316 case 'g':
317 graphType = grid;
318 optarg = setFold (optarg, opts);
319 if (setTwo(optarg, opts))
320 errexit(c);
321 break;
322 case 'h':
323 graphType = hypercube;
324 if (setOne(optarg, opts))
325 errexit(c);
326 break;
327 case 'k':
328 graphType = complete;
329 if (setOne(optarg, opts))
330 errexit(c);
331 break;
332 case 'b':
333 graphType = completeb;
334 if (setTwo(optarg, opts))
335 errexit(c);
336 break;
337 case 'B':
338 graphType = ball;
339 if (setTwo(optarg, opts))
340 errexit(c);
341 break;
342 case 'm':
343 graphType = trimesh;
344 if (setOne(optarg, opts))
345 errexit(c);
346 break;
347 case 'r':
348 graphType = randomg;
349 if (setTwo(optarg, opts))
350 errexit(c);
351 break;
352 case 'R':
353 graphType = randomt;
354 if (setOne(optarg, opts))
355 errexit(c);
356 break;
357 case 'n':
358 opts->pfx = optarg;
359 break;
360 case 'N':
361 opts->name = optarg;
362 break;
363 case 'o':
364 opts->outfile = openFile(optarg, "w");
365 break;
366 case 'p':
367 graphType = path;
368 if (setOne(optarg, opts))
369 errexit(c);
370 break;
371 case 'S':
372 graphType = sierpinski;
373 if (setTwoOpt(optarg, opts, 2))
374 errexit(c);
375 if (opts->graphSize2 > 3) {
376 fprintf(stderr, "%dD Sierpinski not implemented - use 2 or 3 ", opts->graphSize2);
377 errexit(c);
378 }
379 break;
380 case 's':
381 graphType = star;
382 if (setOne(optarg, opts))
383 errexit(c);
384 break;
385 case 't':
386 graphType = tree;
387 if (setTwoOpt(optarg, opts, 2))
388 errexit(c);
389 break;
390 case 'T':
391 graphType = torus;
392 if (setTwoTwoOpt(optarg, opts, 0))
393 errexit(c);
394 break;
395 case 'i':
396 if (readOne(optarg,&(opts->cnt)))
397 errexit(c);
398 break;
399 case 'v':
400 opts->Verbose = 1;
401 break;
402 case 'w':
403 graphType = wheel;
404 if (setOne(optarg, opts))
405 errexit(c);
406 break;
407 case '?':
408 if (optopt == '?')
409 usage(0);
410 else
411 fprintf(stderr, "Unrecognized flag \"-%c\" - ignored\n",
412 optopt);
413 break;
414 }
415 }
416
417 argc -= optind;
418 argv += optind;
419 if (!opts->outfile)
420 opts->outfile = stdout;
421 if (graphType == unknown) {
422 fprintf(stderr, "Graph type not set\n");
423 usage(1);
424 }
425
426 return graphType;
427}
428
429static opts_t opts;
430
431static void dirfn (int t, int h)
432{
433 if (h > 0)
434 fprintf (opts.outfile, " %s%d -> %s%d\n", opts.pfx, t, opts.pfx, h);
435 else
436 fprintf (opts.outfile, " %s%d\n", opts.pfx, t);
437}
438
439static void undirfn (int t, int h)
440{
441 if (h > 0)
442 fprintf (opts.outfile, " %s%d -- %s%d\n", opts.pfx, t, opts.pfx, h);
443 else
444 fprintf (opts.outfile, " %s%d\n", opts.pfx, t);
445}
446
447static void
448closeOpen (void)
449{
450 if (opts.directed)
451 fprintf(opts.outfile, "}\ndigraph {\n");
452 else
453 fprintf(opts.outfile, "}\ngraph {\n");
454}
455
456int main(int argc, char *argv[])
457{
458 GraphType graphType;
459 edgefn ef;
460
461 opts.pfx = "";
462 opts.name = "";
463 opts.cnt = 1;
464 graphType = init(argc, argv, &opts);
465 if (opts.directed) {
466 fprintf(opts.outfile, "digraph %s{\n", opts.name);
467 ef = dirfn;
468 }
469 else {
470 fprintf(opts.outfile, "graph %s{\n", opts.name);
471 ef = undirfn;
472 }
473
474 switch (graphType) {
475 case grid:
476 makeSquareGrid(opts.graphSize1, opts.graphSize2,
477 opts.foldVal, opts.isPartial, ef);
478 break;
479 case circle:
480 makeCircle(opts.graphSize1, ef);
481 break;
482 case path:
483 makePath(opts.graphSize1, ef);
484 break;
485 case tree:
486 if (opts.graphSize2 == 2)
487 makeBinaryTree(opts.graphSize1, ef);
488 else
489 makeTree(opts.graphSize1, opts.graphSize2, ef);
490 break;
491 case trimesh:
492 makeTriMesh(opts.graphSize1, ef);
493 break;
494 case ball:
495 makeBall(opts.graphSize1, opts.graphSize2, ef);
496 break;
497 case torus:
498 if ((opts.parm1 == 0) && (opts.parm2 == 0))
499 makeTorus(opts.graphSize1, opts.graphSize2, ef);
500 else
501 makeTwistedTorus(opts.graphSize1, opts.graphSize2, opts.parm1, opts.parm2, ef);
502 break;
503 case cylinder:
504 makeCylinder(opts.graphSize1, opts.graphSize2, ef);
505 break;
506 case mobius:
507 makeMobius(opts.graphSize1, opts.graphSize2, ef);
508 break;
509 case sierpinski:
510 if (opts.graphSize2 == 2)
511 makeSierpinski(opts.graphSize1, ef);
512 else
513 makeTetrix(opts.graphSize1, ef);
514 break;
515 case complete:
516 makeComplete(opts.graphSize1, ef);
517 break;
518 case randomg:
519 makeRandom (opts.graphSize1, opts.graphSize2, ef);
520 break;
521 case randomt:
522 {
523 int i;
524 treegen_t* tg = makeTreeGen (opts.graphSize1);
525 for (i = 1; i <= opts.cnt; i++) {
526 makeRandomTree (tg, ef);
527 if (i != opts.cnt) closeOpen ();
528 }
529 freeTreeGen (tg);
530 }
531 makeRandom (opts.graphSize1, opts.graphSize2, ef);
532 break;
533 case completeb:
534 makeCompleteB(opts.graphSize1, opts.graphSize2, ef);
535 break;
536 case hypercube:
537 makeHypercube(opts.graphSize1, ef);
538 break;
539 case star:
540 makeStar(opts.graphSize1, ef);
541 break;
542 case wheel:
543 makeWheel(opts.graphSize1, ef);
544 break;
545 default:
546 /* can't happen */
547 break;
548 }
549 fprintf(opts.outfile, "}\n");
550
551 exit(0);
552}
553