routespl.c File Reference

#include "config.h"
#include <assert.h>
#include <common/geomprocs.h>
#include <common/render.h>
#include <float.h>
#include <limits.h>
#include <math.h>
#include <pathplan/pathplan.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <util/agxbuf.h>
#include <util/alloc.h>
#include <util/gv_math.h>
#include <util/list.h>
#include <util/prisize_t.h>

Include dependency graph for routespl.c:

Go to the source code of this file.

Macros
#define	FUDGE   .0001
#define	INIT_DELTA   10
#define	LOOP_TRIES   15 /* number of times to try to limiting boxes to regain space, using smaller divisions */

Functions
static int	checkpath (size_t, boxf *, path *)
static void	printpath (path *pp)
pointf *	simpleSplineRoute (pointf tp, pointf hp, Ppoly_t poly, size_t *n_spl_pts, int polyline)
	Given a simple (ccw) polygon, route an edge from tp to hp.
int	routesplinesinit (void)
void	routesplinesterm (void)
static void	limitBoxes (boxf *boxes, size_t boxn, const pointf *pps, size_t pn, double delta)
static pointf *	routesplines_ (path *pp, size_t *npoints, int polyline)
pointf *	routesplines (path *pp, size_t *npoints)
pointf *	routepolylines (path *pp, size_t *npoints)
static double	overlap (double i0, double i1, double j0, double j1)
static pointf	get_centroid (Agraph_t *g)
static void	nodes_delete (nodes_t *pvec)
static bool	cycle_contains_edge (nodes_t *cycle, edge_t *edge)
static bool	eq (const node_t *a, const node_t *b)
static bool	is_cycle_unique (cycles_t *cycles, nodes_t *cycle)
static void	dfs (graph_t *g, node_t *search, nodes_t *visited, node_t *end, cycles_t *cycles)
static cycles_t	find_all_cycles (graph_t *g)
static nodes_t *	find_shortest_cycle_with_edge (cycles_t *cycles, edge_t *edge, size_t min_size)
static pointf	get_cycle_centroid (graph_t *g, edge_t *edge)
static void	bend (pointf spl[4], pointf centroid)
void	makeStraightEdge (graph_t *g, edge_t *e, int et, splineInfo *sinfo)
void	makeStraightEdges (graph_t *g, edge_t **edge_list, size_t e_cnt, int et, splineInfo *sinfo)

Variables
static int	nedges
	total no. of edges used in routing
static size_t	nboxes
	total no. of boxes used in routing
static int	routeinit

Macro Definition Documentation

FUDGE

#define FUDGE   .0001

INIT_DELTA

#define INIT_DELTA   10

Definition at line 280 of file routespl.c.

LOOP_TRIES

#define LOOP_TRIES   15 /* number of times to try to limiting boxes to regain space, using smaller divisions */

Definition at line 281 of file routespl.c.

Function Documentation

bend()

static void bend ( pointf  spl[4], pointf  centroid  )

static

Definition at line 903 of file routespl.c.

References dist(), DIST, mid_pointf(), pointf_s::x, and pointf_s::y.

Here is the call graph for this function:

checkpath()

static int checkpath ( size_t  boxn, boxf *  boxes, path *  thepath  )

static

Definition at line 603 of file routespl.c.

References agerrorf(), path::end, boxf::LL, overlap(), port::p, printpath(), PRISIZE_T, path::start, boxf::UR, Verbose, pointf_s::x, and pointf_s::y.

Referenced by routesplines_().

Here is the call graph for this function:

Here is the caller graph for this function:

cycle_contains_edge()

static bool cycle_contains_edge ( nodes_t *  cycle, edge_t *  edge  )

static

Definition at line 761 of file routespl.c.

References aghead, agtail, and edge.

Referenced by find_shortest_cycle_with_edge().

Here is the caller graph for this function:

dfs()

static void dfs ( graph_t *  g, node_t *  search, nodes_t *  visited, node_t *  end, cycles_t *  cycles  )

static

Definition at line 809 of file routespl.c.

References agfstout(), aghead, agnxtout(), dfs(), eq(), gv_alloc(), and is_cycle_unique().

Referenced by dfs(), and find_all_cycles().

Here is the call graph for this function:

Here is the caller graph for this function:

eq()

static bool eq ( const node_t *  a, const node_t *  b  )

static

Definition at line 779 of file routespl.c.

Referenced by dfs(), and is_cycle_unique().

Here is the caller graph for this function:

find_all_cycles()

static cycles_t find_all_cycles ( graph_t *  g )

static

Definition at line 835 of file routespl.c.

References agfstnode(), agnxtnode(), dfs(), and gv_alloc().

Referenced by get_cycle_centroid().

Here is the call graph for this function:

Here is the caller graph for this function:

find_shortest_cycle_with_edge()

static nodes_t * find_shortest_cycle_with_edge ( cycles_t *  cycles, edge_t *  edge, size_t  min_size  )

static

Definition at line 854 of file routespl.c.

References cycle_contains_edge(), edge, and NULL.

Referenced by get_cycle_centroid().

Here is the call graph for this function:

Here is the caller graph for this function:

get_centroid()

static pointf get_centroid ( Agraph_t *  g )

static

Definition at line 741 of file routespl.c.

References GD_bb, pointf_s::x, and pointf_s::y.

Referenced by get_cycle_centroid().

Here is the caller graph for this function:

get_cycle_centroid()

static pointf get_cycle_centroid ( graph_t *  g, edge_t *  edge  )

static

Definition at line 874 of file routespl.c.

References cnt(), edge, find_all_cycles(), find_shortest_cycle_with_edge(), get_centroid(), ND_coord, NULL, pointf_s::x, and pointf_s::y.

Referenced by makeStraightEdges().

Here is the call graph for this function:

Here is the caller graph for this function:

is_cycle_unique()

static bool is_cycle_unique ( cycles_t *  cycles, nodes_t *  cycle  )

static

Definition at line 781 of file routespl.c.

References eq().

Referenced by dfs().

Here is the call graph for this function:

Here is the caller graph for this function:

limitBoxes()

static void limitBoxes ( boxf *  boxes, size_t  boxn, const pointf *  pps, size_t  pn, double  delta  )

static

Definition at line 242 of file routespl.c.

References delta, FUDGE, boxf::LL, boxf::UR, pointf_s::x, and pointf_s::y.

Referenced by routesplines_().

Here is the caller graph for this function:

makeStraightEdge()

void makeStraightEdge	(	graph_t *	g,
		edge_t *	e,
		int	et,
		splineInfo *	sinfo
	)

Definition at line 926 of file routespl.c.

References ED_to_virt, free(), gv_calloc(), makeStraightEdges(), and sinfo.

Referenced by genroute(), and spline_edges_().

Here is the call graph for this function:

Here is the caller graph for this function:

makeStraightEdges()

void makeStraightEdges	(	graph_t *	g,
		edge_t **	edge_list,
		size_t	e_cnt,
		int	et,
		splineInfo *	sinfo
	)

Definition at line 945 of file routespl.c.

References add_pointf(), addEdgeLabels(), aghead, agtail, APPROXEQPT, clip_and_install(), Concentrate, del(), dx, ED_head_port, ED_tail_port, EDGETYPE_CURVED, EDGETYPE_PLINE, GD_nodesep, get_cycle_centroid(), head, make_polyline(), MILLIPOINT, ND_coord, perp(), Ppoly_t::pn, Ppoly_t::ps, Agraph_s::root, sinfo, pointf_s::x, and pointf_s::y.

Referenced by dot_splines_(), and makeStraightEdge().

Here is the call graph for this function:

Here is the caller graph for this function:

nodes_delete()

static void nodes_delete ( nodes_t *  pvec )

static

Definition at line 752 of file routespl.c.

References free(), and NULL.

Here is the call graph for this function:

overlap()

static double overlap ( double  i0, double  i1, double  j0, double  j1  )

static

Definition at line 574 of file routespl.c.

Referenced by arrow_length_crow(), arrow_length_diamond(), arrow_length_normal(), and checkpath().

Here is the caller graph for this function:

printpath()

static void printpath ( path *  pp )

static

Definition at line 726 of file routespl.c.

References path::boxes, port::constrained, path::end, boxf::LL, path::nbox, port::p, PRISIZE_T, path::start, port::theta, boxf::UR, pointf_s::x, and pointf_s::y.

Referenced by checkpath().

Here is the caller graph for this function:

routepolylines()

pointf * routepolylines	(	path *	pp,
		size_t *	npoints
	)

Definition at line 570 of file routespl.c.

References routesplines_().

Referenced by make_flat_bottom_edges(), make_flat_edge(), make_flat_labeled_edge(), and make_regular_edge().

Here is the call graph for this function:

Here is the caller graph for this function:

routesplines()

pointf * routesplines	(	path *	pp,
		size_t *	npoints
	)

Definition at line 566 of file routespl.c.

References routesplines_().

Referenced by make_flat_bottom_edges(), make_flat_edge(), make_flat_labeled_edge(), and make_regular_edge().

Here is the call graph for this function:

Here is the caller graph for this function:

routesplines_()

static pointf * routesplines_ ( path *  pp, size_t *  npoints, int  polyline  )

static

Route a path using the path info in pp. This includes start and end points plus a collection of contiguous boxes contain the terminal points. The boxes are converted into a containing polygon. A shortest path is constructed within the polygon from between the terminal points. If polyline is true, this path is converted to a spline representation. Otherwise, we call the path planner to convert the polyline into a smooth spline staying within the polygon. In both cases, the function returns an array of the computed control points. The number of these points is given in npoints.

Note that the returned points are stored in a single array, so the points must be used before another call to this function.

During cleanup, the function determines the x-extent of the spline in the box, so the box can be shrunk to the minimum width. The extra space can then be used by other edges.

If a catastrophic error, return NULL and npoints is 0.

Definition at line 301 of file routespl.c.

References Pedge_t::a, agerrorf(), aghead, agnameof(), agraphof(), agtail, agwarningf(), Pedge_t::b, path::boxes, checkpath(), port::constrained, path::data, delta, ED_edge_type, ED_showboxes, ED_to_orig, path::end, free(), GD_showboxes, gv_calloc(), INIT_DELTA, is_exactly_equal(), limitBoxes(), boxf::LL, LOOP_TRIES, make_polyline(), path::nbox, nboxes, ND_showboxes, nedges, NORMAL, NULL, port::p, Ppoly_t::pn, prev, Proutespline(), ps, Ppoly_t::ps, Pshortestpath(), SIZE_MAX, path::start, port::theta, boxf::UR, pointf_s::x, Pxy_t::x, pointf_s::y, and Pxy_t::y.

Referenced by routepolylines(), and routesplines().

Here is the call graph for this function:

Here is the caller graph for this function:

routesplinesinit()

int routesplinesinit

(

void

)

Data initialized once until matching call to routeplineterm Allows recursive calls to dot

Definition at line 220 of file routespl.c.

References nboxes, nedges, routeinit, Show_boxes, start_timer(), and Verbose.

Referenced by dot_splines_().

Here is the call graph for this function:

Here is the caller graph for this function:

routesplinesterm()

void routesplinesterm

(

void

)

Definition at line 233 of file routespl.c.

References elapsed_sec(), nboxes, nedges, PRISIZE_T, routeinit, and Verbose.

Referenced by dot_splines_().

Here is the call graph for this function:

Here is the caller graph for this function:

simpleSplineRoute()

pointf * simpleSplineRoute	(	pointf	tp,
		pointf	hp,
		Ppoly_t	poly,
		size_t *	n_spl_pts,
		int	polyline
	)

Definition at line 173 of file routespl.c.

References Pedge_t::a, agerrorf(), Pedge_t::b, free(), gv_calloc(), make_polyline(), NULL, Ppoly_t::pn, Proutespline(), ps, Ppoly_t::ps, Pshortestpath(), pointf_s::x, Pxy_t::x, pointf_s::y, and Pxy_t::y.

Referenced by makeSimpleFlatLabels().

Here is the call graph for this function:

Here is the caller graph for this function:

Variable Documentation

nboxes

size_t nboxes

static

Definition at line 32 of file routespl.c.

Referenced by routesplines_(), routesplinesinit(), and routesplinesterm().

nedges

int nedges

static

Definition at line 31 of file routespl.c.

Referenced by attached_clustering(), coarsen_match(), compute_apsp_artificial_weights_packed(), compute_new_weights(), constructSierpinski(), constructTetrix(), cpExGraph(), cpGraph(), create_hierarchy(), delaunay_tri(), graphSize(), Import_coord_clusters_from_dot(), Import_dot_splines(), init_ex_graph(), make_coarse_ex_graph(), make_coarse_graph(), makeGraph(), makeGraphData(), makeMatrix(), maxmatch(), mult_sparse_dense_mat_transpose(), nop_init_edges(), routesplines_(), routesplinesinit(), routesplinesterm(), sparse_stress_subspace_majorization_kD(), SparseMatrix_import_dot(), wcp(), and x_layout().

routeinit

int routeinit

static

Definition at line 34 of file routespl.c.

Referenced by routesplinesinit(), and routesplinesterm().