graph_generator.c File Reference

#include "config.h"
#include <inttypes.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	vtx_data
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)
static void	constructSierpinski (unsigned v1, unsigned v2, unsigned v3, unsigned depth, vtx_data *graph)
void	makeSierpinski (unsigned depth, edgefn ef)
static void	constructTetrix (unsigned v1, unsigned v2, unsigned v3, unsigned v4, unsigned depth, vtx_data *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 void	push (int_stack_t *sp, unsigned j, unsigned d)
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 139 of file graph_generator.c.

Function Documentation

addTree()

static void addTree ( tree_t *  tp, unsigned  sz  )

static

Definition at line 499 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_data *  graph  )

static

Definition at line 205 of file graph_generator.c.

References constructSierpinski(), graph(), and nedges.

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_data *  graph  )

static

Definition at line 265 of file graph_generator.c.

References constructTetrix(), graph(), and nedges.

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 464 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 664 of file graph_generator.c.

References free(), freeTree(), 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 558 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 579 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:

makeBall()

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

Definition at line 372 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 191 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 46 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 34 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 83 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 123 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 337 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 416 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 25 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 387 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 655 of file graph_generator.c.

References genTree(), 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 236 of file graph_generator.c.

References constructSierpinski(), free(), graph(), and gv_calloc().

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 141 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 58 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 308 of file graph_generator.c.

References constructTetrix(), free(), graph(), and gv_calloc().

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 91 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 180 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 644 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 349 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 108 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 69 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 455 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 527 of file graph_generator.c.

prevRoot()

static unsigned prevRoot ( tree_t *  tp )

static

Definition at line 481 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:

push()

static void push ( int_stack_t *  sp, unsigned  j, unsigned  d  )

static

Definition at line 522 of file graph_generator.c.

Referenced by genTree().

Here is the caller graph for this function:

resetTree()

static void resetTree ( tree_t *  tp )

static

Definition at line 471 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 506 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 494 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 477 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 485 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 489 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 549 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 539 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 631 of file graph_generator.c.

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

Referenced by makeRandomTree().

Here is the caller graph for this function: