Places node boxes in replacement areas of orthogonal drawing step and route edges to minimize bends. More...

#include <ogdf/orthogonal/EdgeRouter.h>

Public Member Functions
	EdgeRouter ()

	EdgeRouter (PlanRep &pru, OrthoRep &H, GridLayoutMapped &L, CombinatorialEmbedding &E, RoutingChannel< int > &rou, MinimumEdgeDistances< int > &med, NodeArray< int > &nodewidth, NodeArray< int > &nodeheight)

virtual	~EdgeRouter ()

void	addbends (BendString &bs, const char *s2)

edge	addLeftBend (edge e)

edge	addRightBend (edge e)

void	align (bool b)
	set alignment option: place nodes in cage at outgoing generalization

void	call ()
	places nodes in cages and routes incident edges

void	call (PlanRep &pru, OrthoRep &H, GridLayoutMapped &L, CombinatorialEmbedding &E, RoutingChannel< int > &rou, MinimumEdgeDistances< int > &med, NodeArray< int > &nodewidth, NodeArray< int > &nodeheight, bool align=false)
	places nodes in cages and routes incident edges

void	compute_gen_glue_points_x (node v)
	compute glue points positions

void	compute_gen_glue_points_y (node v)
	compute glue points positions

void	compute_glue_points_x (node &v)
	compute glue points positions

void	compute_glue_points_y (node v)
	compute glue points positions

void	compute_place (node v, NodeInfo &inf)
	computes placement

void	compute_routing (node v)
	computes routing after compute_place

int	cp_x (adjEntry ae)
	Returns assigned connection point (cage border) x-coordinate of `ae` 's source.

int	cp_y (adjEntry ae)
	Returns assigned connection point (cage border) y-coordinate of `ae` 's source.

void	fix_position (node v, int x=0, int y=0)
	same as set but updates m_fixed, coordinates cant be changed afterwards

int	gp_x (adjEntry ae)
	Returns assigned glue point (node border) x-coordinate.

int	gp_y (adjEntry ae)
	Returns assigned glue point (node border) y-coordinate.

adjEntry	inEntry (NodeInfo &inf, OrthoDir d, int pos)
	adjEntries for edges in inLists

void	init (PlanRep &pru, RoutingChannel< int > &rou, bool align=false)

void	initialize_node_info (node v, int sep)
	sets values derivable from input

void	multiDelta ()
	for all multiple edges, set the delta value on both sides to minimum if not m_minDelta

adjEntry	outEntry (NodeInfo &inf, OrthoDir d, int pos)
	adjEntries for edges in inLists

void	place (node v)
	applies precomputed placement

void	set_position (node v, int x=0, int y=0)
	sets position for node v in layout to value x,y, invoked to have central control over change

void	setDistances ()
	sets the computed distances in structure MinimumEdgeDistance m_med

Private Types
enum class	BendType { BendFree , Bend1Left , Bend1Right , Bend2Left , Bend2Right , ProbBf , ProbB1L , ProbB1R , ProbB2L , ProbB2R }
	Edge types, defined by necessary bends. More...

using	NodeInfo = edge_router::NodeInfo

enum class	ProcessType { unprocessed , processed , used }
	Process status of nodes. More...

Private Member Functions
BendType	abendType (adjEntry ae)

int	alpha_move (OrthoDir s_to, OrthoDir s_from, node v)
	computes the alpha value described in the paper

int	beta_move (OrthoDir s_from, OrthoDir s_to, int move_num, node v)
	computes the beta value described in the paper

int	compute_move (OrthoDir s_from, OrthoDir s_to, int &kflip, node v)
	compute the maximum number of moveable edges

bool	oppositeExpander (adjEntry ae)
	check if the target node of the outgoing adjEntry still is a expander

node	oppositeNode (adjEntry ae)
	helper for oppositeExpander

void	set_corners (node v)
	set coordinates of cage corners after placement

void	unsplit (edge e1, edge e2)

int	updateBends (const node v, ListIterator< edge > &it, const bool updateX, const OrthoDir dir, const bool bendLeft, const bool bendUp, int pos=0)

void	updateBends (const node v, ListIterator< edge > &it, int &pos, int &lastunbend, const bool updateX, const OrthoDir dir, const bool bendLeft, const bool bendUp, const bool subtract)

void	updateLowerEdgesBends (const node v, ListIterator< edge > &it, int &pos, int &base, const bool updateX, const OrthoDir dir, const bool bendLeft)

void	updateOneBend (const bool isDoubleBend, const adjEntry adj, const node v, const OrthoDir dir, const bool bendLeft, const BendType btSingle, const BendType btDouble)

Private Attributes
AdjEntryArray< int >	alefte

AdjEntryArray< int >	alowe

AdjEntryArray< int >	arighte

AdjEntryArray< int >	auppe

double	Cconst
	relative sep to overhang / delta to eps

NodeArray< NodeInfo >	infos
	holds the cage and placement information

EdgeArray< int >	lefte

EdgeArray< int >	lowe

AdjEntryArray< BendType >	m_abends
	bends

AdjEntryArray< int >	m_acp_x

AdjEntryArray< int >	m_acp_y
	edge connection point coordinates before treatment

AdjEntryArray< int >	m_agp_x

AdjEntryArray< int >	m_agp_y
	because edges can connect two replacement cages

bool	m_align

AdjEntryArray< node >	m_cage_point
	newly introduced bends destroy edge to point connection

CombinatorialEmbedding *	m_comb

NodeArray< bool >	m_fixed
	saves info about changed position, no further change is allowed

GridLayoutMapped *	m_layoutp

MinimumEdgeDistances< int > *	m_med

NodeArray< OrthoDir >	m_mergeDir
	direction of adjacent (to) merger edges

NodeArray< bool >	m_mergerSon
	is part of merger son cage

bool	m_minDelta
	set minimum delta values for flip decision and adjust distances correspondingly

NodeArray< int >	m_newx

NodeArray< int >	m_newy
	new placement position for original node

NodeArray< int > *	m_nodeheight

NodeArray< int > *	m_nodewidth

NodeArray< BendType >	m_oppositeBendType
	keep the information about the type of bend inserted at one end of an (originally unbend) edge, so that we can check possible bendsaving

OrthoRep *	m_orp

int	m_overh
	minimum overhang

NodeArray< ProcessType >	m_processStatus
	keep information about already processed Nodes

PlanRep *	m_prup

RoutingChannel< int > *	m_rc

int	m_sep
	minimum separation

EdgeArray< int >	righte
	max box borders for bendfree edges

EdgeArray< int >	uppe

Detailed Description

Places node boxes in replacement areas of orthogonal drawing step and route edges to minimize bends.

Definition at line 52 of file EdgeRouter.h.

Member Typedef Documentation

◆ NodeInfo

using ogdf::EdgeRouter::NodeInfo = edge_router::NodeInfo

private

Definition at line 53 of file EdgeRouter.h.

Member Enumeration Documentation

◆ BendType

enum class ogdf::EdgeRouter::BendType

strongprivate

Edge types, defined by necessary bends.

Enumerator
BendFree	No resulting bends.
Bend1Left	One resulting bend to the left.
Bend1Right	One resulting bend to the right.
Bend2Left	Two resulting bends to the left.
Bend2Right	Two resulting bends to the right.
ProbBf	No preliminary bends.
ProbB1L	One preliminary bend to the left.
ProbB1R	One preliminary bend to the right.
ProbB2L	Two preliminary bends to the left.
ProbB2R	Two preliminary bends to the right.

Definition at line 163 of file EdgeRouter.h.

◆ ProcessType

enum class ogdf::EdgeRouter::ProcessType

strongprivate

Process status of nodes.

Enumerator
unprocessed	unprocessed
processed	processed in degree-1 preprocessing
used	used by degree-1

Definition at line 187 of file EdgeRouter.h.

Constructor & Destructor Documentation

◆ EdgeRouter() [1/2]

ogdf::EdgeRouter::EdgeRouter ( )

inline

Definition at line 57 of file EdgeRouter.h.

◆ EdgeRouter() [2/2]

ogdf::EdgeRouter::EdgeRouter	(	PlanRep &	pru,
		OrthoRep &	H,
		GridLayoutMapped &	L,
		CombinatorialEmbedding &	E,
		RoutingChannel< int > &	rou,
		MinimumEdgeDistances< int > &	med,
		NodeArray< int > &	nodewidth,
		NodeArray< int > &	nodeheight
	)

◆ ~EdgeRouter()

virtual ogdf::EdgeRouter::~EdgeRouter ( )

inlinevirtual

Definition at line 63 of file EdgeRouter.h.

Member Function Documentation

◆ abendType()

BendType ogdf::EdgeRouter::abendType ( adjEntry ae )

inlineprivate

Definition at line 211 of file EdgeRouter.h.

◆ addbends()

void ogdf::EdgeRouter::addbends	(	BendString &	bs,
		const char *	s2
	)

◆ addLeftBend()

edge ogdf::EdgeRouter::addLeftBend ( edge e )

◆ addRightBend()

edge ogdf::EdgeRouter::addRightBend ( edge e )

◆ align()

void ogdf::EdgeRouter::align ( bool b )

inline

set alignment option: place nodes in cage at outgoing generalization

postprocessing function, hmm maybe preprocessing

Definition at line 154 of file EdgeRouter.h.

◆ alpha_move()

int ogdf::EdgeRouter::alpha_move	(	OrthoDir	s_to,
		OrthoDir	s_from,
		node	v
	)

private

computes the alpha value described in the paper

◆ beta_move()

int ogdf::EdgeRouter::beta_move	(	OrthoDir	s_from,
		OrthoDir	s_to,
		int	move_num,
		node	v
	)

private

computes the beta value described in the paper

number of additional bend free edges on side s_from if move_num edges are moved from side s_from to s_to

◆ call() [1/2]

void ogdf::EdgeRouter::call ( )

places nodes in cages and routes incident edges

◆ call() [2/2]

void ogdf::EdgeRouter::call	(	PlanRep &	pru,
		OrthoRep &	H,
		GridLayoutMapped &	L,
		CombinatorialEmbedding &	E,
		RoutingChannel< int > &	rou,
		MinimumEdgeDistances< int > &	med,
		NodeArray< int > &	nodewidth,
		NodeArray< int > &	nodeheight,
		bool	align = `false`
	)

places nodes in cages and routes incident edges

◆ compute_gen_glue_points_x()

void ogdf::EdgeRouter::compute_gen_glue_points_x ( node v )

compute glue points positions

◆ compute_gen_glue_points_y()

void ogdf::EdgeRouter::compute_gen_glue_points_y ( node v )

compute glue points positions

◆ compute_glue_points_x()

void ogdf::EdgeRouter::compute_glue_points_x ( node & v )

compute glue points positions

◆ compute_glue_points_y()

void ogdf::EdgeRouter::compute_glue_points_y ( node v )

compute glue points positions

◆ compute_move()

int ogdf::EdgeRouter::compute_move	(	OrthoDir	s_from,
		OrthoDir	s_to,
		int &	kflip,
		node	v
	)

private

compute the maximum number of moveable edges

dependant on space on available edges, return number of saved bends

◆ compute_place()

void ogdf::EdgeRouter::compute_place	(	node	v,
		NodeInfo &	inf
	)

computes placement

◆ compute_routing()

void ogdf::EdgeRouter::compute_routing ( node v )

computes routing after compute_place

◆ cp_x()

int ogdf::EdgeRouter::cp_x ( adjEntry ae )

inline

Returns assigned connection point (cage border) x-coordinate of ae 's source.

Definition at line 103 of file EdgeRouter.h.

◆ cp_y()

int ogdf::EdgeRouter::cp_y ( adjEntry ae )

inline

Returns assigned connection point (cage border) y-coordinate of ae 's source.

Definition at line 106 of file EdgeRouter.h.

◆ fix_position()

void ogdf::EdgeRouter::fix_position	(	node	v,
		int	x = `0`,
		int	y = `0`
	)

same as set but updates m_fixed, coordinates cant be changed afterwards

◆ gp_x()

int ogdf::EdgeRouter::gp_x ( adjEntry ae )

inline

Returns assigned glue point (node border) x-coordinate.

Definition at line 109 of file EdgeRouter.h.

◆ gp_y()

int ogdf::EdgeRouter::gp_y ( adjEntry ae )

inline

Returns assigned glue point (node border) y-coordinate.

Definition at line 112 of file EdgeRouter.h.

◆ inEntry()

adjEntry ogdf::EdgeRouter::inEntry	(	NodeInfo &	inf,
		OrthoDir	d,
		int	pos
	)

inline

adjEntries for edges in inLists

Definition at line 130 of file EdgeRouter.h.

◆ init()

void ogdf::EdgeRouter::init	(	PlanRep &	pru,
		RoutingChannel< int > &	rou,
		bool	align = `false`
	)

◆ initialize_node_info()

void ogdf::EdgeRouter::initialize_node_info	(	node	v,
		int	sep
	)

sets values derivable from input

◆ multiDelta()

void ogdf::EdgeRouter::multiDelta ( )

for all multiple edges, set the delta value on both sides to minimum if not m_minDelta

postprocessing function, hmm maybe preprocessing

◆ oppositeExpander()

bool ogdf::EdgeRouter::oppositeExpander ( adjEntry ae )

inlineprivate

check if the target node of the outgoing adjEntry still is a expander

Definition at line 228 of file EdgeRouter.h.

◆ oppositeNode()

node ogdf::EdgeRouter::oppositeNode ( adjEntry ae )

inlineprivate

helper for oppositeExpander

Definition at line 225 of file EdgeRouter.h.

◆ outEntry()

adjEntry ogdf::EdgeRouter::outEntry	(	NodeInfo &	inf,
		OrthoDir	d,
		int	pos
	)

inline

adjEntries for edges in inLists

Definition at line 121 of file EdgeRouter.h.

◆ place()

void ogdf::EdgeRouter::place ( node v )

applies precomputed placement

◆ set_corners()

void ogdf::EdgeRouter::set_corners ( node v )

private

set coordinates of cage corners after placement

◆ set_position()

void ogdf::EdgeRouter::set_position	(	node	v,
		int	x = `0`,
		int	y = `0`
	)

sets position for node v in layout to value x,y, invoked to have central control over change

◆ setDistances()

void ogdf::EdgeRouter::setDistances ( )

sets the computed distances in structure MinimumEdgeDistance m_med

◆ unsplit()

void ogdf::EdgeRouter::unsplit	(	edge	e1,
		edge	e2
	)

private

◆ updateBends() [1/2]

int ogdf::EdgeRouter::updateBends	(	const node	v,
		ListIterator< edge > &	it,
		const bool	updateX,
		const OrthoDir	dir,
		const bool	bendLeft,
		const bool	bendUp,
		int	pos = `0`
	)

private

◆ updateBends() [2/2]

void ogdf::EdgeRouter::updateBends	(	const node	v,
		ListIterator< edge > &	it,
		int &	pos,
		int &	lastunbend,
		const bool	updateX,
		const OrthoDir	dir,
		const bool	bendLeft,
		const bool	bendUp,
		const bool	subtract
	)

private

◆ updateLowerEdgesBends()

void ogdf::EdgeRouter::updateLowerEdgesBends	(	const node	v,
		ListIterator< edge > &	it,
		int &	pos,
		int &	base,
		const bool	updateX,
		const OrthoDir	dir,
		const bool	bendLeft
	)

private

◆ updateOneBend()

void ogdf::EdgeRouter::updateOneBend	(	const bool	isDoubleBend,
		const adjEntry	adj,
		const node	v,
		const OrthoDir	dir,
		const bool	bendLeft,
		const BendType	btSingle,
		const BendType	btDouble
	)

inlineprivate

Definition at line 259 of file EdgeRouter.h.

Member Data Documentation

◆ alefte

AdjEntryArray<int> ogdf::EdgeRouter::alefte

private

Definition at line 278 of file EdgeRouter.h.

◆ alowe

AdjEntryArray<int> ogdf::EdgeRouter::alowe

private

Definition at line 278 of file EdgeRouter.h.

◆ arighte

AdjEntryArray<int> ogdf::EdgeRouter::arighte

private

Definition at line 278 of file EdgeRouter.h.

◆ auppe

AdjEntryArray<int> ogdf::EdgeRouter::auppe

private

Definition at line 278 of file EdgeRouter.h.

◆ Cconst

double ogdf::EdgeRouter::Cconst

private

relative sep to overhang / delta to eps

Definition at line 209 of file EdgeRouter.h.

◆ infos

NodeArray<NodeInfo> ogdf::EdgeRouter::infos

private

holds the cage and placement information

Definition at line 205 of file EdgeRouter.h.

◆ lefte

EdgeArray<int> ogdf::EdgeRouter::lefte

private

Definition at line 277 of file EdgeRouter.h.

◆ lowe

EdgeArray<int> ogdf::EdgeRouter::lowe

private

Definition at line 277 of file EdgeRouter.h.

◆ m_abends

AdjEntryArray<BendType> ogdf::EdgeRouter::m_abends

private

bends

0 = bendfree, 1 = single bend from left to node, 2 = single from right, 3 = int from left, 4 = int from right,...

Definition at line 289 of file EdgeRouter.h.

◆ m_acp_x

AdjEntryArray<int> ogdf::EdgeRouter::m_acp_x

private

Definition at line 281 of file EdgeRouter.h.

◆ m_acp_y

AdjEntryArray<int> ogdf::EdgeRouter::m_acp_y

private

edge connection point coordinates before treatment

Definition at line 281 of file EdgeRouter.h.

◆ m_agp_x

AdjEntryArray<int> ogdf::EdgeRouter::m_agp_x

private

Definition at line 279 of file EdgeRouter.h.

◆ m_agp_y

AdjEntryArray<int> ogdf::EdgeRouter::m_agp_y

private

because edges can connect two replacement cages

Definition at line 279 of file EdgeRouter.h.

◆ m_align

bool ogdf::EdgeRouter::m_align

private

Definition at line 300 of file EdgeRouter.h.

◆ m_cage_point

AdjEntryArray<node> ogdf::EdgeRouter::m_cage_point

private

newly introduced bends destroy edge to point connection

Definition at line 280 of file EdgeRouter.h.

◆ m_comb

CombinatorialEmbedding* ogdf::EdgeRouter::m_comb

private

Definition at line 199 of file EdgeRouter.h.

◆ m_fixed

NodeArray<bool> ogdf::EdgeRouter::m_fixed

private

saves info about changed position, no further change is allowed

Definition at line 276 of file EdgeRouter.h.

◆ m_layoutp

GridLayoutMapped* ogdf::EdgeRouter::m_layoutp

private

Definition at line 197 of file EdgeRouter.h.

◆ m_med

MinimumEdgeDistances<int>* ogdf::EdgeRouter::m_med

private

Definition at line 201 of file EdgeRouter.h.

◆ m_mergeDir

NodeArray<OrthoDir> ogdf::EdgeRouter::m_mergeDir

private

direction of adjacent (to) merger edges

Definition at line 299 of file EdgeRouter.h.

◆ m_mergerSon

NodeArray<bool> ogdf::EdgeRouter::m_mergerSon

private

is part of merger son cage

Definition at line 298 of file EdgeRouter.h.

◆ m_minDelta

bool ogdf::EdgeRouter::m_minDelta

private

set minimum delta values for flip decision and adjust distances correspondingly

Definition at line 222 of file EdgeRouter.h.

◆ m_newx

NodeArray<int> ogdf::EdgeRouter::m_newx

private

Definition at line 275 of file EdgeRouter.h.

◆ m_newy

NodeArray<int> ogdf::EdgeRouter::m_newy

private

new placement position for original node

Definition at line 275 of file EdgeRouter.h.

◆ m_nodeheight

NodeArray<int>* ogdf::EdgeRouter::m_nodeheight

private

Definition at line 203 of file EdgeRouter.h.

◆ m_nodewidth

NodeArray<int>* ogdf::EdgeRouter::m_nodewidth

private

Definition at line 202 of file EdgeRouter.h.

◆ m_oppositeBendType

NodeArray<BendType> ogdf::EdgeRouter::m_oppositeBendType

private

keep the information about the type of bend inserted at one end of an (originally unbend) edge, so that we can check possible bendsaving

Definition at line 292 of file EdgeRouter.h.

◆ m_orp

OrthoRep* ogdf::EdgeRouter::m_orp

private

Definition at line 198 of file EdgeRouter.h.

◆ m_overh

int ogdf::EdgeRouter::m_overh

private

minimum overhang

Definition at line 208 of file EdgeRouter.h.

◆ m_processStatus

NodeArray<ProcessType> ogdf::EdgeRouter::m_processStatus

private

keep information about already processed Nodes

Definition at line 295 of file EdgeRouter.h.

◆ m_prup

PlanRep* ogdf::EdgeRouter::m_prup

private

Definition at line 196 of file EdgeRouter.h.

◆ m_rc

RoutingChannel<int>* ogdf::EdgeRouter::m_rc

private

Definition at line 200 of file EdgeRouter.h.

◆ m_sep

int ogdf::EdgeRouter::m_sep

private

minimum separation

Definition at line 207 of file EdgeRouter.h.

◆ righte

EdgeArray<int> ogdf::EdgeRouter::righte

private

max box borders for bendfree edges

Definition at line 277 of file EdgeRouter.h.

◆ uppe

EdgeArray<int> ogdf::EdgeRouter::uppe

private

Definition at line 277 of file EdgeRouter.h.

The documentation for this class was generated from the following file:

include/ogdf/orthogonal/EdgeRouter.h

OpenGraph DrawingFramework

Public Member Functions

Private Types

Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ NodeInfo

Member Enumeration Documentation

◆ BendType

◆ ProcessType

Constructor & Destructor Documentation

◆ EdgeRouter() [1/2]

◆ EdgeRouter() [2/2]

◆ ~EdgeRouter()

Member Function Documentation

◆ abendType()

◆ addbends()

◆ addLeftBend()

◆ addRightBend()

◆ align()

◆ alpha_move()

◆ beta_move()

◆ call() [1/2]

◆ call() [2/2]

◆ compute_gen_glue_points_x()

◆ compute_gen_glue_points_y()

◆ compute_glue_points_x()

◆ compute_glue_points_y()

◆ compute_move()

◆ compute_place()

◆ compute_routing()

◆ cp_x()

◆ cp_y()

◆ fix_position()

◆ gp_x()

◆ gp_y()

◆ inEntry()

◆ init()

◆ initialize_node_info()

◆ multiDelta()

◆ oppositeExpander()

◆ oppositeNode()

◆ outEntry()

◆ place()

◆ set_corners()

◆ set_position()

◆ setDistances()

◆ unsplit()

◆ updateBends() [1/2]

◆ updateBends() [2/2]

◆ updateLowerEdgesBends()

◆ updateOneBend()

Member Data Documentation

◆ alefte

◆ alowe

◆ arighte

◆ auppe

◆ Cconst

◆ infos

◆ lefte

◆ lowe

◆ m_abends

◆ m_acp_x

◆ m_acp_y

◆ m_agp_x

◆ m_agp_y

◆ m_align

◆ m_cage_point

◆ m_comb

◆ m_fixed

◆ m_layoutp

◆ m_med

◆ m_mergeDir

◆ m_mergerSon

◆ m_minDelta

◆ m_newx

◆ m_newy

◆ m_nodeheight

◆ m_nodewidth

Open
Graph Drawing
Framework