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