ortho.c File Reference

#include "config.h"
#include <assert.h>
#include <float.h>
#include <math.h>
#include <stdbool.h>
#include <stddef.h>
#include <ortho/maze.h>
#include <ortho/fPQ.h>
#include <ortho/ortho.h>
#include <common/geomprocs.h>
#include <common/globals.h>
#include <common/render.h>
#include <common/pointset.h>
#include <util/alloc.h>
#include <util/exit.h>
#include <util/list.h>
#include <util/unused.h>
#include <common/arith.h>

Include dependency graph for ortho.c:

Go to the source code of this file.

Data Structures
struct	epair_t
struct	chanItem

Macros
#define	DEBUG
#define	CELL(n)   ((cell*)ND_alg(n))
#define	MID(a, b)   (((a)+(b))/2.0)
#define	TRANS   10

Functions
static UNUSED void	emitSearchGraph (FILE *fp, sgraph *sg)
	dumps in dot format snode::cells and edges of sgraph for debugging
static UNUSED void	emitGraph (FILE *fp, maze *mp, size_t n_edges, route *route_list, epair_t[])
static cell *	cellOf (snode *p, snode *q)
static pointf	midPt (cell *cp)
static pointf	sidePt (snode *ptr, cell *cp)
static void	setSeg (segment *sp, bool dir, double fix, double b1, double b2, int l1, int l2)
static route	convertSPtoRoute (sgraph *g, snode *fst, snode *lst)
static void	freeChannel (void *chan)
static void	freeChanItem (void *item)
static int	chancmpid (void *k1, void *k2)
static int	dcmpid (void *k1, void *k2)
static void	addChan (Dt_t *chdict, channel *cp, double j)
static Dt_t *	extractHChans (maze *mp)
static Dt_t *	extractVChans (maze *mp)
static void	insertChan (channel *chan, segment *seg)
static channel *	chanSearch (Dt_t *chans, segment *seg)
static void	assignSegs (size_t nrtes, route *route_list, maze *mp)
static void	addLoop (sgraph *sg, cell *cp, snode *dp, snode *sp)
static void	addNodeEdges (sgraph *sg, cell *cp, snode *np)
static char *	bendToStr (bend b)
static void	putSeg (FILE *fp, segment *seg)
static UNUSED void	dumpChanG (channel *cp, double v)
static void	assignTrackNo (Dt_t *chans)
static void	create_graphs (Dt_t *chans)
static int	eqEndSeg (bend S1l2, bend S2l2, bend T1, bend T2)
static int	overlapSeg (segment *S1, segment *S2, bend T1, bend T2)
static int	ellSeg (bend S1l1, bend S1l2, bend T)
static int	segCmp (segment *S1, segment *S2, bend T1, bend T2)
static int	seg_cmp (segment *S1, segment *S2)
static int	add_edges_in_G (channel *cp)
static int	add_np_edges (Dt_t *chans)
static segment *	next_seg (segment *seg, int dir)
static int	propagate_prec (segment *seg, int prec, int hops, int dir)
static bool	is_parallel (segment *s1, segment *s2)
static int	decide_point (pair *ret, segment *si, segment *sj, int dir1, int dir2)
static void	set_parallel_edges (segment *seg1, segment *seg2, int dir1, int dir2, int hops, maze *mp)
static void	removeEdge (segment *seg1, segment *seg2, int dir, maze *mp)
static int	addPEdges (channel *cp, maze *mp)
static int	add_p_edges (Dt_t *chans, maze *mp)
static int	assignTracks (maze *mp)
static double	vtrack (segment *seg, maze *m)
static double	htrack (segment *seg, maze *m)
static void	attachOrthoEdges (maze *mp, size_t n_edges, route *route_list, splineInfo *sinfo, epair_t es[], bool doLbls)
static int	edgeLen (Agedge_t *e)
static int	edgecmp (const void *x, const void *y)
static bool	spline_merge (node_t *n)
static bool	swap_ends_p (edge_t *e)
void	orthoEdges (Agraph_t *g, bool useLbls)
static pointf	coordOf (cell *cp, snode *np)
static boxf	emitEdge (FILE *fp, Agedge_t *e, route rte, maze *m, boxf bb)

Variables
int	odb_flags
static Dtdisc_t	chanDisc
static Dtdisc_t	chanItemDisc
static splineInfo	sinfo = { swap_ends_p, spline_merge, true, true }
static char *	prolog2
static char *	epilog2

Macro Definition Documentation

CELL

#define CELL

(

n

)

((cell*)ND_alg(n))

Definition at line 54 of file ortho.c.

DEBUG

#define DEBUG

Definition at line 24 of file ortho.c.

MID

#define MID	(		a,
			b
	)		(((a)+(b))/2.0)

Definition at line 55 of file ortho.c.

TRANS

#define TRANS   10

Definition at line 1320 of file ortho.c.

Function Documentation

add_edges_in_G()

static int add_edges_in_G ( channel *  cp )

static

Definition at line 697 of file ortho.c.

References cmp(), G, channel::G, insert_edge(), seg_cmp(), and channel::seg_list.

Referenced by add_np_edges().

Here is the call graph for this function:

Here is the caller graph for this function:

add_np_edges()

static int add_np_edges ( Dt_t *  chans )

static

Definition at line 721 of file ortho.c.

References add_edges_in_G(), dtflatten(), dtlink, and channel::seg_list.

Referenced by assignTracks().

Here is the call graph for this function:

Here is the caller graph for this function:

add_p_edges()

static int add_p_edges ( Dt_t *  chans, maze *  mp  )

static

Definition at line 1033 of file ortho.c.

References addPEdges(), dtflatten(), and dtlink.

Referenced by assignTracks().

Here is the call graph for this function:

Here is the caller graph for this function:

addChan()

static void addChan ( Dt_t *  chdict, channel *  cp, double  j  )

static

Definition at line 315 of file ortho.c.

References chanDisc, chanItem::chans, dtinsert, dtmatch, dtopen(), Dtoset, free(), gv_alloc(), and chanItem::v.

Referenced by extractHChans(), and extractVChans().

Here is the call graph for this function:

Here is the caller graph for this function:

addLoop()

static void addLoop ( sgraph *  sg, cell *  cp, snode *  dp, snode *  sp  )

static

Definition at line 443 of file ortho.c.

References snode::cells, createSEdge(), snode::isVert, sgraph::nnodes, cell::nsides, and cell::sides.

Referenced by orthoEdges().

Here is the call graph for this function:

Here is the caller graph for this function:

addNodeEdges()

static void addNodeEdges ( sgraph *  sg, cell *  cp, snode *  np  )

static

Definition at line 463 of file ortho.c.

References snode::cells, createSEdge(), sgraph::nnodes, cell::nsides, and cell::sides.

Referenced by orthoEdges().

Here is the call graph for this function:

Here is the caller graph for this function:

addPEdges()

static int addPEdges ( channel *  cp, maze *  mp  )

static

Definition at line 941 of file ortho.c.

References pair::a, pair::b, decide_point(), edge_exists(), G, channel::G, is_parallel(), removeEdge(), channel::seg_list, and set_parallel_edges().

Referenced by add_p_edges().

Here is the call graph for this function:

Here is the caller graph for this function:

assignSegs()

static void assignSegs ( size_t  nrtes, route *  route_list, maze *  mp  )

static

Definition at line 421 of file ortho.c.

References chanSearch(), maze::hchans, insertChan(), segment::isVert, route::n, route::segs, and maze::vchans.

Referenced by orthoEdges().

Here is the call graph for this function:

Here is the caller graph for this function:

assignTrackNo()

static void assignTrackNo ( Dt_t *  chans )

static

Definition at line 527 of file ortho.c.

References dtflatten(), dtlink, dumpChanG(), channel::G, odb_flags, channel::seg_list, top_sort(), vertex::topsort_order, and rawgraph::vertices.

Referenced by assignTracks().

Here is the call graph for this function:

Here is the caller graph for this function:

assignTracks()

static int assignTracks ( maze *  mp )

static

Definition at line 1048 of file ortho.c.

References add_np_edges(), add_p_edges(), assignTrackNo(), create_graphs(), maze::hchans, and maze::vchans.

Referenced by orthoEdges().

Here is the call graph for this function:

Here is the caller graph for this function:

attachOrthoEdges()

static void attachOrthoEdges ( maze *  mp, size_t  n_edges, route *  route_list, splineInfo *  sinfo, epair_t  es[], bool  doLbls  )

static

Definition at line 1097 of file ortho.c.

References add_pointf(), addEdgeLabels(), aghead, agnameof(), agtail, clip_and_install(), ED_head_port, ED_label, ED_tail_port, htrack(), segment::isVert, route::n, ND_coord, NULL, route::segs, textlabel_t::set, sinfo, Verbose, vtrack(), 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:

bendToStr()

static char * bendToStr ( bend  b )

static

Definition at line 476 of file ortho.c.

References B_DOWN, B_LEFT, B_NODE, B_RIGHT, B_UP, and NULL.

Referenced by putSeg().

Here is the caller graph for this function:

cellOf()

static cell * cellOf ( snode *  p, snode *  q  )

static

Definition at line 61 of file ortho.c.

References snode::cells.

Referenced by convertSPtoRoute().

Here is the caller graph for this function:

chancmpid()

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

static

Definition at line 274 of file ortho.c.

References paird::p1, and paird::p2.

chanSearch()

static channel * chanSearch ( Dt_t *  chans, segment *  seg  )

static

Definition at line 410 of file ortho.c.

References chanItem::chans, segment::comm_coord, dtmatch, and segment::p.

Referenced by assignSegs(), htrack(), removeEdge(), set_parallel_edges(), and vtrack().

Here is the caller graph for this function:

convertSPtoRoute()

static route convertSPtoRoute ( sgraph *  g, snode *  fst, snode *  lst  )

static

Definition at line 140 of file ortho.c.

References B_DOWN, B_LEFT, B_NODE, B_RIGHT, B_UP, cell::bb, cellOf(), snode::cells, gv_calloc(), gv_recalloc(), IsNode, snode::isVert, boxf::LL, midPt(), route::n, N_DAD, N_EDGE, segment::next, NULL, prev, segment::prev, route::segs, setSeg(), sidePt(), updateWts(), 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:

coordOf()

static pointf coordOf ( cell *  cp, snode *  np  )

static

Definition at line 1359 of file ortho.c.

References agerrorf(), cell::bb, graphviz_exit(), boxf::LL, M_BOTTOM, M_LEFT, M_RIGHT, M_TOP, cell::sides, boxf::UR, pointf_s::x, and pointf_s::y.

Referenced by emitSearchGraph().

Here is the call graph for this function:

Here is the caller graph for this function:

create_graphs()

static void create_graphs ( Dt_t *  chans )

static

Definition at line 551 of file ortho.c.

References dtflatten(), dtlink, channel::G, make_graph(), and channel::seg_list.

Referenced by assignTracks().

Here is the call graph for this function:

Here is the caller graph for this function:

dcmpid()

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

static

Definition at line 288 of file ortho.c.

decide_point()

static int decide_point ( pair *  ret, segment *  si, segment *  sj, int  dir1, int  dir2  )

static

Definition at line 798 of file ortho.c.

References pair::a, pair::b, is_parallel(), next_seg(), NULL, propagate_prec(), and seg_cmp().

Referenced by addPEdges().

Here is the call graph for this function:

Here is the caller graph for this function:

dumpChanG()

static UNUSED void dumpChanG ( channel *  cp, double  v  )

static

Definition at line 510 of file ortho.c.

References vertex::adj_list, channel::G, channel::p, paird::p1, paird::p2, putSeg(), channel::seg_list, and rawgraph::vertices.

Referenced by assignTrackNo().

Here is the call graph for this function:

Here is the caller graph for this function:

edgecmp()

static int edgecmp ( const void *  x, const void *  y  )

static

Definition at line 1163 of file ortho.c.

References epair_t::d.

Referenced by orthoEdges().

Here is the caller graph for this function:

edgeLen()

static int edgeLen ( Agedge_t *  e )

static

Definition at line 1156 of file ortho.c.

References aghead, agtail, DIST2, and ND_coord.

Referenced by orthoEdges().

Here is the caller graph for this function:

ellSeg()

static int ellSeg ( bend  S1l1, bend  S1l2, bend  T  )

static

Definition at line 594 of file ortho.c.

References T.

Referenced by segCmp().

Here is the caller graph for this function:

emitEdge()

static boxf emitEdge ( FILE *  fp, Agedge_t *  e, route  rte, maze *  m, boxf  bb  )

static

Definition at line 1377 of file ortho.c.

References aghead, agtail, CELL, htrack(), segment::isVert, boxf::LL, route::n, route::segs, boxf::UR, vtrack(), pointf_s::x, and pointf_s::y.

Referenced by emitGraph().

Here is the call graph for this function:

Here is the caller graph for this function:

emitGraph()

static UNUSED void emitGraph ( FILE *  fp, maze *  mp, size_t  n_edges, route *  route_list, epair_t  es[]  )

static

Definition at line 1463 of file ortho.c.

References cell::bb, bbox(), maze::cells, emitEdge(), epilog2, maze::gcells, boxf::LL, maze::ncells, maze::ngcells, prolog2, TRANS, 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:

emitSearchGraph()

static UNUSED void emitSearchGraph ( FILE *  fp, sgraph *  sg  )

static

The routine uses coordinates of cells calculated from gcells. Coordinates of gcellg are calculated by original specified graph layout engine.

Definition at line 1439 of file ortho.c.

References snode::cells, coordOf(), sgraph::edges, IsNode, midPt(), sgraph::nedges, sgraph::nnodes, sgraph::nodes, sedge::v1, sedge::v2, sedge::weight, 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:

eqEndSeg()

static int eqEndSeg ( bend  S1l2, bend  S2l2, bend  T1, bend  T2  )

static

Definition at line 568 of file ortho.c.

References B_NODE.

Referenced by overlapSeg(), and segCmp().

Here is the caller graph for this function:

extractHChans()

static Dt_t * extractHChans ( maze *  mp )

static

Definition at line 331 of file ortho.c.

References addChan(), cell::bb, maze::cells, snode::cells, chanItemDisc, channel::cp, dtopen(), Dtoset, cell::flags, gv_alloc(), IsHScan, IsNode, boxf::LL, M_LEFT, M_RIGHT, MZ_HSCAN, maze::ncells, channel::p, paird::p1, paird::p2, cell::sides, 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:

extractVChans()

static Dt_t * extractVChans ( maze *  mp )

static

Definition at line 367 of file ortho.c.

References addChan(), cell::bb, maze::cells, snode::cells, chanItemDisc, channel::cp, dtopen(), Dtoset, cell::flags, gv_alloc(), IsNode, IsVScan, boxf::LL, M_BOTTOM, M_TOP, MZ_VSCAN, maze::ncells, channel::p, paird::p1, paird::p2, cell::sides, 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:

freeChanItem()

static void freeChanItem ( void *  item )

static

Definition at line 259 of file ortho.c.

References chanItem::chans, dtclose(), and free().

Here is the call graph for this function:

freeChannel()

static void freeChannel ( void *  chan )

static

Definition at line 252 of file ortho.c.

References free(), free_graph(), channel::G, and channel::seg_list.

Here is the call graph for this function:

htrack()

static double htrack ( segment *  seg, maze *  m  )

static

Definition at line 1087 of file ortho.c.

References cell::bb, chanSearch(), channel::cp, maze::hchans, boxf::LL, channel::seg_list, segment::track_no, boxf::UR, and pointf_s::y.

Referenced by attachOrthoEdges(), and emitEdge().

Here is the call graph for this function:

Here is the caller graph for this function:

insertChan()

static void insertChan ( channel *  chan, segment *  seg  )

static

Definition at line 403 of file ortho.c.

References segment::ind_no, and channel::seg_list.

Referenced by assignSegs().

Here is the caller graph for this function:

is_parallel()

static bool is_parallel ( segment *  s1, segment *  s2  )

static

Definition at line 783 of file ortho.c.

References segment::comm_coord, segment::l1, segment::l2, segment::p, paird::p1, paird::p2, and s1().

Referenced by addPEdges(), decide_point(), and removeEdge().

Here is the call graph for this function:

Here is the caller graph for this function:

midPt()

static pointf midPt ( cell *  cp )

static

Definition at line 69 of file ortho.c.

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

Referenced by convertSPtoRoute(), and emitSearchGraph().

Here is the caller graph for this function:

next_seg()

static segment * next_seg ( segment *  seg, int  dir  )

static

Definition at line 738 of file ortho.c.

References segment::next, and segment::prev.

Referenced by decide_point(), propagate_prec(), removeEdge(), and set_parallel_edges().

Here is the caller graph for this function:

orthoEdges()

void orthoEdges	(	Agraph_t *	g,
		bool	useLbls
	)

Definition at line 1194 of file ortho.c.

References addLoop(), addNodeEdges(), addPS(), agfstnode(), agfstout(), agget(), aghead, agnedges(), agnxtnode(), agnxtout(), AGSEQ, agtail, agwarningf(), assignSegs(), assignTracks(), attachOrthoEdges(), CELL, Concentrate, convertSPtoRoute(), epair_t::d, epair_t::e, ED_label, ED_spl, edgecmp(), edgeLen(), emitGraph(), emitSearchGraph(), extractHChans(), extractVChans(), free(), freeMaze(), freePS(), gv_calloc(), maze::hchans, isInPS(), mkMaze(), newPS(), sgraph::nnodes, sgraph::nodes, Nop, NULL, odb_flags, PQfree(), PQgen(), ps, reset(), textlabel_t::set, maze::sg, shortPath(), sinfo, and maze::vchans.

Referenced by dot_splines_(), and spline_edges_().

Here is the call graph for this function:

Here is the caller graph for this function:

overlapSeg()

static int overlapSeg ( segment *  S1, segment *  S2, bend  T1, bend  T2  )

static

Definition at line 577 of file ortho.c.

References eqEndSeg(), segment::l1, segment::l2, segment::p, and paird::p2.

Referenced by segCmp().

Here is the call graph for this function:

Here is the caller graph for this function:

propagate_prec()

static int propagate_prec ( segment *  seg, int  prec, int  hops, int  dir  )

static

Definition at line 751 of file ortho.c.

References B_DOWN, B_LEFT, B_RIGHT, B_UP, segment::comm_coord, segment::isVert, segment::l1, segment::l2, next_seg(), segment::p, and paird::p1.

Referenced by decide_point().

Here is the call graph for this function:

Here is the caller graph for this function:

putSeg()

static void putSeg ( FILE *  fp, segment *  seg  )

static

Definition at line 500 of file ortho.c.

References bendToStr(), segment::comm_coord, segment::isVert, segment::l1, segment::l2, segment::p, paird::p1, and paird::p2.

Referenced by dumpChanG().

Here is the call graph for this function:

Here is the caller graph for this function:

removeEdge()

static void removeEdge ( segment *  seg1, segment *  seg2, int  dir, maze *  mp  )

static

Definition at line 921 of file ortho.c.

References chanSearch(), channel::G, maze::hchans, segment::ind_no, is_parallel(), segment::isVert, next_seg(), remove_redge(), and maze::vchans.

Referenced by addPEdges().

Here is the call graph for this function:

Here is the caller graph for this function:

seg_cmp()

static int seg_cmp ( segment *  S1, segment *  S2  )

static

Definition at line 684 of file ortho.c.

References agerrorf(), B_DOWN, B_LEFT, B_RIGHT, B_UP, segment::comm_coord, segment::isVert, and segCmp().

Referenced by add_edges_in_G(), and decide_point().

Here is the call graph for this function:

Here is the caller graph for this function:

segCmp()

static int segCmp ( segment *  S1, segment *  S2, bend  T1, bend  T2  )

static

Definition at line 604 of file ortho.c.

References B_NODE, ellSeg(), eqEndSeg(), segment::l1, segment::l2, overlapSeg(), segment::p, paird::p1, and paird::p2.

Referenced by seg_cmp().

Here is the call graph for this function:

Here is the caller graph for this function:

set_parallel_edges()

static void set_parallel_edges ( segment *  seg1, segment *  seg2, int  dir1, int  dir2, int  hops, maze *  mp  )

static

Definition at line 832 of file ortho.c.

References B_LEFT, B_UP, chanSearch(), segment::comm_coord, edge_exists(), channel::G, maze::hchans, segment::ind_no, insert_edge(), segment::isVert, segment::l1, segment::l2, next_seg(), segment::p, paird::p1, and maze::vchans.

Referenced by addPEdges().

Here is the call graph for this function:

Here is the caller graph for this function:

setSeg()

static void setSeg ( segment *  sp, bool  dir, double  fix, double  b1, double  b2, int  l1, int  l2  )

static

Definition at line 114 of file ortho.c.

References segment::comm_coord, segment::isVert, segment::l1, segment::l2, segment::p, paird::p1, and paird::p2.

Referenced by convertSPtoRoute().

Here is the caller graph for this function:

sidePt()

static pointf sidePt ( snode *  ptr, cell *  cp  )

static

Definition at line 82 of file ortho.c.

References cell::bb, snode::cells, snode::isVert, boxf::LL, MID, boxf::UR, pointf_s::x, and pointf_s::y.

Referenced by convertSPtoRoute().

Here is the caller graph for this function:

spline_merge()

static bool spline_merge ( node_t *  n )

static

Definition at line 1175 of file ortho.c.

swap_ends_p()

static bool swap_ends_p ( edge_t *  e )

static

Definition at line 1181 of file ortho.c.

vtrack()

static double vtrack ( segment *  seg, maze *  m  )

static

Definition at line 1078 of file ortho.c.

References cell::bb, chanSearch(), channel::cp, left, boxf::LL, right, channel::seg_list, segment::track_no, boxf::UR, maze::vchans, and pointf_s::x.

Referenced by attachOrthoEdges(), and emitEdge().

Here is the call graph for this function:

Here is the caller graph for this function:

Variable Documentation

chanDisc

Dtdisc_t chanDisc

static

Initial value:

= {
    offsetof(channel,p),
    sizeof(paird),
    offsetof(channel,link),
    0,
    freeChannel,
    chancmpid,
}

Definition at line 296 of file ortho.c.

Referenced by addChan().

chanItemDisc

Dtdisc_t chanItemDisc

static

Initial value:

= {
    offsetof(chanItem,v),
    sizeof(double),
    offsetof(chanItem,link),
    0,
    freeChanItem,
    dcmpid,
}

Definition at line 305 of file ortho.c.

Referenced by extractHChans(), and extractVChans().

epilog2

char* epilog2

static

Initial value:

=
"showpage\n\
%%%%Trailer\n\
%%%%BoundingBox: %.f %.f %.f %.f\n"

Definition at line 1354 of file ortho.c.

Referenced by emitGraph().

odb_flags

int odb_flags

Definition at line 51 of file ortho.c.

Referenced by assignTrackNo(), mkMaze(), and orthoEdges().

prolog2

char* prolog2

static

Definition at line 1322 of file ortho.c.

Referenced by emitGraph().

sinfo

splineInfo sinfo = { swap_ends_p, spline_merge, true, true }

static

Definition at line 1187 of file ortho.c.

Referenced by attachOrthoEdges(), and orthoEdges().