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
37#include <ogdf/basic/Graph.h>
38#include <ogdf/basic/List.h>
39#include <ogdf/basic/basic.h>
44
45namespace ogdf {
46class CombinatorialEmbedding;
47class GridLayoutMapped;
48template<class ATYPE>
49class MinimumEdgeDistances;
50
57
58public:
59 //constructor
61
64 NodeArray<int>& nodeheight);
65
66 virtual ~EdgeRouter() { }
67
68 void init(PlanRep& pru, RoutingChannel<int>& rou, bool align = false);
69
72
74 void call();
75
79 NodeArray<int>& nodeheight, bool align = false);
80
82 void place(node v /*, int l_sep, int l_overh*/);
83
85 void compute_place(node v, NodeInfo& inf /*, int sep = 10.0, int overh = 2*/);
86
89
92
95
98
101
103 void initialize_node_info(node v, int sep);
104
106 int cp_x(adjEntry ae) { return m_acp_x[ae]; }
107
109 int cp_y(adjEntry ae) { return m_acp_y[ae]; }
110
112 int gp_x(adjEntry ae) { return m_agp_x[ae]; }
113
115 int gp_y(adjEntry ae) { return m_agp_y[ae]; }
116
117 void addbends(BendString& bs, const char* s2);
118
120
122
124 adjEntry outEntry(NodeInfo& inf, OrthoDir d, int pos) {
125 if (inf.is_in_edge(d, pos)) {
126 return (*inf.inList(d).get(pos))->adjTarget();
127 } else {
128 return (*inf.inList(d).get(pos))->adjSource(); //we only bend on outentries
129 }
130 }
131
133 adjEntry inEntry(NodeInfo& inf, OrthoDir d, int pos) {
134 if (inf.is_in_edge(d, pos)) {
135 return (*inf.inList(d).get(pos))->adjSource();
136 } else {
137 return (*inf.inList(d).get(pos))->adjTarget();
138 }
139 }
140
142 void set_position(node v, int x = 0, int y = 0);
143
145 void fix_position(node v, int x = 0, int y = 0);
146
148
152
154
157 void align(bool b) { m_align = b; }
158
159#if 0
161 void setOrSep(int sep) {m_hasOrSep = true; m_orSep = sep;}
162#endif
163
164private:
166 enum class BendType {
168 BendFree,
170 Bend1Left,
172 Bend1Right,
174 Bend2Left,
176 Bend2Right,
178 ProbBf,
180 ProbB1L,
182 ProbB1R,
184 ProbB2L,
186 ProbB2R
187 };
188
190 enum class ProcessType {
192 unprocessed,
194 processed,
196 used
197 };
198
207
209
210 int m_sep;
212 double Cconst;
213
214 BendType abendType(adjEntry ae) { return m_abends[ae]; }
215
216 void unsplit(edge e1, edge e2);
217
220
222 int alpha_move(OrthoDir s_to, OrthoDir s_from, node v);
223
226
228 node oppositeNode(adjEntry ae) { return ae->twinNode(); }
229
233 nt = m_prup->typeOf(oppositeNode(ae));
234 return nt == Graph::NodeType::highDegreeExpander || nt == Graph::NodeType::lowDegreeExpander;
235 }
236
237 //if yes, set its m_oppositeBendType value according to the newly introduced bend
238
240
244 int beta_move(OrthoDir s_from, OrthoDir s_to, int move_num, node v);
245
247
250 int compute_move(OrthoDir s_from, OrthoDir s_to, int& kflip, node v);
251
252 int updateBends(const node v, ListIterator<edge>& it, const bool updateX, const OrthoDir dir,
253 const bool bendLeft, const bool bendUp, int pos = 0);
254
255 void updateBends(const node v, ListIterator<edge>& it, int& pos, int& lastunbend,
256 const bool updateX, const OrthoDir dir, const bool bendLeft, const bool bendUp,
257 const bool subtract);
258
259 void updateLowerEdgesBends(const node v, ListIterator<edge>& it, int& pos, int& base,
260 const bool updateX, const OrthoDir dir, const bool bendLeft);
261
262 void updateOneBend(const bool isDoubleBend, const adjEntry adj, const node v, const OrthoDir dir,
263 const bool bendLeft, const BendType btSingle, const BendType btDouble) {
264 const OrthoDir dirB = bendLeft ? OrthoRep::nextDir(dir) : OrthoRep::prevDir(dir);
265 auto& inf = infos[v];
266
267 if (isDoubleBend) { // paper E^
268 // must be double-bend
269 m_abends[adj] = btDouble;
270 inf.inc_E(dirB, dir);
271 } else {
272 // may be single-bend
273 m_abends[adj] = btSingle;
274 inf.inc_E_hook(dirB, dir);
275 }
276 }
277
280 EdgeArray<int> lowe, uppe, lefte, righte;
281 AdjEntryArray<int> alowe, auppe, alefte, arighte;
285
287
293
296
299
300 //alignment test
304};
305
306}
Includes declaration of graph class.
Declaration of doubly linked lists and iterators.
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,...
Basic declarations, included by all source files.
Class for adjacency list elements.
Definition Graph_d.h:143
node twinNode() const
Returns the associated node of the corresponding adjacency entry (shorthand for twin()->theNode()).
Definition Graph_d.h:176
Represents the bends on an edge e consisting of vertical and horizontal segments.
Definition OrthoRep.h:73
Combinatorial embeddings of planar graphs with modification functionality.
Class for the representation of edges.
Definition Graph_d.h:364
Places node boxes in replacement areas of orthogonal drawing step and route edges to minimize bends.
Definition EdgeRouter.h:55
NodeArray< OrthoDir > m_mergeDir
direction of adjacent (to) merger edges
Definition EdgeRouter.h:302
void init(PlanRep &pru, RoutingChannel< int > &rou, bool align=false)
double Cconst
relative sep to overhang / delta to eps
Definition EdgeRouter.h:212
void align(bool b)
set alignment option: place nodes in cage at outgoing generalization
Definition EdgeRouter.h:157
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:208
EdgeArray< int > lefte
Definition EdgeRouter.h:280
int cp_x(adjEntry ae)
Returns assigned connection point (cage border) x-coordinate of ae 's source.
Definition EdgeRouter.h:106
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:231
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:206
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:295
edge addLeftBend(edge e)
AdjEntryArray< int > m_acp_x
Definition EdgeRouter.h:284
bool m_minDelta
set minimum delta values for flip decision and adjust distances correspondingly
Definition EdgeRouter.h:225
node oppositeNode(adjEntry ae)
helper for oppositeExpander
Definition EdgeRouter.h:228
int m_overh
minimum overhang
Definition EdgeRouter.h:211
int gp_y(adjEntry ae)
Returns assigned glue point (node border) y-coordinate.
Definition EdgeRouter.h:115
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:214
edge addRightBend(edge e)
int m_sep
minimum separation
Definition EdgeRouter.h:210
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:203
AdjEntryArray< int > alefte
Definition EdgeRouter.h:281
AdjEntryArray< int > m_agp_x
Definition EdgeRouter.h:282
NodeArray< bool > m_mergerSon
is part of merger son cage
Definition EdgeRouter.h:301
MinimumEdgeDistances< int > * m_med
Definition EdgeRouter.h:204
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:262
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:109
PlanRep * m_prup
Definition EdgeRouter.h:199
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:298
AdjEntryArray< BendType > m_abends
bends
Definition EdgeRouter.h:292
adjEntry inEntry(NodeInfo &inf, OrthoDir d, int pos)
adjEntries for edges in inLists
Definition EdgeRouter.h:133
NodeArray< int > m_newx
Definition EdgeRouter.h:278
void unsplit(edge e1, edge e2)
void compute_gen_glue_points_y(node v)
compute glue points positions
CombinatorialEmbedding * m_comb
Definition EdgeRouter.h:202
virtual ~EdgeRouter()
Definition EdgeRouter.h:66
GridLayoutMapped * m_layoutp
Definition EdgeRouter.h:200
OrthoRep * m_orp
Definition EdgeRouter.h:201
adjEntry outEntry(NodeInfo &inf, OrthoDir d, int pos)
adjEntries for edges in inLists
Definition EdgeRouter.h:124
NodeArray< bool > m_fixed
saves info about changed position, no further change is allowed
Definition EdgeRouter.h:279
BendType
Edge types, defined by necessary bends.
Definition EdgeRouter.h:166
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:283
ProcessType
Process status of nodes.
Definition EdgeRouter.h:190
NodeArray< int > * m_nodewidth
Definition EdgeRouter.h:205
void place(node v)
applies precomputed placement
int gp_x(adjEntry ae)
Returns assigned glue point (node border) x-coordinate.
Definition EdgeRouter.h:112
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:909
Extends GridLayout by a grid mapping mechanism.
Encapsulates a pointer to a list element.
Definition List.h:113
const_iterator get(int pos) const
Returns a const iterator pointing to the element at position pos.
Definition List.h:341
Maintains input sizes for improvement compaction (deltas and epsilons)
Class for the representation of nodes.
Definition Graph_d.h:241
Orthogonal representation of an embedded graph.
Definition OrthoRep.h:225
Planarized representations (of a connected component) of a graph.
Definition PlanRep.h:68
Graph::NodeType typeOf(node v) const
Returns the type of node v.
Definition PlanRep.h:199
Maintains input sizes for constructive compaction (size of routing channels, separation,...
List< edge > & inList(OrthoDir bs)
Definition NodeInfo.h:133
bool is_in_edge(OrthoDir od, int pos)
Definition NodeInfo.h:191
RegisteredArray for edges of a graph, specialized for EdgeArray<edge>.
Definition Graph_d.h:717
RegisteredArray for nodes, edges and adjEntries of a graph.
Definition Graph_d.h:659
#define OGDF_EXPORT
Specifies that a function or class is exported by the OGDF dynamic library (shared object / DLL),...
Definition config.h:117
The namespace for all OGDF objects.
OrthoDir
Definition OrthoRep.h:56