Graphviz: lib/common/routespl.c File Reference

Searching...

No Matches

#include "config.h"
#include <assert.h>
#include <cgraph/agxbuf.h>
#include <cgraph/alloc.h>
#include <cgraph/gv_math.h>
#include <cgraph/list.h>
#include <cgraph/prisize_t.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 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 911 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 769 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 817 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 787 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 843 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 862 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 749 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 882 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 789 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 934 of file routespl.c.

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

Referenced by _spline_edges(), and genroute().

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 953 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 760 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 734 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

◆ routeinit

int routeinit

static

Definition at line 34 of file routespl.c.

Referenced by routesplinesinit(), and routesplinesterm().

Macros

Functions

Variables

Macro Definition Documentation

◆ FUDGE

◆ INIT_DELTA

◆ LOOP_TRIES

Function Documentation

◆ bend()

◆ checkpath()

◆ cycle_contains_edge()

◆ dfs()

◆ eq()

◆ find_all_cycles()

◆ find_shortest_cycle_with_edge()

◆ get_centroid()

◆ get_cycle_centroid()

◆ is_cycle_unique()

◆ limitBoxes()

◆ makeStraightEdge()

◆ makeStraightEdges()

◆ nodes_delete()

◆ overlap()

◆ printpath()

◆ routepolylines()

◆ routesplines()

◆ routesplines_()

◆ routesplinesinit()

◆ routesplinesterm()

◆ simpleSplineRoute()

Variable Documentation

◆ nboxes

◆ nedges

◆ routeinit