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/gv_math.h>
#include <util/list.h>
#include <util/optional.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	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 double	MID (double a, double b)
static cell *	cellOf (snode *p, snode *q)
static pointf	midPt (const cell *cp)
static pointf	sidePt (const snode ptr, const cell *cp)
static segment	setSeg (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 const 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 (const segment S1, const segment S2, bend T1, bend T2)
static int	ellSeg (bend S1l1, bend S1l2, bend T)
static int	segCmp (const segment S1, const segment S2, bend T1, bend T2)
static int	seg_cmp (const segment S1, const segment S2)
static int	add_edges_in_G (channel *cp)
static int	add_np_edges (Dt_t *chans)
static segment *	next_seg (const segment seg, int dir)
static int	propagate_prec (const segment seg, int prec, int hops, int dir)
static bool	is_parallel (const segment s1, const 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 double	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 const char	prolog2 []

Macro Definition Documentation

CELL

#define CELL

(

n

)

((cell*)ND_alg(n))

Definition at line 56 of file ortho.c.

DEBUG

#define DEBUG

Definition at line 24 of file ortho.c.

TRANS

#define TRANS   10

Definition at line 1292 of file ortho.c.

Function Documentation

add_edges_in_G()

static int add_edges_in_G ( channel *  cp )

static

Definition at line 657 of file ortho.c.

References cmp(), G, channel::G, insert_edge(), LIST_GET, LIST_SIZE, 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 680 of file ortho.c.

References add_edges_in_G(), dtflatten(), dtlink, LIST_IS_EMPTY, 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 1006 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 289 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 417 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 437 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 914 of file ortho.c.

References pair::a, pair::b, decide_point(), edge_exists(), G, channel::G, is_parallel(), LIST_GET, LIST_SIZE, 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 395 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 494 of file ortho.c.

References dtflatten(), dtlink, dumpChanG(), channel::G, LIST_GET, LIST_IS_EMPTY, LIST_SIZE, odb_flags, OPTIONAL_SET, 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 1021 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 1069 of file ortho.c.

References add_pointf(), addEdgeLabels(), aghead, agnameof(), agtail, clip_and_install(), epair_t::e, ED_head_port, ED_label, ED_tail_port, htrack(), segment::isVert, LIST, LIST_APPEND, LIST_CLEAR, LIST_FREE, LIST_FRONT, LIST_RESERVE, LIST_SIZE, 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 const char * bendToStr ( bend  b )

static

Definition at line 450 of file ortho.c.

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

Referenced by putSeg().

Here is the caller graph for this function:

cellOf()

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

static

Definition at line 66 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 250 of file ortho.c.

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

chanSearch()

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

static

Definition at line 384 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 127 of file ortho.c.

References B_DOWN, B_LEFT, B_NODE, B_RIGHT, B_UP, cell::bb, cellOf(), snode::cells, IsNode, snode::isVert, LIST, LIST_APPEND, LIST_DETACH, 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 1326 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 519 of file ortho.c.

References dtflatten(), dtlink, channel::G, LIST_SIZE, 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 264 of file ortho.c.

References fcmp().

Here is the call graph for this function:

decide_point()

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

static

Definition at line 746 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 477 of file ortho.c.

References vertex::adj_list, channel::G, LIST_GET, LIST_IS_EMPTY, LIST_SIZE, 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 1133 of file ortho.c.

References epair_t::d.

Referenced by orthoEdges().

Here is the caller graph for this function:

edgeLen()

static double edgeLen ( Agedge_t *  e )

static

Definition at line 1127 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 560 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 1344 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 1430 of file ortho.c.

References cell::bb, bbox(), maze::cells, emitEdge(), 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 1406 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 536 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 305 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 341 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 235 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 228 of file ortho.c.

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

Here is the call graph for this function:

htrack()

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

static

Definition at line 1060 of file ortho.c.

References cell::bb, chanSearch(), channel::cp, maze::hchans, LIST_SIZE, boxf::LL, OPTIONAL_VALUE, channel::seg_list, 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 377 of file ortho.c.

References LIST_APPEND, LIST_SIZE, OPTIONAL_SET, and channel::seg_list.

Referenced by assignSegs().

Here is the caller graph for this function:

is_parallel()

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

static

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

MID()

static double MID ( double  a, double  b  )

static

Definition at line 58 of file ortho.c.

Referenced by sidePt().

Here is the caller graph for this function:

midPt()

static pointf midPt ( const cell *  cp )

static

Definition at line 73 of file ortho.c.

References cell::bb, boxf::LL, mid_pointf(), and boxf::UR.

Referenced by convertSPtoRoute(), and emitSearchGraph().

Here is the call graph for this function:

Here is the caller graph for this function:

next_seg()

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

static

Definition at line 696 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 1162 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(), reset(), textlabel_t::set, maze::sg, shortPath(), sinfo, spline_merge(), swap_ends_p(), 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 ( const segment  S1, const segment  S2, bend  T1, bend  T2  )

static

Definition at line 544 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 ( const segment  seg, int  prec, int  hops, int  dir  )

static

Definition at line 705 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 467 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 893 of file ortho.c.

References chanSearch(), channel::G, maze::hchans, is_parallel(), segment::isVert, next_seg(), OPTIONAL_VALUE, 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 ( const segment  S1, const segment  S2  )

static

Definition at line 646 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 ( const segment  S1, const segment  S2, bend  T1, bend  T2  )

static

Definition at line 569 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 779 of file ortho.c.

References B_LEFT, B_UP, chanSearch(), segment::comm_coord, edge_exists(), channel::G, maze::hchans, insert_edge(), segment::isVert, segment::l1, segment::l2, next_seg(), OPTIONAL_VALUE, 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 segment setSeg ( bool  dir, double  fix, double  b1, double  b2, int  l1, int  l2  )

static

Definition at line 99 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 ( const snode  ptr, const cell *  cp  )

static

Definition at line 81 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 call graph for this function:

Here is the caller graph for this function:

spline_merge()

static bool spline_merge ( node_t *  n )

static

Definition at line 1145 of file ortho.c.

Referenced by orthoEdges().

Here is the caller graph for this function:

swap_ends_p()

static bool swap_ends_p ( edge_t *  e )

static

Definition at line 1151 of file ortho.c.

Referenced by orthoEdges().

Here is the caller graph for this function:

vtrack()

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

static

Definition at line 1051 of file ortho.c.

References cell::bb, chanSearch(), channel::cp, interpolate_pointf(), LIST_SIZE, boxf::LL, OPTIONAL_VALUE, channel::seg_list, 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 270 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 279 of file ortho.c.

Referenced by extractHChans(), and extractVChans().

odb_flags

int odb_flags

Definition at line 53 of file ortho.c.

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

prolog2

const char prolog2[]

static

Definition at line 1294 of file ortho.c.

Referenced by emitGraph().