?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Don't import ogdf namespace
[TortoiseGit.git] / ext / OGDF / src / planarlayout / MixedModelBase.cpp
blob6cc7666fbee717b3d37ca39da49f57812ad65e12
1 /*
2 * $Revision: 2599 $
3 *
4 * last checkin:
5 * $Author: chimani $
6 * $Date: 2012-07-15 22:39:24 +0200 (So, 15. Jul 2012) $
7 ***************************************************************/
8
9 /** \file
10 * \brief Implementation of Mixed-Model basic functionality.
11 *
12 * \author Carsten Gutwenger
13 *
14 * \par License:
15 * This file is part of the Open Graph Drawing Framework (OGDF).
16 *
17 * \par
18 * Copyright (C)<br>
19 * See README.txt in the root directory of the OGDF installation for details.
20 *
21 * \par
22 * This program is free software; you can redistribute it and/or
23 * modify it under the terms of the GNU General Public License
24 * Version 2 or 3 as published by the Free Software Foundation;
25 * see the file LICENSE.txt included in the packaging of this file
26 * for details.
27 *
28 * \par
29 * This program is distributed in the hope that it will be useful,
30 * but WITHOUT ANY WARRANTY; without even the implied warranty of
31 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
32 * GNU General Public License for more details.
33 *
34 * \par
35 * You should have received a copy of the GNU General Public
36 * License along with this program; if not, write to the Free
37 * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
38 * Boston, MA 02110-1301, USA.
39 *
40 * \see http://www.gnu.org/copyleft/gpl.html
41 ***************************************************************/
42
43
44 #include "MixedModelBase.h"
45 #include <ogdf/basic/extended_graph_alg.h>
46 #include <ogdf/basic/simple_graph_alg.h>
47
48
49 namespace ogdf {
50
51
52 /********************************************************************
53 hasLeft, hasRight
54
55 Determine if the kth set in the ordered partition has a "real"
56 left or right vertex, respectively.
57 ********************************************************************/
58
59 bool MixedModelBase::hasLeft (int k) const
60 {
61 const ShellingOrderSet &V = m_mmo[k];
62 const List<InOutPoint> &L = m_iops.inpoints(V[1]);
63
64 ListConstIterator<InOutPoint> it = L.begin();
65 return (it.valid() && (*it).m_adj->twinNode() == m_mmo.m_left[k]);
66 }
67
68 bool MixedModelBase::hasRight(int k) const
69 {
70 const ShellingOrderSet &V = m_mmo[k];
71 const List<InOutPoint> &L = m_iops.inpoints(V[V.len()]);
72
73 ListConstIterator<InOutPoint> it = L.rbegin();
74 return (it.valid() && (*it).m_adj->twinNode() == m_mmo.m_right[k]);
75 }
76
77
78 /********************************************************************
79 computeOrder
80
81 Computes the ordered partition (incl. m_left[k], m_right[k]) and
82 constructs the in- and outpoint lists.
83 ********************************************************************/
84
85
86 void MixedModelBase::computeOrder(
87 AugmentationModule &augmenter,
88 EmbedderModule *pEmbedder,
89 adjEntry adjExternal,
90 ShellingOrderModule &compOrder)
91 {
92 // remove (temporary) deg-1-nodes;
93 removeDeg1Nodes();
94
95 // augment PG (temporary) to achieve required connectivity
96 List<edge> augmentedEdges;
97 augmenter.call(m_PG,augmentedEdges);
98
99 // embed augmented graph (if required)
100 if(pEmbedder)
101 pEmbedder->call(m_PG,adjExternal);
102
103 // compute ordering of biconnected plane graph
104 m_mmo.init(m_PG, compOrder, adjExternal);
105
106 // restore deg1-nodes and mark incident edges
107 m_iops.restoreDeg1Nodes(m_PG,m_deg1RestoreStack);
108
109 // compute in- and outpoint lists
110 for (int k = 1; k <= m_mmo.length(); ++k)
111 {
112 const ShellingOrderSet &V = m_mmo[k];
113 for (int i = 1; i <= V.len(); ++i)
114 {
115 node v = V[i];
116 node cl = (i == 1) ? V.left () : V[i-1];
117 node cr = (i == V.len()) ? V.right() : V[i+1];
118
119 //edge e, er = 0, el = 0;
120 adjEntry adj, adjR = 0, adjL = 0;
121 forall_adj(adj,v)
122 {
123 node t = adj->twinNode();
124 if (t == cr) adjR = adj;
125 if (t == cl) adjL = adj;
126 }
127 // one of adjL and adjR is not 0 by definition of the ordering
128 if (adjR == 0) adjR = adjL;
129 if (adjL == 0) adjL = adjR;
130
131 adj = adjR;
132 do {
133 if (exists(adj))
134 m_iops.pushInpoint(adj);
135 adj = adj->cyclicSucc();
136 } while (m_iops.marked(adj) || (m_mmo.rank(adj->twinNode()) <= k && adj != adjR));
137
138 for ( ; m_iops.marked(adj) || m_mmo.rank(adj->twinNode()) > k; adj = adj->cyclicSucc())
139 if (exists(adj))
140 m_iops.appendOutpoint(adj);
141
142 // move In-/Outpoints to deg1-nodes to appropriate places
143 adjL = m_iops.switchBeginIn(v);
144 adjR = m_iops.switchEndIn (v);
145
146 // has a left- or right edge ?
147 bool has_el = (adjL != 0);
148 bool has_er = (adjR != 0);
149 if (adjL && adjL == adjR) {
150 has_el = (adjL->twinNode() != cr);
151 has_er = !has_el;
152 }
153
154 // determine left(k) and right(k)
155 if (i == 1) m_mmo.m_left [k] = (has_el) ? adjL->twinNode() : cl;
156 if (i == V.len()) m_mmo.m_right[k] = (has_er) ? adjR->twinNode() : cr;
157
158 int xl, xr;
159 m_iops.numDeg1(v,xl,xr,has_el || has_er);
160
161 int x = 0;
162 if (!has_el) x += xl;
163 if (!has_er) x += xr;
164
165 int x_alpha = max(0,min(x, (m_iops.in(v)-m_iops.out(v)+1+2*x-2)/2));
166 int x_beta = x - x_alpha;
167
168 if (!has_el)
169 for( ; x_beta > 0 && xl > 0; --x_beta, --xl)
170 m_iops.switchBeginOut(v);
171 if (!has_er)
172 for( ; x_beta > 0 && xr > 0; --x_beta, --xr)
173 m_iops.switchEndOut(v);
174 }
175 }
176
177 // remove augmented edges
178 ListConstIterator<edge> itE;
179 for(itE = augmentedEdges.begin(); itE.valid(); ++itE)
180 m_PG.delEdge(*itE);
181 }
182
183
184 /********************************************************************
185 removeDeg1Nodes
186
187 Removes deg-1-nodes and store informations for restoring them.
188 ********************************************************************/
189
190 void MixedModelBase::removeDeg1Nodes()
191 {
192 NodeArray<bool> mark(m_PG,false);
193 node v;
194
195 // mark all deg-1-nodes we want to remove
196 int n = m_PG.numberOfNodes();
197 forall_nodes(v,m_PG) {
198 if (n <= 3) break;
199 if ((mark[v] = (v->degree() == 1)) == true) {
200 node w = v->firstAdj()->twinNode();
201 if (mark[w]) mark[w] = false; else --n;
202 }
203 }
204
205 m_PG.removeDeg1Nodes(m_deg1RestoreStack,mark);
206 }
207
208
209 /********************************************************************
210 assignIopCoords
211
212 Computes the relative coordinates of the in- and outpoints,
213 incl. height(v), depth(v).
214 ********************************************************************/
215
216 void MixedModelBase::assignIopCoords()
217 {
218 for (int k = 1; k <= m_mmo.length(); ++k)
219 {
220 const ShellingOrderSet &V = m_mmo[k];
221
222 for (int i = 1; i <= V.len(); ++i)
223 {
224 node v = V[i];
225
226 bool onlyLeft = (m_iops.in(v) == 2 &&
227 i >= 2 && m_iops.inpoints(v).front().m_adj->twinNode() == V[i-1] &&
228 m_iops.marked(m_iops.inpoints(v).back().m_adj));
229 bool onlyRight = (m_iops.in(v) == 2 &&
230 i < V.len() && m_iops.inpoints(v).back().m_adj->twinNode() == V[i+1] &&
231 m_iops.marked(m_iops.inpoints(v).front().m_adj));
232
233 if (m_iops.out(v) >= 1)
234 {
235 int outL = 0, outR = 0;
236
237 int outPlus = m_iops.out(v)/2;
238 int outMinus = m_iops.out(v) - 1 - outPlus;
239 int deltaL = 0, deltaR = 0;
240 outL = outMinus;
241
242 if (m_iops.in(v) == 2) {
243 deltaL = (onlyRight) ? 0 : 1;
244 deltaR = (onlyLeft) ? 0 : 1;
245
246 } else if (m_iops.in(v) >= 3) {
247 deltaL = deltaR = 1;
248
249 } else if (m_iops.in(v) == 1) {
250 node vl = (i == 1) ? m_mmo.m_left[k] : V[i-1];
251 if (m_iops.inpoints(v).front().m_adj->twinNode() != vl) {
252 outL = outPlus;
253 deltaR = 1;
254
255 } else {
256 deltaL = 1;
257 }
258 }
259
260 outR = m_iops.out(v) - 1 - outL;
261
262 List<InOutPoint> &opl = m_iops.outpoints(v);
263 int j;
264 ListIterator<InOutPoint> it = opl.begin();
265 for (j = 0; j < outL; j++, ++it)
266 m_iops.setOutCoord(it,-outL+j,deltaL+j);
267 m_iops.m_height[v] = max(outL+deltaL,outR+deltaR)-1;
268 if (m_iops.m_height[v] == 0 && m_iops.marked((*it).m_adj))
269 m_iops.m_height[v] = 1;
270 m_iops.setOutCoord(it,0,m_iops.m_height[v]);
271 for (j = 1, ++it; j <= outR; j++, ++it)
272 m_iops.setOutCoord(it,j,outR+deltaR-j);
273 }
274
275 if (m_iops.in(v) <= 3)
276 {
277 List<InOutPoint> &ipl = m_iops.inpoints(v);
278 int in_v = m_iops.in(v);
279
280 if (in_v == 3 || (in_v == 2 && !onlyRight)) {
281 if (m_iops.marked(ipl.front().m_adj))
282 m_iops.setInCoord(ipl.begin(),-1,0);
283 }
284 if (in_v == 3 || (in_v == 2 && !onlyLeft)) {
285 if (m_iops.marked(ipl.back().m_adj))
286 m_iops.setInCoord(ipl.rbegin(), 1,0);
287 }
288 if (in_v != 0 && (in_v != 2 || onlyLeft || onlyRight)) {
289 ListIterator<InOutPoint> it = ipl.begin();
290 if (in_v == 3 || (in_v == 2 && onlyLeft))
291 ++it;
292 if (m_iops.marked((*it).m_adj)) {
293 m_iops.setInCoord(it,0,-1);
294 m_iops.m_depth[v] = 1;
295 }
296 }
297
298 } else {
299 int in_l = (m_iops.in(v)-3) / 2;
300 int in_r = m_iops.in(v)-3 - in_l;
301
302 int j;
303 List<InOutPoint> &ipl = m_iops.inpoints(v);
304 ListIterator<InOutPoint> it = ipl.begin();
305 m_iops.setInCoord(it,(in_l == 0 && m_iops.marked((*it).m_adj)) ? -1 : -in_l,0);
306 for (j = 1, ++it; j <= in_l; ++j, ++it)
307 m_iops.setInCoord(it,j-in_l-1,-j);
308 m_iops.setInCoord(it,0,-in_r);
309 m_iops.m_depth[v] = in_r; // inpoint with smallest y-coordinate
310 for (j = 1, ++it; j <= in_r; ++j, ++it)
311 m_iops.setInCoord(it,j,j-in_r-1);
312 m_iops.setInCoord(it,in_r,0);
313 }
314 }
315 }
316 }
317
318
319 /********************************************************************
320 placeNodes
321
322 Implements the placement step. Computes x[v] and y[v].
323 ********************************************************************/
324
325 void MixedModelBase::placeNodes()
326 {
327 m_dyl.init(2,m_mmo.length());
328 m_dyr.init(2,m_mmo.length());
329
330 m_leftOp .init(2,m_mmo.length());
331 m_rightOp.init(2,m_mmo.length());
332
333 m_nextLeft .init(m_PG);
334 m_nextRight.init(m_PG);
335 m_dxla.init(m_PG,0);
336 m_dxra.init(m_PG,0);
337
338 computeXCoords();
339 computeYCoords();
340 }
341
342
343 /********************************************************************
344 computeXCoords
345
346 Computes the absolute x-coordinates x[v] of all nodes in the
347 ordering, furthermore dyla[k] and dyra[k] (used by compute_y_coordinates)
348 ********************************************************************/
349
350 void MixedModelBase::computeXCoords()
351 {
352 NodeArray<int> &x = m_gridLayout.x();
353
354 int k, i;
355 node v;
356
357 // representation of the contour
358 NodeArray<node> prev(m_PG), next(m_PG);
359 NodeArray<node> father(m_PG, 0);
360
361 // maintaining of free space for shifting
362 Array<int> shiftSpace(1,m_mmo.length(), 0);
363 NodeArray<int> comp(m_PG,0);
364
365 forall_nodes(v,m_PG) {
366 m_nextLeft [v] = m_iops.firstRealOut(v);
367 m_nextRight[v] = m_iops.lastRealOut (v);
368 }
369
370 // last_right[v] = last vertex of highest set with right vertex v
371 NodeArray<node> lastRight(m_PG,0);
372 for(k = 2; k <= m_mmo.length(); ++k) {
373 const ShellingOrderSet &V = m_mmo[k];
374 lastRight[m_mmo.m_right[k]] = V[V.len()];
375 }
376
377 NodeArray<int> high(m_PG,0);
378 forall_nodes(v,m_PG) {
379 InOutPoint op;
380 ListConstIterator<InOutPoint> it;
381 for(it = m_iops.outpoints(v).begin(); it.valid(); ++it) {
382 if (!m_iops.marked((*it).m_adj))
383 high[v] = max(m_mmo.rank((*it).m_adj->twinNode()), high[v]);
384 }
385 }
386
387 // initialization
388 const ShellingOrderSet &V1 = m_mmo[1];
389 int p = V1.len();
390
391 x[V1[1]] = m_iops.outLeft(V1[1]);
392 for (i = 2; i <= p; i++) {
393 x[V1[i]] = m_iops.maxRight(V1[i-1]) + m_iops.maxLeft(V1[i]) + 1;
394 }
395
396 for (i = 1; i <= p; i++) {
397 if (i < p) next[V1[i]] = V1[i+1];
398 if (i > 1) prev[V1[i]] = V1[i-1];
399 }
400 prev [V1[1]] = next [V1[p]] = 0;
401
402 // main loop
403 for(k = 2; k <= m_mmo.length(); ++k)
404 {
405 // consider set Vk
406 const ShellingOrderSet &Vk = m_mmo[k];
407 p = Vk.len();
408 node z1 = Vk[1];
409 node cl = m_mmo.m_left[k];
410 node cr = m_mmo.m_right[k];
411
412 if (!hasLeft(k)) {
413 while(lastRight[cl] && high[cl] < k && !hasRight(m_mmo.rank(lastRight[cl])))
414 cl = m_mmo.m_left[k] = lastRight[cl];
415 }
416
417 // determine temporarily the x-coordinates of c_l+1,...,c_r relative to cl
418 int sum = 0;
419 for (v = next[cl]; v != cr; v = next[v]) {
420 sum += x[v]; x[v] = sum;
421 }
422 x[cr] += sum;
423
424 m_leftOp [k] = m_nextRight[cl];
425 m_rightOp[k] = m_nextLeft [cr];
426
427 // compute dxl, dxr, dyl, dyr
428 int dxl, dxr;
429 m_dyl[k] = m_dyr[k] = 0;
430
431 ListConstIterator<InOutPoint> it;
432 if ((it = m_nextRight[cl]).valid()) {
433 dxl = (*it).m_dx;
434 if ((*it).m_adj->twinNode() != z1)
435 dxl++;
436 else
437 m_nextRight[cl] = m_iops.prevRealOut(it);
438
439 if (dxl < 0)
440 m_dyl[k] = m_iops.m_height[cl];
441 else if ((++it).valid())
442 m_dyl[k] = (*it).m_dy;
443 } else {
444 dxl = (m_iops.out(cl) == 0) ? 0 : -m_iops.outLeft(cl);
445 }
446 if ((it = m_nextLeft[cr]).valid()) {
447 dxr = (*it).m_dx;
448 if ((*it).m_adj->twinNode() != Vk[p])
449 dxr--;
450 else
451 m_nextLeft[cr] = m_iops.nextRealOut(it);
452
453 if (dxr > 0)
454 m_dyr[k] = m_iops.m_height[cr];
455 else if ((it = it.pred()).valid())
456 m_dyr[k] = (*it).m_dy;
457 } else {
458 dxr = (m_iops.out(cr) == 0) ? 0 : m_iops.outRight(cr);
459 }
460
461 m_dxla[Vk[1]] = dxl; m_dxra[Vk[p]] = dxr;
462
463 int old_x_cr;
464
465 // vertex case
466 if (!m_iops.isChain(z1))
467 {
468 InOutPoint ip_ct = m_iops.middleNeighbor(z1);
469 InOutPoint op_ct = *m_iops.pointOf(ip_ct.m_adj->twin());
470 node ct = ip_ct.m_adj->twinNode();
471
472 int delta = dxl + m_iops.maxPlusLeft(z1) + ip_ct.m_dx - (x[ct] + op_ct.m_dx);
473 if (delta < 0) delta = 0;
474 x[ct] += delta;
475
476 int x_0 = x[ct] + op_ct.m_dx - ip_ct.m_dx;
477
478 int sum = 0;
479 for (v = prev[ct]; v != cl; v = prev[v]) {
480 x[v] -= sum;
481 if (m_nextRight[v].valid() && (*m_nextRight[v]).m_adj->twinNode() == z1) {
482 InOutPoint op_v = *m_nextRight[v];
483 InOutPoint ip_v = *m_iops.pointOf(op_v.m_adj->twin());
484 int diff = x[v] + op_v.m_dx - x_0 - ip_v.m_dx;
485 if (diff > 0) {
486 sum += diff;
487 x[v] -= diff;
488 }
489 }
490 }
491
492 for (v = next[cl]; v != next[ct]; v = next[v])
493 x[v] += sum;
494 x_0 += sum;
495
496 sum += delta;
497
498 for (v = next[ct]; v != next[cr]; v = next[v]) {
499 x[v] += sum;
500 if (m_nextRight[v].valid() && (*m_nextRight[v]).m_adj->twinNode() == z1) {
501 InOutPoint op_v = *m_nextRight[v];
502 InOutPoint ip_v = *m_iops.pointOf(op_v.m_adj->twin());
503 int diff = x[v] + op_v.m_dx - x_0 - ip_v.m_dx;
504 if (diff < 0) {
505 sum -= diff;
506 x[v] -= diff;
507 }
508 }
509 }
510
511 x[z1] = x_0;
512
513 old_x_cr = x[cr] - x[z1];
514 x[cr] = max(old_x_cr, m_iops.maxPlusRight(z1) - dxr);
515
516 for (v = next[cl]; v != cr; v = next[v]) {
517 x[v] = x[v] - x[z1];
518 father[v] = z1;
519 }
520
521 // chain case
522 } else {
523 int sum = x[z1] = m_iops.maxPlusLeft(z1) + dxl;
524 for (i = 2; i <= p; i++)
525 sum += (x[Vk[i]] = m_iops.maxRight(Vk[i-1]) + m_iops.maxLeft(Vk[i]) + 1);
526
527 old_x_cr = x[cr] - sum;
528 int new_x_cr = m_iops.maxPlusRight(Vk[p]) - dxr;
529 x[cr] = max(old_x_cr, new_x_cr);
530 shiftSpace[k] = max(0, old_x_cr - new_x_cr);
531
532 for (v = next[cl]; v != cr; v = next[v]) {
533 x[v] = x[v] - x[z1];
534 father[v] = z1;
535 }
536 }
537
538 int need = x[cr] - old_x_cr;
539 int k_cr = m_mmo.rank(cr);
540 if (shiftSpace[k_cr] > 0) {
541 int use = min(shiftSpace[k_cr], need);
542 shiftSpace[k_cr] -= use;
543 comp[cr] += use;
544 x[m_mmo.m_right[k_cr]] -= use;
545 }
546
547 // update contour after insertion of z1,...,zp
548 for (i = 1; i <= p; i++) {
549 if (i < p) next[Vk[i]] = Vk[i+1];
550 if (i > 1) prev[Vk[i]] = Vk[i-1];
551 }
552
553 next [prev [z1] = cl] = z1;
554 prev [next [Vk[p]] = cr] = Vk[p];
555
556 }
557
558 // compute final x-coordinates for nodes on final contour
559 int sum = 0;
560 for (v = V1[1]; v != 0; v = next[v])
561 x [v] = (sum += x[v]);
562
563 // compute final x-coordinates for inner nodes
564 for (k = m_mmo.length(); k >= 1; k--) {
565 for (i = 1; i <= m_mmo.len(k); i++) {
566 v = m_mmo(k,i);
567 if (father[v] != 0) {
568 x[v] = x[v] + x[father[v]] - comp[father[v]];
569 }
570 }
571 }
572 }
573
574
575 /********************************************************************
576 computeYCoords
577
578 Computes the absolute y-coordinates y[v] of all nodes in the
579 ordering.
580 ********************************************************************/
581
582 class SetYCoords
583 {
584 public:
585 SetYCoords(const Graph &G, const IOPoints &iops, const MMOrder &mmo,
586 const NodeArray<int> &x, const NodeArray<int> &y) :
587 m_G(G), m_iops(iops), m_mmo(mmo), m_x(x), m_y(y) {
588 }
589
590 void init(int k);
591
592 void checkYCoord (int xleft, int xright, int ys, bool nodeSep);
593 void checkYCoord (int xs, int ys, bool nodeSep ) {
594 checkYCoord (xs, xs, ys, nodeSep);
595 }
596
597 int getYmax() const {
598 return m_ymax;
599 }
600
601 // avoid automatic creation of assignment operator
602 SetYCoords &operator=(const SetYCoords &);
603
604 private:
605 void getNextRegion();
606 node z(int j) const {
607 return (*m_V)[j];
608 }
609
610 bool marked(adjEntry adj) const {
611 return m_iops.marked(adj);
612 }
613
614 const InOutPoint &outpoint(const InOutPoint &ip) {
615 return *m_iops.pointOf(ip.m_adj->twin());
616 }
617
618 void searchNextInpoint();
619
620 const Graph &m_G;
621 const IOPoints &m_iops;
622 const MMOrder &m_mmo;
623 const NodeArray<int> &m_x;
624 const NodeArray<int> &m_y;
625 const ShellingOrderSet *m_V;
626
627 int m_k;
628 node m_cl, m_cr;
629
630 int m_ymax, m_xNext, m_lookAheadX, m_lookAheadNextX;
631 int m_i, m_iNext, m_deltaY, m_infinity;
632 ListConstIterator<InOutPoint> m_itIp, m_itIpNext, m_itLookAhead;
633 bool m_onBase;
634 };
635
636 void SetYCoords::init(int k)
637 {
638 m_k = k; m_V = &m_mmo[k];
639 m_ymax = 0;
640 m_lookAheadX = 0;
641
642 m_i = 0;
643 m_cl = m_mmo.m_left[k]; m_cr = m_mmo.m_right[k];
644
645 m_onBase = true; m_xNext = -1;
646 m_infinity = m_x[m_cr] + m_iops.outRight(m_cr) + 1;
647
648 searchNextInpoint();
649 m_itIp = m_itIpNext; m_i = m_iNext;
650
651 getNextRegion();
652 }
653
654 void SetYCoords::searchNextInpoint()
655 {
656 m_iNext = m_i; m_itIpNext = m_itIp;
657
658 do {
659 if (!m_itIpNext.valid()) {
660 if (++m_iNext > m_V->len()) {
661 m_itIpNext = ListConstIterator<InOutPoint>();
662 return;
663 }
664 m_itIpNext = m_iops.inpoints(z(m_iNext)).begin();
665 } else {
666 ++m_itIpNext;
667 }
668 } while (!m_itIpNext.valid() || (*m_itIpNext).m_dy == 0);
669
670 if (m_itIpNext.valid() && m_iops.marked((*m_itIpNext).m_adj)) {
671 int ipX = m_x[z(m_iNext)] + (*m_itIpNext).m_dx;
672
673 if (m_lookAheadX <= ipX) {
674 for (m_itLookAhead = m_itIpNext;
675 (*m_itLookAhead).m_dx < 0 && m_iops.marked((*m_itLookAhead).m_adj);
676 ++m_itLookAhead) ;
677
678 const InOutPoint &ipLookAhead = *m_itLookAhead;
679 m_lookAheadX = m_x[z(m_iNext)] + ipLookAhead.m_dx;
680 if(ipLookAhead.m_dx < 0) {
681 m_lookAheadNextX = m_x[ipLookAhead.m_adj->twinNode()] + outpoint(ipLookAhead).m_dx;
682 } else {
683 m_lookAheadNextX = m_lookAheadX;
684 }
685 }
686
687 if (m_lookAheadNextX <= ipX) {
688 m_itIpNext = m_itLookAhead;
689 }
690 }
691 }
692
693
694 void SetYCoords::getNextRegion()
695 {
696 int xOld = m_xNext;
697
698 do {
699 if (m_onBase) {
700 m_deltaY = 0;
701 if (!m_itIp.valid()) {
702 m_xNext = m_infinity;
703 } else {
704 const InOutPoint &ip = *m_itIp;
705 m_xNext = (marked(ip.m_adj)) ? (m_x[z(m_i)] + ip.m_dx) :
706 (m_x[ip.m_adj->twinNode()] + outpoint(ip).m_dx);
707 }
708 m_onBase = (m_iNext != m_i);
709
710 } else {
711 const InOutPoint &ip = *m_itIp;
712 m_deltaY = -ip.m_dy;
713 searchNextInpoint();
714 if (m_itIpNext.valid() && ip.m_dx < 0) {
715 const InOutPoint &m_ipNext = *m_itIpNext;
716 m_xNext = (marked(m_ipNext.m_adj)) ? (m_x[z(m_i)] + m_ipNext.m_dx) :
717 (m_x[m_ipNext.m_adj->twinNode()] + outpoint(m_ipNext).m_dx);
718 } else {
719 m_xNext = (marked(ip.m_adj)) ? (m_x[z(m_i)] + ip.m_dx + 1) :
720 (m_x[ip.m_adj->twinNode()] + outpoint(ip).m_dx + 1);
721 }
722
723 m_onBase = (m_iNext != m_i);
724 m_i = m_iNext; m_itIp = m_itIpNext;
725 }
726 } while (m_xNext <= xOld);
727 }
728
729 void SetYCoords::checkYCoord(int xleft, int xright, int ys, bool nodeSep)
730 {
731 while (m_xNext <= xleft)
732 getNextRegion();
733
734 int maxDy = m_deltaY;
735
736 while (m_xNext <= xright) {
737 getNextRegion();
738 if (m_deltaY > maxDy) maxDy = m_deltaY;
739 }
740
741 if (nodeSep && maxDy == 0)
742 maxDy = 1;
743
744 if (ys + maxDy > m_ymax)
745 m_ymax = ys + maxDy;
746 }
747
748 void MixedModelBase::computeYCoords()
749 {
750 NodeArray<int> &x = m_gridLayout.x(), &y = m_gridLayout.y();
751
752 int k, i;
753
754 // representation of the contour
755 NodeArray<node> prev(m_PG), next(m_PG);
756
757 // initialization
758 SetYCoords setY(m_PG,m_iops,m_mmo,x,y);
759
760 const ShellingOrderSet &V1 = m_mmo[1];
761 int p = V1.len();
762
763 for (i = 1; i <= p; ++i) {
764 if (i < p) next[V1[i]] = V1[i+1];
765 if (i > 1) prev[V1[i]] = V1[i-1];
766 }
767 prev [V1[1]] = next [V1[p]] = 0;
768
769 // main loop
770 for (k = 2; k <= m_mmo.length(); ++k)
771 {
772 // consider set Vk
773 const ShellingOrderSet &Vk = m_mmo[k];
774 p = Vk.len();
775 node cl = m_mmo.m_left[k];
776 node cr = m_mmo.m_right[k];
777
778 setY.init(k);
779
780 for(node v = cl; v != next[cr]; v = next[v])
781 {
782 ListConstIterator<InOutPoint> itFirst, itLast;
783
784 const List<InOutPoint> &out = m_iops.outpoints(v);
785
786 if (v == cl) {
787 if (!(itFirst = m_leftOp[k]).valid())
788 itFirst = out.begin();
789 else if ((*itFirst).m_adj->twinNode() != Vk[1])
790 ++itFirst;
791
792 for(itLast = itFirst; itLast.valid() && (m_iops.marked((*itLast).m_adj) ||
793 (*itLast).m_adj->twinNode() == Vk[1]); ++itLast) ;
794
795 } else if (v == cr) {
796 itLast = m_rightOp[k];
797 if (itLast.valid() && (*itLast).m_adj->twinNode() == Vk[p])
798 ++itLast;
799 itFirst = (itLast.valid()) ? itLast.pred() : out.rbegin();
800
801 while(itFirst.valid() && (m_iops.marked((*itFirst).m_adj) ||
802 (*itFirst).m_adj->twinNode() == Vk[p]))
803 --itFirst;
804 itFirst = (itFirst.valid()) ? itFirst.succ() : out.begin();
805
806 } else {
807 itFirst = m_nextLeft[v];
808 itFirst = (itFirst.valid()) ? itFirst.pred() : out.rbegin();
809
810 while (itFirst.valid() && m_iops.marked((*itFirst).m_adj))
811 --itFirst;
812
813 itFirst = (itFirst.valid()) ? itFirst.succ() : out.begin();
814
815 if (m_nextRight[v].valid() && m_nextLeft[v] == m_nextRight[v]) {
816 for (itLast = m_nextRight[v].succ(); itLast.valid() && m_iops.marked((*itLast).m_adj);
817 ++itLast) ;
818 } else {
819 itLast = m_nextLeft[v];
820 }
821 }
822 if (v != cr && itFirst != itLast && m_mmo.rank(next[v]) > m_mmo.rank(v)) {
823 int x_n_v = x[next[v]] - m_iops.outLeft(next[v]);
824 ListConstIterator<InOutPoint> it = (itLast.valid()) ? itLast.pred() : out.rbegin();
825 for( ; ; ) {
826 if(x[v]+(*it).m_dx >= x_n_v)
827 itLast = it;
828 else break;
829 if (it == itFirst) break;
830 --it;
831 }
832 }
833
834 if (v != cl) {
835 int xl = x[prev[v]], xr = x[v];
836 int r_p_v = m_mmo.rank(prev[v]), r_v = m_mmo.rank(v);
837
838 if (r_p_v >= r_v) {
839 if (m_iops.out(prev[v]) > 0)
840 xl += 1+m_iops.outRight(prev[v]);
841 } else {
842 xl += m_dxla[v];
843 }
844 if (r_p_v <= r_v) {
845 if (m_iops.out(v) > 0)
846 xr -= 1+m_iops.outLeft(v);
847 } else {
848 xr += m_dxra[prev[v]];
849 }
850
851 if (xl <= xr)
852 setY.checkYCoord(xl, xr, 1+max(y[prev[v]],y[v]), false);
853 }
854
855 for (ListConstIterator<InOutPoint> it = itFirst; it != itLast; ++it) {
856 const InOutPoint &op = *it;
857
858 if (m_iops.marked(op.m_adj))
859 setY.checkYCoord(x[v]+op.m_dx, y[v]+op.m_dy+1, false);
860 else
861 setY.checkYCoord(x[v]+op.m_dx, y[v]+op.m_dy,
862 (op.m_dx == 0 && op.m_dy == 0 && x[v] == x[op.m_adj->twinNode()]));
863 }
864 }
865
866 for (i = 1; i <= p; i++) {
867 y[Vk[i]] = setY.getYmax();
868 }
869
870 // update contour after insertion of z1,...,zp
871 for (i = 1; i <= p; i++) {
872 if (i < p) next[Vk[i]] = Vk[i+1];
873 if (i > 1) prev[Vk[i]] = Vk[i-1];
874 }
875
876 next [prev [Vk[1]] = cl] = Vk[1];
877 prev [next [Vk[p]] = cr] = Vk[p];
878 }
879 }
880
881
882 /********************************************************************
883 setBends
884
885 Assigns polylines to edges of the original graph and computes the
886 x- and y-coordinates of deg-1-nodes not in the ordering.
887 ********************************************************************/
888
889 void MixedModelBase::setBends ()
890 {
891 //printMMOrder(cout);
892 //printInOutPoints(cout);
893 //cout.flush();
894
895 NodeArray<int> &x = m_gridLayout.x(), &y = m_gridLayout.y();
896 EdgeArray<IPolyline> &bends = m_gridLayout.bends();
897
898 for(int k = 1; k <= m_mmo.length(); ++k)
899 {
900 for (int i = 1; i <= m_mmo[k].len(); ++i)
901 {
902 node v_s = m_mmo(k,i);
903 adjEntry adj;
904 forall_adj(adj,v_s)
905 {
906 node v_t = adj->twinNode();
907 edge e = adj->theEdge();
908 const InOutPoint &p_s = *m_iops.pointOf(adj);
909 if (m_iops.marked(adj)) {
910 x[v_t] = x[v_s] + p_s.m_dx;
911 y[v_t] = y[v_s] + p_s.m_dy;
912 }
913 else if(e->source() == adj->theNode())
914 {
915 const InOutPoint &p_t = *m_iops.pointOf(adj->twin());
916 IPoint p1 (x[v_s] + p_s.m_dx, y[v_s] + p_s.m_dy);
917 IPoint p2 (x[v_t] + p_t.m_dx, y[v_t] + p_t.m_dy);
918
919 bends[e].pushBack(p1);
920 if (m_mmo.rank(v_s) < m_mmo.rank(v_t)) {
921 bends[e].pushBack(IPoint(p1.m_x,p2.m_y));
922 } else {
923 bends[e].pushBack(IPoint(p2.m_x,p1.m_y));
924 }
925 bends[e].pushBack(p2);
926 }
927 }
928 }
929 }
930 }
931
932
933 /********************************************************************
934 postprocessing1
935
936 Tries to reduce the number of bends by changing the outpoints of
937 nodes with indeg and outdeg 2.
938 ********************************************************************/
939
940 void MixedModelBase::postprocessing1()
941 {
942 NodeArray<int> &x = m_gridLayout.x();
943
944 for(int k = 2; k <= m_mmo.length(); ++k) {
945 const ShellingOrderSet &V = m_mmo[k];
946 node v = V[V.len()];
947
948 if (m_iops.in(v) != 2 || m_iops.out(v) != 2) continue;
949
950 const List<InOutPoint> &in = m_iops.inpoints (v);
951 List<InOutPoint> &out = m_iops.outpoints(v);
952 adjEntry adjL = (*in.begin ()).m_adj;
953 adjEntry adjR = (*in.rbegin()).m_adj;
954
955 if (!m_iops.marked(adjL) && !m_iops.marked(adjR) &&
956 x[adjL->twinNode()] + m_iops.pointOf(adjL->twin())->m_dx < x[v] &&
957 x[adjR->twinNode()] + m_iops.pointOf(adjR->twin())->m_dx == x[v]+1 &&
958 m_gridLayout.y(adjR->twinNode()) < m_gridLayout.y(v))
959 {
960 x[v] += 1;
961 m_iops.setOutDx(out.begin (),-1);
962 m_iops.setOutDx(out.rbegin(), 0);
963 }
964 }
965 }
966
967
968 /********************************************************************
969 postprocessing2
970
971 Tries to reduce the number of bends by moving degree-2 nodes on
972 bend points.
973 ********************************************************************/
974
975 void MixedModelBase::firstPoint(int &x, int &y, adjEntry adj)
976 {
977 edge e = adj->theEdge();
978 bool sameDirection = (adj->theNode() == e->source());
979
980 if (m_gridLayout.bends(e).empty()) {
981 node t = (sameDirection) ? e->target() : e->source();
982 x = m_gridLayout.x(t);
983 y = m_gridLayout.y(t);
984 } else {
985 if(sameDirection) {
986 x = m_gridLayout.bends(e).front().m_x;
987 y = m_gridLayout.bends(e).front().m_y;
988 } else {
989 x = m_gridLayout.bends(e).back().m_x;
990 y = m_gridLayout.bends(e).back().m_y;
991 }
992 }
993 }
994
995 bool MixedModelBase::isRedundant(int x1, int y1, int x2, int y2, int x3, int y3)
996 {
997 int dzy1 = x3 - x2;
998 int dzy2 = y3 - y2;
999 int dyx1 = x2 - x1;
1000
1001 if (dzy1 == 0) return (dyx1 == 0);
1002
1003 int f = dyx1 * dzy2;
1004
1005 return (f % dzy1 == 0 && (y2 - y1) == f / dzy1);
1006 }
1007
1008 void MixedModelBase::postprocessing2()
1009 {
1010 m_gridLayout.compactAllBends();
1011
1012 node v;
1013 forall_nodes(v,m_PG)
1014 {
1015 if(v->degree() != 2) continue;
1016
1017 adjEntry adj1 = v->firstAdj();
1018 edge e1 = adj1->theEdge();
1019 adjEntry adj2 = v->lastAdj();
1020 edge e2 = adj2->theEdge();
1021
1022 IPolyline &bends1 = m_gridLayout.bends(e1);
1023 IPolyline &bends2 = m_gridLayout.bends(e2);
1024
1025 if (bends1.empty() && bends2.empty()) continue;
1026
1027 int x1,y1,x3,y3;
1028 firstPoint(x1,y1,adj1);
1029 firstPoint(x3,y3,adj2);
1030
1031 if (isRedundant(x1,y1,m_gridLayout.x(v),m_gridLayout.y(v),x3,y3)) {
1032 if (!bends1.empty()) {
1033 m_gridLayout.x(v) = x1;
1034 m_gridLayout.y(v) = y1;
1035 if(adj1->theNode() == e1->source())
1036 bends1.popFront();
1037 else
1038 bends1.popBack();
1039 } else {
1040 m_gridLayout.x(v) = x3;
1041 m_gridLayout.y(v) = y3;
1042 if(adj2->theNode() == e2->source())
1043 bends2.popFront();
1044 else
1045 bends2.popBack();
1046 }
1047 }
1048 }
1049 }
1050
1051
1052 /********************************************************************
1053 debugging output
1054 ********************************************************************/
1055
1056 void MixedModelBase::printMMOrder(ostream &os)
1057 {
1058 int k, i;
1059
1060 os << "left and right:\n\n";
1061 for (k = 1; k <= m_mmo.length(); ++k)
1062 {
1063 const ShellingOrderSet &V = m_mmo[k];
1064
1065 os << k << ": { ";
1066 for (i = 1; i <= V.len(); i++)
1067 os << V[i] << " ";
1068 os << "};";
1069 if (k >= 2)
1070 os << " cl = " << m_mmo.m_left[k] <<
1071 ", cr = " << m_mmo.m_right[k];
1072 os << endl;
1073
1074 }
1075 os.flush();
1076 }
1077
1078 void MixedModelBase::printInOutPoints(ostream &os)
1079 {
1080 node v;
1081
1082 os << "\n\nin- and outpoint lists:\n";
1083 forall_nodes(v,m_PG) {
1084 const List<InOutPoint> &in = m_iops.inpoints (v);
1085 const List<InOutPoint> &out = m_iops.outpoints(v);
1086
1087 os << "\n" << v << ":\n";
1088 os << " outpoints: ";
1089 ListConstIterator<InOutPoint> it;
1090 for(it = out.begin(); it.valid(); ++it) {
1091 print(os,*it);
1092 os << " ";
1093 }
1094 os << "\n inpoints: ";
1095 for(it = in.begin(); it.valid(); ++it) {
1096 print(os,*it);
1097 os << " ";
1098 }
1099 }
1100 os << endl;
1101 }
1102
1103 void MixedModelBase::print(ostream &os, const InOutPoint &iop)
1104 {
1105 if(iop.m_adj)
1106 os << "[(" << m_PG.original(iop.m_adj->theNode()) << "," <<
1107 m_PG.original(iop.m_adj->twinNode()) << ")," <<
1108 iop.m_dx << "," << iop.m_dy << "]";
1109 else
1110 os << "[ ]";
1111 }
1112
1113 void MixedModelBase::printNodeCoords(ostream &os)
1114 {
1115 node v;
1116
1117 os << "\nx- and y-coordinates:\n\n";
1118 forall_nodes(v,m_PG)
1119 os << v << ": (" << m_gridLayout.x(v) << "," << m_gridLayout.y(v) << ")\n";
1120 }
1121
1122 } // end namespace ogdf
Windows Explorer Extension to Operate Git