graph_generator.c File Reference

#include "config.h"
#include <assert.h>
#include <inttypes.h>
#include <limits.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <math.h>
#include <graph_generator.h>
#include <util/alloc.h>
#include <util/exit.h>
#include <util/list.h>
#include <util/random.h>
#include <util/overflow.h>

Include dependency graph for graph_generator.c:

Go to the source code of this file.

Data Structures
struct	pair
struct	tree_t
struct	treegen_s

Macros
#define	OUTE(h)   if (tl < (hd=(h))) ef( tl, hd)

Functions
void	makePath (unsigned n, edgefn ef)
void	makeComplete (unsigned n, edgefn ef)
void	makeCircle (unsigned n, edgefn ef)
void	makeStar (unsigned n, edgefn ef)
void	makeWheel (unsigned n, edgefn ef)
void	makeCompleteB (unsigned dim1, unsigned dim2, edgefn ef)
void	makeTorus (unsigned dim1, unsigned dim2, edgefn ef)
void	makeTwistedTorus (unsigned dim1, unsigned dim2, unsigned t1, unsigned t2, edgefn ef)
void	makeCylinder (unsigned dim1, unsigned dim2, edgefn ef)
void	makeSquareGrid (unsigned dim1, unsigned dim2, int connect_corners, int partial, edgefn ef)
void	makeTree (unsigned depth, unsigned nary, edgefn ef)
void	makeBinaryTree (unsigned depth, edgefn ef)
typedef	LIST (unsigned)
	vtx_data destructor
typedef	LIST (vtx_data)
static void	constructSierpinski (unsigned v1, unsigned v2, unsigned v3, unsigned depth, vtx_datas_t *graph)
void	makeSierpinski (unsigned depth, edgefn ef)
static void	constructTetrix (unsigned v1, unsigned v2, unsigned v3, unsigned v4, unsigned depth, vtx_datas_t *graph)
void	makeTetrix (unsigned depth, edgefn ef)
void	makeHypercube (unsigned dim, edgefn ef)
void	makeTriMesh (unsigned sz, edgefn ef)
void	makeBall (unsigned w, unsigned h, edgefn ef)
void	makeRandom (unsigned h, unsigned w, edgefn ef)
void	makeMobius (unsigned w, unsigned h, edgefn ef)
static tree_t *	mkTree (unsigned sz)
static void	freeTree (tree_t *tp)
static void	resetTree (tree_t *tp)
static unsigned	treeRoot (tree_t *tp)
static unsigned	prevRoot (tree_t *tp)
static unsigned	treeSize (tree_t *tp)
static unsigned	treeTop (tree_t *tp)
static void	treePop (tree_t *tp)
static void	addTree (tree_t *tp, unsigned sz)
static void	treeDup (tree_t *tp, unsigned J)
static pair	pop (int_stack_t *sp)
static uint64_t	umul (uint64_t a, uint64_t b)
	multiply two 64-bit unsigned integers, exiting on overflow
static uint64_t	uadd (uint64_t a, uint64_t b)
	add two 64-bit unsigned integers, exiting on overflow
static uint64_t *	genCnt (unsigned NN)
static void	genTree (unsigned NN, uint64_t *T, int_stack_t *stack, tree_t *TREE)
static void	writeTree (tree_t *tp, edgefn ef)
treegen_t *	makeTreeGen (unsigned N)
void	makeRandomTree (treegen_t *tg, edgefn ef)
void	freeTreeGen (treegen_t *tg)

Macro Definition Documentation

OUTE

#define OUTE

(

h

)

if (tl < (hd=(h))) ef( tl, hd)

Definition at line 141 of file graph_generator.c.

Function Documentation

addTree()

static void addTree ( tree_t *  tp, unsigned  sz  )

static

Definition at line 483 of file graph_generator.c.

References tree_t::p, tree_t::root, and tree_t::top.

Referenced by genTree().

Here is the caller graph for this function:

constructSierpinski()

static void constructSierpinski ( unsigned  v1, unsigned  v2, unsigned  v3, unsigned  depth, vtx_datas_t *  graph  )

static

Definition at line 224 of file graph_generator.c.

References constructSierpinski(), and graph().

Referenced by constructSierpinski(), and makeSierpinski().

Here is the call graph for this function:

Here is the caller graph for this function:

constructTetrix()

static void constructTetrix ( unsigned  v1, unsigned  v2, unsigned  v3, unsigned  v4, unsigned  depth, vtx_datas_t *  graph  )

static

Definition at line 267 of file graph_generator.c.

References constructTetrix(), and graph().

Referenced by constructTetrix(), and makeTetrix().

Here is the call graph for this function:

Here is the caller graph for this function:

freeTree()

static void freeTree ( tree_t *  tp )

static

Definition at line 448 of file graph_generator.c.

References free(), and tree_t::p.

Referenced by freeTreeGen().

Here is the call graph for this function:

Here is the caller graph for this function:

freeTreeGen()

void freeTreeGen

(

treegen_t *

tg

)

Definition at line 648 of file graph_generator.c.

References free(), freeTree(), LIST_FREE, treegen_s::sp, treegen_s::T, and treegen_s::tp.

Referenced by main().

Here is the call graph for this function:

Here is the caller graph for this function:

genCnt()

static uint64_t * genCnt ( unsigned  NN )

static

Definition at line 542 of file graph_generator.c.

References D, gv_calloc(), I, T, uadd(), and umul().

Referenced by makeTreeGen().

Here is the call graph for this function:

Here is the caller graph for this function:

genTree()

static void genTree ( unsigned  NN, uint64_t *  T, int_stack_t *  stack, tree_t *  TREE  )

static

Definition at line 563 of file graph_generator.c.

References addTree(), pair::d, D, gv_random_u64(), pair::j, M, N, pop(), push(), T, treeDup(), treePop(), treeTop(), and umul().

Referenced by makeRandomTree().

Here is the call graph for this function:

Here is the caller graph for this function:

LIST() [1/2]

typedef LIST

(

unsigned

)

Definition at line 203 of file graph_generator.c.

References LIST_FREE.

LIST() [2/2]

typedef LIST

(

vtx_data

)

Definition at line 210 of file graph_generator.c.

References graph(), LIST_APPEND, LIST_AT, LIST_SIZE, and NULL.

Here is the call graph for this function:

makeBall()

void makeBall	(	unsigned	w,
		unsigned	h,
		edgefn	ef
	)

Definition at line 356 of file graph_generator.c.

References makeCylinder().

Referenced by main().

Here is the call graph for this function:

Here is the caller graph for this function:

makeBinaryTree()

void makeBinaryTree	(	unsigned	depth,
		edgefn	ef
	)

Definition at line 193 of file graph_generator.c.

Referenced by main(), and makeRandom().

Here is the caller graph for this function:

makeCircle()

void makeCircle	(	unsigned	n,
		edgefn	ef
	)

Definition at line 48 of file graph_generator.c.

References makePath().

Referenced by main().

Here is the call graph for this function:

Here is the caller graph for this function:

makeComplete()

void makeComplete	(	unsigned	n,
		edgefn	ef
	)

Definition at line 36 of file graph_generator.c.

Referenced by main(), and makeWheel().

Here is the caller graph for this function:

makeCompleteB()

void makeCompleteB	(	unsigned	dim1,
		unsigned	dim2,
		edgefn	ef
	)

Definition at line 85 of file graph_generator.c.

Referenced by main().

Here is the caller graph for this function:

makeCylinder()

void makeCylinder	(	unsigned	dim1,
		unsigned	dim2,
		edgefn	ef
	)

Definition at line 125 of file graph_generator.c.

Referenced by main(), and makeBall().

Here is the caller graph for this function:

makeHypercube()

void makeHypercube	(	unsigned	dim,
		edgefn	ef
	)

Definition at line 320 of file graph_generator.c.

References dim, and neighbor.

Referenced by main().

Here is the caller graph for this function:

makeMobius()

void makeMobius	(	unsigned	w,
		unsigned	h,
		edgefn	ef
	)

Definition at line 400 of file graph_generator.c.

References makePath().

Referenced by main().

Here is the call graph for this function:

Here is the caller graph for this function:

makePath()

void makePath	(	unsigned	n,
		edgefn	ef
	)

Definition at line 27 of file graph_generator.c.

Referenced by main(), makeCircle(), makeMobius(), makeRandom(), makeStar(), and Pobspath().

Here is the caller graph for this function:

makeRandom()

void makeRandom	(	unsigned	h,
		unsigned	w,
		edgefn	ef
	)

Definition at line 371 of file graph_generator.c.

References makeBinaryTree(), makePath(), and type.

Referenced by main().

Here is the call graph for this function:

Here is the caller graph for this function:

makeRandomTree()

void makeRandomTree	(	treegen_t *	tg,
		edgefn	ef
	)

Definition at line 639 of file graph_generator.c.

References genTree(), LIST_CLEAR, treegen_s::N, resetTree(), treegen_s::sp, treegen_s::T, treegen_s::tp, and writeTree().

Referenced by main().

Here is the call graph for this function:

Here is the caller graph for this function:

makeSierpinski()

void makeSierpinski	(	unsigned	depth,
		edgefn	ef
	)

Definition at line 249 of file graph_generator.c.

References constructSierpinski(), graph(), LIST_AT, LIST_FREE, LIST_GET, and LIST_SIZE.

Referenced by main().

Here is the call graph for this function:

Here is the caller graph for this function:

makeSquareGrid()

void makeSquareGrid	(	unsigned	dim1,
		unsigned	dim2,
		int	connect_corners,
		int	partial,
		edgefn	ef
	)

Definition at line 143 of file graph_generator.c.

References OUTE.

Referenced by main().

Here is the caller graph for this function:

makeStar()

void makeStar	(	unsigned	n,
		edgefn	ef
	)

Definition at line 60 of file graph_generator.c.

References makePath().

Referenced by main(), and makeWheel().

Here is the call graph for this function:

Here is the caller graph for this function:

makeTetrix()

void makeTetrix	(	unsigned	depth,
		edgefn	ef
	)

Definition at line 302 of file graph_generator.c.

References constructTetrix(), graph(), LIST_AT, LIST_FREE, LIST_GET, and LIST_SIZE.

Referenced by main().

Here is the call graph for this function:

Here is the caller graph for this function:

makeTorus()

void makeTorus	(	unsigned	dim1,
		unsigned	dim2,
		edgefn	ef
	)

Definition at line 93 of file graph_generator.c.

Referenced by main().

Here is the caller graph for this function:

makeTree()

void makeTree	(	unsigned	depth,
		unsigned	nary,
		edgefn	ef
	)

Definition at line 182 of file graph_generator.c.

Referenced by main().

Here is the caller graph for this function:

makeTreeGen()

treegen_t * makeTreeGen

(

unsigned

N

)

Definition at line 628 of file graph_generator.c.

References genCnt(), gv_alloc(), mkTree(), N, treegen_s::N, treegen_s::sp, treegen_s::T, and treegen_s::tp.

Referenced by main().

Here is the call graph for this function:

Here is the caller graph for this function:

makeTriMesh()

void makeTriMesh	(	unsigned	sz,
		edgefn	ef
	)

Definition at line 333 of file graph_generator.c.

Referenced by main().

Here is the caller graph for this function:

makeTwistedTorus()

void makeTwistedTorus	(	unsigned	dim1,
		unsigned	dim2,
		unsigned	t1,
		unsigned	t2,
		edgefn	ef
	)

Definition at line 110 of file graph_generator.c.

Referenced by main().

Here is the caller graph for this function:

makeWheel()

void makeWheel	(	unsigned	n,
		edgefn	ef
	)

Definition at line 71 of file graph_generator.c.

References makeComplete(), and makeStar().

Referenced by main().

Here is the call graph for this function:

Here is the caller graph for this function:

mkTree()

static tree_t * mkTree ( unsigned  sz )

static

Definition at line 439 of file graph_generator.c.

References gv_alloc(), gv_calloc(), tree_t::p, tree_t::root, and tree_t::top.

Referenced by makeTreeGen().

Here is the call graph for this function:

Here is the caller graph for this function:

pop()

static pair pop ( int_stack_t *  sp )

static

Definition at line 511 of file graph_generator.c.

References LIST_POP_BACK.

prevRoot()

static unsigned prevRoot ( tree_t *  tp )

static

Definition at line 465 of file graph_generator.c.

References tree_t::p, and tree_t::root.

Referenced by treeDup(), and treePop().

Here is the caller graph for this function:

resetTree()

static void resetTree ( tree_t *  tp )

static

Definition at line 455 of file graph_generator.c.

References tree_t::root, and tree_t::top.

Referenced by makeRandomTree().

Here is the caller graph for this function:

treeDup()

static void treeDup ( tree_t *  tp, unsigned  J  )

static

Definition at line 490 of file graph_generator.c.

References L, M, tree_t::p, prevRoot(), tree_t::top, treeRoot(), and treeSize().

Referenced by genTree().

Here is the call graph for this function:

Here is the caller graph for this function:

treePop()

static void treePop ( tree_t *  tp )

static

Definition at line 478 of file graph_generator.c.

References prevRoot(), and tree_t::root.

Referenced by genTree().

Here is the call graph for this function:

Here is the caller graph for this function:

treeRoot()

static unsigned treeRoot ( tree_t *  tp )

static

Definition at line 461 of file graph_generator.c.

References tree_t::root.

Referenced by treeDup().

Here is the caller graph for this function:

treeSize()

static unsigned treeSize ( tree_t *  tp )

static

Definition at line 469 of file graph_generator.c.

References tree_t::root, and tree_t::top.

Referenced by treeDup().

Here is the caller graph for this function:

treeTop()

static unsigned treeTop ( tree_t *  tp )

static

Definition at line 473 of file graph_generator.c.

References tree_t::top.

Referenced by genTree().

Here is the caller graph for this function:

uadd()

static uint64_t uadd ( uint64_t  a, uint64_t  b  )

static

Definition at line 533 of file graph_generator.c.

References graphviz_exit(), and u64add_overflow().

Referenced by genCnt().

Here is the call graph for this function:

Here is the caller graph for this function:

umul()

static uint64_t umul ( uint64_t  a, uint64_t  b  )

static

Definition at line 523 of file graph_generator.c.

References graphviz_exit(), and u64mul_overflow().

Referenced by genCnt(), and genTree().

Here is the call graph for this function:

Here is the caller graph for this function:

writeTree()

static void writeTree ( tree_t *  tp, edgefn  ef  )

static

Definition at line 615 of file graph_generator.c.

References tree_t::p, and tree_t::top.

Referenced by makeRandomTree().

Here is the caller graph for this function: