Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::EdgeRouter Class Reference

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 More...
 
void call ()
 places nodes in cages and routes incident edges More...
 
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 More...
 
void compute_gen_glue_points_x (node v)
 compute glue points positions More...
 
void compute_gen_glue_points_y (node v)
 compute glue points positions More...
 
void compute_glue_points_x (node &v)
 compute glue points positions More...
 
void compute_glue_points_y (node v)
 compute glue points positions More...
 
void compute_place (node v, NodeInfo &inf)
 computes placement More...
 
void compute_routing (node v)
 computes routing after compute_place More...
 
int cp_x (adjEntry ae)
 Returns assigned connection point (cage border) x-coordinate of ae 's source. More...
 
int cp_y (adjEntry ae)
 Returns assigned connection point (cage border) y-coordinate of ae 's source. More...
 
void fix_position (node v, int x=0, int y=0)
 same as set but updates m_fixed, coordinates cant be changed afterwards More...
 
int gp_x (adjEntry ae)
 Returns assigned glue point (node border) x-coordinate. More...
 
int gp_y (adjEntry ae)
 Returns assigned glue point (node border) y-coordinate. More...
 
adjEntry inEntry (NodeInfo &inf, OrthoDir d, int pos)
 adjEntries for edges in inLists More...
 
void init (PlanRep &pru, RoutingChannel< int > &rou, bool align=false)
 
void initialize_node_info (node v, int sep)
 sets values derivable from input More...
 
void multiDelta ()
 for all multiple edges, set the delta value on both sides to minimum if not m_minDelta More...
 
adjEntry outEntry (NodeInfo &inf, OrthoDir d, int pos)
 adjEntries for edges in inLists More...
 
void place (node v)
 applies precomputed placement More...
 
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 More...
 
void setDistances ()
 sets the computed distances in structure MinimumEdgeDistance m_med More...
 

Private Types

enum  BendType { BendType::BendFree, BendType::Bend1Left, BendType::Bend1Right, BendType::Bend2Left, BendType::Bend2Right, BendType::ProbBf, BendType::ProbB1L, BendType::ProbB1R, BendType::ProbB2L, BendType::ProbB2R }
 Edge types, defined by necessary bends. More...
 
using NodeInfo = edge_router::NodeInfo
 
enum  ProcessType { ProcessType::unprocessed, ProcessType::processed, ProcessType::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 More...
 
int beta_move (OrthoDir s_from, OrthoDir s_to, int move_num, node v)
 computes the beta value described in the paper More...
 
int compute_move (OrthoDir s_from, OrthoDir s_to, int &kflip, node v)
 compute the maximum number of moveable edges More...
 
bool oppositeExpander (adjEntry ae)
 check if the target node of the outgoing adjEntry still is a expander More...
 
node oppositeNode (adjEntry ae)
 helper for oppositeExpander More...
 
void set_corners (node v)
 set coordinates of cage corners after placement More...
 
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 More...
 
NodeArray< NodeInfoinfos
 holds the cage and placement information More...
 
EdgeArray< int > lefte
 
EdgeArray< int > lowe
 
AdjEntryArray< BendTypem_abends
 bends More...
 
AdjEntryArray< int > m_acp_x
 
AdjEntryArray< int > m_acp_y
 edge connection point coordinates before treatment More...
 
AdjEntryArray< int > m_agp_x
 
AdjEntryArray< int > m_agp_y
 because edges can connect two replacement cages More...
 
bool m_align
 
AdjEntryArray< nodem_cage_point
 newly introduced bends destroy edge to point connection More...
 
CombinatorialEmbeddingm_comb
 
NodeArray< bool > m_fixed
 saves info about changed position, no further change is allowed More...
 
GridLayoutMappedm_layoutp
 
MinimumEdgeDistances< int > * m_med
 
NodeArray< OrthoDirm_mergeDir
 direction of adjacent (to) merger edges More...
 
NodeArray< bool > m_mergerSon
 is part of merger son cage More...
 
bool m_minDelta
 set minimum delta values for flip decision and adjust distances correspondingly More...
 
NodeArray< int > m_newx
 
NodeArray< int > m_newy
 new placement position for original node More...
 
NodeArray< int > * m_nodeheight
 
NodeArray< int > * m_nodewidth
 
NodeArray< BendTypem_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 More...
 
OrthoRepm_orp
 
int m_overh
 minimum overhang More...
 
NodeArray< ProcessTypem_processStatus
 keep information about already processed Nodes More...
 
PlanRepm_prup
 
RoutingChannel< int > * m_rc
 
int m_sep
 minimum separation More...
 
EdgeArray< int > righte
 max box borders for bendfree edges More...
 
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

Definition at line 54 of file EdgeRouter.h.

Member Enumeration Documentation

◆ BendType

enum 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 177 of file EdgeRouter.h.

◆ ProcessType

enum 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 201 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 69 of file EdgeRouter.h.

Member Function Documentation

◆ abendType()

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

Definition at line 225 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 168 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 119 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 122 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 125 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 128 of file EdgeRouter.h.

◆ inEntry()

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

adjEntries for edges in inLists

Definition at line 145 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 242 of file EdgeRouter.h.

◆ oppositeNode()

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

helper for oppositeExpander

Definition at line 239 of file EdgeRouter.h.

◆ outEntry()

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

adjEntries for edges in inLists

Definition at line 137 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 292 of file EdgeRouter.h.

Member Data Documentation

◆ alefte

AdjEntryArray<int> ogdf::EdgeRouter::alefte
private

Definition at line 317 of file EdgeRouter.h.

◆ alowe

AdjEntryArray<int> ogdf::EdgeRouter::alowe
private

Definition at line 317 of file EdgeRouter.h.

◆ arighte

AdjEntryArray<int> ogdf::EdgeRouter::arighte
private

Definition at line 317 of file EdgeRouter.h.

◆ auppe

AdjEntryArray<int> ogdf::EdgeRouter::auppe
private

Definition at line 317 of file EdgeRouter.h.

◆ Cconst

double ogdf::EdgeRouter::Cconst
private

relative sep to overhang / delta to eps

Definition at line 223 of file EdgeRouter.h.

◆ infos

NodeArray<NodeInfo> ogdf::EdgeRouter::infos
private

holds the cage and placement information

Definition at line 219 of file EdgeRouter.h.

◆ lefte

EdgeArray<int> ogdf::EdgeRouter::lefte
private

Definition at line 316 of file EdgeRouter.h.

◆ lowe

EdgeArray<int> ogdf::EdgeRouter::lowe
private

Definition at line 316 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 328 of file EdgeRouter.h.

◆ m_acp_x

AdjEntryArray<int> ogdf::EdgeRouter::m_acp_x
private

Definition at line 320 of file EdgeRouter.h.

◆ m_acp_y

AdjEntryArray<int> ogdf::EdgeRouter::m_acp_y
private

edge connection point coordinates before treatment

Definition at line 320 of file EdgeRouter.h.

◆ m_agp_x

AdjEntryArray<int> ogdf::EdgeRouter::m_agp_x
private

Definition at line 318 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 318 of file EdgeRouter.h.

◆ m_align

bool ogdf::EdgeRouter::m_align
private

Definition at line 339 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 319 of file EdgeRouter.h.

◆ m_comb

CombinatorialEmbedding* ogdf::EdgeRouter::m_comb
private

Definition at line 213 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 315 of file EdgeRouter.h.

◆ m_layoutp

GridLayoutMapped* ogdf::EdgeRouter::m_layoutp
private

Definition at line 211 of file EdgeRouter.h.

◆ m_med

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

Definition at line 215 of file EdgeRouter.h.

◆ m_mergeDir

NodeArray<OrthoDir> ogdf::EdgeRouter::m_mergeDir
private

direction of adjacent (to) merger edges

Definition at line 338 of file EdgeRouter.h.

◆ m_mergerSon

NodeArray<bool> ogdf::EdgeRouter::m_mergerSon
private

is part of merger son cage

Definition at line 337 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 236 of file EdgeRouter.h.

◆ m_newx

NodeArray<int> ogdf::EdgeRouter::m_newx
private

Definition at line 314 of file EdgeRouter.h.

◆ m_newy

NodeArray<int> ogdf::EdgeRouter::m_newy
private

new placement position for original node

Definition at line 314 of file EdgeRouter.h.

◆ m_nodeheight

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

Definition at line 217 of file EdgeRouter.h.

◆ m_nodewidth

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

Definition at line 216 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 331 of file EdgeRouter.h.

◆ m_orp

OrthoRep* ogdf::EdgeRouter::m_orp
private

Definition at line 212 of file EdgeRouter.h.

◆ m_overh

int ogdf::EdgeRouter::m_overh
private

minimum overhang

Definition at line 222 of file EdgeRouter.h.

◆ m_processStatus

NodeArray<ProcessType> ogdf::EdgeRouter::m_processStatus
private

keep information about already processed Nodes

Definition at line 334 of file EdgeRouter.h.

◆ m_prup

PlanRep* ogdf::EdgeRouter::m_prup
private

Definition at line 210 of file EdgeRouter.h.

◆ m_rc

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

Definition at line 214 of file EdgeRouter.h.

◆ m_sep

int ogdf::EdgeRouter::m_sep
private

minimum separation

Definition at line 221 of file EdgeRouter.h.

◆ righte

EdgeArray<int> ogdf::EdgeRouter::righte
private

max box borders for bendfree edges

Definition at line 316 of file EdgeRouter.h.

◆ uppe

EdgeArray<int> ogdf::EdgeRouter::uppe
private

Definition at line 316 of file EdgeRouter.h.


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