Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
EdgeRouter.h
Go to the documentation of this file.
1
35#pragma once
36
39#include <ogdf/basic/Layout.h>
45
46namespace ogdf {
47
54
55public:
56 //constructor
58
62
63 virtual ~EdgeRouter() { }
64
65 void init(PlanRep& pru, RoutingChannel<int>& rou, bool align = false);
66
69
71 void call();
72
76 NodeArray<int>& nodeheight, bool align = false);
77
79 void place(node v /*, int l_sep, int l_overh*/);
80
82 void compute_place(node v, NodeInfo& inf /*, int sep = 10.0, int overh = 2*/);
83
86
89
92
95
98
101
103 int cp_x(adjEntry ae) { return m_acp_x[ae]; }
104
106 int cp_y(adjEntry ae) { return m_acp_y[ae]; }
107
109 int gp_x(adjEntry ae) { return m_agp_x[ae]; }
110
112 int gp_y(adjEntry ae) { return m_agp_y[ae]; }
113
114 void addbends(BendString& bs, const char* s2);
115
117
119
122 if (inf.is_in_edge(d, pos)) {
123 return (*inf.inList(d).get(pos))->adjTarget();
124 } else {
125 return (*inf.inList(d).get(pos))->adjSource(); //we only bend on outentries
126 }
127 }
128
131 if (inf.is_in_edge(d, pos)) {
132 return (*inf.inList(d).get(pos))->adjSource();
133 } else {
134 return (*inf.inList(d).get(pos))->adjTarget();
135 }
136 }
137
139 void set_position(node v, int x = 0, int y = 0);
140
142 void fix_position(node v, int x = 0, int y = 0);
143
145
149
151
154 void align(bool b) { m_align = b; }
155
156#if 0
158 void setOrSep(int sep) {m_hasOrSep = true; m_orSep = sep;}
159#endif
160
161private:
163 enum class BendType {
165 BendFree,
167 Bend1Left,
169 Bend1Right,
171 Bend2Left,
173 Bend2Right,
175 ProbBf,
177 ProbB1L,
179 ProbB1R,
181 ProbB2L,
183 ProbB2R
184 };
185
187 enum class ProcessType {
189 unprocessed,
191 processed,
193 used
194 };
195
204
206
207 int m_sep;
209 double Cconst;
210
211 BendType abendType(adjEntry ae) { return m_abends[ae]; }
212
214
217
220
223
225 node oppositeNode(adjEntry ae) { return ae->twinNode(); }
226
230 nt = m_prup->typeOf(oppositeNode(ae));
231 return nt == Graph::NodeType::highDegreeExpander || nt == Graph::NodeType::lowDegreeExpander;
232 }
233
234 //if yes, set its m_oppositeBendType value according to the newly introduced bend
235
237
242
244
248
249 int updateBends(const node v, ListIterator<edge>& it, const bool updateX, const OrthoDir dir,
250 const bool bendLeft, const bool bendUp, int pos = 0);
251
252 void updateBends(const node v, ListIterator<edge>& it, int& pos, int& lastunbend,
253 const bool updateX, const OrthoDir dir, const bool bendLeft, const bool bendUp,
254 const bool subtract);
255
256 void updateLowerEdgesBends(const node v, ListIterator<edge>& it, int& pos, int& base,
257 const bool updateX, const OrthoDir dir, const bool bendLeft);
258
259 void updateOneBend(const bool isDoubleBend, const adjEntry adj, const node v, const OrthoDir dir,
260 const bool bendLeft, const BendType btSingle, const BendType btDouble) {
261 const OrthoDir dirB = bendLeft ? OrthoRep::nextDir(dir) : OrthoRep::prevDir(dir);
262 auto& inf = infos[v];
263
264 if (isDoubleBend) { // paper E^
265 // must be double-bend
266 m_abends[adj] = btDouble;
267 inf.inc_E(dirB, dir);
268 } else {
269 // may be single-bend
270 m_abends[adj] = btSingle;
271 inf.inc_E_hook(dirB, dir);
272 }
273 }
274
277 EdgeArray<int> lowe, uppe, lefte, righte;
278 AdjEntryArray<int> alowe, auppe, alefte, arighte;
282
284
290
293
296
297 //alignment test
301};
302
303}
Declaration of class GridLayout.
Declaration of class GridLayoutMapped which extends GridLayout by a grid mapping mechanism.
Declaration of class Layout.
Declaration of class MinimumEdgeDistances which maintains minimum distances between attached edges at...
Declaration of class NodeInfo.
Declaration of orthogonal representation of planar graphs.
Declaration of a base class for planar representations of graphs and cluster graphs.
Declaration of class RoutingChannel which maintains required size of routing channels and separation,...
Class for adjacency list elements.
Definition Graph_d.h:79
Dynamic arrays indexed with adjacency entries.
Represents the bends on an edge e consisting of vertical and horizontal segments.
Definition OrthoRep.h:67
Combinatorial embeddings of planar graphs with modification functionality.
Dynamic arrays indexed with edges.
Definition EdgeArray.h:125
Class for the representation of edges.
Definition Graph_d.h:300
Places node boxes in replacement areas of orthogonal drawing step and route edges to minimize bends.
Definition EdgeRouter.h:52
NodeArray< OrthoDir > m_mergeDir
direction of adjacent (to) merger edges
Definition EdgeRouter.h:299
void init(PlanRep &pru, RoutingChannel< int > &rou, bool align=false)
double Cconst
relative sep to overhang / delta to eps
Definition EdgeRouter.h:209
void align(bool b)
set alignment option: place nodes in cage at outgoing generalization
Definition EdgeRouter.h:154
void addbends(BendString &bs, const char *s2)
void fix_position(node v, int x=0, int y=0)
same as set but updates m_fixed, coordinates cant be changed afterwards
NodeArray< NodeInfo > infos
holds the cage and placement information
Definition EdgeRouter.h:205
EdgeArray< int > lefte
Definition EdgeRouter.h:277
int cp_x(adjEntry ae)
Returns assigned connection point (cage border) x-coordinate of ae 's source.
Definition EdgeRouter.h:103
void initialize_node_info(node v, int sep)
sets values derivable from input
void updateLowerEdgesBends(const node v, ListIterator< edge > &it, int &pos, int &base, const bool updateX, const OrthoDir dir, const bool bendLeft)
bool oppositeExpander(adjEntry ae)
check if the target node of the outgoing adjEntry still is a expander
Definition EdgeRouter.h:228
int compute_move(OrthoDir s_from, OrthoDir s_to, int &kflip, node v)
compute the maximum number of moveable edges
NodeArray< int > * m_nodeheight
Definition EdgeRouter.h:203
void multiDelta()
for all multiple edges, set the delta value on both sides to minimum if not m_minDelta
int alpha_move(OrthoDir s_to, OrthoDir s_from, node v)
computes the alpha value described in the paper
NodeArray< BendType > m_oppositeBendType
keep the information about the type of bend inserted at one end of an (originally unbend) edge,...
Definition EdgeRouter.h:292
edge addLeftBend(edge e)
AdjEntryArray< int > m_acp_x
Definition EdgeRouter.h:281
bool m_minDelta
set minimum delta values for flip decision and adjust distances correspondingly
Definition EdgeRouter.h:222
node oppositeNode(adjEntry ae)
helper for oppositeExpander
Definition EdgeRouter.h:225
int m_overh
minimum overhang
Definition EdgeRouter.h:208
int gp_y(adjEntry ae)
Returns assigned glue point (node border) y-coordinate.
Definition EdgeRouter.h:112
void compute_glue_points_x(node &v)
compute glue points positions
void compute_glue_points_y(node v)
compute glue points positions
BendType abendType(adjEntry ae)
Definition EdgeRouter.h:211
edge addRightBend(edge e)
int m_sep
minimum separation
Definition EdgeRouter.h:207
void compute_routing(node v)
computes routing after compute_place
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
RoutingChannel< int > * m_rc
Definition EdgeRouter.h:200
AdjEntryArray< int > alefte
Definition EdgeRouter.h:278
AdjEntryArray< int > m_agp_x
Definition EdgeRouter.h:279
NodeArray< bool > m_mergerSon
is part of merger son cage
Definition EdgeRouter.h:298
MinimumEdgeDistances< int > * m_med
Definition EdgeRouter.h:201
void compute_place(node v, NodeInfo &inf)
computes placement
void updateOneBend(const bool isDoubleBend, const adjEntry adj, const node v, const OrthoDir dir, const bool bendLeft, const BendType btSingle, const BendType btDouble)
Definition EdgeRouter.h:259
void compute_gen_glue_points_x(node v)
compute glue points positions
int updateBends(const node v, ListIterator< edge > &it, const bool updateX, const OrthoDir dir, const bool bendLeft, const bool bendUp, int pos=0)
EdgeRouter(PlanRep &pru, OrthoRep &H, GridLayoutMapped &L, CombinatorialEmbedding &E, RoutingChannel< int > &rou, MinimumEdgeDistances< int > &med, NodeArray< int > &nodewidth, NodeArray< int > &nodeheight)
int cp_y(adjEntry ae)
Returns assigned connection point (cage border) y-coordinate of ae 's source.
Definition EdgeRouter.h:106
PlanRep * m_prup
Definition EdgeRouter.h:196
void set_corners(node v)
set coordinates of cage corners after placement
NodeArray< ProcessType > m_processStatus
keep information about already processed Nodes
Definition EdgeRouter.h:295
AdjEntryArray< BendType > m_abends
bends
Definition EdgeRouter.h:289
adjEntry inEntry(NodeInfo &inf, OrthoDir d, int pos)
adjEntries for edges in inLists
Definition EdgeRouter.h:130
NodeArray< int > m_newx
Definition EdgeRouter.h:275
void unsplit(edge e1, edge e2)
void compute_gen_glue_points_y(node v)
compute glue points positions
CombinatorialEmbedding * m_comb
Definition EdgeRouter.h:199
virtual ~EdgeRouter()
Definition EdgeRouter.h:63
GridLayoutMapped * m_layoutp
Definition EdgeRouter.h:197
OrthoRep * m_orp
Definition EdgeRouter.h:198
adjEntry outEntry(NodeInfo &inf, OrthoDir d, int pos)
adjEntries for edges in inLists
Definition EdgeRouter.h:121
NodeArray< bool > m_fixed
saves info about changed position, no further change is allowed
Definition EdgeRouter.h:276
BendType
Edge types, defined by necessary bends.
Definition EdgeRouter.h:163
void call()
places nodes in cages and routes incident edges
int beta_move(OrthoDir s_from, OrthoDir s_to, int move_num, node v)
computes the beta value described in the paper
AdjEntryArray< node > m_cage_point
newly introduced bends destroy edge to point connection
Definition EdgeRouter.h:280
ProcessType
Process status of nodes.
Definition EdgeRouter.h:187
NodeArray< int > * m_nodewidth
Definition EdgeRouter.h:202
void place(node v)
applies precomputed placement
int gp_x(adjEntry ae)
Returns assigned glue point (node border) x-coordinate.
Definition EdgeRouter.h:109
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 setDistances()
sets the computed distances in structure MinimumEdgeDistance m_med
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
NodeType
The type of nodes.
Definition Graph_d.h:569
Extends GridLayout by a grid mapping mechanism.
Encapsulates a pointer to a list element.
Definition List.h:103
Maintains input sizes for improvement compaction (deltas and epsilons)
Dynamic arrays indexed with nodes.
Definition NodeArray.h:125
Class for the representation of nodes.
Definition Graph_d.h:177
Orthogonal representation of an embedded graph.
Definition OrthoRep.h:219
Planarized representations (of a connected component) of a graph.
Definition PlanRep.h:57
Graph::NodeType typeOf(node v) const
Returns the type of node v.
Definition PlanRep.h:188
Maintains input sizes for constructive compaction (size of routing channels, separation,...
#define OGDF_EXPORT
Specifies that a function or class is exported by the OGDF DLL.
Definition config.h:101
static MultilevelBuilder * getDoubleFactoredZeroAdjustedMerger()
The namespace for all OGDF objects.
OrthoDir
Definition OrthoRep.h:50