From e9d6c4621c15632cd317bad4f126efcba425563b Mon Sep 17 00:00:00 2001 From: Emden Gansner Date: Wed, 14 Sep 2011 16:28:27 -0400 Subject: [PATCH] Add triangular mesh and n-ary tree --- cmd/tools/graph_generator.c | 62 +++++++++++++++++++++++++++++++++++-- cmd/tools/graph_generator.h | 23 ++++++++------ cmd/tools/gvgen.1 | 12 +++++++ cmd/tools/gvgen.c | 53 ++++++++++++++++++++++++++++--- 4 files changed, 133 insertions(+), 17 deletions(-) diff --git a/cmd/tools/graph_generator.c b/cmd/tools/graph_generator.c index 4e318945c..b4a8a8fe8 100644 --- a/cmd/tools/graph_generator.c +++ b/cmd/tools/graph_generator.c @@ -190,14 +190,39 @@ makeSquareGrid(int dim1, int dim2, int connect_corners, int partial, edgefn ef) } } +static int +ipow (int base, int power) +{ + int ip; + if (power == 1) return base; + + ip = base; + power--; + while (power--) ip *= base; + return ip; +} + +void makeTree(int depth, int nary, edgefn ef) +{ + unsigned int i, j; + unsigned int n = (ipow(nary,depth)-1)/(nary-1); /* no. of non-leaf nodes */ + unsigned int idx = 2; + + for (i = 1; i <= n; i++) { + for (j = 0; j < nary; j++) { + ef (i, idx++); + } + } +} + void makeBinaryTree(int depth, edgefn ef) { unsigned int i; unsigned int n = (1 << depth) - 1; - for (i = 0; i < n; i++) { - ef( i + 1, 2 * i + 2); - ef( i + 1, 2 * i + 3); + for (i = 1; i <= n; i++) { + ef( i, 2 * i); + ef( i, 2 * i + 1); } } @@ -298,3 +323,34 @@ void makeHypercube(int dim, edgefn ef) } } } + +void makeTriMesh(int sz, edgefn ef) +{ + int i, j, idx; + + if (sz == 1) { + ef (1, 0); + return; + } + ef(1,2); + ef(1,3); + idx = 2; + for (i=2; i < sz; i++) { + for (j=1; j <= i; j++) { + ef(idx,idx+i); + ef(idx,idx+i+1); + if (j < i) + ef(idx,idx+1); + idx++; + } + } + for (j=1; j < sz; j++) { + ef (idx,idx+1); + idx++; + } +} + +void makeMobius(int dim1, int dim2, edgefn ef) +{ +} + diff --git a/cmd/tools/graph_generator.h b/cmd/tools/graph_generator.h index c6a638b58..2e8bbf7b2 100644 --- a/cmd/tools/graph_generator.h +++ b/cmd/tools/graph_generator.h @@ -16,17 +16,20 @@ typedef void (*edgefn)(int, int); -extern void makeCircle(int , edgefn); -extern void makeComplete(int , edgefn); +extern void makeCircle(int, edgefn); +extern void makeComplete(int, edgefn); extern void makeCompleteB(int, int, edgefn); -extern void makePath(int , edgefn); -extern void makeStar(int , edgefn); +extern void makePath(int, edgefn); +extern void makeStar(int, edgefn); extern void makeWheel (int, edgefn); -extern void makeTorus(int , int , edgefn); -extern void makeCylinder(int , int , edgefn); -extern void makeSquareGrid(int , int , int, int, edgefn); -extern void makeBinaryTree(int , edgefn); -extern void makeSierpinski(int , edgefn); -extern void makeHypercube(int , edgefn); +extern void makeTorus(int, int, edgefn); +extern void makeCylinder(int, int, edgefn); +extern void makeSquareGrid(int, int, int, int, edgefn); +extern void makeBinaryTree(int, edgefn); +extern void makeSierpinski(int, edgefn); +extern void makeHypercube(int, edgefn); +extern void makeTree(int, int, edgefn); +extern void makeTriMesh(int, edgefn); +extern void makeMobius(int, int, edgefn); #endif diff --git a/cmd/tools/gvgen.1 b/cmd/tools/gvgen.1 index ff02517fb..d763e7ad8 100644 --- a/cmd/tools/gvgen.1 +++ b/cmd/tools/gvgen.1 @@ -28,6 +28,9 @@ gvgen \- generate graphs .BI -b x,y ] [ +.BI -m n +] +[ .BI -p n ] [ @@ -40,6 +43,9 @@ gvgen \- generate graphs .BI -t n ] [ +.BI -t d,n +] +[ .BI -T x,y ] [ @@ -96,6 +102,9 @@ Generate a complete \fIx\fP by \fIy\fP bipartite graph. This will have \fIx+y\fP vertices and \fIx*y\fP edges. .TP +.BI \-m " n" +Generate a triangular mesh with \fIn\fP vertices on a side. +.TP .BI \-p " n" Generate a path on \fIn\fP vertices. This will have \fIn-1\fP edges. @@ -114,6 +123,9 @@ Generate a binary tree of height \fIn\fP. This will have \fI2^n-1\fP vertices and \fI2^n-2\fP edges. .TP +.BI \-t " h,n" +Generate a n-ary tree of height \fIh\fP. +.TP .BI \-T " x,y" Generate an \fIx\fP by \fIy\fP torus. This will have \fIx*y\fP vertices and diff --git a/cmd/tools/gvgen.c b/cmd/tools/gvgen.c index 00ebac882..7726b1757 100644 --- a/cmd/tools/gvgen.c +++ b/cmd/tools/gvgen.c @@ -40,7 +40,7 @@ typedef enum { unknown, grid, circle, complete, completeb, path, tree, torus, cylinder, - sierpinski, hypercube, star, wheel + sierpinski, hypercube, star, wheel, trimesh } GraphType; typedef struct { @@ -83,6 +83,7 @@ static char *Usage = "Usage: %s [-dV?] [options]\n\ -h : hypercube \n\ -k : complete \n\ -b : complete bipartite\n\ + -m : triangular mesh\n\ -n : use in node names (\"\")\n\ -N : use for the graph (\"\")\n\ -o : put output in (stdout)\n\ @@ -90,6 +91,7 @@ static char *Usage = "Usage: %s [-dV?] [options]\n\ -s : star\n\ -S : sierpinski\n\ -t : binary tree \n\ + -t, : n-ary tree \n\ -T : torus \n\ -w : wheel\n\ -d : directed graph\n\ @@ -108,6 +110,11 @@ static void errexit(char opt) usage(1); } +/* readPos: + * Read and return a single int from s, guaranteed to be >= min. + * A pointer to the next available character from s is stored in e. + * Return -1 on error. + */ static int readPos(char *s, char **e, int min) { int d; @@ -167,6 +174,33 @@ static int setTwo(char *s, opts_t* opts) else return d; } +/* setTwoOpt: + * Return non-zero on error. + */ +static int setTwoOpt(char *s, opts_t* opts, int dflt) +{ + int d; + char *next; + + d = readPos(s, &next, 1); + if (d < 0) + return d; + opts->graphSize1 = d; + + if (*next != ',') { + opts->graphSize2 = dflt; + return 0; + } + + s = next + 1; + d = readPos(s, &next, 1); + if (d > 1) { + opts->graphSize2 = d; + return 0; + } + else return d; +} + static char* setFold(char *s, opts_t* opts) { char *next; @@ -181,7 +215,7 @@ static char* setFold(char *s, opts_t* opts) return next; } -static char *optList = ":n:N:c:C:dg:G:h:k:b:o:p:s:S:t:T:Vw:"; +static char *optList = ":m:n:N:c:C:dg:G:h:k:b:o:p:s:S:t:T:Vw:"; static GraphType init(int argc, char *argv[], opts_t* opts) { @@ -228,6 +262,11 @@ static GraphType init(int argc, char *argv[], opts_t* opts) if (setTwo(optarg, opts)) errexit(c); break; + case 'm': + graphType = trimesh; + if (setOne(optarg, opts)) + errexit(c); + break; case 'n': opts->pfx = optarg; break; @@ -254,7 +293,7 @@ static GraphType init(int argc, char *argv[], opts_t* opts) break; case 't': graphType = tree; - if (setOne(optarg, opts)) + if (setTwoOpt(optarg, opts, 2)) errexit(c); break; case 'T': @@ -339,7 +378,13 @@ int main(int argc, char *argv[]) makePath(opts.graphSize1, ef); break; case tree: - makeBinaryTree(opts.graphSize1, ef); + if (opts.graphSize2 == 2) + makeBinaryTree(opts.graphSize1, ef); + else + makeTree(opts.graphSize1, opts.graphSize2, ef); + break; + case trimesh: + makeTriMesh(opts.graphSize1, ef); break; case torus: makeTorus(opts.graphSize1, opts.graphSize2, ef); -- 2.40.0