maze.c File Reference

#include "config.h"
#include <assert.h>
#include <cgraph/cgraph.h>
#include <common/geomprocs.h>
#include <float.h>
#include <limits.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 <util/alloc.h>
#include <util/list.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, size_t 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 141 of file maze.c.

BIG

#define BIG   16384

Definition at line 143 of file maze.c.

CHANSZ

#define CHANSZ

(

w

)

(((w)-3)/2)

Definition at line 144 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 138 of file maze.c.

HORZ

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

Definition at line 142 of file maze.c.

IS_SMALL

#define IS_SMALL

(

v

)

(CHANSZ(v) < 2)

Definition at line 145 of file maze.c.

MARGIN

#define MARGIN   36

Definition at line 31 of file maze.c.

mu

#define mu   500 /* weight of bends */

Definition at line 139 of file maze.c.

Function Documentation

chkSgraph()

static void chkSgraph ( sgraph *  g )

static

Definition at line 310 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 256 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 292 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 502 of file maze.c.

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

Referenced by mkMaze(), and 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 106 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 201 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 454 of file maze.c.

References agfstnode(), agnnodes_z(), agnxtnode(), cell::bb, maze::cells, expandbbf(), cell::flags, free(), freeMaze(), maze::gcells, gv_alloc(), gv_calloc(), boxf::LL, MARGIN, mkMazeGraph(), MZ_ISNODE, maze::ncells, ND_alg, ND_coord, ND_xsize, ND_ysize, maze::ngcells, NULL, 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 333 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(), LIST, LIST_APPEND, LIST_DETACH, 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, size_t  n_gcells, boxf  BB, boxf *  rects, size_t  nrect  )

static

Definition at line 64 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 155 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 173 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 95 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 129 of file maze.c.

Referenced by mkMazeGraph().

post

char* post = "showpage\n"

Definition at line 60 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 34 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 121 of file maze.c.

Referenced by mkMazeGraph().