Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
NodeInfo.h
Go to the documentation of this file.
1
37#pragma once
38
45
46#include <array>
47
48namespace ogdf {
49namespace edge_router {
50
52public:
53 //standard constr.
54 NodeInfo() { init(); }
55
56 void init() {
57 for (int i = 0; i < 4; i++) {
58 for (int j = 0; j < 4; j++) {
59 m_nbe[i][j] = 0;
60 m_delta[i][j] = 0;
61 m_eps[i][j] = 0;
62 m_routable[i][j] = 0;
63 m_flips[i][j] = 0;
64 }
65 num_s_edges[i] = 0;
66 m_gen_pos[i] = -1;
67 m_nbf[i] = 0;
68 m_coord[i] = 0;
69 m_ccoord[i] = 0;
70 }
71 lu = ll = ru = rl = tl = tr = bl = br = 0;
72 }
73
74 //Constructor, adj holds entry for inner face edge
77 : m_adj(adj) {
78 init();
79 get_data(H, L, v, rc, nw, nh);
80 }
81
82 // The following two definitions are necessary because the existence
83 // of the move constructor deletes the implicitly defined copy constructor.
84 NodeInfo(const NodeInfo&) = default;
85 NodeInfo& operator=(const NodeInfo&) = default;
86
88 : m_rc(other.m_rc)
89 , m_coord(other.m_coord)
90 , m_ccoord(other.m_ccoord)
91 , m_gen_pos(other.m_gen_pos)
92 , num_s_edges(other.num_s_edges)
93 , m_nbf(other.m_nbf) {
94 cage_x_size = other.cage_x_size;
95 cage_y_size = other.cage_y_size;
96 box_x_size = other.box_x_size;
97 box_y_size = other.box_y_size;
98
99 lu = other.lu;
100 ll = other.ll;
101 ru = other.ru;
102 rl = other.rl;
103 tl = other.tl;
104 tr = other.tr;
105 bl = other.bl;
106 br = other.br;
107
108 m_firstAdj = other.m_firstAdj;
109 m_adj = other.m_adj;
110 m_vdegree = other.m_vdegree;
111
112 for (int i = 0; i < 4; ++i) {
113 // these should work with move cstrs once VC++ implements rvalue references v3
114 in_edges[i] = std::move(other.in_edges[i]);
115 point_in[i] = std::move(other.point_in[i]);
116
117 for (int j = 0; j < 4; ++j) {
118 m_delta[i][j] = other.m_delta[i][j];
119 m_eps[i][j] = other.m_eps[i][j];
120 m_routable[i][j] = other.m_routable[i][j];
121 m_flips[i][j] = other.m_flips[i][j];
122 m_nbe[i][j] = other.m_nbe[i][j];
123 }
124 }
125 }
126
127 virtual ~NodeInfo() { }
128
130 int coord(OrthoDir bs) const { return m_coord[static_cast<int>(bs)]; }
131
133 int cageCoord(OrthoDir bs) const { return m_ccoord[static_cast<int>(bs)]; }
134
135 //return distance between Node and Cage coord
137 int result;
138 int bsi = static_cast<int>(bs);
139 switch (bs) {
140 case OrthoDir::South:
141 case OrthoDir::East:
142 result = m_ccoord[bsi] - m_coord[bsi];
143 break;
144 case OrthoDir::North:
145 case OrthoDir::West:
146 result = m_coord[bsi] - m_ccoord[bsi];
147 break;
148 default:
149 std::cout << "unknown direction in coordDistance" << std::flush;
151 }
152 OGDF_ASSERT(result >= 0);
153 return result;
154 }
155
156 // original box sizes, fake
157 int node_xsize() const { return box_x_size; }
158
159 int node_ysize() const { return box_y_size; }
160
161 int nodeSize(OrthoDir od) const {
162 return (static_cast<int>(od) % 2 == 0) ? box_y_size : box_x_size;
163 }
164
165 int cageSize(OrthoDir od) const {
166 return (static_cast<int>(od) % 2 == 0) ? cage_y_size : cage_x_size;
167 }
168
170 int rc(OrthoDir od) const { return m_rc[static_cast<int>(od)]; }
171
172 List<edge>& inList(OrthoDir bs) { return in_edges[static_cast<int>(bs)]; }
173
174 List<bool>& inPoint(OrthoDir bs) { return point_in[static_cast<int>(bs)]; }
175
176 //these values are computed dependant on the nodes placement
177 // position of first and last unbend edge on every side
178 int l_upper_unbend() { return lu; }
179
180 int l_lower_unbend() { return ll; }
181
182 int r_upper_unbend() { return ru; }
183
184 int r_lower_unbend() { return rl; }
185
186 int t_left_unbend() { return tl; }
187
188 int t_right_unbend() { return tr; }
189
190 int b_left_unbend() { return bl; }
191
192 int b_right_unbend() { return br; }
193
194 //object separation distances
195 //if (no) generalization enters..., side/gener. dependant paper delta values
196 //distance at side mainside, left/right from existing generalization to side neighbour
198 return m_delta[static_cast<int>(mainside)][static_cast<int>(neighbour)];
199 }
200
201 //paper epsilon
203 return m_eps[static_cast<int>(mainside)][static_cast<int>(neighbour)];
204 }
205
206 //cardinality of the set of edges that will bend, bside side to the side bneighbour
208 return m_nbe[static_cast<int>(s1)][static_cast<int>(sneighbour)];
209 }
210
211 //number of edges flipped from s1 to s2 to save one bend
212 int& flips(OrthoDir s1, OrthoDir s2) {
213 return m_flips[static_cast<int>(s1)][static_cast<int>(s2)];
214 }
215
216 // number of edges routed bendfree
217 int num_bend_free(OrthoDir s) const { return m_nbf[static_cast<int>(s)]; }
218
219 void num_bend_free_increment(OrthoDir s) { ++m_nbf[static_cast<int>(s)]; }
220
221 int num_edges(OrthoDir od) const {
222 return num_s_edges[static_cast<int>(od)]; //return number of edges at side od
223 }
224
225 //position of gen. edges in edge lists for every side, starting with 1
226 int gen_pos(OrthoDir od) const { return m_gen_pos[static_cast<int>(od)]; }
227
228 bool has_gen(OrthoDir od) { return m_gen_pos[static_cast<int>(od)] > -1; }
229
230 bool is_in_edge(OrthoDir od, int pos) {
231 ListConstIterator<bool> b_it = point_in[static_cast<int>(od)].get(pos);
232 return *b_it;
233 }
234
235 void set_coord(OrthoDir bs, int co) { m_coord[static_cast<int>(bs)] = co; }
236
237 void setCageCoord(OrthoDir bs, int co) { m_ccoord[static_cast<int>(bs)] = co; }
238
239 //delta values, due to placement problems, cut to box_size / 2
241 int bsidei = static_cast<int>(bside);
242 int bneighbouri = static_cast<int>(bneighbour);
243 switch (bside) {
244 case OrthoDir::North:
245 case OrthoDir::South:
246 if (dval > box_y_size) {
247 dval = int(floor(((double)box_y_size / 2))) - m_eps[bsidei][bneighbouri];
248 }
249 break;
250 case OrthoDir::East:
251 case OrthoDir::West:
252 if (dval > box_x_size) {
253 dval = int(floor(((double)box_x_size / 2))) - m_eps[bsidei][bneighbouri];
254 }
255 break;
256 default:
257 OGDF_ASSERT(false);
258 }
259 m_delta[bsidei][bneighbouri] = dval;
260 }
261
263 m_eps[static_cast<int>(mainside)][static_cast<int>(neighbour)] = dval;
264 }
265
266#if 0
268 void set_num_bend_edges(box_side bs1, box_side bs2, int num) {nbe[bs1][bs2] = num;}
269#endif
270
272 void set_gen_pos(OrthoDir od, int pos) {
273 m_gen_pos[static_cast<int>(od)] = pos; //odir: N 0, E 1
274 }
275
276 void set_num_edges(OrthoDir od, int num) {
277 num_s_edges[static_cast<int>(od)] = num; //odir: N 0, E 1, check correct od parameter?
278 }
279
282 cage_x_size = m_ccoord[static_cast<int>(OrthoDir::South)]
283 - m_ccoord[static_cast<int>(OrthoDir::North)];
284 cage_y_size = m_ccoord[static_cast<int>(OrthoDir::East)]
285 - m_ccoord[static_cast<int>(OrthoDir::West)];
286 }
287
288 //set the unbend edges after (in) placement step
289 void set_l_upper(int d) { lu = d; }
290
291 void set_l_lower(int d) { ll = d; }
292
293 void set_r_upper(int d) { ru = d; }
294
295 void set_r_lower(int d) { rl = d; }
296
297 void set_t_left(int d) { tl = d; }
298
299 void set_t_right(int d) { tr = d; }
300
301 void set_b_left(int d) { bl = d; }
302
303 void set_b_right(int d) { br = d; }
304
305 //paper set E_s1_s2
306 void inc_E_hook(OrthoDir s_from, OrthoDir s_to, int num = 1) {
307 int s_from_i = static_cast<int>(s_from);
308 int s_to_i = static_cast<int>(s_to);
309 m_routable[s_from_i][s_to_i] += num;
310 m_nbe[s_from_i][s_to_i] += num;
311 }
312
313 void inc_E(OrthoDir s_from, OrthoDir s_to, int num = 1) {
314 m_nbe[static_cast<int>(s_from)][static_cast<int>(s_to)] += num;
315 }
316
317 //read the information for node v from attributed graph/planrep
318 //(needs positions ...)
320 NodeArray<int>& nh); //check input parameter
321
322 // card. of paper E^_s1,s2
324 return m_routable[static_cast<int>(s_from)][static_cast<int>(s_to)];
325 }
326
327 int vDegree() { return m_vdegree; }
328
329 adjEntry& firstAdj() { return m_firstAdj; }
330
331 friend std::ostream& operator<<(std::ostream& O, const NodeInfo& inf);
332
333private:
334 std::array<int, 4> m_rc;
335 std::array<int, 4> m_coord; //coordinates of box segments, x for ls_left/right, y for s_top/bottom
336 std::array<int, 4> m_ccoord; //coordinates of expanded cage segments, -"-
337 int cage_x_size, cage_y_size, //cage size
338 box_x_size, box_y_size; //box size
339 int lu, ll, ru, rl, tl, tr, bl, br; //first/last unbend edge on all sides
340 //most of the following are only [4][2] but use 44 for users conv
341 int m_delta[4][4]; //sepa. distance (paper delta)
342 int m_eps[4][4]; //corner separation distance (paper epsilon)
343 std::array<int, 4> m_gen_pos; //pos num of generaliz. edge in adj lists
344 std::array<int, 4> num_s_edges; //number of edges at sides 0..3=N..W
345 int m_routable[4][4]; //number of reroutable edges, paper E^_s1,s2, got to be initialized after box placement
346 int m_flips[4][4]; //real number of flipped edges
347 int m_nbe[4][4]; //paper E_s1,s2
348 std::array<int, 4> m_nbf; //number of bendfree edges per side
349 adjEntry m_firstAdj; //adjEntry of first encountered outgoing edge, note: this is a copy
350
351 std::array<List<edge>, 4> in_edges; //inedges on each side will be replaced by dynamic ops
352 //preliminary bugfix of in/out dilemma
353 std::array<List<bool>, 4> point_in; //save in/out info
354 adjEntry m_adj; //entry of inner cage face
355 //degree of expanded vertex
357};
358
359std::ostream& operator<<(std::ostream& O, const NodeInfo& inf);
360
361}
362}
Declaration and implementation of AdjEntryArray class.
Declaration of class GridLayout.
Declaration of class MinimumEdgeDistances which maintains minimum distances between attached edges at...
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
Exception thrown when an algorithm realizes an internal bug that prevents it from continuing.
Definition exceptions.h:241
Representation of a graph's grid layout.
Definition GridLayout.h:46
Doubly linked lists (maintaining the length of the list).
Definition List.h:1435
Encapsulates a pointer to a list element.
Definition List.h:103
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
Maintains input sizes for constructive compaction (size of routing channels, separation,...
int num_routable(OrthoDir s_from, OrthoDir s_to) const
Definition NodeInfo.h:323
int coord(OrthoDir bs) const
Returns nodeboxside coordinates (real size)
Definition NodeInfo.h:130
List< edge > & inList(OrthoDir bs)
Definition NodeInfo.h:172
NodeInfo(OrthoRep &H, GridLayout &L, node v, adjEntry adj, RoutingChannel< int > &rc, NodeArray< int > &nw, NodeArray< int > &nh)
Definition NodeInfo.h:75
NodeInfo(NodeInfo &&other)
Definition NodeInfo.h:87
void num_bend_free_increment(OrthoDir s)
Definition NodeInfo.h:219
void setCageCoord(OrthoDir bs, int co)
Definition NodeInfo.h:237
bool has_gen(OrthoDir od)
Definition NodeInfo.h:228
int gen_pos(OrthoDir od) const
Definition NodeInfo.h:226
void compute_cage_size()
compute the size of the cage face and the node box
Definition NodeInfo.h:281
int & flips(OrthoDir s1, OrthoDir s2)
Definition NodeInfo.h:212
bool is_in_edge(OrthoDir od, int pos)
Definition NodeInfo.h:230
void inc_E_hook(OrthoDir s_from, OrthoDir s_to, int num=1)
Definition NodeInfo.h:306
List< bool > & inPoint(OrthoDir bs)
Definition NodeInfo.h:174
std::array< List< bool >, 4 > point_in
Definition NodeInfo.h:353
void set_coord(OrthoDir bs, int co)
Definition NodeInfo.h:235
NodeInfo & operator=(const NodeInfo &)=default
int num_bend_free(OrthoDir s) const
Definition NodeInfo.h:217
std::array< List< edge >, 4 > in_edges
Definition NodeInfo.h:351
NodeInfo(const NodeInfo &)=default
void set_gen_pos(OrthoDir od, int pos)
set position of generalization on each side
Definition NodeInfo.h:272
int eps(OrthoDir mainside, OrthoDir neighbour) const
Definition NodeInfo.h:202
void set_delta(OrthoDir bside, OrthoDir bneighbour, int dval)
Definition NodeInfo.h:240
int coordDistance(OrthoDir bs)
Definition NodeInfo.h:136
void inc_E(OrthoDir s_from, OrthoDir s_to, int num=1)
Definition NodeInfo.h:313
std::array< int, 4 > m_nbf
Definition NodeInfo.h:348
int cageSize(OrthoDir od) const
Definition NodeInfo.h:165
void set_eps(OrthoDir mainside, OrthoDir neighbour, int dval)
Definition NodeInfo.h:262
void set_num_edges(OrthoDir od, int num)
Definition NodeInfo.h:276
int delta(OrthoDir mainside, OrthoDir neighbour) const
Definition NodeInfo.h:197
int cageCoord(OrthoDir bs) const
Returns nodecageside coordinates (expanded size)
Definition NodeInfo.h:133
std::array< int, 4 > num_s_edges
Definition NodeInfo.h:344
std::array< int, 4 > m_rc
Definition NodeInfo.h:334
friend std::ostream & operator<<(std::ostream &O, const NodeInfo &inf)
int num_bend_edges(OrthoDir s1, OrthoDir sneighbour)
Definition NodeInfo.h:207
std::array< int, 4 > m_ccoord
Definition NodeInfo.h:336
void get_data(OrthoRep &O, GridLayout &L, node v, RoutingChannel< int > &rc, NodeArray< int > &nw, NodeArray< int > &nh)
int num_edges(OrthoDir od) const
Definition NodeInfo.h:221
int rc(OrthoDir od) const
Returns routing channel size.
Definition NodeInfo.h:170
std::array< int, 4 > m_gen_pos
Definition NodeInfo.h:343
int nodeSize(OrthoDir od) const
Definition NodeInfo.h:161
std::array< int, 4 > m_coord
Definition NodeInfo.h:335
#define OGDF_EXPORT
Specifies that a function or class is exported by the OGDF DLL.
Definition config.h:101
#define OGDF_THROW(CLASS)
Replacement for throw.
Definition exceptions.h:63
#define OGDF_ASSERT(expr)
Assert condition expr. See doc/build.md for more information.
Definition basic.h:41
static MultilevelBuilder * getDoubleFactoredZeroAdjustedMerger()
std::ostream & operator<<(std::ostream &O, const NodeInfo &inf)
The namespace for all OGDF objects.
OrthoDir
Definition OrthoRep.h:50