maze.c File Reference

#include "config.h"
#include <cgraph/alloc.h>
#include <float.h>
#include <math.h>
#include <stdbool.h>
#include <stddef.h>
#include <ortho/maze.h>
#include <ortho/partition.h>
#include <ortho/trap.h>
#include <common/arith.h>

Include dependency graph for maze.c:

Go to the source code of this file.

Data Structures
struct	snodeitem

Macros
#define	DEBUG
#define	MARGIN   36;
#define	delta   1 /* weight of length */
#define	mu   500 /* weight of bends */
#define	BEND(g, e)   ((g->nodes + e->v1)->isVert != (g->nodes + e->v2)->isVert)
#define	HORZ(g, e)   ((g->nodes + e->v1)->isVert)
#define	BIG   16384
#define	CHANSZ(w)   (((w)-3)/2)
#define	IS_SMALL(v)   (CHANSZ(v) < 2)

Functions
static void	psdump (cell *gcells, int n_gcells, boxf BB, boxf *rects, size_t nrect)
	dumps maze::gcells and maze::cells via rects to PostScript
static int	vcmpid (void *k1, void *k2)
	compares points by X and then by Y
static int	hcmpid (void *k1, void *k2)
	compares points by Y and then by X
static void	updateWt (sedge *ep, double sz)
	updates single sedge::weight
void	updateWts (sgraph *g, cell *cp, sedge *ep)
	updates sedge::weight of cell edges
static void	markSmall (cell *cp)
static void	createSEdges (cell *cp, sgraph *g)
	fills cell::sides and sgraph::edges
static snode *	findSVert (sgraph *g, Dt_t *cdt, pointf p, snodeitem *ditems, bool isVert)
	finds a snode by point or creates it
static void	chkSgraph (sgraph *g)
static sgraph *	mkMazeGraph (maze *mp, boxf bb)
	creates and fills sgraph for maze
maze *	mkMaze (graph_t *g)
	creates maze and fills maze::gcells and maze::cells. A subroutine of orthoEdges.
void	freeMaze (maze *mp)

Variables
char *	pre
char *	post = "showpage\n"
static Dtdisc_t	vdictDisc
static Dtdisc_t	hdictDisc

Macro Definition Documentation

BEND

#define BEND	(		g,
			e
	)		((g->nodes + e->v1)->isVert != (g->nodes + e->v2)->isVert)

Definition at line 136 of file maze.c.

BIG

#define BIG   16384

Definition at line 138 of file maze.c.

CHANSZ

#define CHANSZ

(

w

)

(((w)-3)/2)

Definition at line 139 of file maze.c.

DEBUG

#define DEBUG

Definition at line 14 of file maze.c.

delta

#define delta   1 /* weight of length */

Definition at line 133 of file maze.c.

HORZ

#define HORZ	(		g,
			e
	)		((g->nodes + e->v1)->isVert)

Definition at line 137 of file maze.c.

IS_SMALL

#define IS_SMALL

(

v

)

(CHANSZ(v) < 2)

Definition at line 140 of file maze.c.

MARGIN

#define MARGIN   36;

Definition at line 26 of file maze.c.

mu

#define mu   500 /* weight of bends */

Definition at line 134 of file maze.c.

Function Documentation

chkSgraph()

static void chkSgraph ( sgraph *  g )

static

Definition at line 306 of file maze.c.

References snode::cells, sgraph::nnodes, and sgraph::nodes.

Referenced by mkMazeGraph().

Here is the caller graph for this function:

createSEdges()

static void createSEdges ( cell *  cp, sgraph *  g  )

static

Definition at line 252 of file maze.c.

References cell::bb, BIG, createSEdge(), delta, cell::edges, IS_SMALL, IsSmallH, IsSmallV, boxf::LL, M_BOTTOM, M_LEFT, M_RIGHT, M_TOP, mu, cell::nedges, cell::sides, boxf::UR, pointf_s::x, and pointf_s::y.

Referenced by mkMazeGraph().

Here is the call graph for this function:

Here is the caller graph for this function:

findSVert()

static snode * findSVert ( sgraph *  g, Dt_t *  cdt, pointf  p, snodeitem *  ditems, bool  isVert  )

static

Definition at line 288 of file maze.c.

References createSNode(), dtinsert, dtmatch, snode::index, snode::isVert, snodeitem::np, and snodeitem::p.

Referenced by mkMazeGraph().

Here is the call graph for this function:

Here is the caller graph for this function:

freeMaze()

void freeMaze

(

maze *

mp

)

Definition at line 504 of file maze.c.

References maze::cells, dtclose(), free(), freeSGraph(), maze::gcells, maze::hchans, maze::sg, cell::sides, and maze::vchans.

Referenced by orthoEdges().

Here is the call graph for this function:

Here is the caller graph for this function:

hcmpid()

static int hcmpid ( void *  k1, void *  k2  )

static

Definition at line 101 of file maze.c.

References dfp_cmp(), dy, pointf_s::x, and pointf_s::y.

Here is the call graph for this function:

markSmall()

static void markSmall ( cell *  cp )

static

cp corresponds to a real node. If it is small, its associated cells should be marked as usable.

Definition at line 196 of file maze.c.

References cell::bb, snode::cells, cell::flags, IS_SMALL, IsNode, snode::isVert, boxf::LL, M_BOTTOM, M_LEFT, M_RIGHT, M_TOP, MZ_SMALLH, MZ_SMALLV, cell::nsides, cell::sides, boxf::UR, pointf_s::x, and pointf_s::y.

Referenced by mkMazeGraph().

Here is the caller graph for this function:

mkMaze()

maze * mkMaze

(

graph_t *

g

)

Definition at line 453 of file maze.c.

References agfstnode(), agnnodes(), agnxtnode(), cell::bb, maze::cells, cell::flags, free(), maze::gcells, gv_alloc(), gv_calloc(), boxf::LL, MARGIN, mkMazeGraph(), MZ_ISNODE, maze::ncells, ND_alg, ND_coord, ND_xsize, ND_ysize, maze::ngcells, odb_flags, partition(), psdump(), maze::sg, boxf::UR, pointf_s::x, and pointf_s::y.

Referenced by orthoEdges().

Here is the call graph for this function:

Here is the caller graph for this function:

mkMazeGraph()

static sgraph * mkMazeGraph ( maze *  mp, boxf  bb  )

static

Subroutines: createSGraph, findSVert with createSNode, initSEdges and chkSgraph

Definition at line 329 of file maze.c.

References cell::bb, maze::cells, snode::cells, chkSgraph(), createSEdges(), createSGraph(), dtclose(), dtmatch, dtnext, dtopen(), Dtoset, findSVert(), free(), maze::gcells, gsave(), gv_calloc(), hdictDisc, snode::index, initSEdges(), boxf::LL, M_BOTTOM, M_LEFT, M_RIGHT, M_TOP, markSmall(), maze::ncells, maze::ngcells, sgraph::nnodes, sgraph::nodes, snodeitem::np, cell::nsides, snodeitem::p, cell::sides, boxf::UR, vdictDisc, pointf_s::x, and pointf_s::y.

Referenced by mkMaze().

Here is the call graph for this function:

Here is the caller graph for this function:

psdump()

static void psdump ( cell *  gcells, int  n_gcells, boxf  BB, boxf *  rects, size_t  nrect  )

static

Definition at line 60 of file maze.c.

References cell::bb, boxf::LL, post, pre, boxf::UR, pointf_s::x, and pointf_s::y.

Referenced by mkMaze().

Here is the caller graph for this function:

updateWt()

static void updateWt ( sedge *  ep, double  sz  )

static

At present, we use a step function. When a bound is reached, the weight becomes huge. We might consider bumping up the weight more gradually, the thinner the channel, the faster the weight rises.

Definition at line 150 of file maze.c.

References BIG, sedge::cnt, and sedge::weight.

Referenced by updateWts().

Here is the caller graph for this function:

updateWts()

void updateWts	(	sgraph *	g,
		cell *	cp,
		sedge *	ep
	)

Iterate over edges in a cell, adjust weights as necessary. It always updates the bent edges belonging to a cell. A horizontal/vertical edge is updated only if the edge traversed is bent, or if it is the traversed edge.

Definition at line 168 of file maze.c.

References cell::bb, BEND, CHANSZ, cell::edges, HORZ, boxf::LL, cell::nedges, updateWt(), boxf::UR, pointf_s::x, and pointf_s::y.

Referenced by convertSPtoRoute().

Here is the call graph for this function:

Here is the caller graph for this function:

vcmpid()

static int vcmpid ( void *  k1, void *  k2  )

static

Definition at line 90 of file maze.c.

References dfp_cmp(), dx, pointf_s::x, and pointf_s::y.

Here is the call graph for this function:

Variable Documentation

hdictDisc

Dtdisc_t hdictDisc

static

Initial value:

= {
    offsetof(snodeitem,p),
    sizeof(pointf),
    offsetof(snodeitem,link),
    0,
    0,
    hcmpid,
}

Definition at line 124 of file maze.c.

Referenced by mkMazeGraph().

post

char* post = "showpage\n"

Definition at line 55 of file maze.c.

Referenced by dijkstra(), and psdump().

pre

char* pre

Initial value:

= "%!PS-Adobe-2.0\n\
/node {\n\
  /Y exch def\n\
  /X exch def\n\
  /y exch def\n\
  /x exch def\n\
  newpath\n\
  x y moveto\n\
  x Y lineto\n\
  X Y lineto\n\
  X y lineto\n\
  closepath fill\n\
} def\n\
/cell {\n\
  /Y exch def\n\
  /X exch def\n\
  /y exch def\n\
  /x exch def\n\
  newpath\n\
  x y moveto\n\
  x Y lineto\n\
  X Y lineto\n\
  X y lineto\n\
  closepath stroke\n\
} def\n"

Definition at line 29 of file maze.c.

Referenced by dijkstra(), and psdump().

vdictDisc

Dtdisc_t vdictDisc

static

Initial value:

= {
    offsetof(snodeitem,p),
    sizeof(pointf),
    offsetof(snodeitem,link),
    0,
    0,
    vcmpid,
}

Definition at line 116 of file maze.c.

Referenced by mkMazeGraph().